Mastering Algorithms With C - Kyle Loudon [152]
Computing the Derivative of a Polynomial
The derivative of a function is fundamental to calculus and can be described in many ways. For now, let's simply look at a formulaic description, specifically for polynomials. To compute the derivative of a polynomial, we apply to each of its terms one of two formulas:
where k is a constant, r is a rational number, and x is an unknown. The symbol d /dx means "derivative of," where x is the variable in the polynomial. For each term that is a constant, we apply the first formula; otherwise, we apply the second. For example, suppose we have the function:
In order to compute f ' (x), the derivative of f (x), we apply the second formula to the first three terms of the polynomial, and the first formula to the last term, as follows:
Sometimes it is necessary to compute higher-order derivatives as well, which are derivatives of derivatives. For example, the second derivative of f (x), written f '' (x), is the derivative of f ' (x). Similarly, the third derivative of f (x), written f ''' (x), is the derivative of f '' (x), and so forth. Thus, to compute the second derivative of f (x) in the previous equation, we compute the derivative of f ' (x), as follows:
Understanding the First and Second Derivative
Now let's look at what derivatives really mean. To use Newton's method properly, it is important to understand the meaning of the first and second derivative in particular.
The value of the first derivative of f (x) at some point x = x 0 indicates the slope of f (x) at point x 0; that is, whether f (x) is increasing (sloping upward from left to right) or decreasing (sloping downward). If the value of the derivative is positive, f (x) is increasing; if the value is negative, f (x) is decreasing; if the value is zero, f (x) is neither increasing nor decreasing. The magnitude of the value indicates how fast f (x) is increasing or decreasing. For example, Figure 13.6, example a, depicts a function whose value increases within the shaded regions; thus, these are the regions where the first derivative is positive. The plot of the first derivative crosses the x-axis at the points where the slope of f (x) changes sign.
The value of the second derivative of f (x) at some point x = x 0 indicates the concavity of f (x) at point x 0, that is, whether the function is opening upward or downward. The magnitude of the value indicates how extreme the concavity is. In Figures 13-6a and 13-6c, the dotted line indicates the point at which the concavity of the function changes sign. This is the point at which the plot of the second derivative crosses the x-axis.
Another way to think of the value of the derivative of f (x) at some point x = c is as the slope of the line tangent to f (x) at c, expressed in point-slope form. The point-slope form of a line is:
Thus, if f (x) = x 3 - x 2 - 3x + 1.8 as shown in Figure 13.6, example a, the equation of the line tangent to f (x) at c = 1.5 as can be determined as follows. Figure 13.6, example d, is a plot of this line along with f (x).
Figure 13.6. The meaning of the first and second derivatives of f (x)
Selecting an Initial Point for Newton's Method
Now that we understand a little about derivatives, let's return to Newton's method. Paramount to Newton's method is the proper selection of an initial iteration point x 0. In order for Newton's method to converge to the root we are looking for, the initial iteration point must be "near enough" and on the correct side of the root we are seeking. There are two rules that must be followed to achieve this:
Determine an interval [a, b ] for x 0 where one and only one root exists. To do this, choose a and b so that the signs of f (a) and f (b) are not the same and f ' (x) does not change sign. If f (a) and f (b) have different signs, the interval contains at least one root. If the sign of f ' (x) does not change on [a, b ], the interval contains only one root because the function can only increase or decrease on the interval.
Choose either x 0 = a or x 0 = b so that f (x 0)