Nonlinear finite elements/Newton Raphson method

The Newton-Raphson method

The Newton-Raphson method is a technique used to find the roots of nonlinear algebraic equations. The method is also called Newton's method.

Let us revisit Newton's method of finding roots in the context of an equation with one degree of freedom. Let the nonlinear equation be

$f(x)=0.$

We wish to find one root of the equation (recall that if $f(x)$ is linear or quadratic, we can find the root in exact form).

Let us select a point $x_1$ on the curve (see Figure 1). The slope of the curve at point $x_1$ is $df(x_1)/dx$. Therefore, the equation of the tangent to the curve at $(x_1,f(x_1))$ is

$y-f(x_1)=\frac{df(x_1)}{dx}(x-x_1).$

At $y=0$, the tangent meets the $x$-axis at $x_2$. Therefore we have

$-f(x_1)=\frac{df(x_1)}{dx}(x_2-x_1)⟹x_2=x_1-\frac{f(x_1)}{df(x_1)/dx}.$

Recall that the root of $f(x)$ is the point where the curve of the function meets the $x$-axis. Therefore, we can repeat the process until we arrive at the root. The Newton iteration scheme is given by

$x_{r+1}=x_r-\frac{f(x_r)}{\frac{df(x_r)}{dx}}.$

File:NewtonIter.png Figure 1. Newton's method of finding roots.

The iterative procedure is terminated when the following condition is met:

$|x_{r+1}-x_r|<ϵ$

where $ϵ$ is a small value that depends on the desired accuracy and on machine precision. The Newton-Raphson method gives a quadratic convergence rate. That is, the difference between the answer and the approximate solution is proportional to the previous difference squared. This can be seen by Taylor expanding the non-linear equation and its derivative around the root, and inserting this into the expression for $x_{r+1}$.