Hw5

HOMEWORK FOR ADVANCED NUMERICAL COMPUTING - CS 543

Michael J. Johnson Spring 2008 Abstract. These are the homework assignments for Advanced Numerical Computing – CS 543 taught at Kuwait University Spring Semester 2008.

Typeset by AMS-TEX

1

2

CS 543

1. Homework Problem 1.1. Let Ξ1 = {0, 1, 5}, Ξ2 = {0, 1, 2, 5}, and Ξ3 = {0, 1, 3, 5}. a) Is P3,Ξ1 a subspace of P6,Ξ1 ? b) Is P3,Ξ1 a subspace of P3,Ξ2 ? c) Is P3,Ξ2 a subspace of P3,Ξ3 ? Problem 1.2. Let Ξ1 = {0, 1, 2, 3, 5} and Ξ2 = {0, 1, 2, 3, 4, 5}, and consider  4 4x − 5x2 + 1     (x − 1)3 + (x − 1) s(x) :=  2    (x − 3) + 2

if 0 ≤ x < 1 if 1 ≤ x < 2 if 2 ≤ x < 3 if 3 ≤ x ≤ 5.

a) Find the Matlab/Octave representation of s as an element of P4,Ξ1 . b) Find the Matlab/Octave representation of s as an element of P5,Ξ1 . c) Find the Matlab/Octave representation of s as an element of P4,Ξ2 . d) Does s belong to C[a, b]? e) Does s belong to C 1 [a, b]? P∞ Problem 1.3. Let k ∈ N and define f (x) = j=−∞ cj Bjk (x). Determine the largest value of j0 and the smallest value of j1 such that f (x) =

j1 X

cj Bjk (x) for all x ∈ [ξ1 , ξ2 ].

j=j0

Problem 1.4. Let Ξ be the knots a = ξ1 < ξ2 < · · · < ξN +1 = b and let k ∈ N0 . Prove that Sk,Ξ ∩ Sk+1,Ξ = Πk | . [a,b]

Problem 1.5. Let k ∈ N and assume that the P knots {. . . , ξ−1 , ξ0 , ξ1 , . . . } are equispaced ∞ (ie. ξi+1 − ξi = h for all i). Prove that f (x) = j=−∞ ξj Bjk (x) is a polynomial of degree 1.

CS 543

3

2. Homework The questions here may involve both written and Octave work. Let me suggest the following format for your answers: Give me your written work (on paper) along with a diskette or an archive (via email). The diskette or archive should contain Octave scripts (*.m files). For each question, your written answer should mention which Octave script file I’m supposed to see from your diskette or archive. You may find the Octave commands disp, keyboard, input useful in Octave scripts. Problem 2.1. Let Ξ = {0, 1, 2, 4}. Find the unique spline s ∈ S1,Ξ which satisfies s(0) = 3, s(1) = 0, s(2) = 1, and s(4) = −1. Problem 2.2. Let Ξ = {0, 1, 3, 6, 10} and k = 3. a) Choose Ξext in an appropriate manner. b) Using Octave, construct the pp representation of f (x) = B13 (x) + B23 (x) + B33 (x) + B43 (x) and plot f on the interval [0, 10]. Problem 2.3. Let Ξ = {−2, 1, 2, 5, 6}. Use Octave to verify the identity d k B (x) = dx i



k ξi+k − ξi



Bik−1 (x)

−



k ξi+k+1 − ξi+1



k−1 Bi+1 (x)

for i = 1, k = 3. (Suggestion: Construct the LHS and the RHS, and then plot both on the same plot). Problem 2.4. Let Ξ = {3, 4, 7, 8, 10, 13}. Use Octave to verify the identity Bik (x)

=



x − ξi ξi+k − ξi



Bik−1 (x)

+



ξi+k+1 − x ξi+k+1 − ξi+1



k−1 Bi+1 (x)

for i = 1, k = 4. Problem 2.5. Use Octave to construct and plot the natural quintic (degree 5) spline which passes thru the points (1, 1), (2, 5), and (5, 5). Problem 2.6. Use Octave to construct and plot the complete quintic spline s which passes thru the points (0, 0), (2, 3), and (3, 1) and satisfies s0 (0) = 1, s00 (0) = −1, s0 (3) = 0, s00 (3) = −2.

4

CS 543

3.

Homework

Problem 3.1. Let f (x) = ln x, 1 ≤ x ≤ 4 (that’s log in Octave). Write an Octave script which, given N, does the following: a) Constructs the natural spline interpolant s, of degree 5, which interpolates f at the N +1 equispaced points which start with 1 and end with 4 (you may use the supplementary Octave command natural spline). b) Compute (approximately) EN = max |s(x) − f (x)| a≤x≤b

Run your script for the values N = 40, 80, 160 and record the error measurements E 40 , E80 , E160 . Problem 3.2. Consider the error estimate given in Theorem 6.1. How well does this error estimate correlate with the results of the above experiment? Explain. Problem 3.3. Prove that if ψ ∈ Cc (R) satisfies the Strang-Fix conditions of order k + 1, then so does n X φ(x) := λj ψ(x − τj ). j=1

Problem 3.4. Suppose the pp s ∈ PX,4 has the Octave representation (X,S), where X contains the knots and S is the matrix of coefficients. Explain how you would obtain the Octave representation of the pp a) f (x) = 5s(x). b) g(x) = s(x − 3). c) h(x) = s(4x). Problem 3.5. Let ψ be the B-spline of degree k = 2 having knots {−3/2, −1/2, 1/2, 3/2}. a) Use Octave to find scalars λ1 , λ2 , λ3 so that φ(x) := λ1 ψ(x + 1) + λ2 ψ(x) + λ3 ψ(x − 1) satisfies

Z

∞

t` φ(t) dt = δ`,0 for ` = 0, 1, 2.

−∞

b) Construct the pp representation of φ and plot φ.

CS 543

5

4. Homework Let k = 4 and let φ be the function of the form φ(x) = λ1 ψk (x + 2) + λ2 ψk (x + 1) + λ3 ψk (x) + λ4 ψk (x − 1) + λ5 ψk (x − 2) as described in Theorem 9.10, and let f ∈ C[0, 2] be defined by f (x) = cos(9 cos−1 (x − 1)) Note that in Octave, f (x) can be expressed as cos(9*acos(x-1)). Problem 4.1. (a) Use the supplementary Octave command quasi interpolant to construct the Octave representation of the pp φ. (b) Determine the support of φ. (c) Use Octave to verify that φ satisfies the equations Z ∞ t` φ(t) dt = δ`,0 for ` = 0, 1, 2, 3, 4. −∞

Problem 4.2. Use Octave to verify that φ ∗0 p = p for all p ∈ Πk . I suggest the following steps: (a) Choose a basis q0 , q1 , q2 , q3 , q4 for Πk . (b) For ` = 0, 1, 2, 3, 4, plot q` and φ ∗0 q` over the interval [−3, 3] to verify that they are equal (use the supp. Octave command semi discrete val). Problem 4.3. For h > 0 and [a, b] = [0, 2] consider the functions fe and se which are described on pages 25 and 26 of our lecture notes. (a) Write an octave function f wig.m which returns fe(x) (see the skeleton file f wig.m on our esnips repository). (b) Plot (in the same plot window) the function fe over the interval [−0.25, 2.25] for h = 1/10 and h = 1/20. Problem 4.4. Let se = φ ∗0h fe. (a) Plot the error f − se over the interval [0, 2] for h = 1/10 and h = 1/20. (b) Approximate Eh := kf − sek[0,2] for h = 1/20, 1/40, and 1/80. (c) Do the values Eh from part (b) correspond well with the error estimate in Approximation Theorem 8.9? Problem 4.5. Prove that the centered cardinal B-spline ψk satisfies ψk = ψ0 ∗ ψk−1 for k = 1, 2, 3, . . . Suggestion: Give a proof by induction. The base case k = 1 can be worked out explicitly, the induction step can be had by first showing that the derivatives are equal (property (iii) on page 4 of our lecture notes should be helpful here). It will then follow that ψk and ψ0 ∗ ψk−1 differ by a constant, and it is easy to finally show that this constant is 0.

6

CS 543

5. Homework Problem 5.1. Let N ∈ N and let CN be equipped with the usual inner-product:

hx, yi =

N −1 X

x(j)y(j),

j=0

where z denotes the complex conjugate of z (note eix = e−ix if x is real). For ω ∈ R, let Eω ∈ CN be given by Eω (j) = ei2πωj ,

j = 0, 1, . . . , N − 1.

(a) Prove that the vectors √1N E`/N , ` = 0, 1, . . . , N − 1, form an orthonormal basis for CN . (b) It is a well-known theorem in linear algebra that if v0 , v1 , . . . , vN −1 form an orthonormal basis for an inner-product space V , then

v=

N −1 X

hv, v` iv` for all v ∈ V.

`=0

Use this theorem and part (a) above to prove Inversion Theorem 13.3. Problem 5.2. Use Proposition 12.9 with 5 1 1 φ(x) = − ψ2 (x + 1) + ψ2 (x) − ψ2 (x − 1), 8 4 8

x ∈ R,

to approximate the Fourier transform of the function f (x) =



sin2 πx if − 1 ≤ x ≤ 1 0

otherwise

Let h be a user-defined parameter and plot the result for h = 0.1, 0.5, 0.25. Problem 5.3. Prove the following: Theorem. Let u : Z → C and v : Z → C be finitely supported sequences and put y = u ∗ v. Let N ∈ N and let U, V, Y ∈ CN denote the N -point discrete Fourier transforms of u, v, y, respectively. Then Y` = U` V` , ` = 0, 1, . . . , N − 1.

CS 543

7

Problem 5.4. With reference to the Applied Mathematics Example on page 28, recall that the Green’s function for the differential operator L, defined by 00

0

Ly = y − 2y + 2y,

is

G(x) =



−ex sin x if x ≤ 0 0

otherwise

.

2

With f (x) = (x2 + x)e−x , we consider the differential equation Ly = f whose exact 2 solution is yexact (x) = 41 e−x . (a) Write an octave script which approximates the convolution y = G ∗ f , where h > 0 is a user-defined parameter and φ is as defined in Problem 5.2. You can assume that G is supported on [−40, 0] and f is supported on [−8, 8]. (b) For h = 0.1, 0.05, 0.025, determine (approximately) Eh = ky − yexact kR . Does Eh look like chα for some constants c and α? Problem 5.5. The temperature along a wire of infinite length is modelled as the sequence ut : Z → R, where ut (j) represents the temperature of the wire at time t ∈ N0 (in seconds) and position j ∈ Z (in centimeters). It is assumed that heat flow in the wire is governed by the discrete heat equation ut+1 (j) − ut (j) =

ut (j − 1) − 2ut (j) + ut (j + 1) , 8

t ∈ N0 ,

j ∈ Z.

(a) Show that there exists a sequence r : Z → R, with supp r ⊂ {−1, 0, 1} such that ut+1 = r ∗ ut for all t ∈ N0 . (b) Show that if r (t) is defined recursively by r (1) = r and r (t+1) = r∗r (t) , then ut = r (t) ∗u0 . (c) Find a simple formula for the N -point DFT of the sequence r (t) . (b) If the temperature at time t = 100 is given by u 100 (stored in temp 100.dat), apply deconvolution to approximate the initial temperature u0 . NOTE: If temp 100.dat is saved in your working directory, the octave command load temp 100.dat will load the vector u 100 and the left-most support position m u. Keep in mind that the given temperature values include some added noise.