Math 104A Homework #3 Instructor: Lihui Chai General Instructions: Please write your homework papers neatly. You need to turn in both full printouts of your codes and the appropriate runs you made. Write your own code, individually. Do not copy codes! 1. (a) Let f C 2 [x0 , x1 ] and P1 its interpolation linear polynomial at x0 and x1 . Prove that 1 kf P1 k (x1 x0 )2 M2 , 8 (1) where |f 00 (x)| M2 for all x [x0 , x1 ] and kf P1 k = max |f (x) P1 (x)|. x[x0 ,x1 ] (b) Let P1 (x) be the linear polynomial that interpolates f (x) = sin x at x0 = 0 and x1 = /2. Using (a) find a bound for the maximum error kf P1 k and compare this bound with the actual error at x = /4. 2. (a) Equating the leading coefficient of in the Lagrange form of the interpolation polynomial Pn (x) with that of the Newton's form deduce that f [x0 , x1 , ..., xn ] = n X j=0 f (xj ) n Q . (2) (xj xk ) k=0 k6=j (b) Use (a) to conclude that divided differences are symmetric functions of their arguments, i.e. any permutation of x0 , x1 , ..., xn leaves the corresponding divided difference unchanged. 3. In Newton's form of the interpolation polynomial we need to compute the coefficients, c0 = f [x0 ], c1 = f [x0 , x1 ], ..., cn = f [x0 , x1 , ..., xn ]. In the table of divided differences we proceed column by column and the needed coefficients are in the uppermost diagonal. A simple 1D array, c of size n + 1, can be used to store and compute these values. We just have to compute them from bottom to top to avoid losing values we have already computed. The following pseudocode does precisely this: for j = 0, 1, ..., n do All course materials (class lectures and discussions, handouts, homework assignments, examinations, web materials) and the intellectual content of the course itself are protected by United States Federal Copyright Law, the California Civil Code. The UC Policy 102.23 expressly prohibits students (and all other persons) from recording lectures or discussions and from distributing or selling lectures notes and all other course materials without the prior written permission of Prof. Hector D. Ceniceros. 1 cj = fj end for for k = 1, ..., n do for j = n, n 1, ..., k do cj = (cj cj1 )/(xj xjk ) end for end for The evaluation of the interpolation polynomial in Newton's form can be then done with the Horner-like scheme: p = cn for j = n, n 1, ..., 0 do p = cj + (x xj )p end for (a) Write computer codes to compute the coefficients c0 , c1 , ..., cn and to evaluate the corresponding interpolation polynomial at an arbitrary point x. Test your codes and turn in a run of your test. 2 (b) Consider the function f (x) = ex for x [1, 1] and the nodes xj = 1 + j(2/10), j = 0, 1, ..., 10. Use your code in (a) to evaluate P10 (x) at the points x j = 1 + j(2/100), j = 0, 1, ..., 100 and plot the error f (x) P10 (x). 4. Inverse Interpolation. Suppose that we want to solve the equation f (x) = 0, for some function f which has an inverse f 1 . If we have two approximations x0 and x1 of a zero x of f then we 1 can use interpolation to find a better approximation, x f (0), as follows. Let y0 = f (x0 ) and y1 = f (x1 ). Table 1 yj = f (xj ) y0 y1 xj x0 x1 f 1 [y0 , y1 ] and P1 (0) = x0 + f 1 [y0 , y1 ](0 y0 ) = x0 y0 f 1 [y0 , y1 ]. We could now define x2 = P1 (0), evaluate f at this point to get y2 = f (x2 ), and then add one more row to our table 1 to get f 1 [y0 , y1 , y2 ]. Once this is computed we can evaluate P2 (0) to get an improved approximation x , etc. Let f (x) = x ex using the values f (0.5) = 0.106530659712633 and f (0.6) = 0.051188363905973 find an approximate value for the zero x of f by evaluating P1 (0). 5. Obtain the Hermite interpolation polynomial corresponding to the data f (0) = 0, f 0 (0) = 0, f (1) = 2, f 0 (1) = 3. 2 Interpolation Hector D. Ceniceros 1 Approximation Theory Given f C[a, b], we would like to find a \"good\" approximation to it by \"simpler functions\