Math 552 Scientific Computing II Spring 2015 SOLUTIONS: Homework Set 2 1. Apply the Gram-Schmidt orthogonalization process to the polynomials 1, x, x2 , . . . to find the first 5 Legendre polynomials. ANS: For a general weight R 1function w(x) ≥ 0, the inner product of two functions f (x) and g(x) is hf, giw = −1 f (x)g(x)w(x) dx. The weight function w(x) = 1 generates the Legendre polynomials, or Z 1 hf, gi = f (x)g(x) dx. −1 Applying the Gram-Schmidt process to {1, x, x2 , . . .} produces a set of mutually orthogonal polynomials {L0 (x), L1 (x), L2 (x), . . .}, the first 5 of which are L0 (x) = 1 L1 (x) = x − 0 hx, L0 i L0 (x) = x − L0 (x) hL0 , L0 i 2 = x hx2 , L0 i hx2 , L1 i L0 (x) − L1 (x) hL0 , L0 i hL1 , L1 i 2/3 0 = x2 − L0 (x) − L1 (x) 2 2/3 = x2 − 1/3 L2 (x) = x2 − hx3 , L0 i hx3 , L1 i hx3 , L2 i L0 (x) − L1 (x) − L2 (x) hL0 , L0 i hL1 , L1 i hL2 , L2 i 0 2/5 0 = x3 − L0 (x) − L1 (x) − L2 (x) 2 2/3 8/45 = x3 − 0 ∗ 1 − 3/5 ∗ x − 0 ∗ (x2 − 1/3) = x3 − 3/5x L3 (x) = x3 − hx4 , L0 i hx4 , L1 i hx4 , L2 i hx4 , L3 i L0 (x) − L1 (x) − L2 (x) − L3 (x) hL0 , L0 i hL1 , L1 i hL2 , L2 i hL3 , L3 i 2/5 0 16/105 0 = x4 − L0 (x) − L1 (x) − L2 (x) − L3 (x) 2 2/3 8/45 8/175 = x4 − 1/5 ∗ 1 − 0 ∗ x − 6/7 ∗ (x2 − 1/3) − 0 ∗ (x3 − 3/5x) = x4 − 6/7x2 + 3/35 L4 (x) = x4 − hx5 , L0 i hx5 , L1 i hx5 , L2 i hx5 , L3 i L0 (x) − L1 (x) − L2 (x) − L3 (x) − hL0 , L0 i hL1 , L1 i hL2 , L2 i hL3 , L3 i hx5 , L4 i L4 (x) hL4 , L4 i 0 2/7 0 16/315 0 = x5 − L0 (x) − L1 (x) − L2 (x) − L3 (x) − L4 (x) 2 2/3 8/45 8/175 hL4 , L4 i = x5 − 0 ∗ 1 − 3/7 ∗ x − 0 ∗ (x2 − 1/3) − 70/63 ∗ (x3 − 3/5x) − 0 ∗ (x4 − 6/7x2 + 3/35) = x5 − 70/63x3 + 5/21x L5 (x) = x5 − Of course, these may be rescaled to produce, for example, an orthonormal basis in addition to an orthogonal basis. 2. (5pts-3,1,1)The Chebyshev polynomials are defined for x ∈ [−1, 1] by Tn (x) = cos(nθ), x = cos θ. a) Derive the 3-term recurrence relation, Tn+1 (x) = 2xTn (x) − Tn−1 (x) . b) Given T0 (x) = 1 and T1 (x) = x, use the recurrence relation to find T2 (x) and T3 (x). c) What are the roots of T3 (x)? ANS: a) 2xTn (x) − Tn−1 (x) = = = = = = 2 cos (θ) cos (nθ) − cos ((n − 1)θ) 2 cos (θ) cos (nθ) − cos (nθ − θ) 2 cos (θ) cos (nθ) − (cos (nθ) cos (θ) + sin (nθ) sin (θ)) cos (θ) cos (nθ) − sin (nθ) sin (θ) cos ((n + 1)θ) Tn+1 (x) b) T2 (x) = 2xT1 (x) − T0 (x) = 2xx − 1 = 2x2 − 1 and T3 (x) = 2xT2 (x) − T1 (x) = 2x(2x2 − 1) − x = 4x3 − 3x. p c) The roots of T3 (x) = 4x3 − 3x = x(4x2 − 3) are x = 0, ± 3/4. 3. Consider the integral, Z 1 2 xe−x dx . 0 Use the 4-point Gaussian-Legendre quadrature rule to approximate the integral (after changing variables to obtain an integral over [-1,1]). The points and weights are: x1 x2 x3 x4 = −0.861136311594053 = −0.339981043584856 = −x2 = −x1 c1 c2 c3 c4 = 0.347854845137454 = 0.652145154862546 = c2 = c1 What is the absolute error in the approximation? ANS: First, let’s determine the exact answer. Letting u = x2 then du = 2x dx giving 1 Z Z 1 1 −u e−1 1 1 −u −x2 e du = − e = ≈ 0.316060279414279 xe dx = 2 0 2 2e 0 0 we must make a change of variable in order to the Rintegral as one over R 1 express t+1 2 1 −x2 [−1, 1]. Letting t = 2x − 1 ⇒ dt = 2dx, so 0 xe dx = −1 t+1 e−( 2 ) 21 dt = 2 R t+1 2 1 1 (t + 1)e−( 2 ) dt. Rewriting the integral again in therm of x, we have 4 −1 Z 1 −1 x+1 2 1 (x + 1)e−( 2 ) dx 4 Here is a MATLAB script to perform the needed computations x = [-0.861136311594053 -0.339981043584856 ... 0.339981043584856 0.861136311594053]’; c = [ 0.347854845137454 0.652145154862546 ... 0.652145154862546 0.347854845137454]’; f = ’0.25*(x+1).*exp(-((x+1)/2).^2)’; gauss_approx = dot(c,eval(f)) exact = (exp(1)-1)/(2*exp(1)) error = abs(exact-gauss_approx) whose output is gauss_approx 0.316058997487186 exact 0.316060279414279 error 1.28192709325514e-06 4. (5pts) We proved in class that for n ≥ 2 that Gauss-Legendre Quadrature rule Z 1 f (x) dx ≈ (∗) −1 n X cj f (xj ) j=1 is exact for any polynomial of degree ≤ 2n − 1, where {xj }nj=1 are the n distinct roots of the Legendre polynomial pn (x) of degree n, and {cj }nj=1 the corresponding weights. Show that indeed this is the best we can expect by proving that (∗) is not exact for n Y f (x) = (x − xj )2 , j=1 a polynomial of degree 2n. (Hint: Compute the approximation for any n. Why can’t it be correct? There are no numerics in this problem, only theory!) ANS: Note that by construction f (xj ) = 0, indeed xj is a double root of f (x) for 1 ≤ j ≤ n. Thus, n X cj f (xj ) = 0 . j=1 Clearly f (x) is a polynomial – hence continuous – such that f (x) R≥ 0 on [−1, 1] 1 being the product of squared term, but f 6≡ 0 over the interval so −1 f (x) dx > 0 while the quadrature rule gives 0. We then have a 2n degree polynomial for which the quadrature rule is not exact. Thus it is not exact for all polynomials up to and including those of degree 2n.

© Copyright 2018