44 Iteration Newton'smethod

Iteration To solve φ(x) = x for x, start with some x0 nearby, and let x1 equal φ(x0), x2 equal φ(x1), x3 equal φ(x2), · ·

xn+1 equal φ(xn), · ·

Then x equals φ(x), if the sequence of xn’s approaches x, and if the function φ is continuous at x.

√ Example: To solve x = 4 x + 14, let x0 equal 0, and √ 4

x2 x3 x4

0 + 14 x1 = √ = 4 1.9979448 + 14 √ = 4 1.9999357 + 14 √ = 4 1.9999979 + 14

= 1.9979448, = 1.9999357, = 1.9999979, = 1.9999998, · ·

√ x = 4 1.9999998 + 14 = 1.9999999 ∼ = 2.0000000 Note that

√ 4

√ 2 + 14 = 4 16 = 2.

√ Also, to solve x = 4 x + 14, two more iterations: x0 = 100.0000000

x0 = 1, 000, 000.0000000

x1 =

3.2675798

x1 =

x2 =

2.0384865

x2 =

2.5989365

x3 =

2.0012015

x3 =

2.0184595

x4 =

2.0000375

x4 =

2.0005765

x5 =

2.0000011

x5 =

2.0000175

x6 =

31.622885

2.0000000 x6 = 2.0000005 √ 1 4 Since φ(x) equals x + 14 = (x + 14) 4 , and 1 1 1 1 − 34 − 34 − 34 0 since φ (x) equals 4 (x+14) ≤ 4 (0+14) ≤ 4 (14) ≤ 28 , for x ≥ 0, the Mean Value Theorem gives us 1 |xn − 2| |xn+1 − 2| = |φ(xn) − φ(2)| ≤ 28

Whenever the xn and their limit x are in an interval where |φ0(x)| ≤ M < 1, then we have −M ≤ −M ≤ −M ≤

φ0(x)

φ(xn) − φ(x) xn − x xn+1 − x

xn − x xn+1 − x x −x n xn+1 − x

≤ M ≤ M ≤ M ≤ M ≤ M · xn − x ,

so that each xn is closer than its predecessor by a factor at least as small as M .

Since we have xn − x ≤ M · xn−1 − x ≤ M · M · xn−2 − x ≤ M · M · M · xn−3 − x ≤ ...,

n we finally have xn − x ≤ M · x0 − x ,

which approaches 0 as n → ∞.

Thus the xn approach x. On the other hand, if |φ0(x)| ≥ 1, the x0ns get farther and farther apart, and thus they diverge.

√ For x < 0, x − x − 14 = 0 also means that x = − 4 x + 14: 4

x0 =

0.000000000000000

x1 = −1.93433642026767 x2 = −1.86375062881515

x3 = −1.86647046865692 x4 = −1.86636588677009

x5 = −1.86636990842419

x6 = −1.86636975377359

x7 = −1.86636975972060

x8 = −1.86636975950070 √ 1 4 Since φ(x) equals − x + 14 = −(x + 14) 4 , and since 1 1 − 34 − 34 0 |φ (x)| equals | − 4 (x + 14) | ≤ 4 (−2 + 14) ≤ 0.04 = 1 for x ≤ 0, the MVT gives |xn+1 − 2| ≤ 25 |xn − 2|.

1 , 25

Newton’s Method–For Approximating Solutions to f (x) = 0: f (xn)

0

f (xn) =

xn+1 − xn+1 =

f (xn)

xn+1 =

f 0(xn)

xn = − xn

xn+1 = φ(xn),

−

f( x)

xn −

xn − xn+1

f (xn) f 0(x

n)

f (xn) f 0(xn) where φ(u) = u −

(Note that φ(x) = x iff f (x) = 0.)

y

f (xn)

=

xn+1 f (u) f 0(u)

.

xn x

To determine convergence, we check to see if |φ0(x)| < 1 :   d f (x) 0 φ (x) = x− 0 dx f (x) = 1−

f 0(x) · f 0(x) − f (x) · f 00(x)

=

f 0(x) · f 0(x)

=

f (x) · f 00(x)

(f 0(x))2

(f 0(x))2

−

f 0(x) · f 0(x) − f (x) · f 00(x) (f 0(x))2

(f 0(x))2

If f 0(x) stays away from 0, and if f 00(x) doesn’t grow much, then φ0(x) will approach 0 as f (x) does, and convergence here will be much faster than it is with ordinary iteration, where |φ0(x)| < M ≤ 1 would have sufficed.

Using Newton’s Method to solve f (x) = x4 − x − 14 = 0, by iterating f (x) x4 − x − 14 3x4 + 14 x → φ(x) = x − 0 =x− = 3 f (x) 4x − 1 4x3 − 1 x0 x1 x2 x3 x4 x5 x6 x7 x8

= 100.00000000 = 75.00002225 = 56.25005832 = 42.18762266 = 31.64086896 = 23.73094950 = 17.79880697 = 13.35031786 = 10.01526160

x9 x10 x11 x12 x13 x14 x15 x16 x17 x18

= = = = = = = = = =

7.516800847 5.649166684 4.262199457 3.252353679 2.559601542 2.160625768 2.017473769 2.000232796 2.000000041948 2.0000000000000013623

Using Newton’s Method to solve f (x) = x4 − x − 14 = 0, by iterating f (x) x4 − x − 14 3x4 + 14 x → φ(x) = x − 0 =x− = 3 f (x) 4x − 1 4x3 − 1 x0 =

0.000

x1 = −14.000 x2 = −10.500 x3 =

x4 = x5 = x6 =

x7 = −2.5980

x8 = −2.1179

x9 = −1.9067

−7.877

x10 = −1.8676

−4.445

x12 = −1.866369759501389

−5.912 −3.364

x11 = −1.8663709

x13 = −1.86636975950037621146202891

In most examples the number of correct digits will ultimately double, roughly, with each step.

√ Example: To find c: Use Newton’s Method on f (x) = x2 − c: Iterate x2 − c 2x2 − (x2 − c) f (x) = x− = φ(x) = x − 0 f (x) 2x 2x c x+ x2 + c x. = = 2x 2 To guarantee convergence, we make sure that 2 2 x − c (2x)(2x) − 2(x + c) 0 < 1, = |φ (x)| = 2x2 (2x)2 √ by noting that if x0 ≥ 0 then every later xk is ≥ c, 1 0 and that |φ (x)| is smaller than for all these x. 2

√ Example: To find 2, use Newton’s Method on f (x) = x2 −2. x2 + 2 Iterate φ(x) = : 2x 1 = 1.0000000000000000000000000 x0 = 1 3 = 1.5000000000000000000000000 x1 = 2 17 x2 = = 1.4166666666666666666666667 12 577 x3 = = 1.4142156862745098039215686 408 665857 = 1.4142135623746899106262955 x4 = 470832 886731088897 x5 = = 1.4142135623730950488016896 627013566048

√ Continued Fractions Approaching 2 3 2 577 408

=1 +

1

17

2

12

=1 + 2+

1

2+

1 2+

1

=1 +

1

1

2+

1

2+

1

2+ 2+

1 2+

1 2

1 2

665857 470832

1

=1 +

1

2+

1

2+

1

2+

1

2+

1

2+

1

2+

1

2+

1

2+

1

2+

1

2+

1

2+

1

2+ 2+

1 2+

1 2

1

Let x equal 2 +

1

2+

1

2+

1

2+ 2+ Then x satisfies x = 2 + x2

1

1 2 + ··· .

x = 2x + 1

x2 − 2x = 1

x2 − 2x + 1 = 2 √ x − 1 = ± 2 √ 2, since x > 1. x − 1 =

√ Thus we have 2 = x − 1 and we finally obtain: √ 2 =1 +

1 1

2+

1

2+

1

2+ 2+

1 2 + ··· ,