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 $.

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")  }
  }

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

Humor



I like telling Dad jokes.

Sometimes he laughs!

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.