next up previous
Next: Bibliography Up: Advanced Computer Algebra: From Newton Previous: Hensel Lifting

Solving polynomial equations via Newton iteration

Let R be a commutative ring R with units. Let p $ \in$ R and $ \phi$ $ \in$ R[y]. We are concerned with solving the equation

$\displaystyle \phi$(g)  =  0. (120)

The following Proposition 10 states that Relation (122) computes better and better approximations of solutions of Relation (120) that is, approximations modulo higher and higher powers of p.

Proposition 10   Let $ \phi$ $ \in$ R[y], k $ \in$ $ \mbox{${\mathbb N}$}$ and g, h $ \in$ R be such that

$\displaystyle \phi$(g$\displaystyle \equiv$  0 modpk (121)

Assume that $ \phi$$\scriptstyle \prime$(g) is invertible modulo p and let denote by $ \phi$$\scriptstyle \prime$(g)-1 its inverse. Consider an element h $ \in$ R such that

h  $\displaystyle \equiv$  g - $\displaystyle \phi$(g$\displaystyle \phi$$\scriptstyle \prime$(g)-1modp2 k (122)

Then the following assertions hold
  1. $ \phi$(g$ \equiv$  0 modp2 k
  2. h  $ \equiv$  g modpk
  3. $ \phi$$\scriptstyle \prime$(h) is invertible modulo p

Remark 18   Intuitively, Proposition 10 says that if g is a good approximation of a zero of $ \phi$ then h is a better approximation, at least twice as accurate.

Remark 19   Proposition 10 leads to an algorithm provided that we can Then for computing the inverse of $ \phi$$\scriptstyle \prime$(h) modulo p the idea is to apply the algorithm to itself! That is, to the particular case of

$\displaystyle \phi$(g)  =  1/g - f (123)

This leads to Algorithm 9. Finally recall that for a prime element p in an Euclidean domain R, the computation of $ \phi$$\scriptstyle \prime$(g)-1 modulo p can be done by the Extended Euclidean Algorithm.

Algorithm 9  

\begin{minipage}{12 cm}
\item[{\bf Input:}] ${\ell} \...
...}) s_{r-1} \mod{ p^{\ell}}$\ \\
\> {\bf return} $g$\end{tabbing}\end{minipage}}

Theorem 14   Algorithm 9 is correct.

Proof. Let gr  $ \equiv$  gr-1 - $ \phi$(gr-1)sr-1modp2r. Then we have

g  $\displaystyle \equiv$  gr modp$\scriptstyle \ell$ (124)

In other words gr is a solution of higher precision. Then proving the theorem turns into proving the invariants for i = 0 ... r
  1. gi  $ \equiv$  g0modp,
  2. $ \phi$(gi$ \equiv$  0 modp2i,
  3. if i < r then si $ \phi$$\scriptstyle \prime$(gi$ \equiv$  1 modp2i.
The case i = 0 is clear and we assume that i > 0 holds. Then by induction hypothesis p2i-1 divides
$ \phi$(gi-1)
si-1 - $ \phi$$\scriptstyle \prime$(gi-1)-1
Then p2i divides their product, that is

$\displaystyle \phi$(gi-1si-1  $\displaystyle \equiv$  $\displaystyle \phi$(gi-1)$\displaystyle \phi$$\scriptstyle \prime$(gi-1)-1 modp2i. (125)

Now we calculate

gi $\displaystyle \equiv$ gi-1 - $\displaystyle \phi$(gi-1)si-1 modp2i
  $\displaystyle \equiv$ gi-1 - $\displaystyle \phi$(gi-1)$\displaystyle \phi$$\scriptstyle \prime$(gi-1)-1 modp2i

Now applying Proposition 10 with g = gi, h = gi and k = 2i-1 we obtain the first two invariants.

... $ \qedsymbol$

Remark 20   The general mutivariate Newton iteration works as follows. Let $ \phi$ = ($ \phi_{{1}}^{{}}$,...,$ \phi_{{n}}^{{}}$) be a function in n variables y1,..., yn. From an approximation a $ \in$ $ \mbox{${\mathbb R}$}$n to a commo root of $ \phi_{{1}}^{{}}$,...,$ \phi_{{n}}^{{}}$ we obtain a better one a * with

a *   =  a - J-1(a$\displaystyle \phi$(a) (127)

where J is the Jacobian matrix of $ \phi$. The Hensel lifting can be considered as a special case of Newton iteration as follows.

next up previous
Next: Bibliography Up: Advanced Computer Algebra: From Newton Previous: Hensel Lifting
Marc Moreno Maza