UPPSALA UNIVERSITET

Matematiska institutionen Christer Kiselman

018-4713216 (a); 018-300708 (b); 0708-870708 (m)

PROV I MATEMATIK

Transformer för beräkningar

2000 05 22, 09:00–14:00

000522tent

Tillåtna hjälpmedel: Ordlista 2000 05 09 (eller senare version). Formelsamling 2000 05 17 (eller senare version). Skrivdon.

Svara på svenska eller annat språk.

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

(a) Calculate b̂. (3)

(b) Calculate a ∗ b. (3)

2. Study the convolution equation b ∗ z = w, where b is a given vector in l^{1}(Z) (the black box), z is the input signal and w is the output signal. The problem is to decide which output signals w are possible with certain black boxes b.

(a) Let b = δ_{0} +δ_{1} +δ_{2}, w = δ_{0} +δ_{1}. Prove that there is no solution z to the equation b ∗ z = w such that z(j) = 0 for all large |j|. (2)

(b) Now let b = δ_{0} + δ_{1}, w = δ_{0} + 2δ_{1} + δ_{2}. Prove that there exists an input signal z such that b ∗ z = w and such that z(j) = 0 for all large values of |j|. (2)

(c) Finally let b = δ_{0} + δ_{1}, w = δ_{0}. Find all solutions z ∈ l^{∞}(Z) to b ∗ z = w. (2)

3. Suppose we know that b ∈ l^{2}(Z_{6}) satisfies b̂(0) = 0, b̂(k) ≠ 0, k = 1, ..., 5.

(a) What is the dimension of the space of input signals producing the zero output signal, in other words, what is the dimension of the space

{z ∈ l^{2}(Z_{6}); b ∗ z = 0}?  (3)

(b) Determine the dimension of all possible output signals, i.e., the dimension of the

space

{b ∗ z; z ∈ l^{2}(Z_{6})}.  (3)

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

Var god vänd. Please turn over. → → → 5. 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}). (3)

(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, 2, 4, 6, 10, 12, 10, 8). (3)

6. Suggest an O(N log N) algorithm for computing matrix-vector multiplication, assuming the matrix to be Toeplitz. (Recall that the elements of a Toeplitz matrix are constant along diagonals. A circulant matrix is Toeplitz but not necessarily conversely.) (6)

7. Define f: R^{2} → R by f(x) = 1 − ∥x∥_{2}^{2} when ∥x∥_{2} < 1, f(x) = 0 when ∥x∥_{2} ⩾ 1. Calculate the Radon transform φ = ℛf of f, i.e., calculate φ(ω, p) for ω = (cos θ, sin θ) ∈ S^{1}, p ∈ R. (5)

Svar med korta anvisningar om hur man kan lösa uppgifterna

1. Man finner att b̂ = (0, 0, 3). Därför blir den punktvisa produkten âb̂ av â och b̂ noll. Och därför även a ∗ b = 0 eftersom dess Fouriertransform är just âb̂.

2. I (a) vet man att z(n) + z(n − 1) + z(n − 2) = 0 för alla n ≠ 0, 1. Om man startar med ett stort n och går nedåt så ger detta z(n) = 0 för alla n ⩾ 0. Om man startar med ett stort negativt index och går uppåt, så får man z(n) = 0 för alla n ⩽ −1. Alltså skulle z = 0, vilket motsäger ekvationen för n = 0, 1.

I (b) gissar man lätt att z = δ_{0} + δ_{1} ger en lösning.

I (c) ser man att en godtycklig lösning kan skrivas som en summa z = x + cy, där x(n) = 0, n ⩽ −1, x(n) = (−1)^{n}, n ⩾ 0, där y(n) = (−1)^{n} och där c är ett godtyckligt komplext tal. (Vektorn x löser ekvationen b ∗ x = δ_{0} medan y löser den homogena ekvationen b ∗ y = 0.)

3. Man ser att det första rummet har dimensionen 1 (ekvationen b̂ẑ = 0 bestämmer z(1), z(2), z(3), z(4), z(5) men inte z(0)), det andra dimensionen 5 (b̂(n)ẑ(n) kan anta godtyckliga värden för n = 1, 2, 3, 4, 5 men inte för n = 0).

4. Man räknar ut att û = (3, 2 + ω^{2}, 2 + ω) och v̂ = (7, 4ω + 3ω^{2}, 3ω + 4ω^{2}), där ω är som i uppgift 1. Med tekniken från den snabba Fouriertransformen ger detta att

ẑ(0) = û(0) + v̂(0) = 10,
ẑ(1) = û(1) + θv̂(1) = −2 − 3ω + ω^{2} = −3 − 4ω,
ẑ(2) = û(2) + ωv̂(2) = 6 + ω + 3ω^{2} = 3 − 2ω,
ẑ(3) = û(0) − v̂(0) = −4,
ẑ(4) = û(1) − θv̂(1) = 6 + 3ω + ω^{2} = 5 + 2ω,
ẑ(5) = û(2) − ωv̂(2) = −2 + ω − 3ω^{2} = 1 + 4ω,

där θ = e^{−iπ/3} = −ω^{2}; θ^{2} = ω, θ^{3} = −1, θ^{4} = ω^{2}, θ^{5} = −ω. (Man kan förstås beräkna ẑ direkt också.)

5. Att visa (a) är rutin. För (b) så vet man (eller räknar ut) att P (z) ges av medelvärdena av talen två och två, alltså P (z) = (\frac{3}{2}, \frac{3}{2}, 5, 5, 11, 11, 9, 9), medan Q(z) är den information som behöver läggas till för att få z, alltså Q(z) = z − P (z) = (−\frac{1}{2}, \frac{1}{2}, −1, 1, −1, 1, 1, −1).

6. Man kan bygga ut en N × N Toeplitzmatris A till en 2N × 2N cyklisk matris C genom att dra ut diagonalerna. Och för en cyklisk matris vet man att produkten med en vektor är en faltning, som i sin tur kan beräknas medelst den snabba Fouriertransformationen, varvid det räcker med O(N log N) multiplikationer.

7. Man ser att φ(ω, p) är oberoende av ω. Det handlar om att integrera den positiva delen av en parabel som eventuellt sticker upp ovanför planet z = 0. Man vet att ett sådant parabelsegment fyller ut två tredjedelar av den omskrivna rektangeln. Basen är 2\sqrt{1 − p^{2}} och höjden är 1 − p^{2}. Alltså blir svaret ℛf(ω, p) = φ(ω, p) = \frac{4}{3}(1 − p^{2})^{3/2} då |p| < 1; φ(ω, p) = 0 då |p| ⩾ 1.