514 ARITHMETIC 4.7 Algebraic functions. The coefficients of (My space web page)
514 ARITHMETIC 4.7 Algebraic functions. The coefficients of each power series W(z) that satisfies a general equation of the form An(z)W(z)n + . . . + Al(z)Wz) + Adz) = 0, (29) where each A,(z) is a polynomial, can be computed efficiently by using methods due to H. T. Kung and J. F. Traub; see JACM 25 (1978), 245-260. EXERCISES 1. [M10] The text explains how to divide V(z) by V(z) when VO # 0; how should the division be done when VO = O? 2. [Zoo] If the coefficients of U(z) and V(z) are integers and Vo # 0, find a recurrence relation for the integers Vt+ W,, where W, is defined by (3). How would you use this for power series division? 3. [Ml51 Does formula (9) give the right results when cx = O? When (Y = l? b 4. [HA&?3] Show that simple modifications of (9) can be used to calculate evcz) and ln(1 + V(z)), when V(z) = VIZ + vZz2 + … . 5. [MOO] What happens when a power series is reverted twice; i.e., if the output of Algorithm L or T is reverted again? b 6. [k%] (H. T. Kung.) Apply Newton s method to the computation of W(z) = l/V(z), when V(0) # 0, by finding the power series root of the equation f(z) = 0, where f(z) = z-l -V(z). 7. [MB ] Use Lagrange s inversion formula (12) to find a simple expression for the coefficient W, in the reversion of z = t -P. b 8. (A&Z] Lagrange s inversion formula can be generalized as follows: If W(z) = wlz+wzz2+~~~ = Glt + Gzt + G3t3 + . . . = G(t), where z and t are related by Eq. (lo), then W, = U,-l/n where Uo +U~z+Uzz2 +… = (Gl +2G2z+3G3z2 +…)(l +vZz+~z2 +…)- . (Equation (12) is the special case G1 = 1, Gz = Gs = . . . = 0. This equation can be proved, for example, by using tree-enumeration formulas as in exercise 2.3.4.4-33.) Extend Algorithm L so that it obtains the coefficients WI, W2, . . . in this more general situation, without substantially increasing its running time. 9. [11] Find the values of T,, computed by Algorithm T as it determines the first five coefficients in the reversion of z = t -t2. 10. [A&%] Given that y = x + alxoL+l + u2xa+ + . .. , cy # 0, show how to compute the coefficients in the expansion x = y + bzy21a + b3y3/ + . b 11. [M,Z5] (Composition of power series.) Let U(z)=U0+Ulz+U2z2+~~~ and V(z)=Vlz+~z2+V3z3+~~~; design an algorithm that computes the first N coefficients of U(V(z)).
We highly recommend you visit web and email hosting services if you need stable and cheap web hosting platform for your web applications.