Ch6.1.2 Fixed Point Iteration

Fixed Point Iteration for Sqrt(2)

title

\[ \small{x_{k+1} = \frac{x_{k}}{2} + \frac{1}{x_k}} \]

sqrt(2)

[1] 1.414214

babylonian(1.4,3)

n =  0 , x(n) =  1.4 
n =  1 , x(n) =  1.414286 
n =  2 , x(n) =  1.414214 
n =  3 , x(n) =  1.414214

babylonian(1.42,3)

n =  0 , x(n) =  1.42 
n =  1 , x(n) =  1.414225 
n =  2 , x(n) =  1.414214 
n =  3 , x(n) =  1.414214

Humor



What did the fish say when he hit the wall?

Dam.

Fixed Point Definition

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

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

Fixed Point Theorem 2: 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