Relationship between Fixed Point Iteration & Newton's Method

Connection to Banach fixed-point iteration: For a Function

• Banach’s Iteration → Finds fixed point.
• Newton’s Method → Finds zero.

Newton’s method is an instance of the Banach’s iteration $x_{k+1}=g(x_k)$ where $g(x)=x-\frac{f(x)}{f^{\prime }(x)}$.

Newton’s method can be written as:

$$g(x_{k+1})=x_{k+1}=x_k-\frac{f\left(x_k\right)}{f^{\prime }\left(x_k\right)}$$

This is a fixed point iteration $x_{k+1}=g\left(x_k\right)$ where:

$$g(x)=x-\frac{f(x)}{f^{\prime }(x)}$$

Now, if ${\mathrm{x}}^{\ast }$ is a zero of $f$¹ , then $\mathrm{f}\left({\mathrm{x}}^{\ast }\right)=0$, which gives us:

$$g\left(x^{\ast }\right)=x^{\ast }-\frac{f\left(x^{\ast }\right)}{f^{\prime }\left(x^{\ast }\right)}=x^{\ast }-\frac{0}{f^{\prime }\left(x^{\ast }\right)}=x^{\ast }$$

So ${\mathrm{x}}^{\ast }$ is indeed a fixed point of $g$. The key insight is that zeros of $f$ correspond to fixed points of $g$.

Footnotes

1. Because of this assumption, we don’t apply the iteration formula, instead, use it as the condition that holds true. ↩