university-logo

Numerical Analysis I Solutions of Equations in One Variable

Instructor: Wei-Cheng Wang ^{1}

Department of Mathematics National TsingHua University

Fall 2010

1These slides are based on Prof. Tsung-Ming Huang(NTNU)’s original slides

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  1 / 1

university-logo

Outline

university-logo

Bisection Method

Idea

If f (x) ∈ C[a, b] and f (a)f (b) < 0, then ∃ c ∈ (a, b) such that f (c) = 0.

university-logo

Bisection method algorithm

Given f (x) defined on (a, b), the maximal number of iterations M, and stop criteria δ and ε, this algorithm tries to locate one root of f (x).

Compute fa = f (a), fb = f (b), and e = b − a If sign(fa) = sign(fb), then stop End If For k = 1, 2, …, M

e = e/2, c = (a + b)/2, fc = f (c) If (|e| < δ or |fc| < ε), then stop End If If sign(fc) ≠ sign(fa)

b = c, fb = fc Else

a = c, fa = fc End If

End For

university-logo

Let {c_{n}} be the sequence of numbers produced. The algorithm should stop if one of the following conditions is satisfied.

1 the iteration number k > M,

2 |c_{k} − c_{k−1}| < δ, or

3 |f (c_{k})| < ε. Let [a_{0}, b_{0}], [a_{1}, b_{1}], … denote the successive intervals produced by the bisection algorithm. Then

a = a_{0} ≤ a_{1} ≤ a_{2} ≤ ⋯ ≤ b_{0} = b
⇒ {a_{n}} and {b_{n}} are bounded
⇒ lim_{n→∞}a_{n} and lim_{n→∞}b_{n} exist

university-logo

Let {c_{n}} be the sequence of numbers produced. The algorithm should stop if one of the following conditions is satisfied.

1 the iteration number k > M,

2 |c_{k} − c_{k−1}| < δ, or

3 |f (c_{k})| < ε. Let [a_{0}, b_{0}], [a_{1}, b_{1}], … denote the successive intervals produced by the bisection algorithm. Then

a = a_{0} ≤ a_{1} ≤ a_{2} ≤ ⋯ ≤ b_{0} = b
⇒ {a_{n}} and {b_{n}} are bounded
⇒ lim_{n→∞}a_{n} and lim_{n→∞}b_{n} exist

university-logo

Let {c_{n}} be the sequence of numbers produced. The algorithm should stop if one of the following conditions is satisfied.

1 the iteration number k > M,

2 |c_{k} − c_{k−1}| < δ, or

3 |f (c_{k})| < ε. Let [a_{0}, b_{0}], [a_{1}, b_{1}], … denote the successive intervals produced by the bisection algorithm. Then

a = a_{0} ≤ a_{1} ≤ a_{2} ≤ ⋯ ≤ b_{0} = b
⇒ {a_{n}} and {b_{n}} are bounded
⇒ lim_{n→∞}a_{n} and lim_{n→∞}b_{n} exist

university-logo

Since

b_{1} − a_{1} = \frac{1}{2}(b_{0} − a_{0})
b_{2} − a_{2} = \frac{1}{2}(b_{1} − a_{1}) = \frac{1}{4}(b_{0} − a_{0})
⋮
b_{n} − a_{n} = \frac{1}{2^{n}}(b_{0} − a_{0})

hence

lim_{n→∞}b_{n} − lim_{n→∞}a_{n} = lim_{n→∞}(b_{n} − a_{n}) = lim_{n→∞} \frac{1}{2^{n}}(b_{0} − a_{0}) = 0.

Therefore

lim_{n→∞}a_{n} = lim_{n→∞}b_{n} ≡ z.

Since f is a continuous function, we have that lim_{n→∞}f (a_{n}) = f ( lim_{n→∞}a_{n}) = f (z) and lim_{n→∞}f (b_{n}) = f ( lim_{n→∞}b_{n}) = f (z).

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  6 / 1

university-logo

Since

b_{1} − a_{1} = \frac{1}{2}(b_{0} − a_{0})
b_{2} − a_{2} = \frac{1}{2}(b_{1} − a_{1}) = \frac{1}{4}(b_{0} − a_{0})
⋮
b_{n} − a_{n} = \frac{1}{2^{n}}(b_{0} − a_{0})

hence

lim_{n→∞}b_{n} − lim_{n→∞}a_{n} = lim_{n→∞}(b_{n} − a_{n}) = lim_{n→∞} \frac{1}{2^{n}}(b_{0} − a_{0}) = 0.

Therefore

lim_{n→∞}a_{n} = lim_{n→∞}b_{n} ≡ z.

Since f is a continuous function, we have that lim_{n→∞}f (a_{n}) = f ( lim_{n→∞}a_{n}) = f (z) and lim_{n→∞}f (b_{n}) = f ( lim_{n→∞}b_{n}) = f (z).

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  6 / 1

university-logo

Since

b_{1} − a_{1} = \frac{1}{2}(b_{0} − a_{0})
b_{2} − a_{2} = \frac{1}{2}(b_{1} − a_{1}) = \frac{1}{4}(b_{0} − a_{0})
⋮
b_{n} − a_{n} = \frac{1}{2^{n}}(b_{0} − a_{0})

hence

lim_{n→∞}b_{n} − lim_{n→∞}a_{n} = lim_{n→∞}(b_{n} − a_{n}) = lim_{n→∞} \frac{1}{2^{n}}(b_{0} − a_{0}) = 0.

Therefore

lim_{n→∞}a_{n} = lim_{n→∞}b_{n} ≡ z.

Since f is a continuous function, we have that lim_{n→∞}f (a_{n}) = f ( lim_{n→∞}a_{n}) = f (z) and lim_{n→∞}f (b_{n}) = f ( lim_{n→∞}b_{n}) = f (z).

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  6 / 1

university-logo

Since

b_{1} − a_{1} = \frac{1}{2}(b_{0} − a_{0})
b_{2} − a_{2} = \frac{1}{2}(b_{1} − a_{1}) = \frac{1}{4}(b_{0} − a_{0})
⋮
b_{n} − a_{n} = \frac{1}{2^{n}}(b_{0} − a_{0})

hence

lim_{n→∞}b_{n} − lim_{n→∞}a_{n} = lim_{n→∞}(b_{n} − a_{n}) = lim_{n→∞} \frac{1}{2^{n}}(b_{0} − a_{0}) = 0.

Therefore

lim_{n→∞}a_{n} = lim_{n→∞}b_{n} ≡ z.

Since f is a continuous function, we have that lim_{n→∞}f (a_{n}) = f ( lim_{n→∞}a_{n}) = f (z) and lim_{n→∞}f (b_{n}) = f ( lim_{n→∞}b_{n}) = f (z).

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  6 / 1

university-logo

On the other hand,

f (a_{n})f (b_{n}) < 0
⇒ lim_{n→∞}f (a_{n})f (b_{n}) = f^{2}(z) ≤ 0
⇒ f (z) = 0

Therefore, the limit of the sequences {a_{n}} and {b_{n}} is a zero of f in [a, b]. Let c_{n} = \frac{1}{2}(a_{n} + b_{n}). Then

|z − c_{n}| = | lim_{n→∞}a_{n} − \frac{1}{2}(a_{n} + b_{n})|
= |\frac{1}{2} [ lim_{n→∞}a_{n} − b_{n}] + \frac{1}{2} [ lim_{n→∞}a_{n} − a_{n}] |
≤ max {| lim_{n→∞}a_{n} − b_{n}|, | lim_{n→∞}a_{n} − a_{n}|}
≤ |b_{n} − a_{n}| = \frac{1}{2^{n}}|b_{0} − a_{0}|.

This proves the following theorem.

university-logo

f (a_{n})f (b_{n}) < 0
⇒ lim_{n→∞}f (a_{n})f (b_{n}) = f^{2}(z) ≤ 0
⇒ f (z) = 0

Therefore, the limit of the sequences {a_{n}} and {b_{n}} is a zero of f in [a, b]. Let c_{n} = \frac{1}{2}(a_{n} + b_{n}). Then

|z − c_{n}| = | lim_{n→∞}a_{n} − \frac{1}{2}(a_{n} + b_{n})|
= |\frac{1}{2} [ lim_{n→∞}a_{n} − b_{n}] + \frac{1}{2} [ lim_{n→∞}a_{n} − a_{n}] |
≤ max {| lim_{n→∞}a_{n} − b_{n}|, | lim_{n→∞}a_{n} − a_{n}|}
≤ |b_{n} − a_{n}| = \frac{1}{2^{n}}|b_{0} − a_{0}|.

This proves the following theorem.

university-logo

f (a_{n})f (b_{n}) < 0
⇒ lim_{n→∞}f (a_{n})f (b_{n}) = f^{2}(z) ≤ 0
⇒ f (z) = 0

Therefore, the limit of the sequences {a_{n}} and {b_{n}} is a zero of f in [a, b]. Let c_{n} = \frac{1}{2}(a_{n} + b_{n}). Then

|z − c_{n}| = | lim_{n→∞}a_{n} − \frac{1}{2}(a_{n} + b_{n})|
= |\frac{1}{2} [ lim_{n→∞}a_{n} − b_{n}] + \frac{1}{2} [ lim_{n→∞}a_{n} − a_{n}] |
≤ max {| lim_{n→∞}a_{n} − b_{n}|, | lim_{n→∞}a_{n} − a_{n}|}
≤ |b_{n} − a_{n}| = \frac{1}{2^{n}}|b_{0} − a_{0}|.

This proves the following theorem.

university-logo

f (a_{n})f (b_{n}) < 0
⇒ lim_{n→∞}f (a_{n})f (b_{n}) = f^{2}(z) ≤ 0
⇒ f (z) = 0

Therefore, the limit of the sequences {a_{n}} and {b_{n}} is a zero of f in [a, b]. Let c_{n} = \frac{1}{2}(a_{n} + b_{n}). Then

|z − c_{n}| = | lim_{n→∞}a_{n} − \frac{1}{2}(a_{n} + b_{n})|
= |\frac{1}{2} [ lim_{n→∞}a_{n} − b_{n}] + \frac{1}{2} [ lim_{n→∞}a_{n} − a_{n}] |
≤ max {| lim_{n→∞}a_{n} − b_{n}|, | lim_{n→∞}a_{n} − a_{n}|}
≤ |b_{n} − a_{n}| = \frac{1}{2^{n}}|b_{0} − a_{0}|.

This proves the following theorem.

university-logo

Theorem

Let {[a_{n}, b_{n}]} denote the intervals produced by the bisection algorithm. Then lim_{n→∞}a_{n} and lim_{n→∞}b_{n} exist, are equal, and represent a zero of f (x). If

z = lim_{n→∞}a_{n} = lim_{n→∞}b_{n} and c_{n} = \frac{1}{2}(a_{n} + b_{n}),

then

|z − c_{n}| ≤ \frac{1}{2^{n}} (b_{0} − a_{0}).

Remark

{c_{n}} converges to z with the rate of O(2^{−n}).

university-logo

Theorem

Let {[a_{n}, b_{n}]} denote the intervals produced by the bisection algorithm. Then lim_{n→∞}a_{n} and lim_{n→∞}b_{n} exist, are equal, and represent a zero of f (x). If

z = lim_{n→∞}a_{n} = lim_{n→∞}b_{n} and c_{n} = \frac{1}{2}(a_{n} + b_{n}),

then

|z − c_{n}| ≤ \frac{1}{2^{n}} (b_{0} − a_{0}).

Remark

{c_{n}} converges to z with the rate of O(2^{−n}).

university-logo

Example

How many steps should be taken to compute a root of f (x) = x^{3} + 4x^{2} − 10 = 0 on [1, 2] with relative error 10^{−3}?

solution: Seek an n such that

\frac{|z − c_{n}|}{|z|} ≤ 10^{−3} ⇒ |z − c_{n}| ≤ |z| × 10^{−3}.

Since z ∈ [1, 2], it is sufficient to show

|z − c_{n}| ≤ 10^{−3}.

That is, we solve

2^{−n}(2 − 1) ≤ 10^{−3} ⇒ −n log_{10} 2 ≤ −3

which gives n ≥ 10.

university-logo

Example

How many steps should be taken to compute a root of f (x) = x^{3} + 4x^{2} − 10 = 0 on [1, 2] with relative error 10^{−3}?

solution: Seek an n such that

\frac{|z − c_{n}|}{|z|} ≤ 10^{−3} ⇒ |z − c_{n}| ≤ |z| × 10^{−3}.

Since z ∈ [1, 2], it is sufficient to show

|z − c_{n}| ≤ 10^{−3}.

That is, we solve

2^{−n}(2 − 1) ≤ 10^{−3} ⇒ −n log_{10} 2 ≤ −3

which gives n ≥ 10.

university-logo

Fixed-Point Iteration

Definition

x is called a fixed point of a given function f if f (x) = x.

Root-finding problems and fixed-point problems

Find x^{∗} such that f (x^{∗}) = 0. Let g(x) = x − f (x). Then g(x^{∗}) = x^{∗} − f (x^{∗}) = x^{∗}. ⇒ x^{∗} is a fixed point for g(x). Find x^{∗} such that g(x^{∗}) = x^{∗}. Define f (x) = x − g(x) so that f (x^{∗}) = x^{∗} − g(x^{∗}) = x^{∗} − x^{∗} = 0 ⇒ x^{∗} is a zero of f (x).

university-logo

Definition

x is called a fixed point of a given function f if f (x) = x.

Root-finding problems and fixed-point problems

Find x^{∗} such that f (x^{∗}) = 0. Let g(x) = x − f (x). Then g(x^{∗}) = x^{∗} − f (x^{∗}) = x^{∗}. ⇒ x^{∗} is a fixed point for g(x). Find x^{∗} such that g(x^{∗}) = x^{∗}. Define f (x) = x − g(x) so that f (x^{∗}) = x^{∗} − g(x^{∗}) = x^{∗} − x^{∗} = 0 ⇒ x^{∗} is a zero of f (x).

university-logo

Definition

x is called a fixed point of a given function f if f (x) = x.

Root-finding problems and fixed-point problems

Find x^{∗} such that f (x^{∗}) = 0. Let g(x) = x − f (x). Then g(x^{∗}) = x^{∗} − f (x^{∗}) = x^{∗}. ⇒ x^{∗} is a fixed point for g(x). Find x^{∗} such that g(x^{∗}) = x^{∗}. Define f (x) = x − g(x) so that f (x^{∗}) = x^{∗} − g(x^{∗}) = x^{∗} − x^{∗} = 0 ⇒ x^{∗} is a zero of f (x).

university-logo

Example

The function g(x) = x^{2} − 2, for −2 ≤ x ≤ 3, has fixed points at x = −1 and x = 2 since

g(−1) = (−1)^{2} − 2 = −1 and g(2) = 2^{2} − 2 = 2.

university-logo

Theorem (Existence and uniqueness)

1 If g ∈ C[a, b] such that a ≤ g(x) ≤ b for all x ∈ [a, b], then g has a

fixed point in [a, b]. 2 If, in addition, g′(x) exists in (a, b) and there exists a positive

constant M < 1 such that |g′(x)| ≤ M < 1 for all x ∈ (a, b). Then the fixed point is unique.

university-logo

Theorem (Existence and uniqueness)

1 If g ∈ C[a, b] such that a ≤ g(x) ≤ b for all x ∈ [a, b], then g has a

fixed point in [a, b]. 2 If, in addition, g′(x) exists in (a, b) and there exists a positive

constant M < 1 such that |g′(x)| ≤ M < 1 for all x ∈ (a, b). Then the fixed point is unique.

university-logo

Proof

Existence: If g(a) = a or g(b) = b, then a or b is a fixed point of g and we are done. Otherwise, it must be g(a) > a and g(b) < b. The function h(x) = g(x) − x is continuous on [a, b], with

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

By the Intermediate Value Theorem, ∃ x^{∗} ∈ [a, b] such that h(x^{∗}) = 0. That is

g(x^{∗}) − x^{∗} = 0 ⇒ g(x^{∗}) = x^{∗}.

Hence g has a fixed point x^{∗} in [a, b].

university-logo

Existence: If g(a) = a or g(b) = b, then a or b is a fixed point of g and we are done. Otherwise, it must be g(a) > a and g(b) < b. The function h(x) = g(x) − x is continuous on [a, b], with

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

By the Intermediate Value Theorem, ∃ x^{∗} ∈ [a, b] such that h(x^{∗}) = 0. That is

g(x^{∗}) − x^{∗} = 0 ⇒ g(x^{∗}) = x^{∗}.

Hence g has a fixed point x^{∗} in [a, b].

university-logo

Existence: If g(a) = a or g(b) = b, then a or b is a fixed point of g and we are done. Otherwise, it must be g(a) > a and g(b) < b. The function h(x) = g(x) − x is continuous on [a, b], with

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

By the Intermediate Value Theorem, ∃ x^{∗} ∈ [a, b] such that h(x^{∗}) = 0. That is

g(x^{∗}) − x^{∗} = 0 ⇒ g(x^{∗}) = x^{∗}.

Hence g has a fixed point x^{∗} in [a, b].

university-logo

Existence: If g(a) = a or g(b) = b, then a or b is a fixed point of g and we are done. Otherwise, it must be g(a) > a and g(b) < b. The function h(x) = g(x) − x is continuous on [a, b], with

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

By the Intermediate Value Theorem, ∃ x^{∗} ∈ [a, b] such that h(x^{∗}) = 0. That is

g(x^{∗}) − x^{∗} = 0 ⇒ g(x^{∗}) = x^{∗}.

Hence g has a fixed point x^{∗} in [a, b].

university-logo

Existence: If g(a) = a or g(b) = b, then a or b is a fixed point of g and we are done. Otherwise, it must be g(a) > a and g(b) < b. The function h(x) = g(x) − x is continuous on [a, b], with

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

By the Intermediate Value Theorem, ∃ x^{∗} ∈ [a, b] such that h(x^{∗}) = 0. That is

g(x^{∗}) − x^{∗} = 0 ⇒ g(x^{∗}) = x^{∗}.

Hence g has a fixed point x^{∗} in [a, b].

university-logo

Uniqueness: Suppose that p ≠ q are both fixed points of g in [a, b]. By the Mean-Value theorem, there exists ξ between p and q such that

g′(ξ) = \frac{g(p) − g(q)}{p − q} = \frac{p − q}{p − q} = 1.

However, this contradicts to the assumption that |g′(x)| ≤ M < 1 for all x in [a, b]. Therefore the fixed point of g is unique.

university-logo

Uniqueness: Suppose that p ≠ q are both fixed points of g in [a, b]. By the Mean-Value theorem, there exists ξ between p and q such that

g′(ξ) = \frac{g(p) − g(q)}{p − q} = \frac{p − q}{p − q} = 1.

However, this contradicts to the assumption that |g′(x)| ≤ M < 1 for all x in [a, b]. Therefore the fixed point of g is unique.

university-logo

Uniqueness: Suppose that p ≠ q are both fixed points of g in [a, b]. By the Mean-Value theorem, there exists ξ between p and q such that

g′(ξ) = \frac{g(p) − g(q)}{p − q} = \frac{p − q}{p − q} = 1.

However, this contradicts to the assumption that |g′(x)| ≤ M < 1 for all x in [a, b]. Therefore the fixed point of g is unique.

university-logo

Example

Show that the following function has a unique fixed point.

g(x) = (x^{2} − 1)/3, x ∈ [−1, 1].

Solution: The Extreme Value Theorem implies that

min_{x∈[−1,1]}g(x) = g(0) = −\frac{1}{3},

max_{x∈[−1,1]}g(x) = g(±1) = 0.

That is g(x) ∈ [−1, 1], ∀ x ∈ [−1, 1]. Moreover, g is continuous and

|g′(x)| = |\frac{2x}{3} | ≤ \frac{2}{3}, ∀ x ∈ (−1, 1).

By above theorem, g has a unique fixed point in [−1, 1].

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  15 / 1

university-logo

Let p be such unique fixed point of g. Then

p = g(p) = \frac{p^{2} − 1}{3} ⇒ p^{2} − 3p − 1 = 0

⇒ p = \frac{1}{2}(3 − \sqrt{13}).

university-logo

Fixed-point iteration or functional iteration

Given a continuous function g, choose an initial point x_{0} and generate {x_{k}}_{k=0}^{∞} by

x_{k+1} = g(x_{k}), k ≥ 0.

{x_{k}} may not converge, e.g., g(x) = 3x. However, when the sequence converges, say,

lim_{k→∞}x_{k} = x^{∗},

then, since g is continuous,

g(x^{∗}) = g( lim_{k→∞}x_{k}) = lim_{k→∞}g(x_{k}) = lim_{k→∞}x_{k+1} = x^{∗}.

That is, x^{∗} is a fixed point of g.

university-logo

Fixed-point iteration

Given x_{0}, tolerance TOL, maximum number of iteration M. Set i = 1 and x = g(x_{0}). While i ≤ M and |x − x_{0}| ≥ TOL

Set i = i + 1, x_{0} = x and x = g(x_{0}). End While

university-logo

Example

The equation

x^{3} + 4x^{2} − 10 = 0

has a unique root in [1, 2]. Change the equation to the fixed-point form x = g(x).

(a) x = g_{1}(x) ≡ x − f (x) = x − x^{3} − 4x^{2} + 10

(b) x = g_{2}(x) = (\frac{10}{x} − 4x)^{1/2}

x^{3} = 10 − 4x^{2} ⇒ x^{2} = \frac{10}{x} − 4x ⇒ x = ± (\frac{10}{x} − 4x)^{1/2}

university-logo

(c) x = g_{3}(x) = \frac{1}{2} (10 − x^{3})^{1/2}

4x^{2} = 10 − x^{3} ⇒ x = ±\frac{1}{2} (10 − x^{3})^{1/2}

(d) x = g_{4}(x) = (\frac{10}{4+x})^{1/2}

x^{2}(x + 4) = 10 ⇒ x = ± (\frac{10}{4 + x} )^{1/2}

(e) x = g_{5}(x) = x − \frac{x^{3}+4x^{2}−10}{3x^{2}+8x}

x = g_{5}(x) ≡ x − \frac{f (x)}{f′(x)}

university-logo

Results of the fixed-point iteration with initial point x_{0} = 1.5

university-logo

Theorem (Fixed-point Theorem)

Let g ∈ C[a, b] be such that g(x) ∈ [a, b] for all x ∈ [a, b]. Suppose that g′ exists on (a, b) and that ∃ k with 0 < k < 1 such that

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

Then, for any number x_{0} in [a, b],

x_{n} = g(x_{n−1}), n ≥ 1,

converges to the unique fixed point x in [a, b].

university-logo

Proof:

By the assumptions, a unique fixed point exists in [a, b]. Since g([a, b]) ⊆ [a, b], {x_{n}}_{n=0}^{∞} is defined and x_{n} ∈ [a, b] for all n ≥ 0. Using the Mean Values Theorem and the fact that |g′(x)| ≤ k, we have

|x − x_{n}| = |g(x_{n−1}) − g(x)| = |g′(ξ_{n})||x − x_{n−1}| ≤ k|x − x_{n−1}|,

where ξ_{n} ∈ (a, b). It follows that

|x_{n} − x| ≤ k|x_{n−1} − x| ≤ k^{2}|x_{n−2} − x| ≤ ⋯ ≤ k^{n}|x_{0} − x|.  (1)

Since 0 < k < 1, we have

lim_{n→∞}k^{n} = 0

and

lim_{n→∞}|x_{n} − x| ≤ lim_{n→∞}k^{n}|x_{0} − x| = 0.

Hence, {x_{n}}_{n=0}^{∞} converges to x.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  23 / 1

university-logo

Corollary

If g satisfies the hypotheses of above theorem, then

|x − x_{n}| ≤ k^{n} max{x_{0} − a, b − x_{0}}

and

|x_{n} − x| ≤ \frac{k^{n}}{1 − k}|x_{1} − x_{0}|, ∀ n ≥ 1.

Proof: From (1),

|x_{n} − x| ≤ k^{n}|x_{0} − x| ≤ k^{n} max{x_{0} − a, b − x_{0}}.

For n ≥ 1, using the Mean Values Theorem,

|x_{n+1} − x_{n}| = |g(x_{n}) − g(x_{n−1})| ≤ k|x_{n} − x_{n−1}| ≤ ⋯ ≤ k^{n}|x_{1} − x_{0}|.

university-logo

Thus, for m > n ≥ 1,

|x_{m} − x_{n}| = |x_{m} − x_{m−1} + x_{m−1} − ⋯ + x_{n+1} − x_{n}|
≤ |x_{m} − x_{m−1}| + |x_{m−1} − x_{m−2}| + ⋯ + |x_{n+1} − x_{n}|
≤ k^{m−1}|x_{1} − x_{0}| + k^{m−2}|x_{1} − x_{0}| + ⋯ + k^{n}|x_{1} − x_{0}|
= k^{n}|x_{1} − x_{0}| (1 + k + k^{2} + ⋯ + k^{m−n−1}).

It implies that

|x − x_{n}| = lim_{m→∞}|x_{m} − x_{n}| ≤ lim_{m→∞}k^{n}|x_{1} − x_{0}| ∑_{j=0}^{m−n−1}k^{j}

≤ k^{n}|x_{1} − x_{0}| ∑_{j=0}^{∞}k^{j} = \frac{k^{n}}{1 − k}|x_{1} − x_{0}|.

university-logo

Example

For previous example,

f (x) = x^{3} + 4x^{2} − 10 = 0.

For g_{1}(x) = x − x^{3} − 4x^{2} + 10, we have

g_{1}(1) = 6 and g_{1}(2) = −12,

so g_{1}([1, 2]) ⊈ [1, 2]. Moreover,

g′_{1}(x) = 1 − 3x^{2} − 8x ⇒ |g′_{1}(x)| ≥ 1 ∀ x ∈ [1, 2]

• DOES NOT guarantee to converge or not

university-logo

For g_{3}(x) = \frac{1}{2}(10 − x^{3})^{1/2}, ∀ x ∈ [1, 1.5],

g′_{3}(x) = −\frac{3}{4}x^{2}(10 − x^{3})^{−1/2} < 0, ∀ x ∈ [1, 1.5],

so g_{3} is strictly decreasing on [1, 1.5] and

1 < 1.28 ≈ g_{3}(1.5) ≤ g_{3}(x) ≤ g_{3}(1) = 1.5, ∀ x ∈ [1, 1.5].

On the other hand,

|g′_{3}(x)| ≤ |g′_{3}(1.5)| ≈ 0.66, ∀ x ∈ [1, 1.5]

Hence, the sequence is convergent to the fixed point.

university-logo

For g_{4}(x) = \sqrt{10/(4 + x)}, we have

\sqrt{\frac{10}{6}} ≤ g_{4}(x) ≤ \sqrt{\frac{10}{5}}, ∀ x ∈ [1, 2] ⇒ g_{4}([1, 2]) ⊆ [1, 2]

Moreover,

|g′_{4}(x)| = |\frac{−5}{\sqrt{10}(4 + x)^{3/2}} | ≤ \frac{5}{\sqrt{10}(5)^{3/2}} < 0.15, ∀ x ∈ [1, 2].

The bound of |g′_{4}(x)| is much smaller than the bound of |g′_{3}(x)|, which explains the more rapid convergence using g_{4}.

university-logo

Newton’s method

Suppose that f : ℝ → ℝ and f ∈ C^{2}[a, b], i.e., f′′ exists and is continuous. If f (x^{∗}) = 0 and x^{∗} = x + h where h is small, then by Taylor’s theorem

0 = f (x^{∗}) = f (x + h)
= f (x) + f′(x)h + \frac{1}{2}f′′(x)h^{2} + \frac{1}{3!}f′′′(x)h^{3} + ⋯
= f (x) + f′(x)h + O(h^{2}).

Since h is small, O(h^{2}) is negligible. It is reasonable to drop O(h^{2}) terms. This implies

f (x) + f′(x)h ≈ 0 and h ≈ −\frac{f (x)}{f′(x)}, if f′(x) ≠ 0.

Hence

x + h = x − \frac{f (x)}{f′(x)}

is a better approximation to x^{∗}.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  29 / 1

university-logo

This sets the stage for the Newton-Rapbson’s method, which starts with an initial approximation x_{0} and generates the sequence {x_{n}}_{n=0}^{∞} defined by

x_{n+1} = x_{n} − \frac{f (x_{n})}{f′(x_{n})}.

Since the Taylor’s expansion of f (x) at x_{k} is given by

f (x) = f (x_{k}) + f′(x_{k})(x − x_{k}) + \frac{1}{2}f′′(x_{k})(x − x_{k})^{2} + · · · .

At x_{k}, one uses the tangent line

y = ℓ(x) = f (x_{k}) + f′(x_{k})(x − x_{k})

to approximate the curve of f (x) and uses the zero of the tangent line to approximate the zero of f (x).

university-logo

Newton’s Method

Given x_{0}, tolerance TOL, maximum number of iteration M. Set i = 1 and x = x_{0} − f (x_{0})/f′(x_{0}). While i ≤ M and |x − x_{0}| ≥ TOL

Set i = i + 1, x_{0} = x and x = x_{0} − f (x_{0})/f′(x_{0}). End While

university-logo

Three stopping-technique inequalities

(a). |x_{n} − x_{n−1}| < ε,
(b). \frac{|x_{n} − x_{n−1}|}{|x_{n}|} < ε, x_{n} ≠ 0,
(c). |f (x_{n})| < ε.

Note that Newton’s method for solving f (x) = 0

x_{n+1} = x_{n} − \frac{f (x_{n})}{f′(x_{n})}, for n ≥ 1

is just a special case of functional iteration in which

g(x) = x − \frac{f (x)}{f′(x)}.

university-logo

Example

The following table shows the convergence behavior of Newton’s method applied to solving f (x) = x^{2} − 1 = 0. Observe the quadratic convergence rate.

n x_{n}  |e_{n}| ≡ |1 − x_{n}|
0 2.0  1
1 1.25  0.25
2 1.025  2.5e-2
3 1.0003048780488 3.048780488e-4
4 1.0000000464611 4.64611e-8
5 1.0  0

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  33 / 1

university-logo

Theorem

Assume f (x^{∗}) = 0, f′(x^{∗}) ≠ 0 and f (x), f′(x) and f′′(x) are continuous on N_{ε}(x^{∗}). Then if x_{0} is chosen sufficiently close to x^{∗}, then

\{x_{n+1} = x_{n} − \frac{f (x_{n})}{f′(x_{n})}\} → x^{∗}.

Proof: Define

g(x) = x − \frac{f (x)}{f′(x)}.

Find an interval [x^{∗} − δ, x^{∗} + δ] such that

g([x^{∗} − δ, x^{∗} + δ]) ⊆ [x^{∗} − δ, x^{∗} + δ]

and

|g′(x)| ≤ k < 1, ∀ x ∈ (x^{∗} − δ, x^{∗} + δ).

university-logo

Since f′ is continuous and f′(x^{∗}) ≠ 0, it implies that ∃ δ_{1} > 0 such that f′(x) ≠ 0 ∀ x ∈ [x^{∗} − δ_{1}, x^{∗} + δ_{1}] ⊆ [a, b]. Thus, g is defined and continuous on [x^{∗} − δ_{1}, x^{∗} + δ_{1}]. Also

g′(x) = 1 − \frac{f′(x)f′(x) − f (x)f′′(x)}{[f′(x)]^{2}} = \frac{f (x)f′′(x)}{[f′(x)]^{2}},

for x ∈ [x^{∗} − δ_{1}, x^{∗} + δ_{1}]. Since f′′ is continuous on [a, b], we have g′ is continuous on [x^{∗} − δ_{1}, x^{∗} + δ_{1}]. By assumption f (x^{∗}) = 0, so

g′(x^{∗}) = \frac{f (x^{∗})f′′(x^{∗})}{|f′(x^{∗})|^{2}} = 0.

Since g′ is continuous on [x^{∗} − δ_{1}, x^{∗} + δ_{1}] and g′(x^{∗}) = 0, ∃ δ with 0 < δ < δ_{1} and k ∈ (0, 1) such that

|g′(x)| ≤ k, ∀ x ∈ [x^{∗} − δ, x^{∗} + δ].

university-logo

Claim: g([x^{∗} − δ, x^{∗} + δ]) ⊆ [x^{∗} − δ, x^{∗} + δ]. If x ∈ [x^{∗} − δ, x^{∗} + δ], then, by the Mean Value Theorem, ∃ ξ between x and x^{∗} such that

|g(x) − g(x^{∗})| = |g′(ξ)||x − x^{∗}|.

It implies that

|g(x) − x^{∗}| = |g(x) − g(x^{∗})| = |g′(ξ)||x − x^{∗}|
≤ k|x − x^{∗}| < |x − x^{∗}| < δ.

Hence, g([x^{∗} − δ, x^{∗} + δ]) ⊆ [x^{∗} − δ, x^{∗} + δ]. By the Fixed-Point Theorem, the sequence {x_{n}}_{n=0}^{∞} defined by

x_{n} = g(x_{n−1}) = x_{n−1} − \frac{f (x_{n−1})}{f′(x_{n−1})}, for n ≥ 1,

converges to x^{∗} for any x_{0} ∈ [x^{∗} − δ, x^{∗} + δ].

university-logo

Example

When Newton’s method applied to f (x) = cos x with starting point x_{0} = 3, which is close to the root \frac{π}{2} of f , it produces x_{1} = −4.01525, x_{2} = −4.8526, ⋯, which converges to another root −\frac{3π}{2} .

university-logo

Secant method

Disadvantage of Newton’s method

In many applications, the derivative f′(x) is very expensive to compute, or the function f (x) is not given in an algebraic formula so that f′(x) is not available.

By definition,

f′(x_{n−1}) = lim_{x→x_{n−1}} \frac{f (x) − f (x_{n−1})}{x − x_{n−1}}.

Letting x = x_{n−2}, we have

f′(x_{n−1}) ≈ \frac{f (x_{n−2}) − f (x_{n−1})}{x_{n−2} − x_{n−1}} = \frac{f (x_{n−1}) − f (x_{n−2})}{x_{n−1} − x_{n−2}}.

Using this approximation for f′(x_{n−1}) in Newton’s formula gives

x_{n} = x_{n−1} − \frac{f (x_{n−1})(x_{n−1} − x_{n−2})}{f (x_{n−1}) − f (x_{n−2})},

which is called the Secant method.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  38 / 1

university-logo

From geometric point of view, we use a secant line through x_{n−1} and x_{n−2} instead of the tangent line to approximate the function at the point x_{n−1}. The slope of the secant line is

s_{n−1} = \frac{f (x_{n−1}) − f (x_{n−2})}{x_{n−1} − x_{n−2}}

and the equation is

M(x) = f (x_{n−1}) + s_{n−1}(x − x_{n−1}).

The zero of the secant line

x = x_{n−1} − \frac{f (x_{n−1})}{s_{n−1}} = x_{n−1} − f (x_{n−1})\frac{x_{n−1} − x_{n−2}}{f (x_{n−1}) − f (x_{n−2})}

is then used as a new approximate x_{n}.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  39 / 1

university-logo

Secant Method

Given x_{0}, x_{1}, tolerance TOL, maximum number of iteration M. Set i = 2; y_{0} = f (x_{0}); y_{1} = f (x_{1});

x = x_{1} − y_{1}(x_{1} − x_{0})/(y_{1} − y_{0}). While i ≤ M and |x − x_{1}| ≥ TOL

Set i = i + 1; x_{0} = x_{1}; y_{0} = y_{1}; x_{1} = x; y_{1} = f (x);

x = x_{1} − y_{1}(x_{1} − x_{0})/(y_{1} − y_{0}). End While

university-logo

Method of False Position

1 Choose initial approximations x_{0} and x_{1} with f (x_{0})f (x_{1}) < 0. 2 x_{2} = x_{1} − f (x_{1})(x_{1} − x_{0})/(f (x_{1}) − f (x_{0})) 3 Decide which secant line to use to compute x_{3}:

If f (x_{2})f (x_{1}) < 0, then x_{1} and x_{2} bracket a root, i.e.,

x_{3} = x_{2} − f (x_{2})(x_{2} − x_{1})/(f (x_{2}) − f (x_{1}))

Else, x_{0} and x_{2} bracket a root, i.e.,

x_{3} = x_{2} − f (x_{2})(x_{2} − x_{0})/(f (x_{2}) − f (x_{0}))

End if

university-logo

Method of False Position

Given x_{0}, x_{1}, tolerance TOL, maximum number of iteration M. Set i = 2; y_{0} = f (x_{0}); y_{1} = f (x_{1}); x = x_{1} − y_{1}(x_{1} − x_{0})/(y_{1} − y_{0}). While i ≤ M and |x − x_{1}| ≥ TOL

Set i = i + 1; y = f (x).

If y · y_{1} < 0, then set x_{0} = x_{1}; y_{0} = y_{1}.

Set x_{1} = x; y_{1} = y; x = x_{1} − y_{1}(x_{1} − x_{0})/(y_{1} − y_{0}). End While

university-logo

Error analysis for iterative methods

Definition

Let {x_{n}} → x^{∗}. If there are positive constants c and α such that

lim_{n→∞} \frac{|x_{n+1} − x^{∗}|}{|x_{n} − x^{∗}|^{α}} = c,

then we say the rate of convergence is of order α.

We say that the rate of convergence is 1 linear if α = 1 and 0 < c < 1. 2 superlinear if

lim_{n→∞} \frac{|x_{n+1} − x^{∗}|}{|x_{n} − x^{∗}|} = 0;

3 quadratic if α = 2.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  43 / 1

university-logo

Suppose that {x_{n}}_{n=0}^{∞} and {x̃_{n}}_{n=0}^{∞} are linearly and quadratically convergent to x^{∗}, respectively, with the same constant c = 0.5. For simplicity, suppose that

\frac{|x_{n+1} − x^{∗}|}{|x_{n} − x^{∗}|} ≈ c and \frac{|x̃_{n+1} − x^{∗}|}{|x̃_{n} − x^{∗}|^{2}} ≈ c.

These imply that

|x_{n} − x^{∗}| ≈ c|x_{n−1} − x^{∗}| ≈ c^{2}|x_{n−2} − x^{∗}| ≈ ⋯ ≈ c^{n}|x_{0} − x^{∗}|,

and

|x̃_{n} − x^{∗}| ≈ c|x̃_{n−1} − x^{∗}|^{2} ≈ c [c|x̃_{n−2} − x^{∗}|^{2}]^{2} = c^{3}|x̃_{n−2} − x^{∗}|^{4}
≈ c^{3} [c|x̃_{n−3} − x^{∗}|^{2}]^{4} = c^{7}|x̃_{n−3} − x^{∗}|^{8}
≈ ⋯ ≈ c^{2^{n}−1}|x̃_{0} − x^{∗}|^{2^{n}}.

university-logo

Remark

Quadratically convergent sequences generally converge much more quickly thank those that converge only linearly.

Theorem

Let g ∈ C[a, b] with g([a, b]) ⊆ [a, b]. Suppose that g′ is continuous on (a, b) and ∃ k ∈ (0, 1) such that

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

If g′(x^{∗}) ≠ 0, then for any x_{0} ∈ [a, b], the sequence

x_{n} = g(x_{n−1}), for n ≥ 1

converges only linearly to the unique fixed point x^{∗} in [a, b].

university-logo

Proof:

By the Fixed-Point Theorem, the sequence {x_{n}}_{n=0}^{∞} converges to x^{∗}. Since g′ exists on (a, b), by the Mean Value Theorem, ∃ ξ_{n} between x_{n} and x^{∗} such that

x_{n+1} − x^{∗} = g(x_{n}) − g(x^{∗}) = g′(ξ_{n})(x_{n} − x^{∗}).

∵ {x_{n}}_{n=0}^{∞} → x^{∗} ⇒ {ξ_{n}}_{n=0}^{∞} → x^{∗} Since g′ is continuous on (a, b), we have

lim_{n→∞}g′(ξ_{n}) = g′(x^{∗}).

Thus,

lim_{n→∞} \frac{|x_{n+1} − x^{∗}|}{|x_{n} − x^{∗}|} = lim_{n→∞}|g′(ξ_{n})| = |g′(x^{∗})|.

Hence, if g′(x^{∗}) ≠ 0, fixed-point iteration exhibits linear convergence.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  46 / 1

university-logo

Theorem

Let x^{∗} be a fixed point of g and I be an open interval with x^{∗} ∈ I . Suppose that g′(x^{∗}) = 0 and g′′ is continuous with

|g′′(x)| < M, ∀ x ∈ I .

Then ∃ δ > 0 such that

{x_{n} = g(x_{n−1})}_{n=1}^{∞} → x^{∗} for x_{0} ∈ [x^{∗} − δ, x^{∗} + δ]

at least quadratically. Moreover,

|x_{n+1} − x^{∗}| < \frac{M}{2} |x_{n} − x^{∗}|^{2}, for sufficiently large n.

university-logo

Proof:

Since g′(x^{∗}) = 0 and g′ is continuous on I , ∃ δ such that [x^{∗} − δ, x^{∗} + δ] ⊂ I and

|g′(x)| ≤ k < 1, ∀ x ∈ [x^{∗} − δ, x^{∗} + δ].

In the proof of the convergence for Newton’s method, we have

{x_{n}}_{n=0}^{∞} ⊂ [x^{∗} − δ, x^{∗} + δ].

Consider the Taylor expansion of g(x_{n}) at x^{∗}

x_{n+1} = g(x_{n}) = g(x^{∗}) + g′(x^{∗})(x_{n} − x^{∗}) + \frac{g′′(ξ)}{2}(x_{n} − x^{∗})^{2}
= x^{∗} + \frac{g′′(ξ)}{2}(x_{n} − x^{∗})^{2},

where ξ lies between x_{n} and x^{∗}.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  48 / 1

university-logo

Since

|g′(x)| ≤ k < 1, ∀ x ∈ [x^{∗} − δ, x^{∗} + δ]

and

g([x^{∗} − δ, x^{∗} + δ]) ⊆ [x^{∗} − δ, x^{∗} + δ],

it follows that {x_{n}}_{n=0}^{∞} converges to x^{∗}. But ξ_{n} is between x_{n} and x^{∗} for each n, so {ξ_{n}}_{n=0}^{∞} also converges to x^{∗} and

lim_{n→∞} \frac{|x_{n+1} − x^{∗}|}{|x_{n} − x^{∗}|^{2}} = \frac{|g′′(x^{∗})|}{2} < \frac{M}{2} .

It implies that {x_{n}}_{n=0}^{∞} is quadratically convergent to x^{∗} if g′′(x^{∗}) ≠ 0 and

|x_{n+1} − x^{∗}| < \frac{M}{2} |x_{n} − x^{∗}|^{2}, for sufficiently large n.

university-logo

For Newton’s method,

g(x) = x − \frac{f (x)}{f′(x)} ⇒ g′(x) = 1 − \frac{f′(x)}{f′(x)} + \frac{f (x)f′′(x)}{(f′(x))^{2}} = \frac{f (x)f′′(x)}{(f′(x))^{2}}

It follows that g′(x^{∗}) = 0. Hence Newton’s method is locally quadratically convergent.

university-logo

Error Analysis of Secant Method

Reference: D. Kincaid and W. Cheney, ”Numerical analysis” Let x^{∗} denote the exact solution of f (x) = 0, e_{k} = x_{k} − x^{∗} be the errors at the k-th step. Then

e_{k+1} = x_{k+1} − x^{∗}
= x_{k} − f (x_{k})\frac{x_{k} − x_{k−1}}{f (x_{k}) − f (x_{k−1})} − x^{∗}
= \frac{1}{f (x_{k}) − f (x_{k−1})} [(x_{k−1} − x^{∗})f (x_{k}) − (x_{k} − x^{∗})f (x_{k−1})]
= \frac{1}{f (x_{k}) − f (x_{k−1})} (e_{k−1}f (x_{k}) − e_{k}f (x_{k−1}))

= e_{k}e_{k−1} ( \frac{\frac{1}{e_{k}} f (x_{k}) − \frac{1}{e_{k−1}}f (x_{k−1})}{x_{k} − x_{k−1}} · \frac{x_{k} − x_{k−1}}{f (x_{k}) − f (x_{k−1})})

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  51 / 1

university-logo

To estimate the numerator ^{\frac{\frac{1}{e_{k}} f (x_{k})− \frac{1}{e_{k−1}} f (x_{k})}{x_{k}−x_{k−1}}}, we apply the Taylor’s theorem

f (x_{k}) = f (x^{∗} + e_{k}) = f (x^{∗}) + f′(x^{∗})e_{k} + \frac{1}{2}f′′(x^{∗})e_{k}^{2} + O(e_{k}^{3}),

to get

\frac{1}{e_{k}} f (x_{k}) = f′(x^{∗}) + \frac{1}{2}f′′(x^{∗})e_{k} + O(e_{k}^{2}).

Similarly,

\frac{1}{e_{k−1}}f (x_{k−1}) = f′(x^{∗}) + \frac{1}{2}f′′(x^{∗})e_{k−1} + O(e_{k−1}^{2}).

Hence

\frac{1}{e_{k}} f (x_{k}) − \frac{1}{e_{k−1}}f (x_{k−1}) ≈ \frac{1}{2}(e_{k} − e_{k−1})f′′(x^{∗}).

Since x_{k} − x_{k−1} = e_{k} − e_{k−1} and

\frac{x_{k} − x_{k−1}}{f (x_{k}) − f (x_{k−1})} → \frac{1}{f′(x^{∗})},

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  52 / 1

university-logo

we have

e_{k+1} ≈ e_{k}e_{k−1} ( \frac{\frac{1}{2}(e_{k} − e_{k−1})f′′(x^{∗})}{e_{k} − e_{k−1}} · \frac{1}{f′(x^{∗})}) = \frac{1}{2} \frac{f′′(x^{∗})}{f′(x^{∗})}e_{k}e_{k−1}
≡ Ce_{k}e_{k−1}  (2)

To estimate the convergence rate, we assume

|e_{k+1}| ≈ η|e_{k}|^{α},

where η > 0 and α > 0 are constants, i.e.,

\frac{|e_{k+1}|}{η|e_{k}|^{α}} → 1 as k → ∞.

Then |e_{k}| ≈ η|e_{k−1}|^{α} which implies |e_{k−1}| ≈ η^{−1/α}|e_{k}|^{1/α}. Hence (2) gives

η|e_{k}|^{α} ≈ C|e_{k}|η^{−1/α}|e_{k}|^{1/α} ⟹ C^{−1}η^{1+ \frac{1}{α}} ≈ |e_{k}|^{1−α+ \frac{1}{α}} .

Since |e_{k}| → 0 as k → ∞, and C^{−1}η^{1+ \frac{1}{α}} is a nonzero constant,

1 − α + \frac{1}{α} = 0 ⟹ α = \frac{1 + \sqrt{5}}{2} ≈ 1.62.

university-logo

This result implies that C^{−1}η^{1+ \frac{1}{α}} → 1 and

η → C^{\frac{α}{1+α}} = (\frac{f′′(x^{∗})}{2f′(x^{∗})})^{0.62} .

In summary, we have shown that

|e_{k+1}| = η|e_{k}|^{α}, α ≈ 1.62,

that is, the rate of convergence is superlinear. Rate of convergence:

secant method: superlinear Newton’s method: quadratic bisection method: linear

university-logo

Each iteration of method requires secant method: one function evaluation Newton’s method: two function evaluation, namely, f (x_{k}) and f′(x_{k}). ⇒ two steps of secant method are comparable to one step of Newton’s method. Thus

|e_{k+2}| ≈ η|e_{k+1}|^{α} ≈ η^{1+α}|e_{k}|^{\frac{3+\sqrt{5}}{2}} ≈ η^{1+α}|e_{k}|^{2.62}.

⇒ secant method is more efficient than Newton’s method.

Remark

Two steps of secant method would require a little more work than one step of Newton’s method.

university-logo

Accelerating convergence

Aitken’s Δ^{2} method

Accelerate the convergence of a sequence that is linearly convergent. Suppose {y_{n}}_{n=0}^{∞} is a linearly convergent sequence with limit y. Construct a sequence {ŷ_{n}}_{n=0}^{∞} that converges more rapidly to y than {y_{n}}_{n=0}^{∞}.

For n sufficiently large,

\frac{y_{n+1} − y}{y_{n} − y} ≈ \frac{y_{n+2} − y}{y_{n+1} − y} .

Then

(y_{n+1} − y)^{2} ≈ (y_{n+2} − y)(y_{n} − y),

so

y_{n+1}^{2} − 2y_{n+1}y + y^{2} ≈ y_{n+2}y_{n} − (y_{n+2} + y_{n})y + y^{2}

university-logo

and

(y_{n+2} + y_{n} − 2y_{n+1})y ≈ y_{n+2}y_{n} − y_{n+1}^{2}.

Solving for y gives

y ≈ \frac{y_{n+2}y_{n} − y_{n+1}^{2}}{y_{n+2} − 2y_{n+1} + y_{n}}
= \frac{y_{n}y_{n+2} − 2y_{n}y_{n+1} + y_{n}^{2} − y_{n}^{2} + 2y_{n}y_{n+1} − y_{n+1}^{2}}{y_{n+2} − 2y_{n+1} + y_{n}}
= \frac{y_{n}(y_{n+2} − 2y_{n+1} + y_{n}) − (y_{n+1} − y_{n})^{2}}{(y_{n+2} − y_{n+1}) − (y_{n+1} − y_{n})}
= y_{n} − \frac{(y_{n+1} − y_{n})^{2}}{(y_{n+2} − y_{n+1}) − (y_{n+1} − y_{n})}.

Aitken’s Δ^{2} method

ŷ_{n} = y_{n} − \frac{(y_{n+1} − y_{n})^{2}}{(y_{n+2} − y_{n+1}) − (y_{n+1} − y_{n})}.  (3)

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  57 / 1

university-logo

Example

The sequence {y_{n} = cos(1/n)}_{n=1}^{∞} converges linearly to y = 1.

n  y_{n}  ŷ_{n}
1 0.54030 0.96178
2 0.87758 0.98213
3 0.94496 0.98979
4 0.96891 0.99342
5 0.98007 0.99541
6 0.98614
7 0.98981

{ŷ_{n}}_{n=1}^{∞} converges more rapidly to y = 1 than {y_{n}}_{n=1}^{∞}.

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  58 / 1

university-logo

Definition

For a given sequence {y_{n}}_{n=0}^{∞}, the forward difference Δy_{n} is defined by

Δy_{n} = y_{n+1} − y_{n}, for n ≥ 0.

Higher powers of Δ are defined recursively by

Δ^{k}y_{n} = Δ(Δ^{k−1}y_{n}), for k ≥ 2.

The definition implies that Δ^{2}y_{n} = Δ(y_{n+1} − y_{n}) = Δy_{n+1} − Δy_{n} = (y_{n+2} − y_{n+1}) − (y_{n+1} − y_{n}). So the formula for ŷ_{n} in (3) can be written as

ŷ_{n} = y_{n} − \frac{(Δy_{n})^{2}}{Δ^{2}y_{n}}, for n ≥ 0.

university-logo

Theorem

Suppose {y_{n}}_{n=0}^{∞} → y linearly and

lim_{n→∞} \frac{y_{n+1} − y}{y_{n} − y} < 1.

Then {ŷ_{n}}_{n=0}^{∞} → y faster than {y_{n}}_{n=0}^{∞} in the sense that

lim_{n→∞} \frac{ŷ_{n} − y}{y_{n} − y} = 0.

Aitken’s Δ^{2} method constructs the terms in order:

y_{0}, y_{1} = g(y_{0}), y_{2} = g(y_{1}), ŷ_{0} = {Δ^{2}}(y_{0}), y_{3} = g(y_{2}),

ŷ_{1} = {Δ^{2}}(y_{1}), ….

⇒ Assume |ŷ_{0} − y| < |y_{2} − y|

university-logo

Steffensen’s method constructs the terms in order:

y_{0}^{(0)} ≡ y_{0}, y_{1}^{(0)} = g(y_{0}^{(0)}), y_{2}^{(0)} = g(y_{1}^{(0)}),

y_{0}^{(1)} = {Δ^{2}}(y_{0}^{(0)}), y_{1}^{(1)} = g(y_{0}^{(1)}), y_{2}^{(1)} = g(y_{1}^{(1)}), ….

Steffensen’s method (To find a solution of y = g(y))

Given y_{0}, tolerance TOL, maximum number of iteration M. Set i = 1. While i ≤ M

Set y_{1} = g(y_{0}); y_{2} = g(y_{1}); y = y_{0} − (y_{1} − y_{0})^{2}/(y_{2} − 2y_{1} + y_{0}). If |y − y_{0}| < Tol, then STOP. Set i = i + 1; y_{0} = y.

End While

Theorem

Suppose that x = g(x) has the solution x^{∗} with g′(x^{∗}) ≠ 1. If ∃ δ > 0 such that g ∈ C^{3}[x^{∗} − δ, x^{∗} + δ], then Steffensen’s method gives quadratic convergence for any x_{0} ∈ [x^{∗} − δ, x^{∗} + δ].

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  61 / 1

university-logo

Zeros of polynomials and Müller’s method

• Horner’s method: Let

P(x) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n−1}x^{n−1} + a_{n}x^{n}
= a_{0} + x (a_{1} + x (a_{2} + ⋯ + x (a_{n−1} + a_{n}x)⋯))

If

b_{n} = a_{n},
b_{k} = a_{k} + b_{k+1}x_{0}, for k = n − 1, n − 2, …, 1, 0,

then

b_{0} = a_{0} + b_{1}x_{0} = a_{0} + (a_{1} + b_{2}x_{0})x_{0} = ⋯ = P(x_{0}).

Consider

Q(x) = b_{1} + b_{2}x + ⋯ + b_{n}x^{n−1}.
Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  62 / 1

university-logo

Then

b_{0} + (x − x_{0})Q(x) = b_{0} + (x − x_{0}) (b_{1} + b_{2}x + ⋯ + b_{n}x^{n−1})
= (b_{0} − b_{1}x_{0}) + (b_{1} − b_{2}x_{0})x + ⋯ + (b_{n−1} − b_{n}x_{0})x^{n−1} + b_{n}x^{n}
= a_{0} + a_{1}x + ⋯ + a_{n}x^{n} = P(x).

Differentiating P(x) with respect to x gives

P′(x) = Q(x) + (x − x_{0})Q′(x) and P′(x_{0}) = Q(x_{0}).

Use Newton-Raphson method to find an approximate zero of P(x):

x_{k+1} = x_{k} − \frac{P(x_{k})}{Q(x_{k})}, ∀ k = 0, 1, 2, ….

Similarly, let

c_{n} = b_{n} = a_{n},
c_{k} = b_{k} + c_{k+1}x_{k}, for k = n − 1, n − 2, …, 1,

then c_{1} = Q(x_{k}).

Wei-Cheng Wang (NTHU )  Solutions of Equations in One Variable  Fall 2010  63 / 1

university-logo

Horner’s method (Evaluate y = P(x_{0}) and z = P′(x_{0}))

Set y = a_{n}; z = a_{n}. For j = n − 1, n − 2, …, 1

Set y = a_{j} + yx_{0}; z = y + zx_{0}. End for Set y = a_{0} + yx_{0}.

If x_{N} is an approximate zero of P, then

P(x) = (x − x_{N})Q(x) + b_{0} = (x − x_{N})Q(x) + P(x_{N})
≈ (x − x_{N})Q(x) ≡ (x − x̂_{1})Q_{1}(x).

So x − x̂_{1} is an approximate factor of P(x) and we can find a second approximate zero of P by applying Newton’s method to Q_{1}(x). The procedure is called deflation.

university-logo

• Müller’s method for complex root:

Theorem

If z = a + ib is a complex zero of multiplicity m of P(x) with real coefficients, then z̄ = a − bi is also a zero of multiplicity m of P(x) and (x^{2} − 2ax + a^{2} + b^{2})^{m} is a factor of P(x).

Secant method: Given p_{0} and p_{1}, determine p_{2} as the intersection of the x-axis with the line through (p_{0}, f (p_{0})) and (p_{1}, f (p_{1})).

Müller’s method: Given p_{0}, p_{1} and p_{2}, determine p_{3} by the intersection of the x-axis with the parabola through (p_{0}, f (p_{0})), (p_{1}, f (p_{1})) and (p_{2}, f (p_{2})).

university-logo

• Müller’s method for complex root:

Theorem

If z = a + ib is a complex zero of multiplicity m of P(x) with real coefficients, then z̄ = a − bi is also a zero of multiplicity m of P(x) and (x^{2} − 2ax + a^{2} + b^{2})^{m} is a factor of P(x).

Secant method: Given p_{0} and p_{1}, determine p_{2} as the intersection of the x-axis with the line through (p_{0}, f (p_{0})) and (p_{1}, f (p_{1})).

Müller’s method: Given p_{0}, p_{1} and p_{2}, determine p_{3} by the intersection of the x-axis with the parabola through (p_{0}, f (p_{0})), (p_{1}, f (p_{1})) and (p_{2}, f (p_{2})).

university-logo

Let

P(x) = a(x − p_{2})^{2} + b(x − p_{2}) + c

that passes through (p_{0}, f (p_{0})), (p_{1}, f (p_{1})) and (p_{2}, f (p_{2})). Then

f (p_{0}) = a(p_{0} − p_{2})^{2} + b(p_{0} − p_{2}) + c,
f (p_{1}) = a(p_{1} − p_{2})^{2} + b(p_{1} − p_{2}) + c,
f (p_{2}) = a(p_{2} − p_{2})^{2} + b(p_{2} − p_{2}) + c = c.

It implies that

c = f (p_{2}),
b = \frac{(p_{0} − p_{2})^{2} [f (p_{1}) − f (p_{2})] − (p_{1} − p_{2})^{2} [f (p_{0}) − f (p_{2})]}{(p_{0} − p_{2})(p_{1} − p_{2})(p_{0} − p_{1})},
a = \frac{(p_{1} − p_{2}) [f (p_{0}) − f (p_{2})] − (p_{0} − p_{2}) [f (p_{1}) − f (p_{2})]}{(p_{0} − p_{2})(p_{1} − p_{2})(p_{0} − p_{1})}.

university-logo

To determine p_{3}, a zero of P, we apply the quadratic formula to P(x) = 0 and get

p_{3} − p_{2} = \frac{2c}{b ± \sqrt{b^{2} − 4ac}}.

Choose

p_{3} = p_{2} + \frac{2c}{b + sgn(b)\sqrt{b^{2} − 4ac}}

such that the denominator will be largest and result in p_{3} selected as the closest zero of P to p_{2}.

university-logo

Müller’s method (Find a solution of f (x) = 0)

Given p_{0}, p_{1}, p_{2}; tolerance TOL; maximum number of iterations M Set h_{1} = p_{1} − p_{0}; h_{2} = p_{2} − p_{1};

δ_{1} = (f (p_{1}) − f (p_{0}))/h_{1}; δ_{2} = (f (p_{2}) − f (p_{1}))/h_{2}; d = (δ_{2} − δ_{1})/(h_{2} + h_{1}); i = 3.

While i ≤ M Set b = δ_{2} + h_{2}d; D = \sqrt{b^{2} − 4f (p_{2})d}. If |b − D| < |b + D|, then set E = b + D else set E = b − D. Set h = −2f (p_{2})/E; p = p_{2} + h. If |h| < TOL, then STOP. Set p_{0} = p_{1}; p_{1} = p_{2}; p_{2} = p; h_{1} = p_{1} − p_{0}; h_{2} = p_{2} − p_{1};

δ_{1} = (f (p_{1}) − f (p_{0}))/h_{1}; δ_{2} = (f (p_{2}) − f (p_{1}))/h_{2}; d = (δ_{2} − δ_{1})/(h_{2} + h_{1}); i = i + 1.

End while