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

Skrivtid: 08:00–13: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_{5}), a being given by its Fourier transform â = (3, 2, 1, 0, −1), and b = (1, ω^{2}, ω^{4}, ω, ω^{3}), where ω = e^{−2πi/5}.

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

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

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

(a) Prove that the output signals satisfy the relation ĉ(τ)û(τ) = b̂(τ)v̂(τ) for all frequencies τ ∈ R. (3)

(b) Suppose now that the black boxes satisfy |b̂(τ)| + |ĉ(τ)| ⩾ ε > 0 for all τ. Prove that it is possible to reconstruct z from knowledge of u and v. More precisely, prove that there is a formula ẑ(τ) = φ(τ)û(τ) + ψ(τ)v̂(τ) with functions φ and ψ such that z becomes a continuous function of u and v in the sense that there is an estimate ∥z∥_{2} ⩽ C(∥u∥_{2} + ∥v∥_{2}). (3)

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

4. Let u ∈ l^{2}(Z_{N}) and define v ∈ l^{2}(Z_{N/2}) by the formula v(n) = u(n) + u(n + N/2), assuming N to be even. Prove that v̂(n) = û(2n). (Note that û and v̂ are actually defined on different groups, Z_{N} and Z_{N/2}, respectively, but that we may consider them as periodic functions defined on Z, albeit with different periods, just to allow for a brief notation.) (6)

5. We consider a convolution equation of the fourth degree, z ∗ z ∗ z ∗ z = δ, on (a) the finite cyclic group Z_{5} and (b) the infinite cyclic group Z.

(a) Prove that the equation has more than a thousand solutions z ∈ l^{2}(Z_{5}). Give an explicit formula for ẑ(k), k = 0, 1, 2, 3, 4. (3)

(b) Prove that the equation has only four solutions z ∈ l^{1}(Z). Give all solutions explicitly. (3)

6. Show that the discrete sine transform of z = (z(1), ..., z(N − 1)),

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

can be written on the form

DST(z)(j) = \frac{i}{2} ∑_{k=0}^{2N−1} z(k) e^{−2πijk/(2N)},

where

z(0) = z(N) = 0,

and

z(k) = −z(2N − k), k = N + 1, ..., 2N − 1,

thus as a Fourier transform of a vector with period 2N. (This means that the discrete sine transform can be computed using the FFT-algorithm.) (6)

7. It is known that we can define the angle α formed by two nonzero vectors x, y in a real inner-product space by the formula

⟨x, y⟩ = ∥x∥ ∥y∥ cos α.

Here 0 ⩽ α ⩽ π. Calculate the angle between the functions f(x) = 1 + \sqrt{2/3} x and g(x) = 1, x ∈ R, in the space of real-valued Hermite polynomials. (The fact that ∥1∥^{2} = ⟨1, 1⟩ = \sqrt{π} in that space may be used without proof.) (6)

Svar till tentamen i Transformer för beräkningar 2001 06 07

1. (a) We find that b̂ = (0, 0, 0, 5, 0), so that âb̂ = 0.

(b) The convolution product is a ∗ b = 0, since its Fourier transform is âb̂ = 0.

2. (a) We get û = b̂ẑ and v̂ = ĉẑ so that ĉû = ĉb̂ẑ = b̂v̂.

(b) The reconstruction formula follows with C = 2/ε if we choose for example φ(τ) = 1/b̂(τ) and ψ(τ) = 0 when |b̂(τ)| ⩾ ε/2; and φ(τ) = 0 and ψ(τ) = 1/ĉ(τ) when |b̂(τ)| < ε/2. Then ∥φ∥_{∞}, ∥ψ∥_{∞} ⩽ 2/ε.

A little more symmetry is possible: we can take

φ = \frac{|b̂|}{(|b̂| + |ĉ|)b̂}, ψ = \frac{|ĉ|}{(|b̂| + |ĉ|)ĉ},

where φ is defined as zero when b̂ is zero, and similarly ψ is defined as zero when ĉ vanishes. We have |φ|, |ψ| ⩽ 2/ε everywhere.

3. We find û = (8, 8, 8) and v̂ = (22, 7 + 7ω + 8ω^{2}, 7 + 7ω^{2} + 8ω) = (22, −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) = 30,
ẑ(1) = û(1) + θv̂(1) = 8 − ω = \frac{17}{2} + \frac{1}{2} \sqrt{3} i,
ẑ(2) = û(2) + θ^{2}v̂(2) = 7 − ω = \frac{15}{2} + \frac{1}{2} \sqrt{3} i,
ẑ(3) = û(0) − v̂(0) = −14,
ẑ(4) = û(1) − θv̂(1) = 8 + ω = \frac{15}{2} − \frac{1}{2} \sqrt{3} i,
ẑ(5) = û(2) − θ^{2}v̂(2) = 9 + ω = \frac{17}{2} − \frac{1}{2} \sqrt{3} i,

where θ = e^{−πi/3} = −ω^{2} = 1 + ω, θ^{2} = ω, θ^{3} = −1, θ^{4} = ω^{2} = −1 − ω, θ^{5} = −ω. So ẑ = (30, 8−ω, 7−ω, −14, 8+ω, 9+ω) = (30, \frac{17}{2} + \frac{1}{2} \sqrt{3} i, \frac{15}{2} + \frac{1}{2} \sqrt{3} i, −14, \frac{15}{2} − \frac{1}{2} \sqrt{3} i, \frac{17}{2} − \frac{1}{2} \sqrt{3} i).

4. Let ω = e^{−2πi/N}, θ = e^{−2πi/M}, where M = N/2. Then ω^{2} = θ, and we get

v̂(n) = ∑_{k=0}^{M−1} θ^{nk}u(k) + ∑_{k=0}^{M−1} θ^{nk}u(k + M).

Substituting ω^{2} for θ and introducing j = k + M as a new summation index going from M to 2M −1 in the second sum, we see that the two sums together form the sum defining û(2n). Indeed, the factor θ^{nk} there is equal to θ^{nk} = ω^{2n(j−M)} = ω^{2nj}ω^{−nN} = ω^{2nj}.

5. (a) Taking the Fourier transform we see that ẑ(t)^{4} = 1 so that ẑ(k) = i^{m_{k}} for some numbers m_{k} ∈ {0, 1, 2, 3}, k = 0, 1, 2, 3, 4. This gives 4^{5} = 2^{10} = 1024 solutions. And 1024 > 1000.

(b) We get ẑ(τ) = i^{m(τ)} for every τ, but since ẑ(τ) is a continuous function of the real variable τ, the number m must be the same for all τ; hence ẑ(τ) = 1, i, −1, −i are the only possibilities, corresponding to z = i^{m}δ, m = 0, 1, 2, 3.

6. We start by writing the sine function as a sum of two exponential functions

DST(z)(j) = \frac{1}{2i} (∑_{k=1}^{N−1} z(k) e^{ijkπ/N} − ∑_{k=1}^{N−1} z(k) e^{−ijkπ/N}) .

Replacing k by 2N −k and using the periodicity of the exponential function, we can write the first sum above as

∑_{k=1}^{N−1} z(k) e^{ijkπ/N} = ∑_{k=N+1}^{2N−1} z(2N − k) e^{−ijkπ/N}.

Extending z as suggested we obtain the result.

7. We need to calculate also ∥x∥. This can be done using partial integration:

∥x∥^{2} = ⟨x^{2}, 1⟩ = ⟨x, x⟩ = \frac{1}{2} \sqrt{π}.

Thus for affine functions f(x) = a + bx, g(x) = c + dx,

⟨f, g⟩ = ⟨a + bx, c + dx⟩ = ac⟨1, 1⟩ + bd⟨x, x⟩ = \sqrt{π}(ac + \frac{1}{2}bd),

so that

cos α = \frac{ac + \frac{1}{2}bd}{\sqrt{a^{2} + \frac{1}{2}b^{2}}\sqrt{c^{2} + \frac{1}{2}d^{2}}} .

In particular, taking a = 1, b = \sqrt{2/3}, c = 1, d = 0, we get cos α = \frac{1}{2} \sqrt{3}, so that the angle is π/6 radians or 30 degrees.