MATH0033: Numerical Methods 2019-2020
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).
2022-05-07