Jetty web server - 646 ANSWERS TO EXERCISES 4.6.4 For the given
646 ANSWERS TO EXERCISES 4.6.4 For the given rational function we have QYj Pj w[j (x) & (x) 1 2 x+5 3x+ 19 3 4 1 5 so u[ l(x)/w[o~(x) = 1 + 2/(x + 3 + 4/(x + 5)). Notes: A general rational function of the stated form has 2n + 1 degrees of freedom, in the sense that it can be shown to have 2n + 1 essentially independent parameters. If we generalize polynomial chains to arithmetic chains, which allow division operations as well as addition, subtraction, and multiplication, we can obtain the following results with slight modifications to the proofs of Theorems A and M: An arithmetic chain with q addition-subtraction steps has at most q+l degrees of freedom. An arithmetic chain with m multiplication-division steps has at most 2m + 1 degrees of freedom. Therefore an arithmetic chain that computes almost all rational functions of the stated form must have at least 2n addition-subtractions, and n multiplication- divisions; the method in this exercise is optimal. 38. The theorem is certainly true if n = 0. Assume that n is positive, and that a polynomial chain computing P(x; ~0, . . . , 2~~) is given, where each of the parameters aj has been replaced by a real number. Let Xi = Xj X Xk be the first chain multiplication step that involves one of ~0, . . . , un; such a step must exist because of the rank of A. Without loss of generality, we may assume that X, involves u,; thus, Xj has the form houo +. . . + hnun + f(x), where ho, . . , h, are real, h, # 0, and f(x) is a polynomial with real coefficients. (The h s and the coefficients of f(x) are derived from the values assigned to the cy s.) Now change step i to Xi = oi X Xk, where cr is an arbitrary real number. (We could take QI = 0; general cr is used liere merely to show that there is a certain amount of flexibility available in the proof.) Add further steps to calculate X = (a -f(x) -houo -. . . - h,-lu,-1)/h,; these new steps involve only additions and parameter multiplications (by suitable new parameters). Finally, replace X-,-1 = 2~~ everywhere in the chain by this new element X. The result is a chain that calculates Q(x; 210,. . . , t&.-1) = P(x; uo, . . . , h-1, (a -f(x) -houo -.. . - hn-1%~1)lhn); and this chain has one less chain multiplication. The proof will be complete if we can show that Q satisfies the hypotheses. The quantity (a -f(x))/hn leads to a possibly increased value of m, and a new vector B . If the columns of A are Ao, AI, . . . > A, (these vectors being linearly independent over the reals), the new matrix A corresponding to Q has the column vectors Ao -(ho/h&k , An-1 -(hn-l/hn)An, plus perhaps a few rows of zeros to account for an increased value of m, and these columns are clearly also linearly independent. By induction, the chain that computes Q has at least n -1 chain multiplications, so the original chain has at least n. [Pan showed also that the use of division would give no improvement; cf. Problemy Kibernetiki 7 (1962), 21-30. Generalizations to the computation of several polynomials in several variables, with and without various kinds of preconditioning, have been given by S. Winograd, Comm. Pure and Applied Math. 23 (1970), 165-179.1