Newton’s Method

Newton’s Method is traditionally used to find the roots of a non-linear equation.

Definition 1 (Newton’s Method): Let f(x) = 0 be an equation. Define xn recursively as follows:

image3019 image3020

Here f′(xn) refers to the derivative f(x) of at xn.

Property 1: Let xn be defined from f(x) as in Definition 1. As long as function f is well behaved and the initial guess is suitable, then f(xn) ≈ 0 for sufficiently large n.

Observation: Newton’s method requires that f(x) has a derivative and that the derivative not be zero. Usually the method converges quickly to a solution, but this can depend on the initial guess. Also in cases where there are multiple solutions, different initial guesses can lead to different solutions.

Example 1: Use Newton’s Method to find the square root of 25.

The problem is equivalent to solving the equation f(x) = 0 where f(x) = x2 – 25.

From calculus, f′(x) = 2x, and so

image3026

Suppose we start the iteration with x0 = 2, then as we see in Figure 1, the iterations converge to 5 as expected.

Newtons method Excel

Figure 1

Figure 1 – Newton’s Method for Example 1

Note that if we select x0 = 0 the algorithm won’t converge to a solution since  would be undefined. Also if we set x0 = -2 (or any negative value) then the procedure iterates to -5, which is the other solution to f(x) = 0.

We now extend Newton’s method to m equations in m unknowns.

Definition 2 (Newton’s Method): Let X = [xi] be an m × 1 column vector and let F = [fi] be an m × 1 column vector of functions. Our objective is to solve the set of m equations given by F(x) = Ο (here Ο is the zero vector).

Let J = [qij] be the Jacobian matrix, defined by the partial derivatives qij = \frac{\partial f_i}{\partial x_j}. Now define the m × 1 column vectors Xn and the m × m matrices Jn as follows

image3035 image3036 image3037

Property 2: Using the terminology in Definition 2, then for a well-behaved F, a reasonable guess and sufficiently large n, F(Xn) ≈ Ο.

Example 2: Find the solution to the equations  y – ex = 0 and x + y = 3.

Set f(x, y) = y – ex and g(x, y) = x + y – 3. Then we need to find the solution to f(x, y) = 0  and  g(x, y) = 0 , i.e.  F(X) = Ο where X =  \left[ \! \begin{array}{c} x \\ y \end{array} \right] \! and F = \left[ \! \begin{array}{c} f \\ g \end{array} \right] \!. Now

image3049

where we use the notation fx(x,y) to mean \frac{\partial f(x,y)}{\partial x}. Starting with X0 = \left[ \! \begin{array}{c}1\\1\end{array} \! \right], we see in Figure 2 that the procedure converges to x = 0.79206 and y = 2.20794 after 3 iterations.

Newtons method matrix Excel

Figure 2 – Newton’s Method for Example 2

Figure 2 – Newton’s Method for Example 2

Representative formulas for the worksheet in Figure 2 (for iteration 2) are shown in Figure 3.

Formulas Newton's method Excel

Figure 3 – Formulas for 2nd iteration

The example was chosen so that we could check the result using Newton’s method in one variable since the problem is equivalent to ex – 3 = 0 and y = 3 – x. We can therefore apply Newton’s method as in Example 1, with f(x) = ex – x – 3, f′(x) = ex – 1, and so

image3058

The iteration proceeds as in Figure 4.

Newton's method

Figure 4

Figure 4 – Alternative use of Newton’s Method for Example 2

Thus x = 0.79206 and y = 3  – = 3 – 0.79206 = 2.20794, as before.

Leave a Reply

Your email address will not be published. Required fields are marked *