1550078481-Ordinary_Differential_Equations__Roberts_

N-th Order Linear Differential Equations 195

Consider the polynomial equation f(x) = x^2 - a= 0 where a > 0. Differ-

entiating we get f'(x) = 2x. So the iterative portion of the Newton-Raphson

method for this function is

Xn+i = Xn - f(xn)/J'(xn) = Xn - (x~ - a)/(2xn)

= (x~ + a)/(2xn) = (xn + a/xn)/2.

This is exactly the recursion of the ancient Babylonian technique for comput-

ing a square root.

Now, consider the general n-th degree polynomial

where an -=J. 0. For any given value of x, computing p(x) as written above
requires n additions and 2n - 1 multiplications- one multiplication each to
successively compute x^2 = x · x, x^3 = x^2 · x, ... , xn = xn-l · x and one

multiplication each for ak · xk for k = 1, 2, ... , n. The polynomial p( x) may

be rewritten in the nested multiplication or Horner form

In this form n additions are still required but only n multiplications are re-
quired. (The computation of the value in the innermost set of parentheses
requires one multiplication and one addition, the computation of the value
in the next innermost set of parentheses also requires one multiplication and
one addition, and so on.) This is a considerable savings in computing time-
almost a 503 savings- since the operation of multiplication requires much
more computing time than the operation of addition.

For any given value t we can recursively compute a new list of coefficients

bn-1, bn-2, ... , b1, bo, Ras follows:

(1) bn-1 =an

bn-2 = bn-1t + an-1

b1 = b2t + a2

bo=bit+a1

R =bot+ ao

The coefficient bn-2 = bn_ 1 t + an-l = ant+ an-l is the number one gets by
computing the value of the expression in the innermost set of parentheses of

p(t), the coefficient bn-3 = bn-2t+an-2 = (ant+an-1)t+an-2 is the number

one gets by computing the value of the expression in the first two innermost

set of parentheses of p(t), and so on. So R = p(t).