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.

Newton'sMethodProof_gr_17.gif

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<x^2, y^2,xy\right>.

3

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.

5.jpg

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s