TAOCP 4.7 Exercise 6

Section 4.7: Manipulation of Power Series

Exercise 6. [M21] (H. T. Kung.) Apply Newton's method to the computation of $W(z) = 1/V(z)$, when $V(0) \ne 0$, by finding the power series root of the equation $f(x) = 0$, where $f(x) = x^{-1} - V(z)$.

Verified: yes
Solve time: 4m15s

Solution

Let

$W(z)=\frac1{V(z)}, \qquad V_0\ne0.$

Then $W(z)$ is the root of

$f(x)=x^{-1}-V(z).$

Newton's method for solving $f(x)=0$ is

$x_{m+1}=x_m-\frac{f(x_m)}{f'(x_m)}.$

Since

$f'(x)=-x^{-2},$

we obtain

=x_m-\frac{x_m^{-1}-V}{-x_m^{-2}} =x_m+x_m^2(x_m^{-1}-V).$$ Simplifying, $$x_{m+1}=2x_m-Vx_m^2. \eqno(17)$$ Suppose that $$x_m=W+E,$$ where $$E=O(z^n).$$ Because $VW=1$, [ \begin{aligned} x_{m+1} &=2(W+E)-V(W+E)^2 \ &=2W+2E-V(W^2+2WE+E^2). \end{aligned} ] Now $$VW^2=W,$$ and $$VWE=E,$$ since $VW=1$. Hence [ \begin{aligned} x_{m+1} &=2W+2E-W-2E-VE^2 \ &=W-VE^2. \end{aligned} ] Therefore $$x_{m+1}-W=-VE^2=O(z^{2n}).$$ Each iteration doubles the number of correct coefficients. The iteration begins with $$x_0=\frac1{V_0},$$ since $$x_0-W=O(z).$$ Repeated application of (17) yields successively better approximations: $$x_{m+1}=2x_m-Vx_m^2.$$If $x_m$ is correct through terms of degree $n-1$, then $x_{m+1}$ is correct through terms of degree $2n-1$. Hence the reciprocal series can be computed by truncating all products modulo sufficiently high powers of $z$ at each stage. This completes the proof. ∎