Web design templates - 622 ANSWERS TO EXERCISES 4.6.1 For the stated
622 ANSWERS TO EXERCISES 4.6.1 For the stated example, the algorithm yields (i t) = (i z)( i -T), (i f) = (i z)( A -f), (A -i) = (!, -i)( i 
+ (y i)( i T). (Actually any matrix with determinant fl would be a gcrd in this particular case.) 20. It may be helpful to consider the construction of exercise 4.6.2-22, with pm replaced by a small number E. 21. Note that Algorithm R is used only when m-n 5 1; furthermore, the coefficients are bounded by (25) with m = n. [The stated formula is, in fact, the execution time observed in practice, not merely an upper bound. For more detailed information see G. E. Collins, Proc. 1968 Summer Inst. on Symbolic Math. Camp., Robert G. Tobey, ed. (IBM Federal Systems Center: June 1969), 195-231.1 22. A sequence of signs cannot contain two consecutive zeros, since uk+l(x) is a nonzero constant in (29). Moreover we cannot have +, 0, + or -, 0, - as subsequences. The formula V(u, a) -V(u, b) is clearly valid when b = a, so we must only verify it as b incfeases. The polynomials ~~(2) have finitely many roots, and V(u, b) changes only when b encounters or passes such roots. Let 5 be a root of some (possibly several) u3. When b increases from 2 -E to 5, the sign sequence near j goes from +, -j-, - to +, 0, - or from -, f, + to -, 0, + if j > 0; and from +, - to 0, - or from -, + to 0, + if j = 0. (Since u (x) is the derivative, u (x) is negative when U(Z) is decreasing.) Thus the net change in V is -S,,. When b increases from 3: to z + E, a similar argument shows that V remains unchanged. [L. E. Heindel, JACM 18 (1971), 533-548, has applied these ideas to construct algorithms for isolating the real zeros of a given polynomial u(x), in time bounded by a polynomial in deg(u) and log N, where all coefficients yJ are integers with Iuj( 5 N, and all operations are guaranteed to be exact.] 23. If v has n-l real roots occurring between the n real roots of U, then (by considering sign changes) U(X) mod W(Z) has n -2 real roots lying between the n -1 roots of w. 24. First show that hj = g~-1g~~;2(1-6~-1). ~~ -62 . 1-63- . Then show that the exponent of g2 on the left-hand side of (18) has the form 62 + 61x, where 2 = 62 + . . . + 6,-l + 1 - 62(63 + . . + sj-1 + 1) -&(l -62)(& + . . . + f5–1 + 1) - . . . -6,-1(1 -62). (1 -6,-2)(l). B u t x = 1, since it is seen to be independent of S,-, and we can set Sj+1 = 0, etc. A similar derivation works for gs, g4, . , and a simpler derivation works for (23). 25. Each coefficient of U?(X) can be expressed as a determinant in which one column contains only e(u), e(v), and zeros. To use this fact, modify Algorithm C as follows: In step Cl, set g + gcd(e(zl),e(v)) and h + 0. In step C3, if h = 0, set u(x) + V(X), V(X) c r(x)/g, h c e(u)6/g, g t e(u), and return to C2; otherwise proceed as in the unmodified algorithm. The effect of this new initialization is simply to replace Us by uj(x)/gcd(!(zl), e(w)) for all j 2 3; thus, 1 j- will become f?23-5 in (28). 26. In fact, even more is true. Note that the algorithm in exercise 3 computes &P~(z) and Tqn(s) for n 2 -1. Let e, = deg(q,) and d, = deg(p,u -qnv); we observed in exercise 3 that d,-1 + e, = deg(u) for n 2 0. We shall prove that the conditions deg(q) < e, and deg(pu -qv) < d,-2 imply that p(x) = c(x)p,-l(x) and q(z) = c(z)qn-l(z): Given such p and q, we can find c(x) and d(x) such that p(x) = c(x)P~-I(x) + d(x)pn(x) and q(x) = c(x)q+l(x) + d(x)q,(x), since pn-l(x)qn(x) - p,(z)q,--l(s) = fl. Hence pu-qv = c(p,-lu-qq,-lw)+d(p,u-qq,w). If d(x) # 0, we must have deg(c) + e,-1 = deg(d) + e,, since deg(q) < deg(q,); it follows that deg(c) + d,-1 > deg(d) + d,, since this is surely true if d, = -co and otherwise we