2.12 Newton’s Method
Newton’s method is a numerical technique for solving equations of the form
where f : n → n is differentiable. It starts with an initial guess or “seed” value x, which the user supplies. Based upon this, the procedure recursively generates a sequence of values x, x, x, … , which should converge to a solution.
2.12.1 Univariate Newton’s Method
In the univariate case, we consider f : → and seek a value x such that
If f is nonlinear, this may be difficult to solve directly. However, we can fit a linear polynomial approximation to f and easily solve
The solution approximates a solution to the original equation [2.137]. The quality of the approximation depends upon how we construct . Newton’s method repeats this process recursively, at each step improving its approximation of f until the solution for [2.138] comes sufficiently close to a solution for [2.137].
Start with seed value x. Fit a tangent-line approximation  to f :
and select x as the solution to
This is illustrated in Exhibit 2.16.
Repeat the process at x to obtain  and x. Subsequent [k] and x[k + 1] are obtained recursively in this manner. In general
Setting this equal to 0 and solving for x[k + 1] yields
This is the general recursive formula for the univariate Newton’s method.
2.12.2 Example: Univariate Newton’s Method
Consider the equation
In this case,
Starting with seed value x = 1, apply [2.142] recursively. Results are indicated in Exhibit 2.17. Equation [2.143] has solution x = 1.19089.
The univariate Newton’s method is easy to implement and usually converges rapidly. In theory, it can fail. This can happen if f ′(x[k]) = 0 for some k or if f has an inconvenient shape. Such a circumstance is depicted in Exhibit 2.18. These problems may be solved by starting at a different seed value x.
Equation [2.137] need not have any solutions, so failure of Newton’s method to converge may indicate that no solutions exist. Alternatively, [2.137] may have multiple solutions. For any given seed value, Newton’s method will find only one solution. Starting with other seed values may allow us to find others, but Newton’s method may converge to the same solution found with the first seed value. In this situation, Newton’s method must be supplemented with other analyses to ensure all solutions are found. Suitable analyses will depend upon the form of Equation [2.137].
2.12.4 Secant Method
If an analytic expression for the derivative of f is unavailable, it can be approximated using finite differences. Another alternative is the secant method, which is a modification of Newton’s method. Using the same general approach as Newton’s method, it replaces tangent lines with secant lines interpolated between consecutive points x[k − 1] and x[k], as illustrated in Exhibit 2.19.
In recursive formula [2.142] of Newton’s method, the derivative f ′(x[k]) is replaced with the secant line slope
Given values x[k − 1] and x[k], subsequent value x[k + 1] is obtained as
The secant method is initialized with two seed values x and x. The function f need not be differentiable. As long as it is continuous and reasonably well behaved, the secant method generally performs well, but convergence issues similar to those with Newton’s method arise.