APPENDIX B

Newton-Raphson Method

The Newton-Raphson Method is an iterative procedure used to determine the root of an equation. In some simple situations the root is easy to find. Consider the following equation (equation B.1):

Clearly the root of f(x), the value of x such that f(x) = 0, is when x = 3. A slightly more complicated example is a generic quadratic equation (equation B.2):

where the solution is the quadratic equation in the form of (equation B.3):

However, what happens when we need to compute the root of an arbitrary function that does not have an analytical solution? For example, how would we find the root of the following function (equation B.4)?

The answer in this case is not so easily determined. The simplest solution is to guess a possible range that might contain the answer and then step through each value until the answer is found. This brute-force method, however, is highly unreliable and extremely slow. A more robust and faster solution is to use the Newton-Raphson iterative method.

The method requires the analyst to start with a guess, x_o, and then the process iterates through successive values of x until the root is found. The step size of the guess and the direction of the step are determined not only by the value at f(x) but also by its slope, or derivative. The derivation of the method is simple, but it provides deep insight into how the process works. To begin, we can write the definition of a derivative (equation B.5):

FIGURE B.1 Point a would cause a jump forward, while point b would cause a jump backward. Point c is unstable because the slope is nearly 0.

The zero in the numerator is there because we are trying to arrive at the root, with a value of zero and with the hope that this happens at x_n+1. This equation can be rewritten to give the formal definition of the Newton-Raphson procedure (equation B.6):

The reason why this equation doesn't just “work” is that a true definition of a derivative is an instantaneous change in x. If x_n is too far from the root, then the slope as computed by equation B.5 would not be a very accurate representation of the derivative. In other words, there is too much error in the representation, and an iterative process is required to converge onto the right answer.

Figure B.1 provides a graphical view of how the iteration works. At point a, the slope is positive but the value of the function is negative. Thus the next step in the iteration would result in an increase in x. At point b, the slope is still positive but the value is also positive, resulting in a decrease in x. Point c is an illustration of how crucial the starting guess, x_o, is regarding the stability of the iteration. Notice at point c that the slope is effectively zero and would cause the second term in equation B.6 to effectively “blow up.” When applying this method, care should be taken to not start off in this region.