Mastering Algorithms With C - Kyle Loudon [153]
In each of the four parts of Figure 13.7, f (x) is shown as a heavy line, and a and b are shown as vertical dotted lines. If f (a) matches the criteria just given, iteration begins at a and tangent lines slope from a toward the root to which we would like to converge. If f (b) matches the criteria above, iteration begins at b and tangent lines slope from b toward the root to which we would like to converge.
Figure 13.7. Convergence of Newton's method
How Newton's Method Works
As an example, suppose we would like to find the roots of f (x) = x 3 - x 2 - 3x + 1.8. Figure 13-8 illustrates that this function appears to have three roots: one on the interval [-2, -1], another on the interval [0, -1], and a third on the interval [2, 3]. Once we have an idea of the number and location of a function's roots, we test each interval against the rules for selecting an initial iteration point. To do this, we need to know the following:
Using this information, we see that the interval [-2, -1] satisfies the first rule because f (-2) = -4.2 and f (-1) = 2.8, and f ' (x) does not change sign on the interval: it is always positive. Considering this, we know there is, in fact, one and only one root on the interval [-2, -1]. To satisfy the second rule, we see that f '' (x) does not change sign on the interval: it is negative. We select x 0 = -2 as the initial iteration point since f (-2) = -4.2 is also negative. Figure 13.8 illustrates calculating the root on this interval to within 0.0001 of its actual value. We end up iterating five times to obtain this approximation.
Figure 13.8. Calculating the three real roots of f (x) = x3 - x2 - 3x + 1.8 = 0 to within 0.0001 of their actual values
Moving to the root on the interval [0, 1], we see that the first rule is satisfied just as for the previous interval. However, the sign of f '' (x) is not constant on this interval; therefore, the interval does not satisfy the second rule. Suspecting that the root is closer to 1 than 0, we try the interval [0.5, 1] next, which corrects the problem. The first rule is satisfied because f (0.5) = 0.175 and f (1) = -1.2, and f ' (x) does not change sign on the interval: it is negative. To complete the second rule, we select x 0 = 0.5 since f (0.5) = 0.175 is positive and has the same sign as f '' (x) over the interval [0.5, 1]. Figure 13.8 illustrates calculating the root on this interval to within 0.0001 of its actual value. We end up iterating four times to obtain this approximation. Calculating the third root proceeds in a similar manner.
Interface for the Solution of Equations
Name
root
Synopsis
int root(double (*f)(double x), double (*g)(double x), double *x, int *n,
double delta)
Return Value
0if a root is found, -1 otherwise.
Description
Computes the root of f to which Newton's method converges given an initial iteration point. This point is specified in x[0]. The derivative of f is specified in g. The argument n is the maximum number of iterations to perform. The argument delta is the difference between successive approximations at which to stop iterating. Upon return, successive values of x calculated during the iteration process are returned in the x array. Upon return, n contains the number of values in array x. It is the responsibility of the caller to manage the storage associated with x.
Complexity
O (n), where n is the maximum number of iterations the caller wishes to perform.
Implementation and Analysis of the Solution of Equations
Recall that solving an equation of the form f (x) = means finding its roots. The root operation locates the real root to which Newton's method converges given