Successive Substitution: Theory and Example

Iteration

Suppose we wish to solve f (x) = 0 where:

f (x) = x − 1

2(x + A x)

Here A > 0 is some given constant. Obviously this equation has two solutions, namely x = ±A¹²

This formula is credited to Heron (a common name) of Alexandria, a Greek engineer and architect who lived somewhere between 100B.C. and A.D. 100. Incidentally the Babylonians also knew of the formula 2000 years earlier.

Let g(x) = ¹₂(x + ^A_x) so that f(x) = 0 is equivalent to x = g(x)

since

f (x) = 0 = x − 1

2(x + A x) x = 1

2(x + A

x) = g(x)

Let x₀ > 0 be a first approximation to A¹².

define x₁ = g(x₀), x₂ = g(x₁), . . . , x_n+1 = g(x_n).

This is known as successive substituion or iteration.

Iteration: Example

f (x) = x − 1

2(x + A

x), A = 5, x₀ = 2

We first need to find a g(x) such that f (x) = 0 is that same as x = g(x)

So in our case as we have seen g(x) = 1

2(x + A x)

We also would like to be able to measure the accuracy of our solution. In this case _n = |x²n − 5|.

So the sequence {xⁿ} is:

x₀ = 2 ₀ = 1

x₁ = ¹₂(2 + ⁵₂) = ⁹₄ ₁ = (¹₄)² x₂ = ¹₂(⁹₄ + ⁵₉

4

) = ¹⁶¹₇₂ ₂ = (₇₂¹ )² x₃ = ¹₂(¹⁶¹₇₂ + ₁₆₁⁵

72

) = ⁵¹⁸⁴¹₂₃₁₈₄ ₃ = (₂₃₁₈₄¹ )²

Iteration: Example

Say we want to compute square roots and use Newton’s Method. Let R > 0, and let’s set x = p(R).

Then x is a root of the equation x² − R = 0.

Let’s apply Newton’s method.

f (x) = x² − R f⁰(x) = 2x

x_n+1 = x_n − _f^{f (x0}_(xⁿ_n⁾₎

= x_n − ^x_2x^2n−R_n

= ^2x2n−x_2x^2n−R

n

= ^x_2x^2n−R

= ¹₂(xn_n − _x^R_n)

We’ve seen this!

Iteration: Example

If we want to calculate √

17 with an initial approximation of 4, the sequence {xⁿ} is:

x₀ = 4 x₁ = 4.12

x₂ = 4.123106

x₃ = 4.1231056256177

x₄ = 4.123105625617660549821409856

So the number of correct digits for the sequence is 1, 3, 6, 14, 28. We converge very rapidly and see the doubling of correct digits.

Fixed Point Iteration

We compute a sequence of points with a formula of the form

x_n+1 = g(x_n)

The algorithm defined by such an equation is called functional iteration. In Newton’s method g is:

g(x) = x − f (x) f⁰(x)

With our iteration formula we can generate sequences that don’t converge, or ones that do, which is what we are interested in. If the sequence {xⁿ} converges then lim_n→∞ x_n exists. Suppose that lim_n→∞x_n = s.

How does s and g relate if g is continous?

g(s) = g( lim

n→∞x_n) = lim

n→∞g(x_n) = lim

n→∞x_n+1 = s So g(s) = s, and we call s a fixed point of g, that is s remains fixed under successive application of the function g(x).

Contractive Mapping Theorem

A mapping F is said to be contractive if there exists a number λ < 1 such that

|F (x) − F (y)| ≤ λ|x − y|

s

x

s

y F (x) s

F (y) s

Contractive Mapping Theorem Let C be a closed subset of the real line. If F is a contractive mapping of C into C, then F has a unique fixed point and this fixed point is the limit of every sequence obtained by x_n+1 = F (x_n) with a starting point x₀ ∈ C

Contractive Mapping Theorem: Proof

Lets use the contractive property and the iteration formula to obtain:

|xⁿ−xⁿ⁻¹| = |F (xⁿ⁻¹) −F (xⁿ⁻²)| ≤ λ|xⁿ⁻¹−xⁿ⁻²|

Repeat again to get:

|xⁿ−xⁿ⁻¹| ≤ λ|xⁿ⁻¹−xⁿ⁻²| ≤ λ²|xⁿ⁻²−xⁿ⁻³| ≤ . . .

≤ λⁿ⁻¹|x¹ − x⁰| Let’s rewrite x_n in the form:

x_n = x₀ + (x₁ − x⁰) + (x₂ − x¹) + . . . + (x_n − xⁿ⁻¹)

So the sequence {xⁿ} converges if and only if the series

∞

X

n=1

(x_n − xⁿ⁻¹)

converges. To prove it converges it is enough to prove

that _∞

X

n=1

|xⁿ − xⁿ⁻¹|

converges. Using the above comparison

∞

X

n=1

|xⁿ − xⁿ⁻¹| ≤

∞

X

n=1

λⁿ⁻¹|x¹ − x⁰| = 1

1 − λ|x¹ − x⁰| Which converges. Since the sequence converges, let s = lim_n→∞ x_n, so F (s) = s as shown earlier. So the contractive property implies that F is continuous. So is there a unique fixed point? Let x and y be fixed points so.

|x − y| = |F (x) − F (y)| ≤ λ|x − y|

Since λ < 1, |x − y| = 0. s belongs to C since s is the limit of a sequence lying in C.

Contractive Mapping Theorem: Example

Prove the sequence {Xn} defined as follows converges.

 x₀ = −15

x_n+1 = 3 − ¹₂|xⁿ| n ≥ 0

|F (x) − F (y)| = |3 − 1

2|x| − 3 + 1

2|y|| = 1

2||y| − |x||

and by the triangle inequality 1

2||y| − |x|| ≤ 1

2|y − x|

So by the Contractive Mapping Theorem, the sequence converges to the unique fixed point of F , which is 2.

Contractive Mapping Theorem: Example

Use the contractive mapping theorem to compute the fixed point of:

F (x) = 4 + 1

3 sin 2x

|F (x) − F (y)| = 1

3| sin 2x − sin 2y|

Use the Mean-Value Theorem

f⁰(ξ)(b − a) = f(b) − f(a) F⁰(x) = 2

3 cos 2x to get

1

3| sin 2x − sin 2y| = 2

3| cos 2ξ||x − y| ≤ 2

3|x − y|

for some ξ between x and y. This shows there is a fixed point of F

Contractive Mapping Theorem: Example

Using a computer program with an initial value of 4.

x = 4;

m = 20;

for (k = 0; k < M; k++) { x = 4 + 1/3*sin(2*x)

cout << k << ” ” << x << endl;

}

Results in k x

1 4.3297861 2 4.2308951 3 4.2736338

...

15 4.2614840 ...

20 4.2614837

Fixed Point Theorem 2

Lets build up.

Fixed Point Theorem 1: Let g(x) be continuous on [a, b] with range contained in [a, b]. Suppose that there exists a constant 0 ≤ k < 1 such that |g⁰(x)| ≤ k for all x ∈ (a, b). Then the equation x = g(x) has exactly one soultion in [a, b]

Proof. Since the range is contained in [a, b], the solution must be in [a, b]. |g⁰(x)| ≤ k < 1 implies g⁰(x) exists and is uniformly bounded on (a, b). Suppose there were two different solutions, p and q, in [a, b].

Thus p = g(p), q = g(q), p 6= q. By the Mean-Value Theorem there is a point ξ between p and q such that

g(p) − g(q) = (p − q)g⁰(ξ) = p − q

which implies g⁰(ξ) = 1 which is a contradiction.

s

a

s

b b s

b s

Fixed Point Theorem 2

Fixed Point Theorem 2:

Let g(x) be continuous on [a, b] with range contained in [a, b]. Suppose that there exists a constant k < 1 such that |g⁰(x)| ≤ k for all x ∈ (a, b). Then, if x₀ ∈ [a, b], the sequence generated by our iterative function (x_n+1 = g(x_n)) converges to the unique solution to x = g(x) which lies in [a, b].

Moreover an error bound is given by |xⁿ − s| ≤ kⁿ(b − a), where s is the fixed point.

Proof: All points of the sequence are in [a, b] since x_n+1 = g(x_n) is in [a, b] if x_n is in [a, b], and since x₀ is in [a, b] it follows that they all are. Let s denote the unique fixed point to g, if for some n, x_n = s, then x_n+1 = g(x_n) = g(s) = s and so x_n+1 = s also, so by induction all numbers in the sequence after also = s.

If this isn’t the case, that is x_n 6= s for all n. Using the Mean-Value Theorem on the given interval with endpoints s and x_n there is some point ξ between s

and x_n such that

g(x_n) − g(s) = (xⁿ − s)g⁰(ξ) = x_n+1 − s Since g⁰ is bounded by k it follows that

|xⁿ⁺¹ − s| ≤ k|xⁿ − s| ≤ k(b − a)for n = 0, 1, . . . in particular,

|x¹ − s| ≤ k(b − a)

|x² − s| ≤ k|x¹ − s| ≤ k²(b − a) ...

|xⁿ − s| ≤ k|xⁿ⁻¹ − s| ≤ kⁿ(b − a)

Because |k| < 1 , lim^n→∞ kⁿ(b − a) = 0, thus lim_n→∞ |xⁿ − s| = 0, or lim^n→∞ x_n = s.

Fixed Point Theorem 2: Example

Using Theorem 2 does g(x) = .5(x+5/x) converge in the interval [2, 3]

g⁰(x) = .5(1 − 5 x²)

Are the hypothesis of Theorem 2 satisfied? Is the range the same as the domain?

Determine max and min values of g(x) on [2, 3]

to verify the range is contained in [2, 3]. g⁰(x) = 0 when x = √

5. Thus the relative extrema are at x = 2, x = 5^1/2, x = 3.

g(2) = 9/4 g(5^1/2) = 5^1/2 g(3) = 7/3

So if x ∈ [2, 3] then g(x) ∈ [2, 3].

Fixed Point Theorem 2: Example

Now check to see if there is a k such that |g⁰(x)| ≤ k < 1. How?

Find max of |g⁰(x)| on [2, 3] so look at g⁰⁰(x) = _x⁵₃. There are no zeros on [2, 3] so we only need to look at endpoints for extrema.

g⁰(2) = −1/8 g⁰(3) = 2/9

Thus |g⁰(x)| ≤ k = 2/9 on [2, 3].

So by Theorem 2, if x₀ ∈ [2, 3], the series {xⁿ} converges to 5^1/2 and a bound on the error is |xⁿ − 5^1/2| ≤ (2/9)ⁿ

Fixed Point Theorem 3

Let x = g(x) be an equation with a solution p.

Suppose that there exists a δ > 0 and a constant k < 1 such that |g⁰(x)| ≤ k whenever |x − p| ≤ δ.

If p₀ ∈ I = [p − δ, p + δ] then the sequence {pⁿ} generated by iteration (x_n+1 = g(x_n)) converges to p.

Proof: if x ∈ I and x 6= p then the mean value theorem applies to g(x), on the interval with end points x and p. Thus, there exists a point ξ between x and p such that

g(x) − g(p) = (x − p)g⁰(ξ) Because |g⁰(ξ)| ≤ k < 1 it follows that

|g(x) − g(p)| ≤ k|x − p| < |x − p| ≤ δ

Finally, because g(p) = p we have shown that g(x) is closer to p than is x. That is, the range of g(x), for the domain I, is contained in I.

Fixed Point Theorem 3

Since the hypothesis of Theorem 2 are met so are the conclusions so Theorem 3 is correct.

Corollary III: Let x = g(x) be an equation with a solution p. If g⁰(x) is continuous at p and g⁰(p) = 0 then the hypothesis, and therefore the conclusion of theorem 3 are satisified for some interval about p.

This tells us that the closer we get to a solution the faster we will converge.

Convergence Examples

f (x) = x³ − x − 5

We want a g(x) such that x = g(x) is the same as f (x) = 0

x³ − x − 5 = 0

x³ − 5 = x g₁(x) = x³ − 5 x³ − x − 5 = 0

x(x² − 1) = 5

x = _x2⁵₋₁ g₂(x) = _x2⁵₋₁ x³ − x − 5 = 0

x³ = x + 5 g₃(x) = (x + 5)¹³

f (r) = 0 r ≈ 1.9

g₁⁰(x) = 3x² g₁⁰(1.9) ≈ 10.83 g₂⁰(x) = _(x^−10x₂₋₁₎₂ g₂⁰(1.9) ≈ ⁻¹⁹_6.8 g₃⁰(x) = ¹₃(x + 5)⁻²³ g₃⁰(1.9) ≈ ¹

3(6.9)²³

Region of Convergence

Let’s expand f (x) about x_n

f (x) = f (x_n) + f⁰(x_n)(x − xⁿ) + f⁰⁰(ξ)(x − xⁿ)² 2

Now set x = α where α is a root of f (x);

f (α) = 0 = f (x_n) + f⁰(x_n)(α − xⁿ) + f⁰⁰(ξ)(α − xⁿ)² 2

f (x_n) + f⁰(x_n)(α − xⁿ) = −f⁰⁰(ξ)(α − xⁿ)² 2

f (x_n)

f⁰(x_n) + (α − xⁿ) = −f⁰⁰(ξ)(α − xⁿ)² 2f⁰(x_n) since x_n+1 = x_n − _f^{f (x0}_(xⁿ_n⁾₎ (Newton’s method)

(α − xⁿ⁺¹) = −f⁰⁰(ξ)(α − xⁿ)² 2f⁰(x_n)

Region of Convergence

(α − xⁿ⁺¹) = −f⁰⁰(ξ)(α − xⁿ)² 2f⁰(x_n) let _n = |xⁿ − α|

_n+1 = f⁰⁰(ξ)e²_n 2f⁰(x_n)

let m = max

f⁰⁰(ξ) 2f⁰(x)

 in I = [α ± x⁰]

_n+1 = ²_n or m_n+1 = (m_n)²

So the sequence {xⁿ} approaches α if m⁰ < 1 or m|α − x⁰| < 1

Region of Convergence: Example

Let f (x) = x² − C and f(α) = 0 and using the iteration formula: x_n+1 = ¹₂ 

x_n + _x^C

n

 Case 1: x > α

x_n+1 = x_n 2



1 + C x²_n



= Kx_n

Since _x^C₂

n < 1, K < 1, and the minimum of g(x) is α at x_n = α. α ≤ xⁿ⁺¹ < x_n and the sequence, {x⁰, x₁, . . .} converges to α.

Case 2: 0 < x < α x_n+1 = 1

2



x_n + C x_n



The minimum of g(x) at x_n = α and its value is α.

So, x_n+1 > α bringing the result of the first iteration to the right side of α. We know from case 1 that any iteration starting at x > α will converge to the root.

Iteration: Graphical Analysis

We find a g(x) such that f (x) = 0 is that same as x = g(x)

So geometrically what does that tell us about the root of f (x)?

y = g(x) y = x

Iteration: Graphical Analysis

y = g(x) y = x

Where is the root of f (x)?

Iteration: Graphical Analysis

y = g(x) y = x

s

x₀

Iteration: Graphical Analysis

y = g(x) y = x

s

x₀

Roots

What does it mean to be a root? Where the function crosses the X-axis

Why do we want to find roots? It is an extremely useful piece of info to know.

How would you find the intersection between two curves? Set them equal and find the root.

A root r, of function f occurs when f (r) = 0.

For example:

f (x) = x² − 2x − 3

has 2 roots at r = −1 and r = 3. We can verify by substitution. We can also look at f in its factored form.

f (x) = x² − 2x − 3 = (x + 1)(x − 3)

Bisection Method

a b

tf (a)

t

f (b)

if f (a)f (b) < 0 we have a root. Why? Yes. The signs are different so it must cross x-axis an odd # of times. Touching the axis isn’t a cross.

Can we have a root if f (a)f (b) > 0. Why? Yes if it crosses an even # of times.

If we pick an x, a < x < b, will either [a, x] or [x, b]

have a root if [a, b] has a root? Yes.

Bisection Method:Algorithm

Find an interval (The smaller the better) [a, b]

where the the y values at the endpoints are on different sides of the x-axis.

Pick the midpoint, c, of [a, b] and see if that is a root, if it is not see if the root is in [a, c] or [c, b] and repeat on the appropriate new interval.

Bisection Method

Our estimate of the root, c, is:

c = a + b 2

if (f (a)f (c) < 0 root is in [a, c]

if (f (b)f (c) < 0 root is in [b, c]

No we have a new interval, if we repeat we should get closer to the root. What happens to the interval at each interation? It is halved.

c_i = a_i + b_i 2 c₀ = a₀ + b₀

2 c₁ = a₁ + b₁

2

Bisection Method:Convergence

What is the error of c₀, c₁, c₂, . . . , c_i?

₀ = |r − c⁰| ≤ ^a0+b₂ ⁰

₁ = |r − c¹| ≤ ^a1+b₂ ¹ ≤ ^a0₂^{+b2 0}

₂ = |r − c²| ≤ ^a2+b₂ ² ≤ ^a1₂^{+b2 1} ≤ ^a0₂^{+b3 0}

_i = |r − cⁱ| ≤ ^a₂^0i+1+b0

So does the bisection method converge? Yes!

How fast? O(log²(n))!

So for an error tolerance of  b − a

2ⁱ⁺¹ ≤ 

i > log(b − a) − log(2) log(2)

Bisection Method:Example

Find a root for f (x) = x³ + 2x² − 11x − 12 = (x + 1)(x − 3)(x + 4)

Find a root in the interval [4,5]?

f (4) = 4³+2×4²−11×4−12 = 64+32−44−12 = 40

f (5) = 5³+2×5²−11×5−12 = 125+50−55−12 = 108 Now What?

How about between [2, 5]

f (2) = 23 + 2 × 22 − 11 × 2 − 12 = 8 + 8 − 22 − 12 = −18

f (2 + 5

2 ) = f (3.5) = 3.53 + 2 × 3.52 − 11 × 3.5 − 12 = 16.875 f (2 + 3.5

2 ) = f (2.75) = 2.753 + 2 × 2.752 − 11 × 2.75 − 12 = −6.4 f (2.75 + 3.5

2 ) = f (3.13) = 3.9 f (2.75 + 3.13

2 ) = f (2.94) = −1.6, f (3.04 + 3.13

2 ) = f (2.94) = 1.2

Bisection Method:Convergence Example

Say we wanted to compute a root to 32-bit binary precision. How many iterations would be needed if a=16 and b=17?

a = (10000.0)₂ and b = (10001.0)₂, Thus we already know four of the binary digits, so we have 20 left. If the last one is to be correct the error must be less than 2⁻²⁰ (you can also use 2⁻²¹ to be conservative) so

b−a

2ⁿ⁺¹ < 

17−16

2ⁿ⁺¹ < 2⁻²⁰ 2ⁿ⁺¹ > 2²⁰ n ≥ 20

or

n > log 1−log 2⁻¹⁹ log 2

Bisection Method:Implementation Issues

What are some issues to be concerned about during implementation? Starting range.

How would you check to see which side of c the root is on? equality of signs.

We can use f (a)f (c) to see if the numbers have different signs. Are there any problems with this?

overflow, underflow.

Are we concerned with the number of calls to the function to evaluate it? Why? Could be expensive.

Will this always converge? Yes if it can be started properly.

Newton’s Method

x₀

v f (x₀)

x₁

v

x₂

v 



Basic idea is to approximate f (x) by a straight line l(x). Lets use a line tangent to the function at a current guess as the approximation.

Newton’s Method

The tangent line is the deriviative. So:

l(x) = f⁰(x₀)(x − x⁰) + f (x₀)

So we use the root of l(x) as a new approximation to the root of f (x) and repeat the procedure.

This gives us a sequence:

x₁ = x₀ − _f^{f (x0}_(x⁰₀⁾₎ x₂ = x₁ − _f^{f (x0}_(x¹₁⁾₎ x₃ = x₂ − _f^{f (x0}_(x²₂⁾₎

...

x_n+1 = x_n − _f^{f (x0}_(xⁿ_n⁾₎

Does this method always converge? Why? No, because the derivative doesn’t really predict the future.

Newton’s Method:Bad functions

x₀

s

x₁

s

x₂

s LL

LL LL LL LL LL LLL

HH HH HH HH HH HH HH HH HH

x₀

s

x₁

s

































x₀

s

Newton’s Method:Convergence

Doesn’t always converge. But when it does converge, how fast does it do it?

Let’s use Taylor’s series and the error term R_n. Expand about the point x_n

f (x) = f (x_n) + f⁰(x_n)(x − xⁿ) + f⁰⁰(ξ)(x − xⁿ)² 2

Remember ξ is between x and x_n. Let’s set x to the root r, so f (r) = 0.

f (r) = 0 = f (x_n) + f⁰(x_n)(r − xⁿ) + f⁰⁰(ξ)(r − xⁿ)² 2

Now divide by f⁰(x_n)

= f (x_n)

f⁰(x_n) + f⁰(x_n)(r − xⁿ)

f⁰(x_n) + f⁰⁰(ξ)(r − xⁿ)² 2f⁰(x_n)

Reduce terms and substitute our iterative formula.

x_n − xⁿ⁺¹ + (r − xⁿ) + f⁰⁰(ξ)(r − xⁿ)² 2f⁰(x_n)

Newton’s Method:Convergence

Rearrange.

r − xⁿ⁺¹ = − f⁰⁰(ξ)

2f⁰(x_n)(r − xⁿ)² What is r − xⁿ⁺¹? It is the n + 1 error or

_n+1 = |r − xⁿ⁺¹|

_n = |r − xⁿ|

So if we take the absolute value of both sides above we get

_n+1 = r − xⁿ⁺¹ = f⁰⁰(ξ) 2f⁰(x_n)²_n

So we are converging quadratically, but only if we are close to the root r and f⁰(r) 6= 0.

With quadratic convergence we almost double the number of significant digits after each iteration.

if f⁰(0) = 0 then we get at best linear convergence.

See the book for the analysis.

Newton’s Method:Example

Find a root for f (x) = x³ + 2x² − 11x − 12 = (x + 1)(x − 3)(x + 4)

What is f⁰(x):

f⁰(x) = 3x² + 4x − 11

So

x_n+1 = x_n − f (x_n)

f⁰(x_n) = x_n − x³_n + 2x²_n − 11xⁿ − 12 3x²_n + 4x_n − 11

Start with x₀ = 30

x1 = 30 − 28458

2809 = 10.13100748

x2 = 10.13100748 − 3.324046727 = 6.806960753 x3 = 6.806960753 − 2.069106062 = 4.737854691 x4 = 4.737854691 − 1.157209403 = 3.580645288 x5 = 3.580645288 − .4825214818 = 3.098123806 x6 = 3.098123806 − .09455278358 = 3.003571022

Newton’s Method:Implementation Issues

What problems do we have?

Well we must be able to evaluate f⁰(x) which isn’t always the case.

We have to evaluate f (x) and f⁰(x) for each iteration, which could be expensive.

Does not gaurantee convergence!

But it is very fast.

So when did Newton live?

Secant Method

x₀

v f (x₀)

x₁

v x₂

Lets approximate the function with a line, but this time a line between two approximations to the root called a secant line.

Secant Method

So what is x₂?

Let’s equate the slopes between (x₀, f (x₀)), (x₁, f (x₁)) and (x₁, f (x₁)), (x₂, 0):

f (x₁) − f(x⁰)

x₁ − x⁰ = 0 − f(x¹) x₂ − x¹ Rearrange:

x₂ = x₁ − f(x¹) x₁ − x⁰ f (x₁) − f(x⁰)

Do the same thing for x₃ using x₁ and x₂, in general:

x_n+1 = x_n − f(xⁿ) x_n − xⁿ⁻¹ f (x_n) − f(xⁿ⁻¹)

This is a two point method since two approximations are needed.

Secant Method vs Newton’s Method

This is the same as the Newton method except that we approximate f⁰(x) as

f⁰(x) = f (x_n) − f(xⁿ⁻¹) x_n − xⁿ⁻¹

So how does this compare to Newton’s method?

How many function evaluations are needed per iteration? 1

Will it converge? Maybe

How about speed of convergence?

|ⁿ⁺¹ ≈ C|ⁿ|^α α = 1/2(1 + √

5) ≈ 1.62

This isn’t quite as fast as Newton’s method but still superlinear and much faster than bisection. But if you consider number of evaluations it is faster.

Secant Method:Example

Find a root for f (x) = x³ + 2x² − 11x − 12 = (x + 1)(x − 3)(x + 4)

What is the secant iteration formula.

x_n+1 = x_n − f(xⁿ) x_n − xⁿ⁻¹ f (x_n) − f(xⁿ⁻¹)

Lets use x₀ = 5 and x₁ = 0 f (5) = 108

f (0) = −12

x₂ = x₁ − f(x¹)_{f (x}^x1−x0

1)−f (x₀) = 0 − −12_−12−108)⁻¹²⁻⁵ = ¹₂ x₃ = x₂ − f(x²)_{f (x}^x2−x1

2)−f (x₁) == ⁻¹⁶₁₃ = −1.2307 x₄ == −.99176

x₄ == −1.000198215

Secant Method:Implementation Issues

What are some issues to be concerned about during implementation? Starting values. The convergence properties depend on the starting values.

Does not gaurantee convergence!

What if we pick x₀ and x₁ such that f (x₀) = f (x₁)?

Who is this method named after?

Root finding comparison

Bisection Method

• Converges slowly

• Need two starting values on opposite sides of the root

• Always converges.

Newton’s Method

• Converges quickly near the root

• Needs two function evaluations per iteration.

• Need to be able to evaluate f⁰

• May not converge.

Root finding comparison

Secant Method

• Converges quickly near the root, but not as fast as Newton’s.

• Needs one function evaluation per iteration.

• Doesn’t need f⁰

• May not converge.

So what is the best method?

Well hybrids are the most popular, use bisection for so long then switch to Newton’s or Secant.

Polynomial Roots

P₁(z) = a_nzⁿ + a_n−1zⁿ⁻¹ + . . . + a₀ And in factored form

P₁(z) = (z − z¹)ⁿ¹(z − z²)ⁿ² . . . (z − z^q)^nq

with root z_i having multiplicity n_i. If a_n = 1 then the polynomial is monic.

If z_i is a root of multiplicity n_i for P₁ then it is a root of multiplicity n_i − 1 of P1⁰.

P₁(z) = (z − zⁱ)ⁿⁱS(z)

P₁⁰(z) = n_i(z − zⁱ)ⁿⁱ⁻¹S(z) + (z − zⁱ)ⁿⁱS⁰(z)

= (z − zⁱ)ⁿⁱ⁻¹[n_iS(z) + (z − zⁱ)S⁰(z)]

= (z − zⁱ)ⁿⁱ⁻¹T (z)

Therefore z_i is of multiplicity at least n_i − 1 for P1⁰. Is it more?

Polynomial Roots

If the multiplicity of z_i was more than n_i − 1 for P1⁰

then z_i must be a root of T (z) ⇒ T (zⁱ) = 0 But T (z_i) = n_iS(z_i) + (z − zⁱ)S⁰(z_i) = n_iS(z_i) 6= 0 Therefore it must be of multiplicity n_i − 1

If the root (multiplicity) structure of P₁ is P₁(z) = (z − z¹)ⁿ¹(z − z²)ⁿ² . . . (z − z^q)^nq then P₁ and P₁⁰ have the common divisor

P₂(z) = (z − z¹)ⁿ¹⁻¹(z − z²)ⁿ²⁻¹ . . . (z − z^q)^nq−1 and furthermore, that common divisor is a gcd.

Polynomial Roots

Remember the Euclidean gcd algorithm? Lets use that algorithm on these polynomials to get

P₁(z) = Q₁(z)P⁰(z) + R₁(z) P₁⁰(z) = Q₂(z)R₁(z) + R₂(z) R₁(z) = Q₃(z)R₂(z) + R₃(z) R₂(z) = Q₄(z)R₃(z) + R₄(z) ...

R_s−2(z) = Q_s(z)R_s−1(z) + R_s(z) R_s−1(z) = Q_s+1(z)R_s(z)

Then convert R_s(z) to monic form and call it P₂(z) and repeat the Euclidean algorthm for gcd, getting the polynomials P₁, P₂, P₃, . . . , P_q, 1

What happens to the multiplicity of each root as we proceed? They reduce by one.

So what is the multiplicity of root z_i for polynomial P_j? n_i − (j − 1) = nⁱ − j + 1

Polynomial Roots

Let’s divide P₁ by P₂ this gives P₁(z)

P₂(z) = M₁(z) = (z − z¹)(z − z²) . . . (z − z^q) Let’s define

M_i(z) =

( P_i(z)

P_i+1(z) if i < q P_q(z) if i = q

The polynomials M₁, M₂, . . . , M_q all have only simple roots.

So for polynomial M_i what can we say about it’s roots? It has all roots that have at least multiplicity i of P and they are simple roots here.

Polynomial Roots

Let’s also create the polynomials N_i as

N_i(z) =

( M_i(z)

M_i+1(z) if i < q M_q(z) if i = q

The sum of the degrees of the N_is is q and each distinct root of P₁(z) is a root of just one N_i and if the root is of multiplicity of m then it is a root of N_m(z).

Polynomial Roots:Example

P₁(z) = z⁷ − 3z⁵ + 3z³ − z P₁⁰(z) = 7z⁶ − 15z⁴ + 9z² − 1 Lets apply the Euclidean algorithm.

z⁷−3z⁵+3z³−z = 1

7z(7z⁶−15z⁴+9z²−1)−6

7z⁵+12

7 z³−6 7z 7z⁶−15z⁴+9z²−1 = −49

6 z(−6

7z⁵+12

7 z³−6

7z)−z⁴+2z²−1

−6

7z⁵ + 12

7 z³ − 6

7z = 6

7z(−z⁴ + 2z² − 1) + 0

Now make the last polynomial monic we get P₂(z) = z⁴ − 2z² + 1 and repeat on P₂

z⁴ − 2z² + 1 = 1

4z(4z³ − 4z) − z² + 1 4z³ − 4z = −4z(−z² + 1) + 0

Polynomial Roots:Example

Set P₃(z) = z² − 1, and repeat z² − 1 = 1

2z(2z) − 1 2z = −2z(−1) + 0

So P₄(z) = 1 Let find the M_i’s and N_i’s.

M₁(z) = ^P_P^1(z)

2(z) = z³ − z M₂(z) = ^P_P^2(z)

3(z) = z² − 1 M₃(z) = P₃(z) = z² − 1 N₁(z) = ^M_M^1(z)

2(z) = z N₂(z) = ^M_M^2(z)

3(z) = 1

N₃(z) = M₃(z) = z² − 1

So the roots of P₁(z) are 0, 1 (with multiplicity 3) and -1 (with multiplicity 3) or

P₁(z) = (z − 1)³(z + 1)³(z)

Polynomial Roots:Example 2

What is the factored form of the polynomial

p = 2x⁹ − 12x⁸ + 10x⁷ + 84x⁶ − 258x⁵ + 252x⁴+ 46x³ − 276x² + 200x − 48

P₁(x) = x⁹ − 6x⁸ + 5x⁷ + 42x⁶ − 129x⁵ + 126x⁴ +23x³ − 138x² + 100x − 24

P₂(x) = x⁵ − 7x⁴ + 19x³ − 25x² + 16x − 4 P₃(x) = x³ − 4x² + 5x − 2

P₄(x) = x − 1 P₅(x) = 1

M₁(x) = x⁴ + x³ − 7x² − x + 6 = (x − 2)(x + 3)(x − 1)(x + 1) M₂(x) = x² − 3x + 2 = (x − 2)(x − 1)

M₃(x) = x² − 3x + 2 = (x − 2)(x − 1) M₄(x) = x − 1

M₅(x) = 1

N₁(x) = x² + 4x + 3 = (x + 3)(x + 1) N₂(x) = 1

N₃(x) = x − 2 N₄(x) = x − 1

p(x) = 2(x − 2)³(x + 3)(x − 1)⁴(x + 1)

Polynomials

What is a polynomial?

Let φ₁(x), φ₂(x),. . . φ_n(x) be a given set of functions. A polynomial p in the base functions {φⁱ(x)}

is any function of the form:

p(x) = a₁φ₁(x) + a₂φ₂(x) + . . . + a_mφ_m(x)

where the a_i are constants. If the base functions are 1, x, x², . . . , xⁿ then a polynomial

p(x) = a₀ + a₁x + a₂x² + . . . + a_nxⁿ =

n

X

i=0

a_ixⁱ

is called an algebraic polynomial in one variable. If a_n 6= 0 then the polynomial p is of degree n. We will consider only these types of polynomials.

Evaluating Polynomials

If we evaluate a polynomial naively how expensive (in terms of computions) is it?

a₀

a₁x 1 multiply a₂xx 2 multiplies a₃xxx 3 multiplies ...

a_nxx . . . x n multiplies

This gives 1 + 2 + 3 + . . . + n = ⁿ⁽ⁿ⁺¹⁾₂ multiplies.

Then another n additions to add them together.

Are there better ways? i.e. less calculations.

Evaluating Polynomials

What if we notice that xⁿ = xⁿ⁻¹x. Since we already calculated xⁿ⁻¹ why calculate it again? So now we have:

a₁x 1 multiply a₂xx 2 multiplies a₃xx² 2 multiplies a₄xx³ 2 multiplies ...

a_nxxⁿ⁻¹ 2 multiplies

Which is 2n − 1 multiplies and n additions. This is much cheaper than the naive method.

Are there still better ways?

Evaluating Polynomials

What if we write the polynomial in nested form:

p(x) = a₀ + x(a₁ + x(a₂ + . . . + x(a_n−1 + x(a_n)) . . .)

Now we have n multiplications and n additions.

Synthetic Division (Horner’s Method)

Horner’s only contribution to mathematics was published in 1819, however the same method was proposed by ruffini a few years earlier. But, the method was actually published by chu in 1303, but we know it as Horner’s method because of de Morgan

If a polynomial p and a complex number x₀ are given then Horner’s algorithm will give the number p(x₀) and the polynomial

q(x) = p(x) − p(x⁰) x − x⁰

q is of degree one less then p and by rearranging p(x) = (x − x⁰)q(x) + p(x₀)

If we rewrite the unknown polynomial q and the known polynomial p in the following form

p(x) = a₀ + a₁x + a₂x² + . . . + a_nxⁿ

q(x) = b₀ + b₁x + b₂x² + . . . + b_n−1xⁿ⁻¹ and plug in to the above formula we get

Synthetic Division (Horner’s Method)

b_n−1 = a_n

b_n−2 = a_n−1 + x₀b_n−1 ...

b₀ = a₁ + x₀b₁ p(x₀) = a₀ + x₀b₀

We can use this method to evaluate a polynomial quickly with n multiplies and n additions. This method is also good for doing things by hand. To do it by hand set it up the following way

a_n a_n−1 a_n−2 . . . a₀ x₀ x₀b_n−1 x₀b_n−2 . . . x₀b₀ b_n−1 b_n−2 b_n−3 . . . p(x₀)

Synthetic Division: Example

Evaluate p(x) = x⁴ − 4x³ + 7x² − 5x − 2 at x = 3;

First set up the knowns:

1 −4 7 −5 −2 3

Start doing the multiplies and adds:

1 −4 7 −5 −2

3 3 ∗ 0 3 ∗ 1 1 + 0 −4 + 3 and finally

1 −4 7 −5 −2

3 3 −3 12 21

1 −1 4 7 19

so p(3) = 19 and we can write p as

p(x) = (x − 3)(x³ − x² + 4x + 7) + 19

Synthetic Division: Deflation

We can also use synthetic division for deflation, which is removing a linear factor from a polynomial. If x₀ is a zero of the polynomial p, then x − x⁰ is a factor of p, and conversely. And the remaining zeros (roots) of p are the n − 1 roots of p(x)/(x − x⁰).

Example Deflate p(x) = x⁴ − 4x³ + 7x² − 5x − 2 by noting that 2 is a root.

First set up the synthetic division and calculate p(2)

1 −4 7 −5 −2

2 2 −4 6 2

1 −2 3 1 0

Since p(2) = 0, we know it is indeed a root. And

x⁴ − 4x³ + 7x² − 5x − 2 = (x − 2)(x³ − 2x² + 3x + 1)

Synthetic Division: Derivative

Sometime we need not only to calculate p(x) but also p⁰(x) such as with Netwon’s method. Using synthetic division

p(x) = (x − x⁰)q(x) + p(x₀)

If we use the product rule and differentiate we get p⁰(x) = q(x) + (x − x⁰)q⁰(x)

So p⁰(x₀) is

p⁰(x₀) = q(x₀) + (x₀ − x⁰)q⁰(x₀) = q(x₀)

Thus p⁰(x₀) can be found by synthetic division on the polynomial q(x)

Synthetic Division: Derivative Example

For p(x) = 2x⁵ − 7x³ + 4x − 5 find p(3) and p⁰(3).

Find p(3) by synthetic division

2 0 −7 0 4 −5

3 6 18 33 99 309

2 6 11 33 103 304 Now find p⁰(3)

2 6 11 33 103

3 6 36 141 522

2 12 47 174 625 So p⁰(3) = 625

Synthetic Division and Taylor expansion

Let p(x) be a polynomial and suppose we desire the coefficients c_k in the equation

p(x) = a_nxⁿ + a_n−1xⁿ⁻¹ + . . . + a₀

= c_n(x − x⁰)ⁿ + c_n−1(x − x⁰)ⁿ⁻¹ + . . . + c₀

Using Taylor’s Theorem we know that c_k = ^p(k)_k!^(x0). This is expensive to calculate. Is there a more efficient way?

Notice that p(x₀) = c₀. And this coefficient (c₀) can be obtained by applying synthetic division to the polynomial p, using the point x₀. We also obtain the polynomial q(x) such that

q(x) = p(x) − p(x⁰) x − x⁰

Synthetic Division and Taylor expansion

q(x) = p(x) − p(x⁰) x − x⁰

= c_n(x − x⁰)ⁿ + c_n−1(x − x⁰)ⁿ⁻¹ + . . . + c₀

x − x⁰ − p(x₀)

x − x⁰

= c_n(x−x⁰)ⁿ⁻¹+c_n−1(x−x⁰)ⁿ⁻²+. . .+c₁+ c₀

x − x⁰− c₀ x − x⁰

= c_n(x − x⁰)ⁿ⁻¹ + c_n−1(x − x⁰)ⁿ⁻² + . . . + c₁ This shows that the coefficient c₁ can be obtained by applying synthetic division to the polynomial q with point x₀ because c₁ = q(x₀). We repeat the process until all coefficients c_k are found.

Synthetic Division: Taylor Expansion:Example

Find the Taylor expansion of the polynomial p about the point 3.

p(x) = x⁴ − 4x³ + 7x² − 5x − 2

1 −4 7 −5 −2

3 3 −3 12 21

1 −1 4 7 19

3 3 6 30

1 2 10 37

3 3 15

1 5 25

3 3

1 8

So

p(x) = (x−3)⁴+8(x−3)³+25(x−3)²+37(x−3)+19

Polynomials: Localizing zeros

Therorem: All zeros of the polynomial p(x) = a_nxⁿ + a_n−1xⁿ⁻¹+ . . . + a₀ lie in the open disk whose center is at the origin of the complex plane and whose radius is

ρ = 1 + |aⁿ|⁻¹ max

0≤k≤n |a^k|

Example: Find a disk centered at the origin that contains all the zeros of the polynomial

p(x) = x⁴ − 4x³ + 7x² − 5x − 2

One such disk would be ρ = 1 + |a⁴|⁻¹ max

0≤k≤n|a^k| = 1 + 7

1 = 8

Polynomials: Localizing zeros

Take our polynomial p(x) = a_nxⁿ + a_n−1xⁿ⁻¹ + . . . + a₀ and consider the function s(x) = xⁿp(1/x).

This gives

s(x) = xⁿ

"

a_n  1 x

n

+ a_n−1  1 x

n−1

+ . . . + a₀

#

= a_n + a_n−1x + . . . + a₀xⁿ

s is a polynomial of degree at most n. It has the same coefficients as p except in reverse order. Also for a nonzero complex number z the condition p(z) = 0 is equivalent to s(1/z) = 0. Thus

Therorem:If all the zeros of s are in the disk{z :

|z| ≤ ρ}, then all the nonzero roots (r is a root and r 6= 0) of p are outside of the disk{z : |z| < ρ⁻¹}

Polynomials: Localizing zeros

Example: Find a disk centered at the origin that contains no zeros of p, where

p(x) = x⁴ − 4x³ + 7x² − 5x − 2

Using the above thereom we get

s(x) = −2x⁴ − 5x³ + 7x² − 4x + 1

and all zeros of s lie in a disk centered at the origin with a radius of

ρ = 1 + |a⁴|⁻¹ max

0≤k≤n|a^k| = 9 2

Therefore, the zeros of p lie outside the disk of radius ²₉ and furthermore all zeros of p lie in the ring ²₉ < |z| < 8 in the complex plane.