Newton Raphson Method Introduction

In numerical analysis, finding the roots of equations (where a function equals zero) is a common task. Iterative methods are frequently used to approximate these roots. One of the most powerful and widely used iterative methods is the Newton Raphson method. This method uses the function's value and its derivative at a given point to find a better approximation of the root in the next step.

Understanding Order of Convergence

The order of convergence of an iterative method tells us how quickly the sequence of approximations generated by the method approaches the true root. A higher order of convergence means that the method converges faster, requiring fewer iterations to achieve a desired level of accuracy. If the order of convergence is:

• 1 (Linear Convergence): The error in the next iteration is roughly proportional to the error in the current iteration.
• 2 (Quadratic Convergence): The error in the next iteration is roughly proportional to the square of the error in the current iteration. This means the number of correct digits approximately doubles with each iteration, leading to very rapid convergence.

Newton Raphson Method Explained

The Newton Raphson method is an open method that uses the tangent line to approximate the function. The formula for the next approximation $x_{n+1}$ based on the current approximation $x_n$ is given by:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Where:

• $f(x_n)$ is the value of the function at $x_n$.
• $f'(x_n)$ is the value of the derivative of the function at $x_n$.

A crucial requirement for this method to work effectively is that the derivative $f'(x_n)$ must not be zero or very close to zero at the root or near the iterations.

Convergence Order of Newton Raphson Method

The order of convergence of the Newton Raphson method is typically 2, meaning it exhibits quadratic convergence. This rapid convergence is one of its major advantages, allowing it to find roots very efficiently, provided certain conditions are met.

For the Newton Raphson method to achieve quadratic convergence:

• The function $f(x)$ must be continuously differentiable.
• The derivative $f'(x)$ must not be zero at the actual root. If the derivative is zero at the root (i.e., a multiple root), the convergence order can degrade to linear (order 1).
• The initial guess $x_0$ must be sufficiently close to the true root. If the initial guess is too far, the method might diverge or converge to a different root.

Why Quadratic Convergence?

The quadratic convergence of the Newton Raphson method can be understood by examining the Taylor series expansion of the function around the root. If $r$ is the true root, and $x_n$ is an approximation, the error $e_n = x_n - r$. By using Taylor's theorem to expand $f(r)$ around $x_n$ and substituting into the Newton Raphson formula, it can be shown that the error in the next iteration $e_{n+1}$ is proportional to $e_n^2$, thus confirming the order of convergence as 2.

In summary, the Newton Raphson method is highly valued for its speed of convergence, which is typically quadratic, making it very effective for finding roots of functions when the derivative can be easily computed and a good initial guess is available.