2. Let f  : R → R be three times continuously differentiable, and let α e R satisfy f (α) = 0, f\ (α) = 0, f\ (x) 0 for x α, and f\\ (α) 0.

Consider the fixed point method defined by x(k+1)  = φ(x(k)), where

f (x)

φ(x) = x - 2

(a) Write down a formula for φ\ (x), valid for x α, and use this to compute the value of φ\ (α) via Taylor approximations.

Apply a suitable result from fixed point theory to prove that, for a sufficiently good initial guess, the method converges to α at least linearly.

(b) Now, assuming convergence of x(k)  to α, prove that the method actually con-

verges quadratically, with

(x(k+1) - α) f\\\ (α)

k →o   (x(k) - α)2          6f\\ (α) .

Hint: use Taylor approximation to prove that

x(k+1) - α = (x(k) - α)2 + o((x(k) - α)2 ).

You may use without proof the fact that = 1 - e + O(e2 ) as e → 0 .

(c) Assuming the approximation

(x(k+1) - α) f\\\ (α)

(x(k) - α)2          6f\\ (α) ,

derive an estimate for the number of iterations required to approximate the root α = 0 of the function f (x) = x2 + x3  to within a given tolerance 0 < tol < 1, when the above method is applied with the initial guess x(0) = 1.

3.  Consider the linear system Ax = b where

A = ╱ µ(1)   4(µ) 、

and µ is a real parameter.

(a) Prove that the basic stationary iterative method does not converge for A.

(b) For which values of µ is A symmetric positive definite? Calculate the optimal

choice of α giving the fastest convergence for the stationary Richardson method x(k+1)  = (I - αA)x(k) + b,

along with the associated convergence constant 0 < C < 1 such that |x(k+1) - x|2 ≤ C|x(k) - x|2 .

(c) Without considering eigenvalues, give a sN巩O!au4 Ooup!4!ou on µ for the Ja- cobi method to be convergent.  Now, by considering eigenvalues, determine a uaOassv儿h vup sN巩O!au4 condition on µ for the Jacobi method to be convergent.

(d) Prove that when |µ| < 2 the iterates for the Jacobi method satisfy the estimate |x(k+2) - x|2 ≤ C |x\(k) - x|2 ,

for some constant 0 < C\ < 1 that you should specify.

)No4a:  TVa (k + 2) sNda儿sO儿!d4 Va儿a !s uo4 v 4hdo.(

4.  Consider the method

un+1  = un + hf (tn , un ),

for the solution of the Cauchy problem

n = 1, 2, . . . ,

(*)

(a)  Classify the method as either explicit or implicit.

(b)  State the definition of truncation error for a general one-step method.  Show

that the method (*) is of first order as h → 0. State clearly the smoothness assumptions under which your analysis is valid.

(c)  Given δ > 0, let vn  satisfy the perturbed system

Assume that

-Λ ≤ (t, y) ≤ -λ < 0, for some 0 < λ ≤ Λ .

Show that if h < 2/Λ is fixed then the method (*) is stable to perturbations, in the sense that vn - un  is bounded as n → o.

(d) Write down a sufficient condition on h under which the method (*) is stable to perturbations for the problem

(You may use without proof the fact that (arctan(z)) = 1/(1 + z2 ) .)

5.  Consider the second order boundary value problem

y(0) = y0 , y(1) = y1 ,

where q , r and f are continuous functions on [0, 1].

Given an integer N > 0, define the finite difference method

y(n) + qn + rnun  = fn ,    n = 1, . . . , N - 1,

where h  =  1/N , xn   = nh, qn   =  q(xn ), rn   = r(xn ),  fn   =  f (xn ) and un   is the approximation of y(xn ), for each n = 0, . . . , N .

(a) Write the method as a linear system of the form Au = f, specifying the system

matrix A and the vectors u and f .

(b) Without computing eigenvalues, show that if r(x) > 0 and h ≤ 2/ maxxo[0,1] |q(x)|

then the Jacobi and Gauss-Seidel methods both converge for this system.

(c) Prove that the truncation error Tn  := LN (y(xn )) - fn  satisfies |Tn | ≤ Ch2 ,

for some constant C > 0 that you should specify.

(You may assume that y(x) is four times continuously differentiable on [0, 1] .)

(d) Briefly explain the idea of the shooting method for solving the original boundary value problem.