Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH0033: Numerical Methods

2019-2020

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) = −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

 

|xk − α+| ≤  2k+1   = 2k+1 ,

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

k >                         − 1.

(b) Consider first φ1 (x) = x2 − 6. The equation φ1 (x) = x is globally consistent with

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 to either root.

Next consider φ2 (x) = −+6. Global consistency now fails, since the positive 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/(22 (α− )| = |φ2 ( −2)| = 1/(2) = 1/4 < 1 so the fixed point iteration converges to α−  for a sufficiently good initial guess.

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   = 3/2 > 1.  But it can converge to α+  for a sufficiently good initial guess since |φ(α+)| = |φ(3)| = 6/32  = 2/3 < 1.

(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 on  [ −3, − 1] and φ2 ( −3) =  −  ∈ [ −3, − 1] and φ2 ( − 1) =  −  ∈ [ −3, − 1];

and (ii) φ2  is a strict contraction on [ −3, − 1] since |φ(x)| = |1/(2 1/(2) < 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].

2. Let f : R → R be twice continuously differentiable. Let α ∈ R be such that f(α) = 0 and f′(α)  0.

(a) Show that if there exists δ > 0 such that

≤        ∀x,y ∈ [α − δ,α + δ],

then the Newton iteration converges to α for any initial guess x0  ∈ [α − δ,α +δ],

and that

lim                 = c,                                          (*)

(b) Show that (*) implies that the convergence is quadratic (order 2).

(c) Show that if c  0 then the convergence cannot be order p for p > 2.

(d) Let f(x) = x/(1 + x2).

Show that if the initial guess satisfies  |x0 |  ≤  1/4 then the Newton iteration converges quadratically to the root α = 0.

What happens when x0  > 1?

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 − α =  f′′k) (xk − α)2 .                                  (†)

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

If xk  ∈ Iδ  then also ξk  ∈ Iδ, which implies that

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

Hence if x0  ∈ Iδ  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

=                         =: c,       as k → ∞ .

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

k ≥ k0   implies                     ≤ 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

=                  · |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

1 − x2                                           2x(3  x2)

(1 + x2)2                                          (1 + x2)3   .

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

|f′(y)| ≥                      =

and

|f′′(x)| ≤                   =

|f′′(x)|     3   17   17     3   20   20     5              1

|f′(y)|      2   15   16     2   15   16     2            1/4 ,

so quadratic convergence follows by parts (b) and (c) with δ = 1/4. If x0  > 1 then the iteration diverges to +∞. Indeed, if xk  > 1 then

xk+1 − xk  = − f(xk) = xk(1 + (xk)2) > 1 · (xk)2  = 1,

so that xk+1  > xk + 1, which implies by induction that if x0  > 1 then xk  > 1 + k for all k ∈ N, which diverges to infinity as k → ∞ .

3. Consider the solution of the Cauchy problem

  y′(t) = f(t,y(t)),    t > 0,

using the following numerical method:

u0  = y0 ,

  p1  = f(tn,un) 

For n = 1, 2,...,      p2  = f(tn + h,un + a1hp1)                       (*)

 

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) + a2f tn + h,un + a1hf(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

Tn  =                 − Ψ(tn,yn;h),

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 y denoting y′(tn) etc.)

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

and, with g(h) := Ψ(tn,yn;h) = f(tn,yn) + a2f tn + h,yn + a1hf(tn,yn)  ,

g(h) = g(0) + hg′(0) + h2 g′′(η),    for some η ∈ [0,h],

so that

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

Now,

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

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

3

2  =   .

Also, by the chain rule,

g′(h) =    (t∗,y∗) + a1f(tn,yn) (t∗,y∗) ,

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

g′(0) =    (tn,yn) + a1f(tn,yn) (tn,yn) ,

while applying the chain rule to y′  = f gives

y = ∂f (tn,yn) + f(tn,yn)∂f (tn,yn),

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

2

1  =   .

Applying the chain rule again we find that

g′′(h) = 1 2f (t∗,y∗) + 2f(tn,yn) 2f (t∗,y∗) + 1f(tn,yn)2 2f (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

  y′(t)   =   λy(t)   for t > 0,

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

− 1 < 1 + hλ +           < 1.

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.

2

h <      

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)   ∈ 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 7→ 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

 ± s  2 + 1 − α  < 1       ∀λ ∈ σ(A).

Solution

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

B =  I(B)0

1    ,       d =    .

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

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

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

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 =   ,

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)

= λ

µβ

for some λ ∈ σ(A). Then

which has solutions

µ±(λ) =  ± s  2 + 1 − α .

Hence ρ(B) < 1 if and only if |µ±(λ)| < 1 for all λ ∈ σ(A).