3.6 Section 3.2 Newton root finding

Understanding Newton method

Start from the line equation. You remember we normally write it as

$y=c+mx$ where $c$ is the y-axis intercept and $m$ is the slope. But this equation always implicitly assumed that the slope is taken at $x_0=0$, and the intercept is also at $x_0=0$, hence the above can be written as $$\begin{array}{}\text{(1)}& y=f(x)=f\left(x_0\right)+f^{\prime }\left(x_0\right)(x-x_0)\end{array}$$

The above equation is the same as $y=c+mx$ when $x_0=0$

So from (1)

$$\begin{array}{rl}f(x)& =f\left(x_0\right)+f^{\prime }\left(x_0\right)(x-x_0)\\ \frac{f(x)-f\left(x_0\right)}{f^{\prime }\left(x_0\right)}& =(x-x_0)\end{array}$$

Now instead of writing $x$ and $x_0$ we write $x_{n+1}$ and $x_n$, so the above becomes

$$\begin{array}{rl}\frac{f\left(x_{n+1}\right)-f\left(x_n\right)}{f^{\prime }\left(x_n\right)}& =(x_{n+1}-x_n)\\ x_{n+1}& =\frac{f\left(x_{n+1}\right)-f\left(x_n\right)}{f^{\prime }\left(x_n\right)}+x_n\end{array}$$

That is it. Now for $x_{n+1}$, $f\left(x_{n+1}\right)=0$, and that is the whole idea. Replace $f\left(x_{n+1}\right)$ by zero in the above we obtain

$$x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}$$

Which is Newton method.

Theorem: Let $f^{\prime \prime }$be C${}^2$ and let $r$ be a simple zero. There is a neighborhood of r and a constant C s.t. if Newton method is started in that neighborhood it will converge to r according to $|x_{n+1}-r|\le C{|x_n-1|}^2$

Proof of quadratic convergence order

Figure 3.12:quadratic convergence

From diagram we see that

$$\begin{array}{}\text{(1)}& e_{n+1}=r-x_{n+1}\end{array}$$

But from definition of Newton root finding

$$\begin{array}{}\text{(2)}& x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}\end{array}$$

substituting (2) into (1) gives

$$\begin{array}{rl}{e}_{n+1}& =r-(x_n-\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)})\\ & =\stackrel{e_n}{\overbrace{r-x_n}}+\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}\\ & =e_n+\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}\\ \text{(3)}& & =\frac{e_n{f}^{\prime }\left(x_n\right)+f\left(x_n\right)}{f^{\prime }\left(x_n\right)}\end{array}$$

Now evaluate $f(x)$ at $r$ by expanding it using Taylor around $x_n$

$$f(r)=f\left(x_n\right)+h{f}^{\prime }\left(x_n\right)+\frac{h^2{f}^{\prime \prime }\left(\xi \right)}{2!}$$

But $h$ is the distance between $r$ and $x_n$, which is $e_n$, hence the above becomes

$$f(r)=f\left(x_n\right)+e_n{f}^{\prime }\left(x_n\right)+\frac{e_n^2{f}^{\prime \prime }\left(\xi \right)}{2!}$$

But $f(r)=0$ since this is a root finding, and that is our goal. Hence the above becomes

$$\begin{array}{rl}0& =f\left(x_n\right)+e_n{f}^{\prime }\left(x_n\right)+\frac{e_n^2{f}^{\prime \prime }\left(\xi \right)}{2!}\\ \text{(4)}& f\left(x_n\right)+e_n{f}^{\prime }\left(x_n\right)& =-\frac{f^{\prime \prime }\left(\xi \right)}{2!}{e}_n^2\end{array}$$

Substituting (4) into numerator of (3) gives

$$\begin{array}{rl}{e}_{n+1}& =\frac{-\frac{f^{\prime \prime }\left(\xi \right)}{2!}{e}_n^2}{f^{\prime }\left(x_n\right)}\\ & =-\frac{f^{\prime \prime }\left(\xi \right)}{2f^{\prime }\left(x_n\right)}{e}_n^2\end{array}$$

but $\frac{f^{\prime \prime }\left(\xi \right)}{f^{\prime }\left(x_n\right)}\approx \frac{f^{\prime \prime }(r)}{f^{\prime }(r)}=k$ (some constant), hence above becomes

$$e_{n+1}=k_1{e}_n^2$$

where $k_1$ is some constant as well.

Hence we can find a constant C such that $e_{n+1}\le C{e}_n^2$ where $C$ is any constant smaller than $k_1$

The above proofes that Newton method converges quadratically.

3.6.1 Definition of convex function

A function $f(x)$ is convex if $f^{\prime \prime }\left(x\right)$ $\ge 0$ for all $x.$

Mathworld has this definition

”A convex function is a continuous function whose value at the midpoint of every interval in its domain does not exceed the arithmetic mean of its values at the ends of the interval.” diagram below from Mathworld

Figure 3.13:Mathworld

How to use Newton method to find $\sqrt{R}$ ?

Let $x=\sqrt{R}$, hence $x^2-R=0$ is $f(x)$ to use with Newton method. This leads to $x_{n+1}=x_n-\frac{x_n^2-R}{2x_n}=\frac{1}{2}(x_n+\frac{R}{x_n})$

3.6.2 Newton method to solve set of equations

Writing

$$\begin{array}{rl}\left[\begin{array}{c}{x}_{n+1}\\ y_{n+1}\end{array}\right]& =\left[\begin{array}{c}{x}_n\\ y_n\end{array}\right]-F\left(x_n\right)J^{-1}\left(x_n\right)\\ & =\left[\begin{array}{c}{x}_n\\ y_n\end{array}\right]-\left[\begin{array}{c}{F}_1(x_n,y_n)\\ F_2(x_n,y_n)\end{array}\right]\left[\begin{array}{ccc}\frac{\partial F_1(x_n,y_n)}{x_n}& & \frac{\partial F_1(x_n,y_n)}{y_n}\\ \frac{\partial F_2(x_n,y_n)}{x_n}& & \frac{\partial F_2(x_n,y_n)}{x_n}\end{array}\right]\end{array}$$