CH02 PDF

Chapter 2
Solutions of Equations in One

Variable
Hung-Yuan Fan (范洪源)
Department of Mathematics,
National Taiwan Normal University, Taiwan
Spring 2016
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Hung-Yuan Fan (范洪源), Dep. of Math., NTNU, Taiwan Chap . 2, Numerical Analysis (I) 1/108
Section 2.1
The Bisection Method
(二分法)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Solutions of Nonlinear Equations
Root-Finding Problem (勘根問題)

One of the most basic problems in numerical analysis.
Try to find a root (or solution) p of a nonlinear equation of
the form
f(x) = 0,
given a real-valued function f, i.e. f(p) = 0.
The root p is also called a zero (零根) of f.
Note: Three numerical methods will be discussed here:

Bisection method
Newton’s (or Newton-Raphson) method
Secant and False Position (or Regula Falsi) methods
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
The Procedure of Bisection Method
Assume that f is well-defined on the interval [a, b].

Set a1 = a and b1 = b. Find the midpoint p1 of [a1 , b1 ] by
b1 − a1 a 1 + b1
p1 = a 1 + = .
2 2
If f(p1 ) = 0, set p = p1 and we are done.
If f(p1 ) ̸= 0, then we have
f(p1 ) · f(a1 ) > 0 ⇒ p ∈ (p1 , b1 ). Set a2 = p1 and b2 = b1 .
f(p1 ) · f(a1 ) < 0 ⇒ p ∈ (a1 , p1 ). Set a2 = a1 and b2 = p1 .
Continue above process until convergence.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Illustrative Diagram of Bisection Method
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode of Bisection Method
Given f ∈ C[a, b] with f(a) · f(b) < 0 .

Algorithm 2.1: Bisection
INPUT endpoints a, b; tolerance TOL; max. no. of iter. N0 .
OUTPUT an approx. sol. p.
Step 1 Set i = 1 and FA = f(a);
Step 2 While i ≤ N0 do Steps 3–6
Step 3 Set p = a + (b − a)/2; FP = f(p).
Step 4 If FP = 0 or (b − a)/2 < TOL then OUTPUT(p); STOP.
Step 5 Set i = i + 1.
Step 6 If FP · FA > 0 then set a = p and FA = FP.
Else set b = p. (FA is unchanged)
Step 7 OUTPUT(‘Method failed after N0 iterations’) and STOP.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Stopping Criteria (停止準則)
In Step 4, other stopping criteria can be used. Let ϵ > 0 be a given
tolerance and p1 , p2 , . . . , pN be generated by Bisection method.
(1) |pN − pN−1 | < ϵ,
|pN −pN−1 |
(2) |pN | < ϵ with pN ̸= 0,
(3) |f(pN )| < ϵ.
Note: The stopping criterion (2) is preferred in practice.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
An Example for Bisection Method
Example 1, p. 50
(1) Show that the equation
f(x) = x3 + 4x2 − 10 = 0
has exactly one root in [1, 2].

(2) Use Bisection method to determine an approx. root which is
accurate to at least within 10−4 .
The root is p = 1.365230013 correct to 9 decimal places.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Solution
(1) By IVT with f(1)f(2) = (−5)(14) < 0, ∃ p ∈ (1, 2) s.t.
f(p) = 0. Since f ′ (x) = 3x2 + 8x > 0 for x ∈ (1, 2), the root
must be unique in [1, 2].
(2) After 13 iterations, since |a14 | < |p|, we have
|p − p13 | |b14 − a14 |

≤ ≤ 9.0 × 10−5 .
|p| |a14 |
Note that
|f(p9 )| < |f(p13 )|
in the Table 2.1.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Numerical Results for Example 1
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Convergence of the Bisection Method
Thm 2.1 (二分法的收斂定理)

Suppose that f ∈ C[a, b] with f(a) · f(b) < 0. The Bisection method
generates a sequence {pn }∞
n=1 converging to a root p of f with
b−a
|p − pn | ≤ ∀ n ≥ 1.
2n
The rate of convergence is O( 21n ).
pf: For each n ≥ 1, p ∈ (an , bn ) and
b−a
bn − an = by induction.
2n−1
Hence, we hve
bn − a n b−a
|p − pn | ≤ = .
2 2n
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Is the error bound tight?
Remark
Applying Thm 2.1 to Example 1, we see that
2−1
|p − p9 | ≤ ≈ 2 × 10−3 ,
29
but the actual absolute value is |p − p9 | ≈ 4.4 × 10−6 . In this case,
the error bound in Thm 2.1 is much larger than the actual error.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 2, p. 52
As in Example 1, use Thm 2.1 to estimate the smallest number N
of iterations so that |p − pN | < 10−3 .
Sol: Applying Thm 2.1, it follows that

2−1
|p − pN | ≤ < 10−3 ⇐⇒ 2−N < 10−3 ,
2N
or, equivalently, (−N) log10 2 < −3 ⇐⇒ N > log3 2 ≈ 9.96. So,
10
10 iterations will ensure the required accuracy. But, in fact, we
know that
|p − p9 | ≈ 4.4 × 10−6 .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Useful Suggestions for the Bisection Method
In Practical Computation...
To avoid the round-off errors in the computations, use
bn − a n a n + bn
pn = an + instead of pn = .
2 2
To avoid the overflow or underflow of f(pn ) · f(an ), use
sign(f(pn )) · sign(f(an )) < 0 instead of f(pn ) · f(an ) < 0.
Note: The sign function is defined by


 1 if x > 0,
sign(x) = 0 if x = 0,

−1 if x < 0.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Section 2.2
Fixed-Point Iteration
(固定點迭代)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Def 2.2
The number p is called a fixed point (固定點) of a real-valued
function g if g(p) = p.
Note: A root-finding problem of the form
f(p) = 0,
where p is a root of f, can be transformed to a fixed-point form
p = g(p),
for some suitable function g obtained by algebraic transposition.

(函數 g(x) 經由原函數 f(x) 代數移項可得)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Existence & Uniqueness of Fixed Points
Thm 2.3 (固定點的存在性與唯一性)

(i) If g ∈ C[a, b] and g([a, b]) ⊆ [a, b], then g has at least one
fixed point in [a, b].
(ii) If, in addition, g′ (x) exists on (a, b) and ∃ 0 < k < 1 s.t.
|g′ (x)| ≤ k ∀ x ∈ (a, b),
then there is exactly one fixed point in [a, b].
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Illustrative Diagram for Fixed Points
Geometrically, a fixed point p ∈ [a, b] is just the point where the

curves y = g(x) and y = x intersect.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Proof of Thm 2.3
(i) If g(a) = a or g(b) = b, we are done. If not, then g(a) > a
and g(b) < b, since g([a, b]) ⊆ [a, b]. Note that the function
h(x) = g(x) − x ∈ C[a, b] and
h(a) = g(a) − a > 0, h(b) = g(b) − b < 0.
By IVT, ∃ p ∈ (a, b) s.t. h(p) = 0 or g(p) = p.

(ii) Suppose that ∃ p ̸= q ∈ [a, b] s.t. g(p) = p and g(q) = q . By
MVT, ∃ ξ between p and q s.t.
|p − q| = |g(p) − g(q)| = |g′ (ξ)||p − q|

≤ k|p − q|< |p − q|,
which is a contradiction! Hence, g must have a unique fixed

point in [a, b].
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 3: Condition (ii) Is NOT Satisfied (1/2)
Example 3, p. 59
Although the sufficient conditions are NOT satisfied for g(x) = 3−x
on the interval [0, 1], there does exist a unique fixed point of g in
[0, 1].
Sol: Since g′ (x) = −3−x ln 3 < 0 ∀ x ∈ [0, 1], g is strictly

decreasing on [0, 1] and hence
1
= g(1) ≤ g(x) ≤ g(0) = 1 ∀ x ∈ [0, 1],
3
i.e. g ∈ C[0, 1] and g([0, 1]) ⊆ [0, 1].
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 3: Condition (ii) Is NOT Satisfied (2/2)
But also note that
g′ (0) = − ln 3 ≈ −1.0986,
thus |g′ (x)| ≮ 1 on (0, 1) and condition (ii) of Thm 2.3 is not
satisfied. Because g is strictly deceasing on [0, 1], its graph must
intersect the graph of y = x at exactly one fixed point p ∈ (0, 1).
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Fixed-Point Iteration (固定點迭代)
Functional (or Fixed-Point) Iteration

Assume that g ∈ C[a, b] and g([a, b]) ⊆ [a, b]. The fixed-point
iteration generates a sequence {pn }∞
n=1 , with p0 ∈ [a, b], defined by
pn = g(pn−1 ) ∀ n ≥ 1.
This method is also called the functional iteration. (泛函迭代)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Illustrative Diagrams
Starting wirh p0 ∈ [a, b], we obtain a sequence of points
(p0 , p1 ) → (p1 , p1 ) → (p1 , p2 ) → (p2 , p2 ) → (p2 , p3 ) → · · · (p, p),
where p = g(p).
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode of Functional Iteration
To find a sol. p to x = g(x) given an initial approx. p0 .

Algorithm 2.2: Fixed-Point Iteration
INPUT initial approx. p0 ; tolerance TOL; max. no. of iter. N0 .
OUTPUT approx. sol. p to x = g(x).
Step 1 Set i = 1.
Step 3 Set p = g(p0 ).
Step 4 If |p − p0 | < TOL then OUTPUT(p); STOP.
Step 6 Set p0 = p. (Update p0 )
Step 7 OUTPUT(‘Method failed after N0 iterations’); STOP.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
An Illustrative Example
5 Possible Fixed-Point Forms

The root-finding problem
f(x) = x3 + 4x2 − 10 = 0
can be transformed to the following 5 fixed-point forms:

10
(a) x = g1 (x) = x − x3 − 4x2 + 10 (b) x = g2 (x) = ( − 4x)1/2
x
1 10 1/2
(c) x = g3 (x) = (10 − x3 )1/2 (d) x = g4 (x) = ( )
2 4+x
x3 + 4x2 − 10
(e) x = g5 (x) = x −
3x2 + 8x
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Numerical Results with p0 = 1.5
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Some Questions
Under what conditions does the fixed-point iteration (FPI)
pn = g(pn−1 ), n = 1, 2, . . .
converge for any p0 ∈ [a, b]?

What is the error bound for the FPI?
In addition, what is the rate of convergence?
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Convergence of Functional Iteration
Thm 2.4 (Fixed-Point Thm)

Suppose that g ∈ C[a, b] and g([a, b]) ⊆ [a, b]. If g′ (x) exists on
(a, b) and ∃ k ∈ (0, 1) s.t.
|g′ (x)| ≤ k ∀ x ∈ (a, b),
then for any p0 ∈ [a, b], the sequence {pn }∞

n=1 defined by
pn = g(pn−1 ) ∀ n ≥ 1,
converges to the unique fixed point p ∈ [a, b] of g.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Proof of Thm 2.4
Thm 2.3 ensure that ∃! p ∈ [a, b] s.t. g(p) = p.

For each n ≥ 1, it follows from MVT that ∃ ξn between pn−1
and p s.t.
|pn − p| = |g(pn−1 ) − g(p)| = |g′ (ξn )||pn−1 − p| ≤ k|pn−1 − p|.
By induction =⇒ |pn − p| ≤ kn |p0 − p| for n ≥ 0.

Since 0 < k < 1, we see that
lim |pn − p| = 0 ⇐⇒ lim pn = p

n→∞ n→∞
by the Sandwich Thm.
[Q]: What is the order of convergence for the FPI?

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Error Bounds for Fixed-Point Iteration
Cor 2.5 (固定點迭代的誤差上界)
If g satisfies the hypotheses of Thm 2.4, then we have
(1) |pn − p| ≤ kn max{p0 − a, b − p0 } ∀ n ≥ 0,
n
(2) |pn − p| ≤ k |p − p | ∀ n ≥ 1.
1−k 1 0
pf: Inequality (1) followss immediately from the proof of Thm 2.4.
For m > n ≥ 1, by MVT inductively, we obtain
|pm − pn | ≤ |pm − pm−1 | + |pm−1 − pm−2 | + · · · + |pn+1 − pn |
≤ km−1 |p1 − p0 | + km−2 |p1 − p0 | + · · · + kn |p1 − p0 |
= kn (1 + k + k2 + · · · + km−n−1 ) · |p1 − p0 |.
Hence, by taking m → ∞, we have
(∑
∞ ) kn
|p − pn | = lim |pm − pn | ≤ kn ki |p1 − p0 | = |p1 − p0 |.
m→∞ 1−k
i=0 . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Rate of Conv. for Functional Iter.
Remarks
The rate of convergence for the fixed-point iteration depends
kn
on kn or 1−k .
The smaller the value of k, the faster the convergence.
The convergence would be very slow if k ≈ 1.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
The Illustrative Example Revisited
5 Possible Fixed-Point Forms

The root-finding problem
f(x) = x3 + 4x2 − 10 = 0
can be transformed to the following 5 fixed-point forms:

10
(a) x = g1 (x) = x − x3 − 4x2 + 10 (b) x = g2 (x) = ( − 4x)1/2
x
1 10 1/2
(c) x = g3 (x) = (10 − x3 )1/2 (d) x = g4 (x) = ( )
2 4+x
x3 + 4x2 − 10
(e) x = g5 (x) = x −
3x2 + 8x
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Illustration
(a) g1 ([1, 2]) * [1, 2] and |g′1 (x)| > 1 for x ∈ [1, 2].
(b) g2 ([1, 2]) * [1, 2] and |g′2 (x)| ≮ 1 for any interval containing
p ≈ 1.36523, since |g′2 (p)| ≈ 3.4.
(c) Since p0 = 1.5, 1 < 1.28 ≈ g3 (1.5) ≤ g3 (x) ≤ g3 (1) = 1.5

and hence g3 ([1, 1.5]) ⊆ [1, 1.5]. We also note that g′3
satisfies |g′3 (x)| ≤ |g′3 (1.5)| ≈ 0.66 for x ∈ [1, 1.5].
(d) g4 ([1, 2]) ⊆ [1, 2] and the derivative g′4 satisfies

−5
5
|g′4 (x)| = √ < √ ≈ 0.1414.
10(4 + x) 3/2 10(5)3/2
(e) It is Newton’s method satisfying g′5 (p) = 0 theoretically!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Section 2.3
Newton’s Method and Its Extensions
(牛頓法及其推廣)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Derivation of Newton’s Method
Suppose that f(p) = 0, f ′ (p) ̸= 0 and f ∈ C2 [a, b].
Given an initial approximation p0 ∈ [a, b] with f ′ (p0 ) ̸= 0 s.t.
|p − p0 | is sufficiently small.
By Taylor’s Thm, ∃ ξ(p) between p and p0 s.t.
f ′′ (ξ(p))
0 = f(p) = f(p0 ) + f ′ (p0 )(p − p0 ) + (p − p0 )2 .
2
Since |p − p0 | is sufficiently small, it follows that
f(p0 )
0 ≈ f(p0 ) + f ′ (p0 )(p − p0 ) ⇐⇒ p ≈ p0 − .
f ′ (p0 )
This suggests the procedure of Newton’s method:
f(pn−1 )
pn = pn−1 − ∀ n ≥ 1.
f ′ (pn−1 )
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Newton’s Method v.s. Functional Iteration
Observations
Let g be a real-valued function defined by
f(x)
g(x) = x − , x ∈ [a, b],
f ′ (x)
Newton’s method can be viewed as a fixed-point iteration
pn = g(pn−1 ) ∀ n ≥ 1, where |p0 − p| is sufficiently small.
If f(p) = 0, g(p) = p, i.e., p is a fixed-point of g.
g ∈ C[a, b] and its first derivative is given by
f(x)f ′′ (x)
g′ (x) = , x ∈ [a, b].
[f ′ (x)]2
If f(p) = 0, then g′ (p) = 0 follows immediately.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Further Questions
Under what conditions does Newton’s method converge to p?
What is the error bond for Newton’s method?
How to choose a good initial guess p0 ?
What is the rate of convergence for Newton’s method?
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode of Newton’s Method
To find a sol. to f(x) = 0 given an initial approx. p0 .

Algorithm 2.3: Newton’s Method
OUTPUT approx. sol. p to f(x) = 0.
Step 1 Set i = 1.
Step 3 Set p = p0 − f(p0 )/f ′ (p0 ).
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 1, p. 69
Use (a) fixed-point iteration and (b) Newton’s method to find an
approximate root p of the nonlinear equation
f(x) = cos x − x = 0
with initial guess p0 = π4 . The root is p ≈ 0.739085133215161.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Solution (1/3)
(a) Consider the fixed-point form x = g(x), where

π
g(x) = cos(x) ∀ x ∈ [0, ].
2
Then it is easily seen that
1 g ∈ C[0, π2 ],
2 g([0, π2 ]) ⊆ [0, 1] ⊆ [0, π2 ],
3 |g′ (x)| = | − sin(x)| < 1 ∀ x ∈ (0, π2 ).
From Thm 2.4 =⇒ the fixed-point iteration
pn = g(pn−1 ) = cos(pn−1 ) ∀ n ≥ 1
must converge to the unique fixed point p ∈ (0, π2 ) of g for

any initial p0 ∈ [0, π2 ]!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Solution (2/3)
Applying the FPI with an initial guess p0 = π4 , we obtain the

following numerical results.
The root is p ≈ 0.739085133215161.

Note that only 2 significant digits!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Solution (3/3)
(b) For the same initial approx. p0 = π/4, applying Newton’s

method
cos(pn−1 ) − pn−1
pn = pn−1 − ∀ n ≥ 1,
− sin(pn−1 ) − 1
The actual root is p ≈ 0.739085133215161.
we obtain the following numerical results
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Convergence Thm for Newton’s Method
Thm 2.6 (牛頓法的收斂定理)

Let f ∈ C2 [a, b] and p ∈ (a, b). If f(p) = 0 and f ′ (p) ̸= 0, then
∃ δ > 0 s.t. Newton’s method generates a sequence {pn }∞ n=1
defined by
f(pn−1 )
pn = pn−1 − ′ ∀n ≥ 1
f (pn−1 )
converging to p for any p0 ∈ [p − δ, p + δ].
Note: The local convergence of Newton’s method is guaranteed

in Thm 2.6, but the order of convergence is NOT discussed here!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Sketch of Proof (1/2)
Since f ′ (p) ̸= 0, ∃ δ1 > 0 s.t.
f ′ (x) ̸= 0 ∀ x ∈ (p − δ1 , p + δ1 ),
and hence
f(x)
g(x) = x −
f ′ (x)
is well-defined on (p − δ1 , p + δ1 ).
Moreover, since its derivative is given by
f(x)f ′′ (x)
g′ (x) = ∀ x ∈ (p − δ1 , p + δ1 ),
[f ′ (x)]2
it follows that g ∈ C1 (p − δ1 , p + δ1 ) because f ∈ C2 [a, b].

Note that f(p) = 0 =⇒ g(p) = p and g′ (p) = 0.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Sketch of Proof (2/2)
Because g′ is conti. at p, for any k ∈ (0, 1), ∃ 0 < δ < δ1 s.t.
|g′ (x)| < k ∀ x ∈ [p − δ, p + δ].
For x ∈ [p − δ, p + δ], from MVT ⇒ ∃ ξ between x and p s.t.
|g(x) − p| = |g(x) − g(p)| = |g′ (ξ)| |x − p| < δ.
Hence, g([p − δ, p + δ]) ⊆ [p − δ, p + δ].

From Thm 2.4 =⇒ the seq. generated by Newton’s method
pn = g(pn−1 ) ∀ n ≥ 1
converges to p for any p0 ∈ [p − δ, p + δ].
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Questions
How to guess a good initial approximation p0 ?
How to estimate δ > 0 derived in Thm 2.6?
What is the order of convergence for Newton’s method?
How to modify Newton’s method if f ′ (x) is difficult to be
evaluated in practice? Use Secant Method!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Derivation of Secant Method (割線法)
In many applications, it is often difficult to evaluate the

derivative of f.
f(x)−f(pn−1 )
Since f ′ (pn−1 ) = lim x−pn−1 , we have
x→pn−1
f(pn−2 ) − f(pn−1 ) f(pn−1 ) − f(pn−2 )

f ′ (pn−1 ) ≈ =
pn−2 − pn−1 pn−1 − pn−2
for any n ≥ 2.
With above spprox. for the derivative, Neton’s method is
rewritten as
f(pn−1 )(pn−1 − pn−2 )
pn = pn−1 − ∀ n ≥ 2.
f(pn−1 ) − f(pn−2 )
This is called the Secant method with initial approximations

p0 and p1 .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Illustrative Diagram for Secant Method
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Key Steps of Secant Method
Given two initial p0 and p1 with q0 ← f(p0 ) and q1 ← f(p1 ), the
followings are performed repeatedly in the Secant method:
1 Compute the new approximation
q1 (p1 − p0 )
p ← p1 − ;
q1 − q0
2 Update p0 ← p1 and q0 ← q1 ; p1 ← p and q1 ← f(p).
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode of Secant Method
To find a sol. to f(x) = 0 given initial approx. p0 and p1 .

Algorithm 2.4: Secant Method
INPUT initial approx. p0 , p1 ; tolerance TOL; max. no. of iter. N0 .
Step 1 Set i = 2; q0 = f(p0 ); q1 = f(p1 ).
Step 3 Set p = p1 − q1 (p1 − p0 )/(q1 − q0 ).
Step 6 Set p0 = p1 ; q0 = q1 ;
p1 = p ; q1 = f(p).
Step 7. OUTPUT(‘Method failed after N0 iterations’); STOP.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 2, p. 72
Use the Secant method to find a sol. to
f(x) = cos x − x = 0
with initial approx. p0 = 0.5 and p1 = π/4. Compare the results

with those of Newton’s method obtained in Example 1.
Sol: Applying the Secant method
(cos pn−1 − pn−1 )(pn−1 − pn−2 )

pn = pn−1 − ∀ n ≥ 2,
(cos pn−1 − pn−1 ) − (cos pn−2 − pn−2 )
we see that its approximation p5 is accurate to 10 significant

digits, whereas Newton’s method produced the same accuracy
after 3 iterations.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Numerical Results for Example 2
The Secant method is much faster than fixed-point iteration,

but slower than Newton’s method.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Method of False Position (錯位法)
The method of False Position is also called Regula Falsi

method. The root is always bracketed between successive
approximations.
Firstly, find p2 using the Secant method . How to determine

the next approx. p3 ?
If f(p2 ) · f(p1 ) < 0 (or sign(f(p2 )) · sign(f(p1 )) < 0), then p3

is the x-intercept of the line joining (p1 , f(p1 )) and
(p2 , f(p2 )).
If not, p3 is the x-intercept of the line joining (p0 , f(p0 )) and

(p2 , f(p2 )), and then interchange the indices on p0 and p1 .
Continue above procedure until convergence.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Secant Method v.s. Method of False Position
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Key Steps of False Position Method
Given two initial p0 and p1 with q0 ← f(p0 ) and q1 ← f(p1 ), the
followings are performed repeatedly in the False Position method:
1 Compute the new approximation
q1 (p1 − p0 )
p ← p1 − ;
q1 − q0
2 Compute q ← f(p);
3 If q · q1 < 0, update p0 ← p1 and q0 ← q1 ;
4 Update p1 ← p and q1 ← q.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode for Method of False Position
To find a sol. to f(x) = 0 given initial approx. p0 and p1 .

Algorithm 2.5: Method of False Position
INPUT initial approx. p0 , p1 ; tolerance TOL; max. no. of iter. N0 .
Step 1 Set i = 2; q0 = f(p0 ); q1 = f(p1 ).
Step 3 Set p = p1 − q1 (p1 − p0 )/(q1 − q0 ).
Step 5 Set i = i + 1; q = f(p).
Step 6 If q · q1 < 0 then p0 = p1 ; q0 = q1 .
Step 7 Set p1 = p; q1 = q.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 3, p. 74
Use the method of False Position to find a sol. to
f(x) = cos x − x = 0
with p0 = 0.5 and p1 = π/4. Compare the results with those

obtained by Newton’s method and Secant method.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Section 2.4
Error Analysis for Iterative Methods
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Order of Convergence (收斂階數)
Def 2.7 (收斂階數的定義)

A sequence {pn }∞n=0 converges to p of order α, with asymptotic
error constant λ if ∃ α ≥ 1 and λ ≥ 0 with
|pn+1 − p|
lim = λ.
n→∞ |pn − p|α
(i) α = 1 and 0 < λ < 1 =⇒ {pn }∞

n=0 is linearly convergent.
(ii) α = 1 and λ = 0 =⇒ {pn }∞
n=0 is superlinearly convergent.
(iii) α = 2 =⇒ {pn }∞
n=0 is quadratically convergent.
Note: The higher-order convergence is always expected in

practical computation!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Linear Convergence of Functional Iteration
Thm 2.8 (固定點迭代的線性收斂性)

Suppose that g ∈ C[a, b] and g([a, b]) ⊆ [a, b]. If g′ ∈ C(a, b),
∃ k ∈ (0, 1) s.t. |g′ (x)| ≤ k ∀ x ∈ (a, b) and g′ (p) ̸= 0, then for
any p0 ∈ [a, b], the sequence
pn = g(pn−1 ) ∀ n ≥ 1
converges only linearly to the unique fixed point p ∈ [a, b].
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Proof of Thm 2.8
Thm 2.4 (Fixed-Point Thm) ensures that the sequence pn
converges to the unique fixed point p ∈ [a, b].
For each n ≥ 1, by MVT =⇒ ∃ ξn between pn and p s.t.
|pn+1 − p| = |g(pn ) − g(p)| = |g′ (ξn )||pn − p|.
Since lim pn = p, ξn → p as n → ∞. Thus,

n→∞
|pn+1 − p|
lim = lim |g′ (ξn )| = |g′ (p)| > 0
n→∞ |pn − p| n→∞
because g′ ∈ C(a, b), i.e., the sequence pn converges to p only

linearly!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Quadratic Convergence of Functional Iteration
Thm 2.9 (固定點迭代的二次收斂性)

If g(p) = p, g′ (p) = 0 and ∃ open interval I containing p where
g′′ ∈ C(I) and |g′′ (x)| < M ∀ x ∈ I,
then ∃ δ > 0 s.t. the sequence defined by
pn = g(pn−1 ) ∀ n ≥ 1
converges at least quadratically to p for any p0 ∈ [p − δ, p + δ].

Moreover, we have
M
|pn+1 − p| < |pn − p|2 for sufficiently large values of n.
2
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Sketch of the Proof
For any k ∈ (0, 1), since lim g′ (x) = g′ (p) = 0, ∃ δ > 0 s.t.
x→p
|g′ (x)| ≤ k < 1 ∀ x ∈ [p − δ, p + δ] ⊆ I. (1)
From (1) and MVT ⇒ |pn − p| < δ ∀ n ∈ N if |p0 − p| < δ,

and g([p − δ, p + δ]) ⊆ [p − δ, p + δ]. Hence, lim pn = p by
n→∞
Fixed-Point Thm (Thm 2.4).
For n ≥ 1, from Taylor’s Thm ⇒ ∃ ξn between pn and p s.t.
g′′ (ξn )
pn+1 − p = g(pn ) − g(p) = (pn − p)2 .
2
|pn+1 −p| |g′′ (p)|
Taking | · | and n → ∞ ⇒ lim = 2 . (∵ ξn → p)
n→∞ |pn −p|
2
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Quadratic Convergence for Newton’s Method
Corollary (牛頓法的二次收斂性)
Let f(p) = 0, f ′ (p) ̸= 0 and define the real-valued function
f(x)
g(x) = x − ∀ x ∈ I,
f ′ (x)
where I is an open interval containing p. If g′′ ∈ C(I) with

|g′′ (x)| < M ∀ x ∈ I, then ∃ δ > 0 s.t. Newton’s method generates
a sequence {pn }∞n=0 converging at least quadratically to p for any
|g′′ (p)|
p0 ∈ [p − δ, p + δ]. The asymptotic error constant is λ = 2 .
(當初始值 p0 充分接近零根 p, 牛頓法是一個二次收斂的算法!)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Multiple Roots (重根)
Def 2.10 (零根的重數)

A number p is called a zero of multiplicity m ∈ N (重數) of f
if for any x ̸= p, we can write
f(x) = (x − p)m q(x) with lim q(x) ̸= 0.

x→p
Note: A root p of f is called simple (單根) if it is a zero of

multiplicity one, i.e., m = 1.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Thm 2.11 (單根的充分必要條件)
f ∈ C1 [a, b] has a simple zero at p ∈ (a, b) ⇐⇒ f(p) = 0, but
f ′ (p) ̸= 0.
Proof (1/2)
(=⇒) If f has a simple zero at p, then f(x) = (x − p)q(x) for
x ∈ [a, b]\{p}. So, f(p) = 0 and we also see that
f ′ (p) = lim f ′ (x) = lim [q(x) + (x − p)q′ (x)] = lim q(x) ̸= 0,

x→p x→p x→p
since f ∈ C1 [a, b].
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Proof (2/2)
(⇐=) Suppose that f ∈ C1 [a, b] with f(p) = 0 and f ′ (p) ̸= 0 for
some p ∈ (a, b).
From Taylor’s Thm =⇒ for any x ∈ [a, b]\{p}, ∃ ξ(x) between
x and p s.t.
f(x) = f(p) + f ′ (ξ(x))(x − p) = (x − p)q(x),
where q(x) ≡ (f ′ ◦ ξ)(x) = f ′ (ξ(x)) for x ∈ [a, b]\{p}.

Because ξ(x) → p as x → p and f ′ is continuous at p,
( )
lim q(x) = lim f ′ (ξ(x)) = f ′ lim ξ(x) = f ′ (p) ̸= 0.
x→p x→p x→p
Hence, f must have a simple zero at p by Def.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Thm 2.12 (重根的充分必要條件)
f ∈ Cm [a, b] has a zero of multiplicity m at p ∈ (a, b)
⇐⇒ f(p) = f ′ (p) = f ′′ (p) = · · · f(m−1) (p) = 0, but f(m) (p) ̸= 0.
Homework: do Exercise 12 for the proof.
Note: In practice, Newton’s method usually converges linearly to

a zero p of multiplicity m ≥ 2, even though an initial guess p0 is
chosen close to p.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Linear Conv. of Newton’s Method for m = 2
Example 1, p. 83
Consider f(x) = ex − x − 1 = 0 for all x ∈ R.
(a) Show that f has a zrero of multiplicity 2 at p = 0.
(b) Use Newton’s method to compute an approximation to p with
p0 = 1.
Sol:
(a) Since
f(0) = e0 − 0 − 1 = 0, f ′ (0) = e0 − 1 = 0, f ′′ (0) = e0 = 1 ̸= 0,
it follows that p = 0 is a zero of multiplicity 2 by Thm 2.12.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Numerical Results with p0 = 1
(b) The following table shows the linear convergence of

Newton’s method when a multiple zero occurs:
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Improvement of Convergence (1/2)
f(x)
Suppose that f ∈ Cm [a, b] and consider µ(x) = .
f ′ (x)
If f has a zero of multiplicity m(≥ 2) at p, then
f(x) = (x − p)m q(x) and hence
(x − p)m q(x)
µ(x) =
m(x − p)m−1 q(x) + (x − p)m q′ (x)
q(x)
= (x − p) ≡ (x − p)q̂(x).
mq(x) + (x − p)q′ (x)
1
Since q(p) ̸= 0, µ(p) = 0 and lim q̂(x) = m ̸= 0. So, µ(x)
x→p
has a simple zero at p.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Improvement of Convergence (2/2)
Applying Newton’s method for solving the problem µ(x) = 0,

we obtain
µ(x) f(x)f ′ (x)
g(x) =x − = x − . (Check!)
µ′ (x) [f ′ (x)]2 − f(x)f ′′ (x)
Modified Newton’s Method: (修正的牛頓法)
f(pn−1 )f ′ (pn−1 )
pn = pn−1 −
[f ′ (pn−1 )]2 − f(pn−1 )f ′′ (pn−1 )
for all n ≥ 1.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 2, p. 84
Use the Modified Newton’s method for solving the multiple root
x = 0 of f(x) = ex − x − 1 with p0 = 1.
A system with 10 digits of precision is used in this case.
Both the numerator and the denominator approach 0 ⇒
Loss of Significant Digits!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
The Convergence Order of Secant Method
Exercise 14, p. 86 (補充題)

It is shown from pp. 228–229 of [DaB] that if f(p) = 0 and the
sequence {pn }∞n=0 generated by Secant Method converges to p,
then ∃ C > 0 s.t.
|pn+1 − p| ≈ C|pn − p||pn−1 − p|
for sufficiently large values of n. Apply this fact to prove the order
of convergence for Secant Method is
√
1+ 5
α= ≈ 1.62. (golden ratio; 黃金比率)
2
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Proof of Exercise 14
Let en = pn − p for n ≥ 0. If pn → p of order α, then ∃ λ > 0 s.t.
|pn+1 − p| |en+1 |
lim = lim = λ > 0.
n→∞ |pn − p|α n→∞ |en |α
Then for sufficiently large values of n, |en+1 | ≈ λ|en |α . Thus,
|en | ≈ λ|en−1 |α or |en−1 | ≈ λ−1/α |en |1/α .
Using the hypothesis gives
λ|en |α ≈ |en+1 | ≈ C|en | · |en−1 | ≈ Cλ−1/α |en |1+1/α
for sufficiently large values of n. So, we further have

|en |α ≈ Cλ−1/α−1 |en |1+1/α . Since the powers of |en | must agree,
√
1+ 5
α = 1 + 1/α or α = ≈ 1.62.
2
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Remarks
From Exercise 14(a) of Section 2.5, p. 91, we see that if a
sequence pn → p of order α for α > 1, then it is superlinearly
convergent.
Thus, the Secant method must be superlinearly convergent!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Section 2.5
Accelerating Convergence
(加速收斂性)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Acceleration of Linear Convergence
Objective
We try to develop some accelerating techniques for a linearly
convergent sequence {pn }∞
n=0 generated by the fixed-point
iteration.
1 Aitken’s ∆2 method (more rapid convergence)
2 Steffensen’s method (quadratic convergence)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
The Difference Operator ∆
Def 2.13 (向前差分算子)

Let {pn }∞
n= be a sequence generated by some iterative method.
The forward difference operator ∆ is defined by
∆pn = pm+1 − pn ∀ n ≥ 0.
Higher powers of ∆ is defined recursively by
∆k pn = ∆(∆k−1 pn ) ∀ k ≥ 2.
Note: For k = 2 in above Def., we have
∆2 pn = ∆(pn+1 − pn ) = ∆pn+1 − ∆pn

= (pn+2 − pn+1 ) − (pn+1 − pn )
= pn+2 − 2pn+1 + pn .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Derivation of Aitken’s ∆2 Method (1/2)
Assume that pn → p and the signs of pn+2 − p, pn+1 − p, pn − p

are the same.
Moreover, suppose also that
pn+1 − p pn+2 − p
≈ ,
pn − p pn+1 − p
if n is sufficiently large.
Then (pn+1 − p)2 ≈ (pn+2 − p)(pn − p)
⇐⇒ p2n+1 − 2pn+1 p + p2 ≈ pn+2 pn − (pn+2 + pn )p + p2
⇐⇒ (pn+2 − 2pn+1 + pn )p ≈ pn+2 pn − p2n+1
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Derivation of Aitken’s ∆2 Method (2/2)
pn+2 pn − p2n+1
⇐⇒ p ≈
pn+2 − 2pn+1 + pn
(pn pn+2 −2pn pn+1 + p2n ) − (p2n+1 −2pn+1 pn + p2n )
=
pn+2 − 2pn+1 + pn
(pn+1 − pn )2 (∆pn )2
⇐⇒ p ≈ pn − = pn − for n ≥ 0.
pn+2 − 2pn+1 + pn ∆2 pn
Aitken’s ∆2 Method:
(∆pn )2
p̂n = pn − ≡ {∆2 }(pn ) ∀ n ≥ 0,
∆2 pn
where the term pn = g(pn−1 ) is often generated by the

fixed-point iteration for n ≥ 1.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Convergence Behavior for Aitken’s Method
Thm 2.14 (Aitken 序列的收斂定理)

Suppose that {pn }∞
n=0 is a sequence converging linearly to the
limit p with
pn+1 − p
lim < 1.
n→∞ pn − p
Then the Aitken’s ∆2 sequence {p̂n }∞

n=0 converges to p faster than
{pn }∞
n=0 in the sense that
p̂n − p
lim = 0.
n→∞ pn − p
Note: See Exercise 16 for the proof of this theorem.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
The Steffensen’s Method
Steffensen’s Sequences
Aitken’s ∆2 method constructs the terms in order:
p0 , p1 = g(p0 ), p2 = g(p1 ), p̂0 = {∆2 }(p0 ),

p3 = g(p2 ), p̂1 = {∆2 }(p1 ), . . .
Steffensen’s method constructs the same first 4 terms and

every third term of the Steffensen sequence is generated by
the Aitken’s ∆2 operator, i.e.
(0) (0) (0) (0) (0) (1) (0)
p0 , p1 = g(p0 ), p2 = g(p1 ), p0 = {∆2 }(p0 ),
(1) (1) (1) (1) (2) (1)
p1 = g(p0 ), p2 = g(p1 ), p0 = {∆2 }(p0 ), . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode of Steffensen’s Method
To find a sol. to p = g(p) given initial approx. p0 .

Algorithm 2.6: Steffensen’s Method
OUTPUT approx. sol. p to x = g(x).
Step 1 Set i = 1.
Step 3 Set p1 = g(p0 ); p2 = g(p1 );
p = p0 − (p1 − p0 )2 /(p2 − 2p1 + p0 ).
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example
Use the Steffensen’s method to accelerate the fixed-point iteration
pn = g(pn−1 ), n ≥ 1, where
10 1/2
g(x) = g4 (x) = ( ) ,
4+x
for solving f(x) = x3 + 4x2 − 10 = 0 with p0 = 1.5.
Sol: The quadratic convergence of Steffensen’s method is

shown. The computed sol. is accurate to the9th decimal place as
Newton’s method.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Convergence Behavior for Steffensen’s Method
Thm 2.15 (Steffensen 序列的二次收斂性)

Suppose that x = g(x) has the solution p with g′ (p) ̸= 1. If ∃ δ > 0
s.t. g ∈ C3 [p − δ, p + δ], then Steffensen’s method gives quadratic
convergence for any p0 ∈ [p − δ, p + δ].
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Section 2.6
Zeros of Polynomials and
Müller’s Method
(多項式的零根與 Müller 法)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Thm 2.16 (Fundamental Theorem of Algebra; FTA)
Every poly. of degree n ≥ 1 with real or complex coefficients
P(x) = an xn + an−1 xn−1 + · · · + a1 x1 + a0
has exactly n roots (or zeros) in C.
Two Questions
Q1 For any x0 , how to evaluate P(x0 ) efficiently and accurately in
practical computation?
Q2 How to find the complex zeros of P(x) numerically?
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Two Corollaries of FTA
Cor 2.17 (多項式的因式分解)

If P(x) is a poly. of degree n with real or complex coeffs., then ∃
distinct zeros x1 , x2 , · · · , xk ∈ C and m1 , m2 , · · · , mk ∈ N s.t.
P(x) = an (x − x1 )m1 (x − x2 )m2 · · · (x − xk )mk .
Here, mi is the multiplicity of the zero xi for i = 1, 2, . . . , k.
Cor 2.18 (多項式的相等)

Let P(x) and Q(x) be pplys. of degree at most n. If ∃ distinct
x1 , · · · , xk ∈ C with k > n s.t.
P(xi ) = Q(xi ), i = 1, 2, . . . , k,
then P(x) ≡ Q(x), i.e., P(x) = Q(x) ∀ x ∈ C.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
A Nested Technique for Evaluating P(x0 )
Thm 2.19 (Horner’s Method)

Let P(x) = an xn + an−1 xn−1 + · · · + a1 x1 + a0 and x0 ∈ R.
Definebn = an and
bk = ak + bk+1 x0 , k = n − 1, n − 2, . . . , 1, 0.
We then have
(1) b0 = P(x0 ) can be evaluated in a nested manner, i.e.,
P(x0 ) = a0 + (· · · an−3 + (an−2 + (an−1 + an x0 )x0 )x0 · · · )x0 .
(2) If Q(x) = bn xn−1 + bn−1 xn−2 + · · · + b2 x + b1 , then
P(x) = (x − x0 )Q(x) + b0 .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Proof of Thm 2.19
It suffices to prove Part (2), since Part (1) is easily seen from
the construction of bk for k = n, n − 1, . . . , 1, 0.
For the Part (2), we see that
(x − x0 )Q(x) + b0
=(x − x0 )(bn xn−1 + bn−1 xn−2 + · · · b2 x + b1 ) + b0
=bn xn + bn−1 xn−1 + · · · b2 x2 + b1 x
− bn x0 xn−1 − bn−1 x0 xn−2 − · · · − b2 x0 x − b1 x0 + b0
=bn xn + (bn−1 − bn x0 )xn−1 + · · · + (b1 − b2 x0 )x + (b0 − b1 x0 )
=an xn + an−1 xm−1 + · · · + a1 x + a0
=P(x), since an = bn and ak = bk − bk+1 x0 , k = n − 1, . . . , 1, 0.
Therefore, we have b0 = P(x0 ).

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 2, p. 93
Use Horner’s Method to evaluate P(x) = 2x4 − 3x2 + 3x − 4 at
x0 = −2. The actual value is P(x0 ) = P(−2) = 10.
Sol: Try to construct a table as follows.
x0 = −2 a4 = 2 a3 = 0 a2 = −3 a1 = 3 a0 = −4
b4 x0 = −4 b3 x0 = 8 b2 x0 = −10 b1 x0 = 14
b4 = 2 b3 = −4 b2 = 5 b1 = −7 b0 = 10
So, P(x) = (x + 2)(2x3 − 4x2 + 5x − 7) + 10 and hence

P(−2) = b0 = 10 by using Horner’s Metod.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Newton’s Method for Polynomials
From Thm 2.19, we obtain that
P(x) = (x − x0 )Q(x) + b0 .
So, differentiating w.r.t. x gives
P′ (x) = Q(x) + (x − x0 )Q′ (x).
For any x0 ∈ R, we have P′ (x0 ) = Q(x0 ), which can be

evaluated efficiently using Horner’s Method.
Newton’s Method can be rewritten as
P(pk−1 )
pk = pk−1 − , k = 1, 2, . . . ,
Q(pk−1 )
where p0 is a good initial approx. to the zero p of P(x).

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode of Horner’s Method
To evaluate P(x0 ) and P′ (x0 ) for an nth-degree polynomial P(x).

Algorithm 2.7: Horner’s Method
INPUT degree n; coeff. an , · · · , a1 , a0 ; x0 .
OUTPUT y = P(x0 ); z = P′ (x0 ).
Step 1 Set y = an ; z = an .
Step 2 For j = n − 1, n − 2, . . . , 1
Set y = y · x0 + aj ; (Compute bj for P.)
z = z · x0 + y. (Compute bj−1 for Q.)
Step 3 Set y = y · x0 + a0 . (Compute b0 for P.)
Step 4 OUTPUT(y, z); STOP.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Operation Counts (運算量)
The usual method for evaluating
P(x0 ) = an xn0 + an−1 x0n−1 + · · · + a2 x20 + a1 x0 + a0

= an · (x0 · xn−1
0 ) + · · · + a2 · (x0 · x0 ) + a1 · x0 + a0
requires 2n − 1 multiplications and n additions.

The Horner’s Method for evaluating the value P(x0 ) requires
only n multiplications and n additions.
=⇒ This avoids the loss of significance!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Example 3, p. 94
Find an approximation to a zero of
P(x) = 2x4 − 3x2 + 3x − 4
using Newton’s method with x0 = −2 and Horner’s method.
Sol: Using Horner’s Method with initial x0 = −2, we have
−2 2 0 −3 3 −4
−4 8 −10 14
−2 2 −4 5 −7 10 = P(x0 )
−4 16 −42
2 −8 21 −49 = Q(x0 )
P(x0 )
=⇒ x1 = x0 − Q(x0 ) = −2 − 10
−49 ≈ −1.796.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Sol. of Example 3 (Conti’d)
Next, evaluate P(x1 ) and P ′ (x1 ) = Q(x1 ) =⇒
−1.796 2 0 −3 3 −4
−3.592 6.451 −6.197 5.742
−1.796 2 −3.592 3.451 −3.197 1.742 = P(x1 )
−3.592 12.902 −29.368
2 −7.184 16.353 −32.565 = Q(x1 )
P(x1 )
=⇒ x2 = x1 − Q(x 1)
= −1.796 − −32.565
1.742
≈ −1.7425.
Similarly, x3 ≈ −1.73897 and an actual zero to 5 decimal places
is −1.73896.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Complex Zeros of P(x)
Thm 2.20 (實係數多項式的複數重根)

If z = a + bi is a complex zero of multiplicity m of the poly. P(x)
with real coefficients, then
(1) z̄ = a − bi is also a complex zero of multiplicity m of P(x).
(2) P(x) = (x2 − 2ax + a2 + b2 )m Q(x), where Q(x) is some poly.
with Q(z) ̸= 0.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Secant Method v.s. Müller’s Method
Basic Ideas
Secant Method: given p0 and p1 ⇒ p2 is the x-intercept of
the line through (p0 , f(p0 )) and (p1 , f(p1 )).
Müller’s Method: given p0 , p1 and p2 ⇒ p3 is the
x-intercept of the parabola through (p0 , f(p0 )), (p1 , f(p1 ))
and (p2 , f(p2 )).
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Derivation of Müller’s Method (1/4)
Consider the quadratic polynomial
P(x) = a(x − p2 )2 + b(x − p2 ) + c
passing through (p0 , f(p0 )), (p1 , f(p1 )) and (p2 , f(p2 )).
So, we obtain the following linear system
f(p2 ) = a · 0 + b · 0 + c,
f(p0 ) = a(p0 − p2 )2 + b(p0 − p2 ) + c,
f(p1 ) = a(p1 − p2 )2 + b(p1 − p2 ) + c
to determine the constants a, b and c uniquely.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
It follows from Cramer’s Rule that
c = f(p2 ), (2)
(p0 − p2 )2 [f(p − f(p2 )] − (p1 − p2
1) )2 [f(p 0) − f(p2 )]
b= ,
(p0 − p2 )(p1 − p2 )(p0 − p1 )
(3)
(p1 − p2 )[f(p0 ) − f(p2 )] − (p0 − p2 )[f(p1 ) − f(p2 )]
a= . (4)
(p0 − p2 )(p1 − p2 )(p0 − p1 )
Let h1 , h2 , δ1 and δ2 be defined by
h1 = p1 − −p0 , h2 = p2 − p1 ,
δ1 = [f(p1 ) − f(p0 )]/h1 , δ2 = [f(p2 ) − f(p1 )]/h2 . (5)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Substituting (5) into (3)–(4) gives that
(−h2 )(−h1 δ1 − h2 δ2 ) − [−(h1 + h2 )](−h2 δ2 )

a=
−(h1 + h2 )(−h2 )(−h1 )
h2 h1 (δ2 − δ1 ) δ2 − δ1
= = .
(h1 + h2 )h2 h1 h1 + h2
and
(h1 + h2 )2 (−h2 δ2 ) − h22 (−h1 δ1 − h2 δ2 )
b=
−(h1 + h2 )(−h2 )(−h1 )
(h1 + h2 )h1 h2 δ2 + h22 h1 (δ2 − δ1 )
= = δ2 + h2 a.
(h1 + h2 )h2 h1
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
If p3 is the intersection of the x-axis with y = P(x), then
P(p3 ) = a(p3 − p2 )2 + b(p3 − p2 ) + c = 0
with c = f(p2 ). So, we know that

√
−b ± b2 − 4ac −2c
p3 = p2 + = p2 + √
2a b ± b2 − 4ac
−2c
= p2 + √ . (取分母絕對值較大者)
b + sign(b) b2 − 4ac
Repeat above procedure with the points (p1 , f(p1 )), (p2 , f(p2 ))
and (p3 , f(p3 )) to obtain the next approx. p4 to a zero of the
nonlinear equation f(x) = 0.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Pseudocode of Müller’s Method
To find a sol. to f(x) = 0 given 3 approx. p0 , p1 and p2 .
Algorithm 2.8: Müller’s Method
INPUT initial p0 , p1 , p2 ; tol. TOLL; max. no. iter. N0 .
OUTPUT approx. sol. p.
Step 1 Set i = 3.
Step 2 While i ≤ N0 do Steps 3–7.
Step 3 Set h1 = p1 − p0 ; δ1 = [f(p1 ) − f(p0 )]/h1 ;
h2 = p2 − p1 ; δ2 = [f(p2 ) − f(p1 )]/h2 ;
√2 − δ1 )/(h1 + h2 ); b = δ2 + h2 a; c = f(p2 );
a = (δ
D = b2 − 4ac. (May require complex arithmetic.)
Step 4 If |b − D| < |b + D| then set E = b + D;
Else set E = b − D.
Step 5 Set h = −2c/E; p = p2 + h.
Step 6 If |h| < TOL then OUTPUT(p); STOP.
Step 7 Set p0 = p1 ; p1 = p2 ; p2 = p; i = i + 1.
Step 8 OUTPUT(‘Method failed after N0 iterations’); STOP. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
An Illustrative Example, p. 98
Use Müller’s Method to find all zeros of the 4th-degree polynomial
f(x) = x4 − 3x3 + x2 + x + 1
with TOL = 10−5 and the following initial approximations:

(1) p0 = 0.5, p1 = −0.5, p3 = 0; (Complex zero)
(2) p0 = 0.5, p1 = 1.0, p3 = 1.5; (Real zero of small magnitude)
(3) p0 = 1.5, p1 = 2.0, p3 = 2.5. (Real zero of large magnitude)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Numerical Results (1/2)
One complex root z1 is computed by the Müller’s Method, and the

other complex root z2 can be obtained by taking z2 = z¯1 directly.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Numerical Results (2/2)
Two distinct real roots are computed by the Müller’s Method with
different initial points.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Thank you for your attention!
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .

CH02 PDF

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

CH02 PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CH02 PDF

Uploaded by

Copyright:

Available Formats

Chapter 2

Solutions of Equations in One

Hung-Yuan Fan (范洪源)

Root-Finding Problem (勘根問題)

Note: Three numerical methods will be discussed here:

Assume that f is well-defined on the interval [a, b].

Given f ∈ C[a, b] with f(a) · f(b) < 0 .

(3) |f(pN )| < ϵ.

Note: The stopping criterion (2) is preferred in practice.

has exactly one root in [1, 2].

|p − p13 | |b14 − a14 |

Thm 2.1 (二分法的收斂定理)

pf: For each n ≥ 1, p ∈ (an , bn ) and

Sol: Applying Thm 2.1, it follows that

sign(f(pn )) · sign(f(an )) < 0 instead of f(pn ) · f(an ) < 0.

Note: The sign function is defined by

Note: A root-finding problem of the form

where p is a root of f, can be transformed to a fixed-point form

for some suitable function g obtained by algebraic transposition.

Thm 2.3 (固定點的存在性與唯一性)

|g′ (x)| ≤ k ∀ x ∈ (a, b),

then there is exactly one fixed point in [a, b].

Geometrically, a fixed point p ∈ [a, b] is just the point where the

h(a) = g(a) − a > 0, h(b) = g(b) − b < 0.

By IVT, ∃ p ∈ (a, b) s.t. h(p) = 0 or g(p) = p.

|p − q| = |g(p) − g(q)| = |g′ (ξ)||p − q|

which is a contradiction! Hence, g must have a unique fixed

Sol: Since g′ (x) = −3−x ln 3 < 0 ∀ x ∈ [0, 1], g is strictly

But also note that

Functional (or Fixed-Point) Iteration

This method is also called the functional iteration. (泛函迭代)

Starting wirh p0 ∈ [a, b], we obtain a sequence of points

(p0 , p1 ) → (p1 , p1 ) → (p1 , p2 ) → (p2 , p2 ) → (p2 , p3 ) → · · · (p, p),

To find a sol. p to x = g(x) given an initial approx. p0 .

5 Possible Fixed-Point Forms

can be transformed to the following 5 fixed-point forms:

converge for any p0 ∈ [a, b]?

Thm 2.4 (Fixed-Point Thm)

|g′ (x)| ≤ k ∀ x ∈ (a, b),

then for any p0 ∈ [a, b], the sequence {pn }∞

converges to the unique fixed point p ∈ [a, b] of g.

Thm 2.3 ensure that ∃! p ∈ [a, b] s.t. g(p) = p.

|pn − p| = |g(pn−1 ) − g(p)| = |g′ (ξn )||pn−1 − p| ≤ k|pn−1 − p|.

By induction =⇒ |pn − p| ≤ kn |p0 − p| for n ≥ 0.

lim |pn − p| = 0 ⇐⇒ lim pn = p

by the Sandwich Thm.

[Q]: What is the order of convergence for the FPI?

The smaller the value of k, the faster the convergence.

The convergence would be very slow if k ≈ 1.

5 Possible Fixed-Point Forms

can be transformed to the following 5 fixed-point forms:

(c) Since p0 = 1.5, 1 < 1.28 ≈ g3 (1.5) ≤ g3 (x) ≤ g3 (1) = 1.5

(d) g4 ([1, 2]) ⊆ [1, 2] and the derivative g′4 satisfies

(e) It is Newton’s method satisfying g′5 (p) = 0 theoretically!

If f(p) = 0, then g′ (p) = 0 follows immediately.

To find a sol. to f(x) = 0 given an initial approx. p0 .

with initial guess p0 = π4 . The root is p ≈ 0.739085133215161.

(a) Consider the fixed-point form x = g(x), where