498 ARITHMETIC 4.6.4 b 15. [HA4.28] The nth (Cool web site)
498 ARITHMETIC 4.6.4 b 15. [HA4.28] The nth divided difference f(zs, ~1,. . , z~) of a function f(r) at n + 1 distinct points ~0, x1, . , 5% is defined by the formula f(50,21,…,2n)=(f( ~0,~1,…,Z~-1)-f(Z1,…,271–1,21L))/(Z0 -Zn), for n > 0. Thus f(zo, 21,. . ,G) = COCkCn f(%)/ no,,I,,j+&k -23) is a - symmetric function of its n + 1 arguments. (a) Prove that f(zo, . , G) = f (e)/n!, for some 0 between min(zo, , CC,) and max(zo, , G), if the nth derivative f( )(z) exists and is continuous. [Hint: Prove the identity &it1 lit,. . .~nit,l (xo(l-tl) + xl(tl–t2) + . . . f(xo,51,…,xn)= +~n-l(tn-l-tn) + zn(tn-0)). This formula also defines f(zo, ~1,. , z,) in a useful manner when the x3 are not distinct.] (b) If yj = f(xj), show that oj = f(xo, . . . , xj) in Newton s interpolation polynomial (42). 16. [AL%?] How can we readily compute the coefficients of ul ](x) = u,xn +. + ~0, if we are given the values of x0, xl, . . . , ~~-1, CQ, al, . . . , on in Newton s interpolation polynomial (42)? 17. [M45] Is there a way to evaluate the polynomial c 22×3+.. . + xn-lxn = x152 llz<3ln with fewer than n -1 multiplications and 2n -4 additions? (There are (y) terms.) 18. [A&V] If the fourth-degree scheme (9) were changed to Y = (x + ao)x + Ql, 4x) = ((Y -x + m)y + cy3)Ly4, what formulas for computing the q s in terms of the @ s would take the place of (lo)? b 19. [M24] Explain how to determine the adapted coefficients oo, ol, , cy5 in (11) from the coefficients ~5, , ZL~, uo of u(z), and find the o s for the particular polynomial u(z) = x5 + 5×4 -10×3 -50×2 + 13x + 60. b 20. [ZY] Write a MIX program that evaluates a fifth-degree polynomial according to scheme (11); try to make the program as efficient as possible, by making slight modifications to (11). Use MIX s floating point arithmetic operators FADD and FMUL, which are described in Section 4.2.1. 21. [Zoo] Find two additional ways to evaluate the polynomial x6 + 13~~ + 49×4 + 33×3 -61×2 -37x $ 3 by scheme (12) using the two roots of (15) that were not considered in the text. 22. [IL?] What is the scheme for evaluating x6 -3×5 +x4 -2×3 + z2 -32 -1, using Pan s method (16)?