On the Penultimate Remainder Algorithm and the Catalytic Multiplier
A. S. Householder · SIAM Journal on Applied Mathematics · 1970
Given monic polynomials, f(z) and p(z), of degrees n and p < n, respectively, iff(z) is divided by p(z) up to but not including the constant term in the division, and if suitable conditions are satisfied, then the remainder, which is also of degree p, will more closely approximate a true divisor off(z) than does p(z). This is Lin's penultimate remainder algorithm [3]. Unfortunately, when the conditions are not satisfied the remainder can deviate even further from a true divisor, even though p(z) is close to one. Aitken [1], [2] showed that by proper choice of h(z), if the division is made into h(z)f(z), instead of into f(z), then the penultimate remainder will always closely approximate a true divisor, provided only p(z) is itself sufficiently close. This h(z) is Aitken's catalytic multiplier. Lin's development is complicated and unsuggestive. Aitken's derivation of the conditions for convergence is very sketchy and leaves much to the reader. In particular, it depends upon a lemma not explicitly stated and apparently not generally known. It is the purpose of this note to state and prove this lemma, and then to show how these conditions come out quite naturally from it. LEMMA. Let