2.4 Newton's Method

We’d like to convert a root-finding problem to a fixed point problem that converges and does so quickly.

In the previous section, we saw that the condition $f^{\prime }(\hat{x})=0$ yields quadratic convergence.

Idea: If $\hat{x}$ is a root of $g(x)$ and $g^{\prime }(\hat{x})\ne 0$, then $\hat{x}$ is a fixed point of

Furthermore, $f^{\prime }(\hat{x})=0$.

Geometry of Newton's Method

Tangent: $y=g(x_{i-1})+g^{\prime }(x_{i-1})(x-x_{i-1})$
$x_i$ is computed from the intersection of the tangent line at $(x_{i-1},g(x_{i-1}))$ and the x-axis.

The “rise” $(-g(x_{i-1}))$ over the “run” $(x_i-x_{i-1})$ must equal $g^{\prime }(x_{i-1})$. In other words,

Deriving Newton's Method

Input: A function $g$ with root $\hat{x}$, where $g$ is differentiable around $\hat{x}$, an initial point $x_0$ in a neighbourhood $(\hat{x}-\delta ,\hat{x}+\delta )$ such that $|f^{\prime }|<1$ where $f^{\prime }=1-\frac{g}{g^{\prime }}$. Also a desired tolerance $\epsilon$ and max iterations $N$.

Output: An approximate $x$ close to the root $\hat{x}$ of $g$, or failure.

Outline:
• Given $x_0$, evaluate $x=x_0-\frac{g(x_0)}{g\prime (x_0)}$.
• If $|x-x_0|\le \epsilon$, then tolerance is achieved, so output $x$.
• Otherwise, set $x_0\leftarrow x$.
• Repeat this either until the desired accuracy is achieved (and return the iterate) or until the maximum iterations $N$ is reached (print method failed).

Potential issue: What if we don’t know or can’t compute the derivative $g^{\prime }$?

Secant Method

Workaround: Use a difference formula instead:

• This method is called the secant method.
• Need to keep track of two iterates at any given time.
• Need two initial values!
• Some strategies are to pick $x_1$ close to $x_0$, or to set $x_1=x_0+g(x_0)$ which works well if $x_0$ is already a good approximation.
• The order of convergence of the secant method is $\frac{1+\sqrt{5}}{2}$.