Due: Friday, December 8th by 5:00 pm. Please upload a scanned copy on Gradescope and make sure all pages are readable.

Problems marked with , are to be done by hand; those marked with 口 are to be solved using a computer.

When asked to write a MATLAB function include it at the end of your live script.

Problem 1.  To solve the linear system Ax = b, where A ∈ Rn ×n , b ∈ Rn, the following iterative method is proposed:

xk+1)  = −ai,1x k)  − · · · − ai,i−1x)1 + (1 − ai,i)xk)  − ai,i+1x1  − · · · − ai,nx) + bi

for 1 ≤ i ≤ n and a i,i   0 for all i.

(a) , Write the iteration in matrix form. That is, write the iteration as

x(k+1)  = TRx(k) + cR ,

where TR  ∈ Rn ×n , cR  ∈ Rn.  Give TR, cR  in terms of A and b.

(b) , Suppose that A is symmetric and positive definite, then it is known that the eigenvalues of A are real and positive. Prove that the spectral radius of the iteration matrix, TR, is

ρ(TR) = max{| 1 − λ1  | , | 1 − λn  |},

where λ1  and λn  are, respectively, the biggest and smallest eigenvalues of A.

(c) , Show that, when A is symmetric and positive definite, the iteration converges if and only if λ1  < 2.

(d) 口 Write a MATLAB function myiteration which performs the above iteration method in matrix form.  Your function should have as inputs a matrix A, a vector b, the initial guess vector x0 , the tolerance TOL, and an integer max__iterations.  As a stopping criteria,

use the condition

∥x(n)  − x(n− 1)∥∞

∥x(n) ∥∞

2x1  −  x2                  = 3

−x1 + 2x2  −  x3  = 3

−  x2 + 2x3  = 1

and

1 2                = 2

2 3  = 1

1                  3  = 4

Use your program to approximate the solution the systems with x(0)  = 0 and tolerance within  10−5  in the  钝-norm.   For which system does the iteration method give a good approximation within 25 iterations?  Justify your answer.

Problem 2.

(a) , Let n  >  1 be a positive integer.   Use Newton’s method to produce a quadratically convergent method for calculating the nth root of a positive number a.  Prove quadratic convergence.

(b) 口 Consider the following iterative method to find a root p of a function f.  First choose initial approximations p0  and p1  with f(p0 ) · f(p1 ) < 0.  The approximation p2  is chosen as in the Secant method, as the x-intercept of the line joining (p0 , f(p0 )) and (p1 , f(p1 )). To decide which secant line to use to compute p3  consider f(p2 ) · f(p1 ):

. If f(p2 ) · f(p1 )  < 0, then there is a root between p2  and p1 , and choose p3  as the x-intercept of the line joining (p1 , f(p1 )) and (p2 , f(p2 )).

. if not, choose p3  as the x-intercept of the line joining  (p0 , f(p0 ) and  (p2 , f(p2 )), and then interchange the the indices on p0  and p1 .

. In a similar manner, once p3  is found, the sign of f(p3 ) · f(p2 ) determines whether we use p2  and p3  or p3  and p1  to compute p4.  If p3  and p1  are used, a relabeling of p2  and p1  is performed.

Write a MATLAB function myrootmethod.m which implements the above algorithm. Use your method to find a root of f(x) = cos (x) — x with p0  = 0.5 and p1  = π/4 and compare the approximations to those obtained using Newton’s Method and the Secant method.

Problem 3.   Consider the problem of finding a degree at most 4 polynomial interpolant for the function f(x) = ex  on the interval [ — 1, 1].

(a) , Let P4(x) be the degree at most 4 Lagrange interpolating polynomial interpolating f at the nodes x0  =  — 1, x1  =  — 1/2, x2  = 0, x3  =  1/2, x4  =  1.  Find the maximum error when P4(x) is used to approximate f(x) for x e [ — 1, 1].

(b) , Let Q4 (x) be the interpolating polynomial of degree at most 4 with nodes at the zeros

of T(˜)5 (x). Find the maximum error when Q4 (x) is used to approximate f(x) for x e [ — 1, 1].

Comment on how this compares to part(a).

(c) 口 In one figure plot Q4 , f, and the Tchebyshev nodes.

Problem 4.

(a) , Use Newton’s divided differences to find the Hermite cubic polynomial that interpolates the following data

(b) 口 The following two point sets define the top and bottom of a flying saucer shape. Top: