Answer all questions .

1.        (a) Consider the function f : [0, ∞) → R defined by f(x) = sinx − x cos x.

We are interested in finding positive roots of f . Consider the following two fixed point iterations

xk+1  = ϕ 1 (xk ),                        ϕ1 (x) = tanx

k+1  = ϕ2 (k ),                        ϕ2 (x) = x −  +

where x0 and 0 are initial guesses. For each of the two fixed point iterations above, determine

(i) if the method is consistent for any positive root α > 0 of f;           (ii) if the method is locally convergent near a positive root α > 0 of f .

If either of these methods is locally convergent, determine also the corre- sponding order of convergence of that method.

(b) Provide an original example of a real-valued function f of a single real vari- able and a corresponding real root α of f such that Newton’s method has local convergence of order equal to three, and no higher than three. Justify your answer by proving that your example fulfills the required condition.  Your  answer  should  consist  of an  original  example  of your  own  creation that is not found already in the course materials or other references . (25 marks)

2.  Let A ∈ Rn ×n  be the symmetric tridiagonal matrix given by                                                           

A =           . . .     . . .     . . .        

(               )

where a and b are both positive real numbers, and where all other entries of A not shown above are zero.

(a) Show that the eigenvalues λk  of A are given by

λk  = a + 2bcos ( ) ,

for k = 1, . . . ,n. What is the maximum and minimum eigenvalue of A? Hint:  check that the vectors vk  given by

vj(k)  = sin ( )    j = 1, . . . ,n

are  eigenvectors for k = 1, . . . ,n .

(b) Considering still the matrix A given above, show that the Jacobi method for the system Ax = b is convergent if and only if A is positive definite.

(c) For a given initial guess x0 , let xk  , k ≥ 1, denote the k-th iterate of Jacobi’s method for the linear system Ax = b. Let ϵ > 0 be a given tolerance. Find

a sufficient condition on k in terms of n, a, b and ϵ to ensure that ∥xk  − x∥2  ≤ ϵ .

Use this to describe the behaviour of the convergence of Jacobi’s method as n becomes large.

Hint:  your answer should distinguish  the  cases  where a > 2b, a = 2b and a < 2b . (25 marks)

3.  Let A  ∈ Rn ×n   be a symmetric positive definite matrix, let b  ∈ Rn .   For a given 北0  ∈ Rn , consider the Conjugate Gradient method given by the sequence of

iterations

北k+1  = 北k + αkpk ,       αk  =

(Apk , pk )  ,   for each k ≥ 0, where rk  = b − A北k  for all k ≥ 0, with p0  = r0 .

(a) Show that, for any k ≥ 1,

(rk , rj ) = 0   Aj = 0, . . . ,k − 1.

Recall any results from the lectures that you use as part of your answer. (b) Show that the coefficients αk  can be equivalently written as

∥rk ∥2(2)

αk  =

What can be said about the error 北 − 北k  if αk  = 0 for some value of k?

(c) Construct an original example of a matrix A and vector b to show why the Conjugate Gradient method cannot generally be applied in the case where A is not symmetric positive definite.   Your answer should show clearly the reason why the Conjugate Gradient method is not applicable to your example.

Your answer should consist an  original example  of your own  creation that is not found already in the course materials or other references . (25 marks)

y\ (t) = y2 (t)   t > 0,

y(0) = 1

and consider it’s approximation by the Backward Euler method with step length h given by

(1)                                    un+1  = un + hun(2)+1 ,    u0  = 1.

(a) Show that the equation (1) admits two real solutions for un+1  in terms of un , provided that un  satisfies a condition that you should specify as part of your answer.  Explain why one of these solutions is not appropriate for approximating the solution y(t) and can thus be discarded.

(b) Considering only the appropriate solution found in part (a), find a recur- rence relation for the quantity zn  = 1 − 4hun  of the form zn+1  = ϕ(zn ) for some function ϕ that you should determine.

(c) Using your answers in part (a) and (b), prove that for any h > 0, there exists an n ∈ N such that no real solution un+1  exists. What feature of the solution y(t) of the original problem does this numerical scheme reproduce? Hint:   you  may  use  without proof the fact  that  the  exact  solution  of the initial value problem is y(t) = (1 − t)−1 . (25 marks)