1. Consider the numerical solution of f(x) = 0 where f(x) = e/2  - x - 1, which has a unique non-zero root a satisfying a E [2, 3].

(a) Show that it is possible to approximate the root a using the bisection method with initial interval [2, 3], and calculate the number of iterations required for the absolute error to be smaller than 10-5 .

You may assume without proof that 24/3  < e < 3.

(b) Let <f>(x) = 2log (x + 1) for x > -l.

Show that x = <f>(x) is consistent with f(x) = 0, and, using an appropriate the­ orem from lectures, prove that the fixed point iteration xk+1 = <f>(xk) converges linearly to a for all initial guesses x0  E [2, 3], and satisfies an error bound

where O < Ck  < 1 is a k-dependent constant you should specify.

(c) Let rp : IR ----+ IR be continuously differentiable and let (3 E IR be a fixed point of rp s.t. lrp'(/3)1 > 1. Prove that the iteration xk+1 = rp(xk), k = 0, 1, 2, ..., does not converge to (3 for any initial guess x0  E IR, unless xk  = (3 for some k.

Hint: argue by contradiction, using the mean value theorem.

2. Consider the stationary iterative method

x   lk+ = Bxk + c,   k = 0,l,2,...,

for the numerical solution of the linear system

Ax=b.

Here A, B E ffi.n X n   and x,b,C E ]Rn   for some n E N.

(a) Given a vector norm II · II : ffi.n   -----r IR, write down the definition of the induced matrix norm II · II : ffi.n x n   -----r R

(b) Assuming the method is consistent, prove that if IIBII < 1 then llx - xk ll ------r  0

ask -----r oo.

(c) What does it mean for the matrix A to be strictly diagonally dominant (SDD) by rows?

(d) Write down the definition of the iteration matrix B for the Jacobi method.

Prove that if A is SDD then the Jacobi method converges.

You may use without proof the fact that the matrix norm induced by the vector norm llvlloo := maxi=l,...,n lvil satisfies

n

IIMlloo = i1a,x.,n L lmijl,

(e) Now consider the system of nonlinear equations

fi(x1 ,x2) = Xi - x2  = 0,

h(x1 ,x2) = x + x1 - 1 = 0,

which can be written as f(x) = 0 with f = (11 ,hf and x = (x1 ,x2f.

Write down the Newton iteration for the solution of the system f(x) = 0.       Give a sufficient condition on the initial guess xC0)  guaranteeing that the first Newton step can be computed using a Jacobi iteration.

One root of the system lies in the quadrant x1    0, x2    0. Does the Newton iteration converge linearly or quadratically to this root (for a sufficiently good initial guess)?

3.   (a)  Consider the linear system Mx =b where

M=(  µ2)

µ -/- 0 is a real parameter, and b E 2 .

Write down the Jacobi and the Gauss-Seidel methods for the iterative solution of the linear system in the form Pxk+1  =Nxk + b where P and N are matrices you should specify. Without computing the iteration matrices, give a sufficient condition on the parameter µ so that the Jacobi and the Gauss-Seidel methods are both convergent.

(b)  Compute the iteration matrices BJ and Bes for the Jacobi and the Gauss­

Seidel methods respectively.  Using information from the iteration matrices, determine a necessary and sufficient condition onµ for the Jacobi and Gauss­ Seidel methods to be convergent. Which method is expected to converge faster?

(c)  Let A be a symmetric positive definite matrix.  Consider the gradient method for the solution of Ax = b, defined by xk+1 =xk + akrk , where rk  =b - Axk and ak  is the step length.  Prove that the optimal choice of ak , minimising llek+1IIA,  where ek  =x - xk  and llvll :=vTAv= (Av, v), is

4. For the solution of the Cauchy problem

consider the following family of numerical methods, parametrized by O  0  1:

n = 1,2,....

(a)  For which 0 is the method explicit?

(b)  State the values of 0 for which (*) coincides with the forward Euler, backward

Euler and Crank-Nicolson methods respectively.

(c)  State the definition of truncation error for a general one-step method. Show that the method (*) is of second order if 0 = 1/2, and of first order otherwise. State clearly the smoothness assumptions under which your analysis is valid.

(d)  State the definition of absolute stability for a general one-step method. Prove that the method (*) is unconditionally absolutely stable if 0  1/2 and condi­ tionally absolutely stable if 0 < 1/2. In the latter case, determine a necessary and sufficient condition on h for the method to be absolutely stable.