So far we have found an efficient procedure for evaluating a polynomial at any . Next we develop a procedure for getting its derivative at the same .
Notice that for any we can divide by to get
quotient and remainder:
If we substitute the polynomials into Eq. (), and equate coefficients of on the lhs and rhs and solve for the coefficients and remainder we get a series of equations that can be organized as a recursion relation:
Here is the pseudocode for the dual-purpose algorithm:
Step 1: Set p = a[n] and q = 0
Step 2: Do steps 3 and 4 for i from n-1 to 0, decreasing by 1
Step 3: set q = p + x0 * q
Step 4: set p = a[i] + x0 * p
Step 5: The value of P(x_0) is p and the value of P'(x_0) is q
It is left as an exercise to check this pseudocode by playing computer
with a simple example and with the special case .
Finally, we leave as an exercise to complete the Newton-Raphson code for finding the real roots of a general polynomial.