1. Let f (x) = log(x + 2) - x/2.

(a)  Show that f has a unique root α in the interval (0, o).

(b) Prove that [2, 4] is a valid starting interval for the bisection method, and determine

the number of iterations required to find α with an absolute error less than or equal to 10-6 .

(c) Write down the Newton iteration explicitly for this problem.  Does the iteration converge linearly or quadratically to α? Justify your answer.

(d)  Show that φ1 (x) = 2 log(x + 2) and φ2 (x) = eα/2 - 2 both provide consistent fixed point formulations for f (x) = 0.

Prove that one of these formulations converges to α for any initial guess in [2, 4], while the other does not converge to α, regardless of how good the initial guess is, unless one of the iterates equals α itself.

2.   (a)  Consider the iterative solution of the linear system Ax = b, where A = ╱ 3(ξ)   4(1) 、,

ξ  0 is a real parameter, and x, b e R2 .

Without computing eigenvalues, give a sucient condition on ξ for the Jacobi and Gauss-Seidel methods to be convergent.

(b) Write down the iteration matrices for the Jacobi and the Gauss-Seidel methods

for the matrix in part (a), and determine a necessary and sucient condition on ξ for the Jacobi and Gauss-Seidel methods to be convergent.

(c) In the gradient method for the solution of a general linear system Ax = b, the relative step length αk  in the increment xk+1  - xk  = αk rk   (with rk  = b - Axk denoting the residual) is chosen so as to minimise the magnitude of the error vector ek+1  = x - xk+1  with respect to a certain A-weighted norm. Explain why it is not in general possible in a practical implementation to choose αk  so as to minimise the magnitude of ek+1  with respect to the Euclidean norm.

3.  (a)  Show that if X, Y e Rnxn  are symmetric then ρ(XY) s ρ(X)ρ(Y).

(b) Let A e Rnxn  be an invertible matrix, and let b e Rn . Suppose that A = A1 + A2 for some symmetric positive definite matrices A1 , A2  e Rnxn .  Given a1 , a2  > 0,

consider the following iteration, where I e Rnxn  denotes the identity matrix:

 }       k = 0, 1, 2, . . . .

Show that the iteration can be written in the form xk+1   = Bxk  + c for some B e Rnxn  and c e Rn  that you should specify.

(c)  Show that if

R := λ(1σ(a)1 )  │ λ(2σ(a)2 )  │ < 1

then the iteration converges to the exact solution of the linear system Ax = b.   You may assume without proof that the iteration is consistent, and that if X, Y e Rnxn  then ρ(XY) = ρ(YX).

(d) Now suppose that σ(A1 ), σ(A2 ) c [λ- , λ+] for some 0 < λ-  s λ+  < o.

Show that if a1  = a2  = a > 0 the quantity R defined in (c) satisfies

R s ╱max {  │ ,  │}、 2 .

By minimising the right-hand side of this inequality as a function of a, show that a can be chosen so as to give

|xk+1 - x|2  s \2 |xk  - x|2 ,        k = 0, 1, 2, . . . ,

assuming the matrix B in (b) is symmetric.

4.  Consider the following IVP involving a system of ODEs for two unknowns S and I:

,

ì ì ì ì ì

(

ì ì ì ì ì

(

dS

(t) = -βI(t)S(t),

dt

dI

(t) = βI(t)S(t) - γI(t), dt

S(0) = S0 ,        I(0) = I0 ,

0 < t < T,

0 < t < T,

where T, β , γ , S0  and I0  are all positive real numbers.

(a) Write the system in the form

, y\ (t) = f(t, y(t)),    0 < t < T,

defining y, y0  and f, and show that if u, v e [0, 1] × [0, 1] then

|f(t, u) - f(t, v)|o  s L|u - v|o

for some constant L > 0 that you should specify.

(b) Define the truncation error Tn  for the backward Euler scheme applied to this IVP

system with a uniform time step, and show that, under appropriate smoothness assumptions,

|Tn |o  s Ch,

where h is the time step length and C > 0 is a constant you should specify. State the smoothness assumptions on S(t) and I(t) under which your analysis is valid.

(c)  Show that the backward Euler solution un  considered in part (b) satisfies |y(tn ) - un |o  s C* h,        0 < h < h* ,

for some C*  > 0 and h*  > 0 you should specify.

(d) Write down the system (S) of nonlinear equations that must be solved at each time step in the backward Euler method for this IVP system.

Show that if the system (S) has a solution in [0, 1] × [0, 1] and if γ > β then the Newton method for the solution of (S) converges quadratically to that solution, assuming a sufficiently good initial guess (that you need not specify).  If you use any results from lectures, quote them carefully.