UPPSALA UNIVERSITET

Matematiska institutionen Christer Kiselman

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

PROV I MATEMATIK

Transformer för beräkningar

2000 08 23, 08:00–13:00

000823tent

Tillåtna hjälpmedel: Ordlista 2000 05 09. Formelsamling 2000 05 21. Skrivdon. Svara på svenska eller annat språk.

1. Låt a och b vara två vektorer i l^{2}(Z_{4}); a = (1, −i, −1, i) medan b är given av sin Fouriertransform b̂ = (8, 7, 5, 0).

(a) Beräkna â. (3)

(b) Beräkna a ∗ b. (3)

2. Vi studerar två svarta lådor B och C, som definieras av b, c ∈ l^{2}(Z_{3}) och av relationerna u = b ∗ z och v = c ∗ z mellan insignalen z ∈ l^{2}(Z_{3}) och utsignalerna u, v ∈ l^{2}(Z_{3}). Antag att b = (1, 1, −2) och c = (1, 1, 1).

(a) Visa att kännedom om u = b ∗ z inte är tillräcklig för att rekonstruera insignalen z, dvs. visa att det finns en insignal z ≠ 0 som ger utsignal u lika med noll. (3)

(b) Visa att kännedom om både u = b ∗ z och v = c ∗ z räcker för att rekonstruera z. Skriv upp en formel som ger ẑ i termer av û och v̂. (3)

3. Låt u = (1, 0, 2, 0), v = (0, 3, 5, 0), z = (1, 0, 0, 3, 2, 5, 0, 0). Beräkna û, v̂ och sedan ẑ, till exempel med hjälp av den snabba Fouriertransformationen. (6)

4. Låt u ∈ l^{2}(Z_{N}), där N = 2M, och definiera v ∈ l^{2}(Z_{M}) genom v(n) = u(n) + u(n + M), n = 0, 1, ..., M − 1. Bevisa att v̂(n) = û(2n) för alla n ∈ Z_{M}. (5)

5. Finn det polynom av grad 1 som bäst approximerar funktionen e^{−2x} i rummet L^{2}(R, e^{−x^{2}}), dvs. det rum där man definierar Hermitepolynomen och som har inre produkt

⟨f, g⟩ = ∫_{R} f(x)\overline{g(x)}e^{−x^{2}}dx.

Det får anses vara känt att ⟨1, 1⟩ = \sqrt{π}. (6)

6. Definiera f: R^{3} → R genom f(x) = 1 då ∥x∥_{2} = \sqrt{x_{1}^{2} + x_{2}^{2} + x_{3}^{2}} < 1, f(x) = 0 då ∥x∥_{2} ⩾ 1. Beräkna Radontransformen φ = ℛf av f, dvs. beräkna φ(ω, p) då ω ∈ S^{2}, p ∈ R. (5)

7. Betrakta en filterbanktransform av z ∈ Z_{N}, där N = 2^{p} och den grövsta nivån hos transformen har N_{0} = 2^{q} punkter, oberoende av N. Antag att filtren har samma antal element som inte är noll på alla nivåer. Visa att transformen kan beräknas med O(N) aritmetiska operationer. (6)

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

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

2. Man finner att b̂ = (3, 0, 0), ĉ = (0, −3ω^{2}, −3ω), där ω = −\frac{1}{2} − \frac{1}{2} \sqrt{3}i. Därför är û(0) = 3ẑ(0), û(1) = û(2) = 0 för alla z; man kan rekonstruera ẑ(0) men inte ẑ(1) eller ẑ(2). Insignalen z = (1, ω, ω^{2}) har Fouriertransform (0, 0, 3) och ger alltså utsignal noll från den svarta lådan B. Vi har också v̂(1) = −3ω^{2}ẑ(1) och v̂(2) = −2ωẑ(2). Vi kan rekonstruera ẑ och därmed z genom formlerna ẑ(0) = \frac{1}{3} û(0), ẑ(1) = −\frac{1}{3ω^{2}} v̂(1), ẑ(2) = −\frac{1}{3ω} v̂(2).

3. Man finner lätt att û = (3, 2 + i, 1, 2 − i), v̂ = (8, −2, 8, −2), varav följer att ẑ = (11, 2 + i − 2θ, 1 + 8θ^{2}, 2 − i − 2θ^{3}, −5, 2 + i + 2θ, 1 − 8θ^{2}, 2 − i + 2θ^{3}), där θ = \frac{1−i}{\sqrt{2}}, således z = (11, 2 − \sqrt{2} + i + \sqrt{2}i, 1 − 8i, 2 − i + \sqrt{2}(1 + i), −5, 2 + i + \sqrt{2}(1 − i), 1 + 8i, 2 − i − \sqrt{2}(1 + i)).

4. Inför ω = e^{−2πi/M} och θ = e^{−2πi/N}, så att ω^{M} = 1, θ^{N} = 1, ω = θ^{2}. Då blir

v̂(n) = ∑_{0}^{M−1} u(k)ω^{kn} + ∑_{0}^{M−1} u(k + M)ω^{kn} = ∑_{0}^{N−1} u(k)θ^{2kn} = û(2n), n ∈ Z_{M}.

5. Man söker polynomet på formen a + bx och undersöker när skillnaden a + bx − e^{−2x} är ortogonal mot alla polynom av grad 1. Det inträffar precis då a = ⟨e^{−2x}, 1⟩/⟨1, 1⟩ och b = ⟨e^{−2x}, x⟩/⟨x, x⟩. Man behöver därför beräkna de inre produkterna ⟨1, 1⟩ = \sqrt{π}, ⟨e^{−2x}, 1⟩ = e\sqrt{π}, ⟨e^{−2x}, x⟩ = −e\sqrt{π} samt ⟨x, x⟩ = \frac{1}{2} \sqrt{π}. (Utgående från den första inre produkten beräknas den andra medelst translation och den tredje och fjärde medelst partiell integration.) Det följer att a = e, b = −2e. Svar alltså e(1 − 2x).

6. Man ser att φ(ω, p) är oberoende av ω. Planet ω · x = p skär ut en cirkelskiva med radien r = \sqrt{1 − p^{2}} av enhetsklotet om |p| < 1; skivans area πr^{2} = π(1−p^{2}) är just värdet hos Radontransformen. Då |p| ⩾ 1 blir förstås φ(ω, p) = 0.

7. Antalet aritmetiska operationer är proportionellt mot ∑_{k=q}^{p} N/2^{k}, som kan uppskattas sålunda:

∑_{k=q}^{p} \frac{N}{2^{k}} ⩽ ∑_{k=0}^{p} \frac{N}{2^{k}} = ∑_{k=0}^{p} 2^{p−k} = 2^{p+1} − 1 = O(N).