4.6.4 EVALUATION OF POLYNOMIALS 501 b 38. [HiK%] (Shared web hosting)
4.6.4 EVALUATION OF POLYNOMIALS 501 b 38. [HiK%] (V. I^a. Pan, 1962.) The purpose of this exercise is to prove that Horner s rule is really optimal if no preliminary adaptation of coefficients is made; we need n multiplications and n additions to compute unxn + . . . + ~1 x + 1~0, if the variables ZL~, , ~1, ~0, 2, and arbitrary constants are given. Consider chains that are as before except that un, . . . , ~1, ~0, x are each considered to be variables; we may say, for example, that X-j-1 = uj, X0 = x. In order to show that Horner s rule is best, it is convenient to prove a somewhat more general theorem: Let A = (aij), 0 2 i 5 m, 0 5 j 5 n, be an (m f 1) X (n $ 1) matrix of real numbers, of rank n + 1; and let B = (bo, . , b,) be a vector of real numbers. Prove that any polynomial chain that computes P(x; uo, . . , u,) = C( azouo + . . . + ainun + b,)xi O