1. Let f(x) = x2 − x − 6 and denote by α+  and α− respectively the positive and negative roots of f(x) = 0.

(a)  Suppose that the bisection method is used to find α+  with initial interval [1, 4].

Compute the first two approximations x0  and x1  and estimate the number of iterations required for the absolute error to be smaller than 10 −6 .

(b) For each of the three functions

φ 1 (x) = x2 − 6,        φ2 (x) = − ^x + 6,        φ3 (x) = 1 + 6/x    (for x  0),

determine whether the corresponding fixed point iteration xk+1   =  φ(xk ) can converge to α+  or to α− , given a sufficiently good initial guess.   Justify your answers carefully.

(c) For those combinations of function and root for which convergence is possible, determine a suitable interval [a,b] such that the fixed point iteration is guaranteed to converge to the root in question for every initial guess x0  ∈ [a,b].

3.  Consider the solution of the Cauchy problem

y(0) = y0 ,

using the following numerical method:

u0  = y0 ,

  p1  = f(tn ,un )

For n = 1, 2, . . . ,    〈  p2  = f(tn + h,un + a1 hp1 )

‘ un+1  = un + h(p1 + a2p2 ),

where a1 ,a2  ∈ R.

(a) Write the method in one-step form un+1  = un  + hΨ(tn ,un ,un+1;h), specifying

the increment function Ψ . Is the method explicit or implicit?

(b) Determine conditions on the constants  a1 ,a2   under which the method  (*) is

second order consistent as h → 0.   State clearly the smoothness assumptions on y and f under which your analysis is valid.

(c) Determine for which h the method (*) is absolutely stable, in the special case where a1  = 2/3 and a2  = 3/4.

4. Let A ∈ Rn×n  be an invertible matrix, b ∈ Rn , and let x∗ ∈ Rn  be the unique solution of the equation Ax = b. Consider the two-step iteration

xk+1  = B0xk + B1xk−1 + c,    k = 1, 2, . . . ,

where B0 ,B1  ∈ Rn×n  and c ∈ Rn . We say the iteration is consistent if Ax = b ⇔ x = B0x + B1x + c.

(a) Rewrite (#) as an equivalent one-step iteration

uk+1  = Buk + d,    k = 1, 2, . . . ,

for uk  =  ) ∈ R2n, specifying B ∈ R2n×2n  and d ∈ R2n .

(b) Assume that (#) is consistent. Prove that if the sequence (uk ) defined in part (a)

converges for every initial guess u0  = (x(x)0(1)  ) ∈ R2n then the limit is independent of u0  and equals  (x(x) ).

Hint: show that if uk  → u∗ then u∗ is a fixed point of the map u '→ Bu + d .

(c) Now let B0  = αI − βA and B1  = (1 − α)I for some α,β ∈ R with β  0. Determine the choice of c ensuring that (#) is consistent in this case.

(d) Assuming the choices of B0 , B1  and c from part (c), show that (#) converges to x∗ for all initial guesses x0 , x1  ∈ Rn  if and only if

'α βλ ± 4 (α βλ )2 + 1 − α ' < 1

'                                                      '             Aλ ∈ σ(A).