Ch6.1.2 Fixed Point Iteration & Newton's Method

Fixed Point Iteration

Let $ g(x) $ be a function on $ [a,b] $
A fixed point of $ g $ is a value of $ x $ for which $ g(x) = x $.
A fixed point of $ g $ is a point of intersection of the graphs of $ y = g(x) $ and $ y = x $.

title

Example 1: Analytical Solution

title

Our iterating function $ g $ is

\[ g(x) = x^2+x-4 \]

Solve $ g(x) = x $:

\[ \begin{aligned} x^2+x-4 & = x \\ x^2 - 4 &= 0 \\ x &= \pm 2 \end{aligned} \]

Analytic solution usually impossible
Need numerical method

Example 1: Fixed Point Iteration (p = +/- 2)

title

Example 1: Fixed Point Iteration (p = +/- 2)

title

R Code for Fixed Point Iteration

fxdpt <- function(g,x0,m) {
  #  g = iterating function
  # x0 = initial value
  #  m = number of iterations

  # Start by displaying initial value
  cat("n = ", 0,",", "x(n) = ", x0, "\n")

  # Fixed point iteration loop
  for(n in 1:m) {
    x1 <- g(x0)
    x0 <- x1
    cat("n = ", n,",", "x(n) = ", x1, "\n")  }
  }

Example 2: p = 1.36523

title

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  2.525 
n =  2 , x(n) =  1.721454 
n =  3 , x(n) =  1.414551 
n =  4 , x(n) =  1.366381 
n =  5 , x(n) =  1.365231 
n =  6 , x(n) =  1.36523 
n =  7 , x(n) =  1.36523 
n =  8 , x(n) =  1.36523

Example 3: p = 1.36523

title

g <- function(x)
{sqrt(10/(4+x))}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  1.118034 
n =  2 , x(n) =  1.397811 
n =  3 , x(n) =  1.361104 
n =  4 , x(n) =  1.365755 
n =  5 , x(n) =  1.365163 
n =  6 , x(n) =  1.365239 
n =  7 , x(n) =  1.365229 
n =  8 , x(n) =  1.36523

Example 4: p = 1.36523

title

g <- function(x)
{0.5*sqrt(10 - x^3)}
fxdpt(g,1,8)

n =  0 , x(n) =  1 
n =  1 , x(n) =  1.5 
n =  2 , x(n) =  1.286954 
n =  3 , x(n) =  1.402541 
n =  4 , x(n) =  1.345458 
n =  5 , x(n) =  1.37517 
n =  6 , x(n) =  1.360094 
n =  7 , x(n) =  1.367847 
n =  8 , x(n) =  1.363887

Example 5: p = 1.36523

title

g <- function(x)
{x-x^3-4*x^2+10}
fxdpt(g,1.2,8)

n =  0 , x(n) =  1.2 
n =  1 , x(n) =  3.712 
n =  2 , x(n) =  -92.55122 
n =  3 , x(n) =  758423 
n =  4 , x(n) =  -4.362514e+17 
n =  5 , x(n) =  8.302532e+52 
n =  6 , x(n) =  -5.723105e+158 
n =  7 , x(n) =  NaN 
n =  8 , x(n) =  NaN

Example 5: x0 = 1.36

title

g <- function(x)
{x-x^3-4*x^2+10}
fxdpt(g,1.36,8)

n =  0 , x(n) =  1.36 
n =  1 , x(n) =  1.446144 
n =  2 , x(n) =  0.05644622 
n =  3 , x(n) =  10.04352 
n =  4 , x(n) =  -1396.559 
n =  5 , x(n) =  2716014862 
n =  6 , x(n) =  -2.003533e+28 
n =  7 , x(n) =  8.042467e+84 
n =  8 , x(n) =  -5.20197e+254

Example 5: x0 = 1.36523

title

g <- function(x)
{x-x^3-4*x^2+10}
fxdpt(g,1.36523,8)

n =  0 , x(n) =  1.36523 
n =  1 , x(n) =  1.36523 
n =  2 , x(n) =  1.365227 
n =  3 , x(n) =  1.36528 
n =  4 , x(n) =  1.364453 
n =  5 , x(n) =  1.377278 
n =  6 , x(n) =  1.177141 
n =  7 , x(n) =  4.003382 
n =  8 , x(n) =  -114.2673

Example 5: x0 = 1.36523001341410

title

g <- function(x)
{x-x^3-4*x^2+10}
fxdpt(g,1.36523001341410,8)

n =  0 , x(n) =  1.36523 
n =  1 , x(n) =  1.36523 
n =  2 , x(n) =  1.36523 
n =  3 , x(n) =  1.36523 
n =  4 , x(n) =  1.36523 
n =  5 , x(n) =  1.36523 
n =  6 , x(n) =  1.36523 
n =  7 , x(n) =  1.365229 
n =  8 , x(n) =  1.36524

Example 6

title

g <- function(x){2-0.5*x^2}
fxdpt(g,1,8)

n =  0 , x(n) =  1 
n =  1 , x(n) =  1.5 
n =  2 , x(n) =  0.875 
n =  3 , x(n) =  1.617188 
n =  4 , x(n) =  0.6923523 
n =  5 , x(n) =  1.760324 
n =  6 , x(n) =  0.4506294 
n =  7 , x(n) =  1.898467 
n =  8 , x(n) =  0.1979124

Fixed Point Theorem (FPT)

title

If $ g $ is a function on $ [a,b] $ with:

$ g $ continuous on $ [a,b] $
$ g(x) \in [a,b] $
$ |g'(x)| \leq k, \,\, k \in [0,1) $

Then:

There is a unique $ p \in [a,b] $ with $ g(p) = p $
$ x_n = g(x_{n-1}) \rightarrow p $

Example 1 FPT: p = +/- 2

title

For this example,

\[ \begin{aligned} g(x) &= x^2 + x - 4 \\ g'(x) &= 2x \\ \end{aligned} \]

Then $ g $ is continuous on $ [-2,2] $ with

\[ \begin{aligned} g(x) & \notin [-2,2] \\ \max_{x \in [-2,2]} & |g'(x)| = 4 > 1 & \end{aligned} \]

FPT doesn't guarantee convergence

Example 1 FPT: p = +/- 2

title

Example 1 FPT: p = +/- 2

title

Example 2 FPT: p = 1.36523

title

Here \[ g(x) = x-\frac{x^3+4x^2-10}{3x^2+8x} \]

Then $ g $ is continuous on $ [0,5] $ with

\[ \begin{aligned} g(x) & \notin [0,5] \\ g'(x) &= \frac{(6x + 8)(x^3 + 4 x^2 -10)}{x^2(3 x + 8)^2} \\ \max_{x \in [0,5]} &|g'(x)| \geq k > 1 \end{aligned} \]

FPT doesn't guarantee convergence

Example 2 FPT: p = 1.36523

title

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  2.525 
n =  2 , x(n) =  1.721454 
n =  3 , x(n) =  1.414551 
n =  4 , x(n) =  1.366381 
n =  5 , x(n) =  1.365231 
n =  6 , x(n) =  1.36523 
n =  7 , x(n) =  1.36523 
n =  8 , x(n) =  1.36523

Example 3 FPT: p = 1.36523

title

In this example, \[ g(x) = \sqrt{\frac{10}{4+x}} \]

Then $ g $ is continuous on $ [0,2] $ with

\[ \begin{aligned} g(x) & \in [0,2] \\ g'(x) &= -\frac{5}{\sqrt{10}}(4+x)^{-3/2} \\ \max_{x \in [0,2]} &|g'(x)| \leq k = 0.2 \in [0,1) \end{aligned} \]

FPT guarantees convergence

Example 3 FPT: p = 1.36523

title

g <- function(x)
{sqrt(10/(4+x))}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  1.118034 
n =  2 , x(n) =  1.397811 
n =  3 , x(n) =  1.361104 
n =  4 , x(n) =  1.365755 
n =  5 , x(n) =  1.365163 
n =  6 , x(n) =  1.365239 
n =  7 , x(n) =  1.365229 
n =  8 , x(n) =  1.36523

Example 4 FPT: p = 1.36523

title

For this example,

\[ g(x) = 0.5\sqrt{10-x^3} \]

Then $ g $ is continuous on $ [0,2] $ with

\[ \begin{aligned} g(x) & \in [0,2] \\ g'(x) &= - \frac{3}{4}x^2(10-x^3)^{-1/2} \\ \max_{x \in [0,2]} &|g'(x)| > 1 \\ \max_{x \in [0,1.5]} & |g'(x)| < 0.66 = k < 1 \end{aligned} \]

Example 4 FPT: p = 1.36523

title

g <- function(x)
{0.5*sqrt(10 - x^3)}
fxdpt(g,1,8)

n =  0 , x(n) =  1 
n =  1 , x(n) =  1.5 
n =  2 , x(n) =  1.286954 
n =  3 , x(n) =  1.402541 
n =  4 , x(n) =  1.345458 
n =  5 , x(n) =  1.37517 
n =  6 , x(n) =  1.360094 
n =  7 , x(n) =  1.367847 
n =  8 , x(n) =  1.363887

Example 5 FPT: p = 1.36523

title

For this example,

\[ g(x) = x-x^3-4x^2+10 \]

Then $ g $ is continuous on $ [0,2] $ with

\[ \begin{aligned} g(x) & \notin [0,2] \\ g'(x) &= 1 - 3x^2 - 8x \\ \max_{x \in [0,2]} &|g'(x)| \geq k > 1 \end{aligned} \]

FPT doesn't guarantee convergence

Example 5 FPT: p = 1.36523

title

g <- function(x)
{x-x^3-4*x^2+10}
fxdpt(g,1.2,8)

n =  0 , x(n) =  1.2 
n =  1 , x(n) =  3.712 
n =  2 , x(n) =  -92.55122 
n =  3 , x(n) =  758423 
n =  4 , x(n) =  -4.362514e+17 
n =  5 , x(n) =  8.302532e+52 
n =  6 , x(n) =  -5.723105e+158 
n =  7 , x(n) =  NaN 
n =  8 , x(n) =  NaN

Recall: Fixed Point Theorem

title

If $ g $ is a function on $ [a,b] $ with:

$ g $ continuous on $ [a,b] $
$ g(x) \in [a,b] $
$ |g'(x)| \leq k, \,\, k \in [0,1) $

Then:

There is a unique $ p \in [a,b] $ with $ g(p) = p $
$ x_n = g(x_{n-1}) \rightarrow p $

Error Analysis & MVT

title

Why is $ \small{k} $ important?

\[ \small{\max_{x \in [a,b]} |g'(x)| \leq k < 1 } \]

Mean Value Theorem

\[ \small{\begin{aligned} g'(c) & = \frac{g(x_n) - g(p)}{x_n - p} \\ c &\in [x_n, p] \end{aligned}} \]

Also need:

\[ \small{ \begin{aligned} g(x_n) & = x_{n+1} \\ g(p) &= p \end{aligned} } \]

Error Analysis & MVT

title

\[ \small{ \begin{aligned} g'(c) & = \frac{g(x_n) - g(p)}{x_n - p} \\ g(x_n) & = x_{n+1} \\ g(p) &= p \end{aligned} } \]

Error analysis:

\[ \small{ \begin{aligned} E_{n+1} &= |x_{n+1} - p| \\ &= |g'(c)|\cdot |x_n - p| \\ & \mbox{ } \leq k |x_n - p| \end{aligned} } \]

Repeat pattern on right side:

\[ \small{ \begin{aligned} E_{n+1} & \leq k^2|x_{n-1} - p| \\ & \vdots \\ & \leq k^{n+1} |x_0 - p| \end{aligned}} \]

Thus $ \small{ E_{n+1} \sim O(k^{n+1}) } $

FPT2: Error and Speed

title
title

Suppose $ g $ is a function on $ [a,b] $ with

$ p $ a fixed point of $ g $
$ g,\,g',\,g'' $ continuous (smoothness)
$ x_0 $ close enough to $ p $

If the slope of $ g $ at $ p $ satisfies

\[ \small{|g'(p)| = 0 } \]

then $ \small{~ x_n \rightarrow p ~ } $ much faster than if

\[ \small{|g'(p)| \neq 0 } \]

Example: Error and Speed

title title

n =  0 , x(n) =  1.9 
n =  1 , x(n) =  1.465924 
n =  2 , x(n) =  1.369859 
n =  3 , x(n) =  1.36524 
n =  4 , x(n) =  1.36523 
n =  5 , x(n) =  1.36523 
n =  6 , x(n) =  1.36523 
n =  7 , x(n) =  1.36523

n =  0 , x(n) =  1.9 
n =  1 , x(n) =  0.8861433 
n =  2 , x(n) =  1.525136 
n =  3 , x(n) =  1.270086 
n =  4 , x(n) =  1.409894 
n =  5 , x(n) =  1.3414 
n =  6 , x(n) =  1.377166 
n =  7 , x(n) =  1.359052

Root Finding

Suppose we want to find a root of $ f(x) $ on $ [a,b] $.
Then we seek $ p \in [a,b] $ such that $ f(p)=0 $.

title

Root Finding and Fixed Point Iteration

title

\[ g(x) = x - f(x). \]

Suppose $ p $ solves

\[ f(x)=0. \]

Then $ p $ solves $ x = g(x) $:

\[ \begin{aligned} p & = p - f(p) \\ & \Leftrightarrow \\ f(p) & = 0 \end{aligned} \]

Example 1: Root Finding

title

For this example,

\[ \begin{aligned} f(x) &= 4 - x^2 \\ x & \in [-2,2] \end{aligned} \]

Then

\[ \begin{aligned} g(x) & = x - f(x) \\ & = x - (4-x^2) \\ & = x^2+x-4 \end{aligned} \]

Example 1: Root Finding (p = +/- 2)

title

Example 1: Root Finding (p = +/- 2)

title

Example 2 - 5: Root Finding

title

For Examples 2 - 5:

\[ f(x) = x^3+4x^2-10 \]

The root of $ f $ is

\[ p = 1.36523 \]

Example 2 Root Finding: p = 1.36523

title

Newton's Method $ g $
More details later

\[ \small{ \begin{aligned} f(x) &= x^3+4x^2-10 \\ g(x) & = x - \frac{f(x)}{f'(x)} \\ &= x-\frac{x^3+4x^2-10}{3x^2+8x} \end{aligned} } \]

From graph:

\[ |g'(p)| = 0 \]

Example 2 Root Finding: p = 1.36523

title

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  2.525 
n =  2 , x(n) =  1.721454 
n =  3 , x(n) =  1.414551 
n =  4 , x(n) =  1.366381 
n =  5 , x(n) =  1.365231 
n =  6 , x(n) =  1.36523 
n =  7 , x(n) =  1.36523 
n =  8 , x(n) =  1.36523

Example 3 Root Finding: p = 1.36523

title

For this example,

\[ \begin{aligned} x^3+4x^2-10 &= 0 \\ x^2(x+4) &= 10 \\ x & = \sqrt{\frac{10}{4+x}} \\ x &= g(x) \end{aligned} \]

From graph:

\[ 0 < |g'(p)| = k_3 < 1 \]

Example 3 Root Finding: p = 1.36523

title

g <- function(x)
{sqrt(10/(4+x))}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  1.118034 
n =  2 , x(n) =  1.397811 
n =  3 , x(n) =  1.361104 
n =  4 , x(n) =  1.365755 
n =  5 , x(n) =  1.365163 
n =  6 , x(n) =  1.365239 
n =  7 , x(n) =  1.365229 
n =  8 , x(n) =  1.36523

Example 4 Root Finding: p = 1.36523

title

For this example,

\[ \begin{aligned} x^3+4x^2-10 &= 0 \\ 4x^2 &= 10 - x^3 \\ x^2 & = \frac{1}{4}(\sqrt{10-x^3}) \\ x & = 0.5\sqrt{10-x^3} \\ x &= g(x) \end{aligned} \]

From graphs:

\[ 0 < k_3 < |g'(p)| = k_4 < 1 \]

Example 4 Root Finding: p = 1.36523

title

g <- function(x)
{0.5*sqrt(10 - x^3)}
fxdpt(g,1,8)

n =  0 , x(n) =  1 
n =  1 , x(n) =  1.5 
n =  2 , x(n) =  1.286954 
n =  3 , x(n) =  1.402541 
n =  4 , x(n) =  1.345458 
n =  5 , x(n) =  1.37517 
n =  6 , x(n) =  1.360094 
n =  7 , x(n) =  1.367847 
n =  8 , x(n) =  1.363887

Example 5 Root Finding: p = 1.36523

title

For this example,

\[ \begin{aligned} x^3+4x^2-10 &= 0 \\ x +(x^3+4x^2-10) &= x \\ x & = x -x^3-4x^2+10 \\ x &= x - f(x) \\ x &= g(x) \end{aligned} \]

From graph:

\[ |g'(p)| \gg 1 \]

Example 5 Root Finding: p = 1.36523

title

g <- function(x)
{x-x^3-4*x^2+10}
fxdpt(g,1.2,8)

n =  0 , x(n) =  1.2 
n =  1 , x(n) =  3.712 
n =  2 , x(n) =  -92.55122 
n =  3 , x(n) =  758423 
n =  4 , x(n) =  -4.362514e+17 
n =  5 , x(n) =  8.302532e+52 
n =  6 , x(n) =  -5.723105e+158 
n =  7 , x(n) =  NaN 
n =  8 , x(n) =  NaN

Recall Example 2

title

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  2.525 
n =  2 , x(n) =  1.721454 
n =  3 , x(n) =  1.414551 
n =  4 , x(n) =  1.366381 
n =  5 , x(n) =  1.365231 
n =  6 , x(n) =  1.36523 
n =  7 , x(n) =  1.36523 
n =  8 , x(n) =  1.36523

Example 2: Newton's Method

title

Newton's Method $ g $

\[ \small{ \begin{aligned} f(x) &= x^3+4x^2-10 \\ g(x) & = x - \frac{f(x)}{f'(x)} \\ &= x-\frac{x^3+4x^2-10}{3x^2+8x} \end{aligned} } \]

From graph:

\[ |g'(p)| = 0 \]

Newton's Method: Slope Condition

title

Find $ g $ with

\[ |g'(p)| = 0 \]

Newton's Method $ g $

\[ \small{ \begin{aligned} f(x) &= 0 \Rightarrow \\ g(x) & = x - \frac{f(x)}{f'(x)} \\ g'(x) & = 1 - \frac{f'(x)f'(x)-f(x)f''(x)}{\left[f'(x)\right]^2} \\ & = \frac{f(x)f''(x)}{\left[f'(x)\right]^2} \\ \\ g'(p) &= 0, \,\, \text{since $~f(p)=0$} \end{aligned} } \]

Newton's Method: Derivation

Taylor Polynomial about $ a = x_n $:

\[ \small{ f(x) = f(x_n) + f'(x_n)(x-x_n) + \frac{f''(c)}{2}(x-x_n)^2}, \,\, c \in [x_n,x] \]

When $ x = p $:

\[ \small{ \begin{aligned} 0 &\cong f(x_n) + f'(x_n)(p-x_n) \\ p-x_n &\cong -\frac{f(x_n)}{f'(x_n)} \\ p & \cong x_n - \frac{f(x_n)}{f'(x_n)} \\ x_{n+1} & = x_n - \frac{f(x_n)}{f'(x_n)} = g(x_n) \end{aligned} } \]

Example 2 Root Finding: p = 1.36523

title

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,4,8)

n =  0 , x(n) =  4 
n =  1 , x(n) =  2.525 
n =  2 , x(n) =  1.721454 
n =  3 , x(n) =  1.414551 
n =  4 , x(n) =  1.366381 
n =  5 , x(n) =  1.365231 
n =  6 , x(n) =  1.36523 
n =  7 , x(n) =  1.36523 
n =  8 , x(n) =  1.36523

Newton's Method: Cosine

title

Newton's Method $ g $

\[ \small{ \begin{aligned} f(x) &= \cos(x) \\ g(x) & = x - \frac{f(x)}{f'(x)} \\ & = x - \frac{\cos(x)}{(-\sin(x))} \\ & = x + \cot(x) \end{aligned} } \]

From graph:

\[ |g'(p)| = 0 \]

Example 1: Cosine (x0 = 0.5)

title

g <- function(x)
{x+cos(x)/sin(x)}
fxdpt(g,0.5,8)

n =  0 , x(n) =  0.5 
n =  1 , x(n) =  2.330488 
n =  2 , x(n) =  1.380623 
n =  3 , x(n) =  1.573123 
n =  4 , x(n) =  1.570796 
n =  5 , x(n) =  1.570796 
n =  6 , x(n) =  1.570796 
n =  7 , x(n) =  1.570796 
n =  8 , x(n) =  1.570796

Example 2: Cosine (x0 = 0.3)

title

g <- function(x)
{x+cos(x)/sin(x)}
fxdpt(g,0.3,8)

n =  0 , x(n) =  0.3 
n =  1 , x(n) =  3.532728 
n =  2 , x(n) =  5.957659 
n =  3 , x(n) =  2.994993 
n =  4 , x(n) =  -3.777389 
n =  5 , x(n) =  -5.132347 
n =  6 , x(n) =  -4.685825 
n =  7 , x(n) =  -4.712395 
n =  8 , x(n) =  -4.712389

Example 2: Cosine (x0 = 0.3)

\[ \small{ f(x) = \cos(x), \,\, g(x) = x + \frac{\cos(x)}{\sin(x)} } \]

title

Newton's Method: Tangent Line

Tangent line interpretation helpful

title

Newton's Method: Tangent Line

title

Start with $ x_0 $.
Plot $ (x_0,f(x_0)) $ on graph.
Draw tangent line thru $ (x_0,f(x_0)) $.
Find tangent line x-intercept.
$ x_1 $ = x-intercept.

Example 2: Cosine (x0 = 0.3)

\[ \small{ f(x) = \cos(x), \,\, g(x) = x + \frac{\cos(x)}{\sin(x)} } \]

title

Newton's Method: Assumptions

title

\[ \small{ \begin{aligned} g(x) &= x - \frac{f(x)}{f'(x)} \end{aligned} } \]

Newton's method can fail or be slow when

\[ \small{ \begin{aligned} f'(x_n) & = 0 \\ f'(p) & = 0 \\ |p - x_0 | & \gg 0 \end{aligned} } \]

Extrapolation-style methods can increase speed.
Modifications to Newton's method can also be used.

Example 1: Far Away x0 = -2.7

title

Example 1: Far Away x0 = -2.7

title

\[ \small{ \begin{aligned} g(x) &= x - \frac{f(x)}{f'(x)} \end{aligned} } \]

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,-2.7,8)

n =  0 , x(n) =  -2.7 
n =  1 , x(n) =  -0.762963 
n =  2 , x(n) =  -2.625483 
n =  3 , x(n) =  -4.244654 
n =  4 , x(n) =  -3.527627 
n =  5 , x(n) =  -3.07526 
n =  6 , x(n) =  -2.742458 
n =  7 , x(n) =  -1.873374 
n =  8 , x(n) =  -2.442309

Example 2: Far Away x0 = -2.8

title

Example 2: Far Away x0 = -2.8

title

\[ \small{ \begin{aligned} g(x) &= x - \frac{f(x)}{f'(x)} \end{aligned} } \]

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,-2.8,8)

n =  0 , x(n) =  -2.8 
n =  1 , x(n) =  -2.271429 
n =  2 , x(n) =  -2.673034 
n =  3 , x(n) =  7.485308 
n =  4 , x(n) =  4.70637 
n =  5 , x(n) =  2.949942 
n =  6 , x(n) =  1.934381 
n =  7 , x(n) =  1.477257 
n =  8 , x(n) =  1.370916

Example 3: Far Away x0 = -2.9

title

Example 3: Far Away x0 = -2.9

title

\[ \small{ \begin{aligned} g(x) &= x + \frac{f(x)}{f'(x)} \end{aligned} } \]

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,-2.9,8)

n =  0 , x(n) =  -2.9 
n =  1 , x(n) =  -2.531034 
n =  2 , x(n) =  -3.103542 
n =  3 , x(n) =  -2.767878 
n =  4 , x(n) =  -2.100915 
n =  5 , x(n) =  -2.554597 
n =  6 , x(n) =  -3.21517 
n =  7 , x(n) =  -2.858506 
n =  8 , x(n) =  -2.449547

Example 4: Far Away x0 = -3.0

title

Example 4: Far Away x0 = -3.0

title

\[ \small{ \begin{aligned} g(x) &= x - \frac{f(x)}{f'(x)} \end{aligned} } \]

g <- function(x)
{x-(x^3+4*x^2-10)/(3*x^2+8*x)}
fxdpt(g,-3.0,8)

n =  0 , x(n) =  -3 
n =  1 , x(n) =  -2.666667 
n =  2 , x(n) =  Inf 
n =  3 , x(n) =  NaN 
n =  4 , x(n) =  NaN 
n =  5 , x(n) =  NaN 
n =  6 , x(n) =  NaN 
n =  7 , x(n) =  NaN 
n =  8 , x(n) =  NaN

Example 5: f'(p) = 0; Regular Newton

title

For this example,

\[ \small{ \begin{aligned} f(x) &= e^x - x - 1, \,\, p = 0 \\ f(p) & = f'(p) = 0 \end{aligned} } \]

Formulas:
Newton & Modified Newton

\[ \small{ \begin{aligned} g_1(x) &= x - \frac{f(x)}{f'(x)} \\ g_2(x) &= x - \frac{f(x)f'(x)}{\left[f'(x)\right]^2-f(x)f''(x)} \\ \end{aligned} } \]

From graphs:

\[ \small{ \begin{aligned} g_1'(p) & \neq 0 \\ g_2'(p) &= 0 \end{aligned} } \]

Example 5: f'(p) = 0; Regular Newton

title

Example 5: f'(p) = 0; Regular Newton

title

\[ \small{ \begin{aligned} g_1(x) &= x - \frac{f(x)}{f'(x)} \\ x_n & = g_1(x_{n-1}) \end{aligned} } \]

g <- function(x)
{x-(exp(x)-x-1)/(exp(x)-1)}
fxdpt(g,0.8,8)

n =  0 , x(n) =  0.8 
n =  1 , x(n) =  0.452773 
n =  2 , x(n) =  0.243412 
n =  3 , x(n) =  0.1266386 
n =  4 , x(n) =  0.06465538 
n =  5 , x(n) =  0.03267603 
n =  6 , x(n) =  0.01642699 
n =  7 , x(n) =  0.008235981 
n =  8 , x(n) =  0.004123643

Example 6: f'(p) = 0; Modified Newton

title

For this example,

\[ \small{ \begin{aligned} f(x) &= e^x - x - 1, \,\, p = 0 \\ f(p) & = f'(p) = 0 \end{aligned} } \]

Formulas:
Newton & Modified Newton

\[ \small{ \begin{aligned} g_1(x) &= x - \frac{f(x)}{f'(x)} \\ g_2(x) &= x - \frac{f(x)f'(x)}{\left[f'(x)\right]^2-f(x)f''(x)} \\ \end{aligned} } \]

From graphs:

\[ \small{ \begin{aligned} g_1'(p) & \neq 0 \\ g_2'(p) &= 0 \end{aligned} } \]

Example 6: f'(p) = 0; Modified Newton

title

Example 6: f'(p) = 0; Modified Newton

title

\[ x_n = g_2(x_{n-1}) \]

g <- function(x)
{x-(exp(x)-x-1)*(exp(x)-1)/((exp(x)-1)^2-(exp(x)-x-1)*exp(x))}
fxdpt(g,0.8,8)

n =  0 , x(n) =  0.8 
n =  1 , x(n) =  -0.139855 
n =  2 , x(n) =  -0.003111746 
n =  3 , x(n) =  -1.612155e-06 
n =  4 , x(n) =  -2.867545e-10 
n =  5 , x(n) =  -2.867545e-10 
n =  6 , x(n) =  -2.867545e-10 
n =  7 , x(n) =  -2.867545e-10 
n =  8 , x(n) =  -2.867545e-10

Newton's Method: Conclusion

title

\[ \small{ \begin{aligned} g_1(x) &= x - \frac{f(x)}{f'(x)} \\ x_n & = g_1(x_{n-1}) \end{aligned} } \]

Valuable for scientific computing
Fast, reliable, accurate
Can fail or be slow when

\[ \small{ \begin{aligned} f'(x_n) & = 0 \\ f'(p) & = 0 \\ |p - x_0 | & \gg 0 \end{aligned} } \]

Hybrid and extrapolation-style methods can increase speed.
Modifications to Newton's method can also be used.