Newton’s Method

Section A.1 Newton’s Method

FINDING THE ROOT OF ONE NONLINEAR EQUATION.

Newton’s method is a computational algorithm that can be used to find the roots of an equation. Let’s illustrate with an example.

Figure A.1.1.

In Figure A.1.1, the solid blue line represents the function \(f(x)\text{.}\) Assume that \(x^*\) is an unknown root of \(f(x)\) such that \(f(x^*)=0\text{.}\) We may be able to guess at an approximate value of the root \(x=x_0\text{,}\) but this is unlikely to be very precise. Exmining Figure A.1.1, we can see that we can find a better approximation of the function’s root by using a straight-line (dashed red curve) with the same slope as our function at the location of our initial guess,

\begin{equation*} f'(x_0) = \frac{f(x_0)-0}{x_0-x_1} \end{equation*}

which can be rearranged to find our new estimate

\begin{equation*} x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} \end{equation*}

We’ll call this new approximated root \(x_1\text{.}\) It’s very possible that this new guess still lacks the precision that we desire, so we can repeat the process again, iterating as many times as we desire using

\begin{equation*} x_{n}=x_{n-1} - \frac{f(x_{n-1})}{f'(x_{n-1})} \end{equation*}

until \(\left|x_n-x_{n-1}\right|\) is less than some user-defined tolerance that defines the desired precision, as the change in the estimate to our root from one iteration to the next should become smaller as our estimate approaches the real value of the function’s root. Note that this method requires knowledge of the functional form of our function \(f(x)\) as well as knowledge of or the ability to calculate the analytic form of \(f'(x)\text{.}\)

We can be a little more rigorous with the theory underlying Newton’s method. Let’s assume that we have a function \(f(x)\) that has a root \(x^*\) such that \(f(x^*)=0\text{.}\) We can expand our function as a Taylor series around some initial guess for the root, \(x_g\text{,}\) giving us

\begin{equation*} f(x)=f(x_g) + (x-x_g)f'(x_g) + \frac{1}{2}(x-x_g)^2 f''(x_g) + \cdots\text{.} \end{equation*}

Evaluating this expansion at the root \(x=x^*\) gives us

\begin{equation*} 0=f(x^*)=f(x_g) + (x^*-x_g)f'(x_g) + \frac{1}{2}(x^*-x_g)^2 f''(x_g) + \cdots\text{.} \end{equation*}

If we divide both sides by \(f'(x_g)\) and assume that all terms that are order two or higher in \((x^*-x_g)\) are small, then

\begin{equation*} 0=(x^*_\text{est}-x_g) + \frac{f(x_g)}{f'(x_g)} \end{equation*}

\begin{equation*} x^*_\text{est}= x_g- \frac{f(x_g)}{f'(x_g)} \end{equation*}

where \(x^*_\text{est}\) is our estimate of the root based on one iteration of this method. Now, the closer \(x_g\) is to the real root \(x^*\text{,}\) the better our estimate \(x^*_\text{est}\) will be. So, once we have \(x^*_\text{est}\text{,}\) we can use this as our new guess for another iteration, giving us a result identical to what we found above,

\begin{equation*} x_{n}=x_{n-1} - \frac{f(x_{n-1})}{f'(x_{n-1})}\text{,} \end{equation*}

which we iterate until \(\left|x_n-x_{n-1}\right|\) is less than some user-defined tolerance that defines the desired precision.

A word of caution: Newton’s method is not foolproof and it can fail sometimes. Please take a look at other computational methods textbooks or webpages to investigate these failure modes. For the purposes of this text, try several different initial guesses if your first choice leads to a failure of the method.

FINDING THE ROOTS OF A SYSTEM OF NONLINEAR EQUATIONS.

Write your equations in the following form:

\begin{align*} f_1(x_1,...,x_N) =\amp 0 \\ \vdots\amp \\ f_N(x_1,...,x_N) =\amp 0 \end{align*}

with roots \(x_1^*, ...,x_N^*\text{.}\) The Taylor expansion for \(f_i\) can be written as

\begin{equation*} f_i(x^*_1,\dots,x^*_N) = f_i(x_1,\dots,x_N) + \sum\limits_j \left(x_j^*-x_j\right)\frac{\partial f_i}{\partial x_j} + \mathcal{O}(\text{small})=0 \end{equation*}

so that

\begin{equation*} \sum\limits_j \left(x_j-x_j^*\right)\frac{\partial f_i}{\partial x_j} + \mathcal{O}(\text{small}) = f_i(x_1,\dots,x_N)\text{.} \end{equation*}

Each \(i\) value can represent the \(i\)-th equation in a system of equations. This system can be written in vector form as

\begin{equation*} \vec{f}(\vec{x}^*) = \vec{f}(\vec{x}) + \nabla\vec{f}\cdot(\vec{x}^* - \vec{x}) + \mathcal{O}(\text{small}) \end{equation*}

where \(\nabla\vec{f}\) is the \(N\times N\) matrix with elements \(\partial f_i /\partial x_j\text{.}\) Since \(\vec{x}^*\) is a root of the equations, we have \(\vec{f}(\vec{x}^*)=0\) so that

\begin{equation*} \nabla\vec{f} \cdot \Delta \vec{x} + \mathcal{O}(\text{small}) = \vec{f}(\vec{x}) \end{equation*}

where \(\Delta \vec{x}=\vec{x} - \vec{x}^*\text{.}\) Thus, we can get a good estimate of our root, \(\vec{x}'\text{,}\) using

\begin{equation*} \nabla\vec{f} \cdot \Delta \vec{x} = \vec{f}(\vec{x}) \end{equation*}

where \(\Delta\vec{x}=\vec{x}-\vec{x}'\) now. This is a set of ordinary linear simultaneous equations of the form \(\vec{A}\vec{x} = \vec{v}\) which can be solved using the linalg.solve package in NumPy. Once we’ve solved for \(\Delta \vec{x}\text{,}\) our new estimate \(\vec{x}'\) of the root is

\begin{equation*} \vec{x}' = \vec{x}-\Delta\vec{x}\text{.} \end{equation*}

Wheatstone Bridge example.

Prev Top Next