470 ARITHMETIC 4.6.4 Derivatives and (Web design service) changes of variable.
470 ARITHMETIC 4.6.4 Derivatives and changes of variable. Sometimes we want to find the coefficients of u(z + x0), given a constant x0 and the coefficients of U(X). For example, if U(X) = 3×2 + 22 -1, then u(x -2) = 3×2 -10x + 7. This is analogous to a radix conversion problem, converting from base x to base x + 2. By Taylor s theorem, the desired coefficients are given by the derivatives of U(X) at x = x0, namely u(x + x0) = u(x0) + u (xlJ)x + (U (ZO)/2!)Z2 + . . . + (dn)(xo)/n!)xn, (7) so the problem is equivalent to evaluating U(X) and all its derivatives. If we write U(X) = q(z)(z -x0) + r, then u(x + x0) = q(a: + ze)z + r; so r is the constant coefficient of u(z + ZO), and the problem reduces to finding the coefficients of ~(a: + x0), where q(x) is a known polynomial of degree n -1. Thus the following algorithm is indicated: Hl. Set vj + uj for 0 5 j 5 n. H2. For k = 0, 1, . . . , n -1 (in this order), set vj 6 Vj + xovj+l for j = n-1, . . . 7 k + 1, k (in this order). 1 At the conclusion of step H2 we have U(X + x0) = v,xn +. . . + wlx + ~0. This procedure was a principal part of Horner s root-finding method, and when Ic = 0 it is exactly rule (2) for evaluating u(z0). Horner s method requires (n2 + n)/2 multiplications and (n2 + n)/2 addi- tions; but notice that if xo = 1 we avoid all of the multiplications. Fortunately we can reduce the general problem to the case x0 = 1 by introducing compara- tively few multiplications and divisions: Sl. Compute and store the values xi, . . . , xg. S2. Set 1-j t ujx$ for 0 5 j 5 n. (Now V(X) = u(x,-,x).) S3. Perform step H2 but with z. = 1. (Now v(x) = u(x~(x+l)) = U(XOX+XO).) S4. Set vj c vj/xj, for 0 < j 2 n. (Now v(x) = u(z + 50) as desired.) 1 This idea, due to M. Shaw and J. F. Traub [JACM 21 (1974), 161-1671, has the same number of additions and the same numerical stability as Horner s method, but it needs only 2n -1 multiplications and n -1 divisions. About 3n of these multiplications can, in turn, be avoided (see exercise 6). If we want only the first few or the last few derivatives, Shaw and Traub have observed that there are further ways to save time. For example, if we just want to evaluate u(x) and u (x), we can do the job with 2n -1 additions and about n + & multiplications/divisions as follows: Dl. Compute and store the values x2, x3, . . . , xt, x~~, where t = [miz]. D2. Set 1-j t zljxf(j) for 0 2 < 1 -n,wheref(j)=t-1-((n-1-j)mod2t) for 0 2 j < n, and f(n) = t. D3. Set v~j + Vj + vj+lxg(j) for j = n -1, . . . , 1, 0; here g(j) = 2t when n-j is a multiple of 2t, otherwise g(j) = 0 and the multiplication by xg(j) need not be done. D4. Set Vj t Vj + vj+ixg(j) for j = n -1, . . . , 2, 1. NOW VO/X~( ) = U(X) and Vl/Xf(l) = u (x). 1
Note: If you are looking for high quality webhost to host and run your jsp application check Vision jsp web hosting services