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

$$\phi$$ (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

$$\phi \equiv$$ (121)

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

$$\equiv \phi \phi \prime$$ (122)

Then the following assertions hold

1. $\phi$(g)  $\equiv$  0 modp^2 k
2. h  $\equiv$  g modp^k
3. $\phi$^$\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

• check whether $\phi$^$\prime$(g) is invertible modulo p and
• compute its inverse modulo p in case.

Then for computing the inverse of $\phi$^$\prime$(h) modulo p the idea is to apply the algorithm to itself! That is, to the particular case of

$$\phi$$ (123)

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

Algorithm 9  

Theorem 14   Algorithm 9 is correct.

Proof. Let g_r  $\equiv$  g_r-1 - $\phi$(g_r-1)s_r-1modp^2r. Then we have

$$\equiv \ell$$ (124)

In other words g_r is a solution of higher precision. Then proving the theorem turns into proving the invariants for i = 0 ^... r

1. g_i  $\equiv$  g₀modp,
2. $\phi$(g_i)  $\equiv$  0 modp²ⁱ,
3. if i < r then s_i $\phi$^$\prime$(g_i)  $\equiv$  1 modp²ⁱ.

The case i = 0 is clear and we assume that i > 0 holds. Then by induction hypothesis p^2i-1 divides

$\phi$(g_i-1)

s_i-1 - $\phi$^$\prime$(g_i-1)^-1

Then p²ⁱ divides their product, that is

$$\phi \equiv \phi \phi \prime$$ (125)

Now we calculate

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

(126)

Now applying Proposition 10 with g = g_i, h = g_i and k = 2^i-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 y₁,..., y_n. From an approximation a $\in$ $\mbox{${\mathbb R}$}$ⁿ to a commo root of $\phi_{{1}}^{{}}$,...,$\phi_{{n}}^{{}}$ we obtain a better one a ^* with

$$\phi$$ (127)

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

• Consider the coefficients of g and h in a factorization f = g h as indeterminates.
• Comparing the coefficients of 1, x, x²,... lead to a system of n equations and n unknowns whose solution leads to a factorization of f.
• The invertibility of J is equivalent to the coprimality of f and g. Indeed J is exactly the Sylvester matrix of f and g. Hence, its determinant is the resultant of f and g.