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].

Solution

(a)  First note that the roots of f(x) = 0 are α+  = 3 and α−  = −2.

With  initial  interval  [1, 4] the bisection  method produces the  approximations x0  = (4 + 1)/2 = 2.5 and x1  = (4 + 2.5)/2 = 3.25.

The error after k iterations is guaranteed to satisfy

4 − 1       3  

so to ensure that |xk  − α+ | < 10 −6  it suffices to take 2k+1  > 3 × 106 , i.e.

log 3 + 6log 10

log 2

f(x) = 0 so both roots α± are fixed points of φ 1 . Furthermore, φ 1 is continuously differentiable.  However, φ(x) = 2x, so that  |φ1 (α+ )| =  |φ1 (3)| = 6 > 1 and

|φ1 (α− )| = |φ1 ( −2)| = 4 > 1. So the fixed point iteration for φ 1  cannot converge

root α+   is not a fixed point of φ2 ,  so α+   certainly cannot be found by the fixed point iteration.  The negative root α−  is a fixed point of φ2 , however, and

φ2  is real-valued and continuously differentiable  in a neighbourhood of α−  since

α−  > −6. Moreover, since φ(x) = − 1/(2^x + 6) we have |φ2 (α− )| = |φ2 ( −2)| =

Finally consider φ3 (x) = 1 + 6/x. The equation φ3 (x) = x is globally consistent with f(x)  =  0 so both roots α±   are fixed points of φ3 .   Furthermore,  φ3   is

continuously differentiable for x  0 with φ(x) = −6/x2 .  Hence the fixed point

iteration  for  φ3   cannot  converge  to  α−   since  |φ(α− )|  =  |φ( −2)|  =  6/22    =

(c)  By the CMT the iteration for φ2  converges to α−  = −2 for all x0  ∈ [ −3, − 1].  To

justify this, note that (i) φ2  : [ −3, − 1] → [ −3, − 1] since φ2  is strictly decreasing

1/(2^5) < 1 for all x ∈ [ −3, − 1].

By the CMT the iteration for φ3  converges to α+  = 3 for all x0  ∈ [2.5, 4].  To justify this, note that (i) φ3  : [2.5, 4] → [2.5, 4] since φ3  is strictly decreasing on [2.5, 4] and φ3 (2.5) = 1 + 6/2.5 = 17/5 ∈ [2.5, 4] and φ3 (4) = 1 + 6/4 = 5/2 ∈ [2.5, 4];  and  (ii) φ3  is a strict contraction on  [2.5, 4] since  |φ(x)| =  |6/x2 | ≤ 6/(2.5)2  = 24/25 < 1 for all x ∈ [2.5, 4].

Solution

(a) Taylor-expanding f(α) about x = xk  gives

0 = f(α) = f(xk ) + f\ (xk )(α − xk ) + f\\ (ξk )(α − xk )2 ,

for some ξk  between α and xk .

Combining this with the definition of the Newton iteration gives

xk+1 − α =

(xk  − α)2 .

(†)

Given δ > 0 define I6  := [α − δ,α + δ].

|xk+1 − α| ≤  ·  · δ · |xk  − α| =  |xk  − α|.

Hence if x0  ∈ I6  then by induction it follows that

|xk  − α| ≤ 2−k |x0 − α|,    k = 0, 1, . . . ,

so that xk  (and hence also ξk ) converges to α as k → ∞ .               Furthermore, from (†) we have by the continuity of f\  and f\\  that

xk+1  − α        f\\ (ξk )         f\\ (α)

(xk  − α)2         2f\ (xk )       2f\ (α)

(b) From (*) we know that for every C > |c| there exists k0  ∈ N such that

k ≥ k0   implies   I   I ≤ C,    i.e.  |xk+1 − α| ≤ C|xk  − α|2 ,

so the convergence is quadratic.

(c) We argue by contrapositive.  Suppose that the convergence is order p for some p > 2. Then there exist k0  ∈ N and C > 0 such that

k ≥ k0   implies   || ≤ C.

But then for k ≥ k0

I   I = || · |xk  − α|p−2  ≤ C|xk  − α|p−2 ,

which tends to zero as k → ∞ . Hence c = 0.

(d) For f(x) = x/(1 + x2 ) we have

f\ (x) =   1 − x2       and  f\\ (x) = −  2x(3 − x2 )

Hence, for |x|, |y| ≤ 1/4,

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.

Solution

(a) The method can be written as un+1  = un + hΨ(tn ,un ;h) with

Ψ(tn ,un ;h) = f(tn ,un ) + a2 f (tn + h,un + a1 hf(tn ,un )) .

The method is explicit, since Ψ is independent of un+1 .

(This is a two-stage Runge-Kutta method.)

(b) The truncation error of a one-step method un+1  = un + hΨ(tn ,un ;h) is

yn+1 − yn

where yn  = y(tn ) denotes the exact solution of the Cauchy problem at time tn .  Assuming sufficient smoothness (see later for specific assumptions), Taylor ex- pansion gives (with yn(/)  denoting y/ (tn ) etc.)

yn+1  = yn + hyn(/) + yn(//) + y/// (tn + ξ),    for some ξ ∈ [0,h],

and, with g(h) := Ψ(tn ,yn ;h) = f(tn ,yn ) + a2 f (tn + h,yn + a1 hf(tn ,yn )) ,

2

2

so that

Tn  =(yn(/) − g(0)) +  (yn(//) − 2g/ (0)) +  (y/// (tn + ξ) − 3g// (η)) .        (**)

Now,

g(0) = (  + a2 ) f(tn ,yn ),

and f(tn ,yn ) = yn(/)  (since y/ = f), so the O(1) term in (**) vanishes provided

Also, by the chain rule,

g/ (h) =  (   (t∗ ,y∗ ) + a1 f(tn ,yn )  (t∗ ,y∗ )) ,

where t∗ = tn + h and y∗ = yn + a1 hf(tn ,yn ), so that

g/ (0) =  (   (tn ,yn ) + a1 f(tn ,yn )  (tn ,yn )) ,

while applying the chain rule to y/ = f gives

yn(//)  =  (tn ,yn ) + f(tn ,yn )  (tn ,yn ),

so that the O(h) term in (**) vanishes provided

Applying the chain rule again we find that

g// (h) =   (t∗ ,y∗ ) + f(tn ,yn )  (t∗ ,y∗ ) + f(tn ,yn )2  (t∗ ,y∗ ).

Hence, from (**) we see that if a1  =  and a2  =  , and if y/// , f ,  ,  and

 all exist and are bounded, then there exists a constant C > 0 such that |Tn | ≤ Ch2 ,

so the method is of second order.

(c) A method is absolutely stable if, when applied to the model problem

for λ < 0, the numerical approximations un  satisfy un  → 0 as n → ∞ .            Applying the proposed method to this problem (with f(t,y(t)) = λy(t)) gives

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

= un + h ( λun + λ(un + hλun ))

= ( 1 + hλ + ) un .

Hence, by induction,

un  = ( 1 + hλ + )n u0 ,        n = 1, 2, . . . .

Thus the method is absolutely stable if and only if

(hλ)2

The left-hand inequality is always satisfied since the quadratic 2 + σ + σ2 /2 is positive for all real σ (it is positive at infinity and has no real roots). The right- hand inequality holds if and only if

hλ +  = hλ ( 1 + ) < 0,

which, since hλ < 0, holds if and only if 1 + hλ/2 > 0, i.e.

h <  2  

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).

Solution

(a) The iteration can be written in the prescribed one-step form with

B =  ) ,        d = (0(c) ) .

(b) We first show that if uk  → u∗ then u∗ is a fixed point of the map u '→ Bu + d.

For this we use the definition of the iteration and the fact that u '→ Bu + d is continuous to see that

u∗ =  lim uk+1  =  lim (Buk + d) = B ( lim uk ) + d = Bu∗ + d.

k →∞           k →∞                        k →∞

This implies by the definition of B that if u∗ =  (y(x) ) then y = x and x =

B0x + B1y + c, which combine to give that x = B0x + B1x + c. By the assumed consistency of (#) we conclude that x = y = x∗ .

(c)  Consistency for (#) is equivalent to requiring that I − B0  − B1  is invertible and

c = (I − B0 − B1 )x∗ . With the definitions of B0 , B1  given, we have I − B0 − B1  = I − (αI − βA) − (1 − α)I = βA.

Hence (#) is consistent if and only if c = βAx∗ , i.e. c = βb.  Note that invert-

ibility of I − B0 − B1  follows from that of A because β  0.

(d) The iteration converges for all initial guesses u0  ∈ R2n  if and only if ρ(B) < 1.   The constant µ ∈ C is an eigenvalue of B if and only if there exists 0  u =  ( y(x) ) ∈ R2n  such that Bu = µu. Since

B = ( αI  βA   (1 α)I ) ,

this is equivalent to saying that

(αI − βA)x + (1 − α)y = µx     and    x = µy.

By the second equation, the first equation is equivalent to

µβAy = (αµ + 1 − α − µ )y2 .

Since β  0, this implies that for µ  0 (we note that the case µ = 0 is not relevant for calculating the spectral radius)

αµ + 1 − α − µ2

for some λ ∈ σ(A). Then