UPPSALA UNIVERSITET Matematiska institutionen Christer Kiselman, 0708-870708 Prov i matematik Teknisk fysik, B Transformer för beräkningar 2001 05 21

Skrivtid: 9:00–14:00. Tillåtna hjälpmedel: Skrivdon. Ordlista 2001 04 05. Formelsamling 2001 05 06. Räknare. Ej mobiltelefon. Svara på svenska eller annat språk.

1. Let a and b be two vectors in l^{2}(Z_{3}), a being given by its Fourier transform â = (7, 0, 8), and b = (ω^{2}, ω, 1), where ω = e^{−2πi/3} = −\frac{1}{2} − \frac{i}{2} \sqrt{3}.

(a) Calculate the Fourier transform b̂. (3)

(b) Calculate the convolution product a ∗ b. (3)

2. We consider two black boxes B and C, defined by vectors b, c ∈ l^{2}(Z_{4}) and the relations u = b ∗ z and v = c ∗ z between the input signal z and the output signals u and v. We take b = (1, 0, 1, 0) and c = (1, 2, 2, 1).

(a) Prove that knowledge of u alone is not sufficient to recover z; prove also that knowledge of v alone is not sufficient to recover z. (3)

(b) Prove that knowledge of both u and v is indeed enough to reconstruct the input signal z. Give an explicit formula for ẑ in terms of û and v̂. (3)

3. Let u = (7, 0, 8), v = (0, 1, 2), and z = (7, 0, 0, 1, 8, 2). Compute û, v̂ and then ẑ using the fast Fourier transformation. (5)

4. Let u, v ∈ l^{2}(Z_{8}) be the vectors

u = (1/\sqrt{2}, 1/\sqrt{2}, 0, 0, 0, 0, 0, 0), v = (1/\sqrt{2}, −1/\sqrt{2}, 0, 0, 0, 0, 0, 0).

(The first-stage Haar basis.)

(a) Prove that the vectors R_{2k}u, R_{2k}v, k = 0, 1, 2, 3, form an orthonormal system in l^{2}(Z_{8}). (2)

(b) Define

P (z) = ∑_{k=0}^{3}⟨z, R_{2k}u⟩R_{2k}u, Q(z) = ∑_{k=0}^{3}⟨z, R_{2k}v⟩R_{2k}v.

Calculate P (z) and Q(z) when z = (1, 3, 5, 3, 3, 7, 9, 1). (3)

5. We consider a convolution equation of the second degree, z ∗ z = z for vectors z = (z(j))_{j∈Z}.

(a) Find all solutions of this equation in l^{1}(Z). (3)

(b) Prove that the equation has infinitely many solutions in l^{2}(Z). (It would be nice if you could define infinitely many solutions explicitly.) (3)

6. Consider the Poisson equation with boundary conditions zero

\begin{matrix}u′′ = f, 0 < x < 1, \\ u(0) = u(1) = 0, \end{matrix}

and the following finite difference approximation

\begin{matrix}u_{k+1} − 2u_{k} + u_{k−1} = h^{2}f_{k}, k = 1, ..., N − 1, \\ u_{0} = u_{N} = 0. \end{matrix}

Here f_{k} = f(x_{k}), x_{k} = kh, and h = 1/N for some positive integer N.

(a) Use the familiar relation

sin(α + β) = sin α cos β + cos α sin β

to prove that

DST[(u_{k+1} − 2u_{k} + u_{k−1})_{k}](j) = 2( cos \frac{jπ}{N} − 1)DST[u](j),

where DST denotes the discrete sine transform, viz.

DST[z](j) = ∑_{k=1}^{N−1} z(k) sin \frac{jkπ}{N} , j = 1, ..., N − 1.

The inverse transform is given by

z(k) = \frac{2}{N} ∑_{j=1}^{N−1} DST[z](j) sin \frac{jkπ}{N} , k = 0, ..., N.

(3)

(b) Explain how this relation can be used to implement a fast Poisson solver. (3)

7. Define f: R^{2} → R by f(x) = 1 when |x_{1}| < 1 and |x_{2}| < 1; f(x) = 0 otherwise. Calculate the Radon transform φ(ω, p) = Rf(ω, p) of f for arbitrary p ∈ R and a particular choice of ω, viz. ω = (1/\sqrt{2}, 1/\sqrt{2}) ∈ S^{1}. (6)

Svar till tentamen i Transformer för beräkningar 2001 05 21

1. We find that b̂ = (0, 3ω^{2}, 0) = (0, −3 − 3ω, 0) = (0, −\frac{3}{2} + \frac{3}{2} \sqrt{3} i, 0), so that âb̂ = 0. Therefore also a ∗ b = 0, since its Fourier transform is âb̂.

2. We find b̂ = (2, 0, 2, 0) and ĉ = (6, −1 − i, 0, −1 + i), so that u = b ∗ z = 0 as soon as ẑ(0) = ẑ(2) = 0 (ẑ(1) and ẑ(3) being arbitrary), while v = c ∗ z = 0 as soon as ẑ(0) = ẑ(1) = ẑ(3) = 0 (ẑ(2) being arbitrary). The reconstruction of z follows from the formulas ẑ(0) = \frac{1}{2} û(0), ẑ(1) = v̂(1)/(−1 − i) = \frac{1}{2}(−1 + i)v̂(1), ẑ(2) = \frac{1}{2} û(2), ẑ(3) = v̂(3)/(−1 + i) = \frac{1}{2}(−1 − i)v̂(3).

3. We find û = (15, 7+8ω^{2}, 7+8ω) = (15, −1−8ω, 7+8ω) and v̂ = (3, ω+2ω^{2}, 2ω+ω^{2}) = (3, −2−ω, −1+ω), where ω = e^{−2πi/3} = −\frac{1}{2} − \frac{i}{2} \sqrt{3}. With the fast Fourier transformation we the obtain

ẑ(0) = û(0) + v̂(0) = 18,
ẑ(1) = û(1) + θv̂(1) = −2 − 10ω = 3 + 5\sqrt{3} i,
ẑ(2) = û(2) + θ^{2}v̂(2) = 6 + 6ω = 3 − \sqrt{3} i,
ẑ(3) = û(0) − v̂(0) = 12,
ẑ(4) = û(1) − θv̂(1) = −6ω = 3 + 3\sqrt{3} i,
ẑ(5) = û(2) − θ^{2}v̂(2) = 8 + 10ω = 3 − 5\sqrt{3} i,

where θ = e^{−πi/3} = −ω^{2} = 1 + ω, θ^{2} = ω, θ^{3} = −1, θ^{4} = ω^{2} = −1 − ω, θ^{5} = −ω. So ẑ = (18, −2−10ω, 6+6ω, 12, −6ω, 8+10ω) = (18, 3+5\sqrt{3} i, 3−\sqrt{3} i, 12, 3+3\sqrt{3} i, 3−5\sqrt{3} i). (Of course it is also possible to calculate ẑ directly.)

4. To prove (a) is routine. To prove (b): we know that (or just calculate) that P (z) is given by the mean values of the numbers taken two and two, so that P (z) = (2, 2, 4, 4, 5, 5, 5, 5), while Q(z) is the information needed to pass from P (z) to z, i.e., Q(z) = z − P (z) = (−1, 1, 1, −1, −2, 2, 4, −4).

5. (a) Taking the Fourier transform we see that ẑ(t)^{2} = ẑ(t) so that ẑ(t) = 0 or ẑ(t) = 1 for each t ∈ [0, 2π[. Since ẑ is continuous, the only solutions are ẑ(t) = 0 for all t and ẑ(t) = 1 for all t, corresponding to z = 0 and z = δ.

(b) When z is allowed to lie in the larger space l^{2}(Z), we can for instance take f as the characteristic function of an interval I, f = χ_{I}. Then z = f̌ should satisfy z ∗ z = z. Since ẑ ∗ z is problematic, we can argue as follows. Take f_{j} ∈ C^{2} of period 2π such that f_{j} = 1 wherever f = 1 and such that f_{j} → f in L^{2}. Then f_{j}f = f so that z_{j} = f̌_{j} satisfies z_{j} ∗ z = z. Now z_{j} ∈ l^{1}(Z) and z_{j} → z in l^{2}(Z), so the convolution z_{j} ∗ z is well-defined in l^{2} and z_{j} ∗ z → z ∗ z in l^{∞}(Z). So z = z_{j} ∗ z tends to z ∗ z, which proves that z = z ∗ z. Since different intervals give rise to different z, there are infinitely many solutions z. Explicitly, we may take f(t) = 1 for −a < t < a and f(t) = 0 for −π ⩽ t ⩽ −a and a ⩽ t < π, where a is any number in [0, π]. These functions are all in L^{2}([−π, π[) and define infinitely many solutions z = f̌ ∈ l^{2}(Z). The inverse Fourier transform of f is f̌(n) = z(n) = sin(na)/(πn), n ≠ 0; z(0) = a/π. For a = 0 we get z = 0; for a = π we get z = δ. Any a between 0 and π gives a solution in l^{p}(Z), p > 1.

[The following was not required.

(c) Slightly more generally, we may take z ∈ l^{2}(Z) such that ẑ takes only the values 0 and 1. Then z is a solution. To prove this, take z_{j} ∈ l^{1}(Z) such that z_{j} → z in l^{2}(Z). Then z_{j} ∗ z → z ∗ z in l^{∞}(Z). Moreover { \atop z_{j} ∗ z} = ẑ_{j}ẑ → ẑ^{2} = ẑ in L^{1}(]−π, π]), which implies that z_{j} ∗ z → z in l^{∞}(Z). Thus we get even more solutions than those found in (b).

(d) Are there other solutions than those found in (c)? No. Suppose that z ∈ l^{2}(Z) is such that z ∗ z = z as sequences in l^{∞}(Z). We can then show that ẑ takes the values 0 and 1 only. Take again z_{j} ∈ l^{1}(Z) such that z_{j} → z in l^{2}(Z). Then z_{j} ∗ z → z ∗ z = z in l^{∞}(Z), which implies that ẑ_{j}ẑ → ẑ in D′(R) (the space of distributions). Moreover ẑ_{j} → ẑ in L^{2}(]−π, π]), which implies that ẑ_{j}ẑ → ẑ^{2} in L^{1}, hence also in D′. So ẑ^{2} = ẑ as distributions. Since they are functions in L^{1}, they must be equal as elements of that space, which means that they are equal at almost every point. Hence ẑ^{2} = ẑ almost everywhere: the solutions we found in (c) are all solutions.]

6. (a) The derivation of the symbol is straightforward.

(b) The sine transform of the solution is

DST[u](j) = \frac{h^{2}DST[f](j)}{2(cos(jπ/N) − 1)}, j = 1..., N − 1.

Thus the solution can be computed by transforming the right hand side h^{2}f, dividing it by 2(cos(jπ/N)−1), and computing the inverse sine transform of the result. Each transform can be computed in O(N log N) a.o.

7. We see that φ(ω, p) = 0 when |p| ⩾ \sqrt{2}, for then the line ω · x = p does not cut the square |x_{j}| < 1. Moreover, it is clear that φ(ω, 0) = 2\sqrt{2}, that φ(ω, ±\sqrt{2}) = 0, and that φ(ω, p) is affine in the intervals [−\sqrt{2}, 0], [0, \sqrt{2}]. Thus φ(ω, p) = 2(\sqrt{2} − |p|) when |p| < \sqrt{2}, and Rf(ω, p) = max(0, 2(\sqrt{2} − |p|)) for this particular ω. (For any ω ∈ S^{1}, p ↦ Rf(ω, p) is piecewise affine and with a little more work we can determine it exactly.)