Accelerating Convergence 1
2.6 Accelerating Convergence
1. Show that the equation for Aitken’s ∆2-method can be rewritten as
ˆpn=pnpn−2−p2
n−1
pn−2pn−1+pn−2
.
Explain why this formula is inferior to the one used in the text.
Combining the terms on the right-hand side of the formula yields
Note that both formulas for calculating ˆpnhave the potential for cancellation error.
2. Should Aitken’s ∆2-method be applied to a sequence generated by the bisection
method? Explain.
2Section 2.6
3. The sequence listed below was obtained from the method of false position ap-
plied to the function f(x) = tan(πx)−x−6 over the interval (0.40,0.48).
1 0.420867411
2 0.433202750
3 0.440495739
4 0.444807925
5 0.447357748
6 0.448865516
7 0.449757107
(a) Apply Aitken’s ∆2-method to the given sequence.
(b) To nine digits, the zero of fon (0.40,0.48) is x= 0.451047259. Use this
to show that both the original sequence and the output from Aitken’s ∆2–
method are linearly convergent and estimate the corresponding asymptotic
error constants. By how much has Aitken’s ∆2-method reduced the asymp-
totic error constant?
(a) Using the first three terms in the False Position sequence, we calculate
Next, using p2,p3and p4, we calculate
Accelerating Convergence 3
False Position Aitken’s ∆2
npn|en|/|en−1|ˆpn|en|/|en−1|
1 0.420867411
3 0.440495739 0.5913 0.451043933
5 0.447357748 0.5913 0.451046884 0.3409
4. The sequence listed below was obtained from Newton’s method applied to the
function f(x) = x(1 −cos x) to approximate the zero at x= 0.
1 0.646703997
2 0.425971211
3 0.282530441
4 0.187933565
5 0.125165810
6 0.083407519
7 0.055594262
(a) Apply Aitken’s ∆2-method to the given sequence.
(b) Verify that both the original sequence and the output from Aitken’s ∆2–
method are linearly convergent and estimate the corresponding asymptotic
error constants. By how much has Aitken’s ∆2-method reduced the asymp-
totic error constant?
(a) Using the first three terms in the Newton’s method sequence, we calculate
Next, using p2,p3and p4, we calculate
4Section 2.6
Continuing in this manner, we find
(b) The values in columns 3 and 5 in the table below confirm that both the
original Newton’s Method sequence and the accelerated seqeunce converge
Newton’s Method Aitken’s ∆2
npn|en|/|en−1|ˆpn|en|/|en−1|
1 0.646703997
3 0.282530441 0.6633 0.016328890
5. The sequence listed below was obtained from fixed point iteration applied to
the function g(x) = p10/(2 + x), which has a unique fixed point.
1 2.236067977
2 1.536450382
3 1.681574897
4 1.648098560
5 1.655643081
6 1.653933739
7 1.654320556
(a) Apply Aitken’s ∆2-method to the given sequence.
(b) To ten digits, the fixed point of gis x= 1.654249158. Use this to show
that both the original sequence and the output from Aitken’s ∆2-method
are linearly convergent and estimate the corresponding asymptotic error
constant. By how much has Aitken’s ∆2-method reduced the asymptotic
error constant?
(a) Using the first three terms in the fixed point iteration sequence, we calculate
Accelerating Convergence 5
Next, using p2,p3and p4, we calculate
(b) The values in columns 3 and 5 in the table below confirm that both the
Fixed Point Aitken’s ∆2
npn|en|/|en−1|pn|en|/|en−1|
5 1.655643081 0.2266 1.654255499 0.0511
7 1.654320556 0.2264 1.654249174 0.0502
6. Apply Steffensen’s method to the iteration function g(x) = 1
2√10 −x3using a
starting value of p0= 1. Perform four iterations, compute the absolute error in
each approximation and confirm quadratic convergence. To twenty digits, the
fixed point of gnearest x= 1 is x= 1.3652300134140968458.
6Section 2.6
nˆpn|en| |en|/|en−1|2
7. (a) Perform ten iterations to approximate the fixed point of g(x) = cos xus-
ing p0= 0. Verify that the sequence converges linearly and estimate the
asymptotic error constant. To 20 digits, the fixed point is
x= 0.73908513321516064166.
(b) Accelerate the convergence of the sequence obtained in part (a) using
Aitken’s ∆2-method. By how much has Aitken’s ∆2-method reduced the
asymptotic error constant?
(c) Apply Steffensen’s method to g(x) = cos xusing the same starting ap-
proximation specified in part (a). Perform four iterations, and verify that
convergence is quadratic.
(a) Let g(x) = cos xand take p0= 0. The sequence generated by fixed point
npn|en|/|en−1|
2 0.540302306 0.7619
4 0.654289790 0.7158
6 0.701368774 0.6934
8 0.722102425 0.6827
(b) Applying Aitken’s ∆2-method to the sequence obtained in part (a) produces
Accelerating Convergence 7
nˆpn|en|/|en−1|
3 0.728010361
6 0.738050421 0.4749
7 0.738636097 0.4340
(c) Let g(x) = cos xand take ˆp0= 0. Steffensen’s method produces the sequence
nˆpn|en|/|en−1|2
1 0.685073357326045
8. (a) Perform ten iterations to approximate the fixed point of g(x) = ln(4 +
x−x2) using p0= 2. Verify that the sequence converges linearly and
estimate the asymptotic error constant. To 20 digits, the fixed point is
x= 1.2886779668238684115.
(b) Accelerate the convergence of the sequence obtained in part (a) using
Aitken’s ∆2-method. By how much has Aitken’s ∆2-method reduced the
asymptotic error constant?
(c) Apply Steffensen’s method to g(x) = ln(4+x−x2) using the same starting
approximation specified in part (a). Perform four iterations, and verify
that convergence is quadratic.
(a) Let g(x) = ln(4 + x−x2)and take p0= 2. The sequence generated by fixed
npn|en|/|en−1|
1 0.6931471806
3 1.214902035 0.4937
5 1.275243786 0.4461
7 1.286155040 0.4369
8Section 2.6
(b) Applying Aitken’s ∆2-method to the sequence obtained in part (a) produces
nˆpn|en|/|en−1|
4 1.285796238 0.1291
6 1.288573331 0.1835
8 1.288674207 0.1881
(c) Let g(x) = ln(4 + x−x2)and take ˆp0= 2. Steffensen’s method produces the
nˆpn|en|/|en−1|2
1 1.16762958832039
9. (a) Perform ten iterations to approximate the fixed point of g(x) = (1.05 +
ln x)/1.04 using p0= 1. Verify that the sequence converges linearly and
estimate the asymptotic error constant. To 20 digits, the fixed point is
x= 1.1097123038867133005.
(b) Accelerate the convergence of the sequence obtained in part (a) using
Aitken’s ∆2-method. By how much has Aitken’s ∆2-method reduced the
asymptotic error constant?
(c) Apply Steffensen’s method to g(x) = (1.05 + ln x)/1.04 using the same
starting approximation specified in part (a). Perform five iterations, and
verify that convergence is quadratic.
(a) Let g(x) = (1.05 + ln x)/1.04 and take p0= 1. The sequence generated
by fixed point iteration is given in the second column below. The values
in the third column confirm the linear convergence of the sequence with an
asymptotic error constant of roughly 0.88.
Accelerating Convergence 9
npn|en|/|en−1|
2 1.018816780 0.9081
4 1.035738374 0.9002
6 1.050446990 0.8935
8 1.062861811 0.8878
(b) Applying Aitken’s ∆2-method to the sequence obtained in part (a) produces
nˆpn|en|/|en−1|
3 1.186794449
5 1.148195630 0.7137
7 1.130049871 0.7305
(c) Let g(x) = (1.05 + ln x)/1.04 and take ˆp0= 1. Steffensen’s method produces
nˆpn|en|/|en−1|2
2 1.12748779369567 1.3770
10. The function f(x) = 27x4+ 162x3−180x2+ 62x−7 has a zero of multiplicity
3 at x= 1/3. Apply both techniques for restoring quadratic convergence to
Newton’s method to this problem. Use p0= 0, and verify that both resulting
sequences converge quadratically.
Let f(x) = 27x4+ 162x3−180x2+ 62x−7. Then
10 Section 2.6
and
is used, while in “Approach #2,” the iteration function
Approach #1 Approach #2
npn|en|/|en−1|2pn|en|/|en−1|2
1 0.3277945619335347 0.0498 0.3387096774193548 0.0484
11. The function f(x) = x
1+x2−500
841 1−21x
125 has a zero of multiplicity 2 at x= 2.5.
Apply both techniques for restoring quadratic convergence to Newton’s method
to this problem. Use p0= 2, and verify that both resulting sequences converge
quadratically.
Let f(x) = x
1+x2−500
841 1−21x
125 . Then
Accelerating Convergence 11
Approach #1 Approach #2
npn|en|/|en−1|2pn|en|/|en−1|2
12. The function f(x) = x(1 −cos x) has a zero of multiplicity 3 at x= 0. Apply
both techniques for restoring quadratic convergence to Newton’s method to this
problem, using p0= 1. You should observe that the resulting sequences appear
to converge faster than quadratically. What apparent order of convergence do
you observe? Why is convergence faster than quadratic for this problem?
is used, while in “Approach #2,” the iteration function
is used. To explore the order of convergence fully, the values below were obtained
using Maple with the Digits parameter set to 100.
Approach #1 Approach #2
npnpn
21.4229 ×10−41.1936 ×10−5
43.6447 ×10−39 4.6843 ×10−50
13. Suppose Newton’s method is applied to a function with a zero of multiplicity
m > 1. Show that the multiplicity of the zero can be estimated as the integer
nearest to
m≈1
1−pn−pn−1
pn−1−pn−2
.
Verify that this formula produces an accurate estimate when applied to the
sequence listed in Exercise 4 and when applied to the sequence generated when
Newton’s method was applied to the function f(x) = 1 + ln x−xin the text.
12 Section 2.6
It was established in Section 2.5 that when Newton’s method is applied to a func-
Then, in this section, it was established that for linearly convergent sequences, the
asymptotic error constant can be approximated by
For the sequence in Exercise 4 and the sequence in worked Example 2.16, the
produces a very accurate estimate.
x(1 −cos x)1 + ln x−x
npnmˆpnm
2 0.425971211 1.172192189
4 0.187933565 2.9367 1.039705144 1.8570
6 0.083407519 2.9876 1.009734085 1.9621
14. Each of the following functions has a zero of multiplicity greater than one at
the specified location. In each case, apply the secant method to the function
f(x)/f′(x) to approximate the indicated zero. Has the order of convergence
been restored to α≈1.618?
(a) f(x) = 1 + ln x−xhas a zero at x= 1 – use p0=−1 and p1= 2
(b) f(x) = 27x4+ 162x3−180x2+ 62x−7 has a zero at x= 1/3
(c) f(x) = x
1+x2−500
841 1−21x
125 has a zero at x= 2.5
Accelerating Convergence 13
(a) Let f(x) = 1 + ln x−x. Then f′(x) = x−1−1. Applying the secant method
npn|en| |en|/|en−1|1.618
2 0.859075117368965 1.4092 ×10−1
(b) Let f(x) = 27x4+ 162x3−180x2+ 62x−7. Then f′(x) = 108x3+ 486x2−
360x+ 62. Applying the secant method to the function
with p0= 0 and p1= 1 yields the results summarized in the table below.
Here, convergence appears to be erratic, likely due to roundoff error.
npn|en| |en|/|en−1|1.618
4 0.333333452237016 1.1890 ×10−70.0709
(c) Let f(x) = x
1+x2−500
841 1−21x
125 . Then
Applying the secant method to the function
with p0= 2 and p1= 3 yields the results summarized in the table below.
improvement in the approximation to the root.
npn|en| |en|/|en−1|1.618
3 2.500077686554038 7.7687 ×10−51.0647
5 2.500000004821072 4.8211 ×10−9
14 Section 2.6
15. Repeat Exercise 14, but this time replace the standard secant method formula
for pn+1 by the formula
pn+1 =pn−mf(pn)pn−pn−1
f(pn)−f(pn−1),
where mis the multiplicity of the zero being approximated. The functions in
(a) and (c) have m= 2, and the function in (b) has m= 3.
Let f(x) = 1 + ln x−x. As x= 1 is a root of f(x)of multiplicity 2, we attempt
the iteration function
16. The method of false position and fixed point iteration generate linearly conver-
gent sequences for which
lim
n→∞
pn−p
pn−1−p(1)
exists. Note that this limit does not involve absolute values. Let λdenote
the value of this limit. This exercise will lead us through the proof that the
sequence produced by Aitken’s ∆2-method converges more rapidly than linearly
convergent sequences for which (6) exists.
(a) Let
ǫn=pn−p
pn−1−p−λ.
Show that ǫn→0 as n→ ∞.
(b) Show that
∆pn= (pn−p)1−1
ǫn+λ.
(c) Show that
∆2pn= (pn−p)1−1
ǫn+λ−1
ǫn+λ1−1
ǫn−1+λ
=pn−p
(ǫn+λ)(ǫn−1+λ)(λ−1)2+ǫ′
n,
Accelerating Convergence 15
where ǫ′
n=ǫnǫn−1+λ(ǫn+ǫn−1)−2ǫn−1. Further, show that ǫ′
n→0 as
n→ ∞.
(d) Show that
ˆpn−p
pn−p= 1 −ǫn−1+λ
ǫn+λ·(ǫn+λ−1)2
(λ−1)2+ǫ′
n
;
hence, as n→ ∞,ˆpn−p
pn−p→0.
(a) Let
(b) Solving the equation that defines ǫnfor pn−1−pyields
(c)
∆2pn= ∆pn−∆pn−1
16 Section 2.6
(d) Using the definition of ˆpnand the results from parts (a) and (b),