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:
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
Suppose we start the iteration with x0 = 2, then as we see in Figure 1, the iterations converge to 5 as expected.
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 = . Now define the m × 1 column vectors Xn and the m × m matrices Jn as follows
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 = and F = . Now
where we use the notation fx(x,y) to mean . Starting with X0 = , we see in Figure 2 that the procedure converges to x = 0.79206 and y = 2.20794 after 3 iterations.
Figure 2 – Newton’s Method for Example 2
Representative formulas for the worksheet in Figure 2 (for iteration 2) are shown in Figure 3.
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 – x – 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
The iteration proceeds as in Figure 4.
Figure 4 – Alternative use of Newton’s Method for Example 2
Thus x = 0.79206 and y = 3 – x = 3 – 0.79206 = 2.20794, as before.