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
Final 7-day coursework, 2019-2020
Answer all questions
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 − α =
f\\ (ξk ) |
2f\ (xk ) |
(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,
|f\ (y)| ≥ |
1 − (1/4)2 |
= |
15/16 (17/16)2 |
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
a2 = 3 |
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
a1 = 2 |
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
which has solutions
µ± (λ) = α βλ ± 4 (α βλ )2 + 1 − α .
Hence ρ(B) < 1 if and only if |µ± (λ)| < 1 for all λ ∈ σ(A).
2023-05-05