Question

What is the order of convergence of Newton Raphson Method?

Answer 1

The order of convergence of Newton Raphson Method:

According to the method, an approximation of a real-valued function $f\left(x\right)=0$ is given by the formula:

${\mathbf{\text{x}}}_{\mathbf{n}\mathbf{+}\mathbf{1}}{\mathbf{\text{=x}}}_{\mathbf{n}}\mathbf{-}\frac{\mathbf{f}\left(x_n\right)}{{\mathbf{f}}^{\mathbf{\text{'}}}\left(x_n\right)}$

Let $a$ be the exact root of the function and ${\epsilon }_n$be the error in the value at $nth$ approximation,

Then,

$x_n=a+{\epsilon }_n$.

In the same manner:

$x_{n+1}=a+{\epsilon }_{n+1}$

Use the values, $x_n=a+{\epsilon }_n$and $x_{n+1}=a+{\epsilon }_{n+1}$in the formula ${\text{x}}_{n+1}{\text{=x}}_n-\frac{f\left(x_n\right)}{f^{\text{'}}\left(x_n\right)}$:

$a+{\epsilon }_{n+1}\text{=}a{\text{+ε}}_n-\frac{f\left(a+{\epsilon }_n\right)}{f^{\text{'}}\left(a+{\epsilon }_n\right)}$

Simplify::

${\epsilon }_{n+1}{\text{=ε}}_n-\frac{f\left(a+{\epsilon }_n\right)}{f^{\text{'}}\left(a+{\epsilon }_n\right)}$

Now use the formula of Taylor expansion, $f\left(x+a\right)=f\left(a\right)+x{f}^{\text{'}}\left(a\right)+\frac{x^2}{2}{f}^{\text{'}\text{'}}\left(a\right)+....$ as follows:

${\epsilon }_{n+1}{\text{=ε}}_n-\frac{f\left(a\right)+{\epsilon }_n{f}^{\text{'}}\left(a\right)+{\displaystyle \frac{{\epsilon }_n^2}{2}}{f}^{\text{'}\text{'}}\left(a\right)+...}{f^{\text{'}}\left(a\right)+{\epsilon }_n{f}^{\text{'}\text{'}}\left(a\right)+\frac{{\epsilon }_n^2}{2}{f}^{\text{'}\text{'}\text{'}}\left(a\right)+...}$.

Neglect ${\epsilon }_n^2$and higher powers

${\epsilon }_{n+1}{\text{=ε}}_n-\frac{f\left(a\right)+{\epsilon }_n{f}^{\text{'}}\left(a\right)}{f^{\text{'}}\left(a\right)+{\epsilon }_n{f}^{\text{'}\text{'}}\left(a\right)}$

Since, $a$is the exact root, $f\left(a\right)=0$. thus substitute $f\left(a\right)=0$in above equation:

${\epsilon }_{n+1}{\text{=ε}}_n-\frac{{\epsilon }_n{f}^{\text{'}}\left(a\right)}{f^{\text{'}}\left(a\right)+{\epsilon }_n{f}^{\text{'}\text{'}}\left(a\right)}$

Simplify:

$$\begin{gathered} {\epsilon }_{n+1}\text{=}\frac{{\epsilon }_n{f}^{\text{'}}\left(a\right)+{\epsilon }_n^2{f}^{\text{'}\text{'}}\left(a\right)-{\epsilon }_n{f}^{\text{'}}\left(a\right)}{f^{\text{'}}\left(a\right)+{\epsilon }_n{f}^{\text{'}\text{'}}\left(a\right)} \\ \text{=}\frac{\bcancel{{\epsilon }_n{f}^{\text{'}}\left(a\right)}+{\epsilon }_n^2{f}^{\text{'}\text{'}}\left(a\right)-\bcancel{{\epsilon }_n{f}^{\text{'}}\left(a\right)}}{f^{\text{'}}\left(a\right)+{\epsilon }_n{f}^{\text{'}\text{'}}\left(a\right)} \\ \text{=}\frac{{\epsilon }_n^2{f}^{\text{'}\text{'}}\left(a\right)}{f^{\text{'}}\left(a\right)+{\epsilon }_n{f}^{\text{'}\text{'}}\left(a\right)} \\ \text{=}{\epsilon }_n^2\frac{f^{\text{'}\text{'}}\left(a\right)}{f^{\text{'}}\left(a\right)}{\left(1+\frac{f^{\text{'}\text{'}}\left(a\right)}{f^{\text{'}}\left(a\right)}\right)}^{-1} \end{gathered}$$

Since the error ${\epsilon }_{n+1}$varies directly to ${\epsilon }_n^2$. Means, the error in each step varies directly to the square of the error of last step.

It is concluded, the order of convergence of Newton Raphson Method is two or quadratic convergence.