# Newton’s Method

The Newton’s Method is the useful way to approximate the value of root of function. Even though it contains the calculation of the derivative of the function, the speed of the calculation is faster than the other methods, for instance, Bisection Method. Before we describe the Newton’s Method, first let us know about the Newton’s operator.

Suppose that we have a polynomial $f\in \mathbf{k}[x]$ where $\mathbf{k}$ is a field. Then, we can define Newton’s operator like the following:

$N_f:\mathbf{k}[x]\rightarrow \mathbf{k},~~ N_f(x)=x-\frac{f(x)}{f'(x)}$.

Now, we need to decide an initial approximation $x_0$. Then, by this $x_0$, we have the next approximation $x_1$ where $x_1=N_f(x_0)$. Repeatedly, we can get the approximation $\{x_n\}$ which, hopefully, converges to the root of $f$.

We can extend Newton’s method to the multivariate case. That is, if we have $\mathbf{f}$ is a polynomial system (i.e. $\mathbf{f}\in \mathbf{k}[x]^n$), then we can define the Newton’s operator of $\mathbf{f}$ like the following:

$N_{\mathbf{f}}(x)=x-\left(\frac{\partial \mathbf{f}}{\partial x}(x)\right)^{-1}\mathbf{f}(x)$.

We can use the Newton’s Method if each approximation $x_n$ satisfies $\det\left(\frac{\partial \mathbf{f}}{\partial x}(x_n)\right)\ne0$. In other words, if the solution is regular, then we can use the Newton’s Method.

However, we have a problem when the Jacobian matrix $\frac{\partial \mathbf{f}}{\partial x}$ is not square, especially, when we have fewer variables than polynomials. Now, we will consider the way to “squaring up” the Jacobian matrix $\frac{\partial \mathbf{f}}{\partial x}$.

Suppose that we have $n$ variables and $m$ polynomials with $m>n$. First, in order to square up the matrix, we may “add” $m-n$ more variables. However, then the determinant of the new matrix is clearly zero. Thus, it does not satisfy the regularity condition.

Secondly, we may think about the random linear combinations of the polynomials. In other words, consider the matrix $A\in \mathbf{k}^{n\times m}$ and calculate $A\mathbf{f}$. Then, we have the square system $A\mathbf{f}\in \mathbf{k}[x]^n$. Moreover, we can verify the property that $\mathbb{V}(\mathbf{f})\subset \mathbb{V}(A\mathbf{f})$.

We will check the simple example about these problems.

Consider the polynomial system $\mathbf{f}=(x^2~y^2~xy)$ in $\mathbb{Q}[x]$. Then,

(1) find the multiplicity of $(0,0)$

(2) does “squaring up” change the multiplicity of $(0,0)$?

In here, the multiplicity is defined by the number of elements in $\mathbb{Q}[x]/\left$.

From the figure above, we know that the multiplicity is $3$.

Now, we will take any 2 linear combinations of $x^2, y^2$ and $xy$.

When we calculate the Gröbner basis for the ideal generated by randomly obtained 2 polynomials, we know that the leading terms are $xy, x^2$ and $y^3$. Therefore, the multiplicity is changed from $3$ to $4$.