next up previous contents index
Next: 4.3 Classification of global Up: 4. Nonlinear Polynomial Solvers Previous: 4.1 Introduction   Contents   Index


4.2 Local solution methods

Newton-type methods are based on local linearization and are conceptually simple. They are designed to compute roots based on initial approximations. To begin with, we consider Newton's method in one variable [69,293] where we want to find roots for $ f(x)=0$ . If we denote the initial guess of the root as $ x_0$ , then in the neighborhood of $ x_0$ the function $ f(x) $ can be linearly approximated using Taylor expansion as follows:
$\displaystyle f(x) \simeq f(x_0) + (x-x_0)\dot{f}(x_0)\;.$     (4.4)

Provided that $ \dot{f}(x_i)\neq 0$ , the iteration formula immediately follows:
$\displaystyle x_{i+1} = x_i - \frac{f(x_i)}{\dot{f}(x_i)},\;\;\;i=0,1,2\ldots\;.$     (4.5)

This is illustrated in Fig. 4.2(a). A modified Newton's method [151] for one variable is shown in Fig. 4.2(b), where we take a fractional step as follows in order to reduce the possibility of divergence in Fig. 4.2(b) of the full step method given by (4.5)

$\displaystyle x_{i+1}=x_i-\mu \frac{f(x_i)}{\dot{f}(x_i)}\;,$     (4.6)

where $ \mu=max[1, \frac{1}{2}, \frac{1}{4}, ...]$ such that $ \vert f(x_{i+1})\vert<\vert f(x_{i})\vert$ .
Figure 4.2: Newton's method for $ f(x)=0$
\begin{figure}\centerline{ \psfig{figure=fig/Newton.eps,height=2.2in} } \end{figure}

If $ n=l$ in (4.1), we can easily extend Newton's method for a single variable to $ n$ variables as follows:

$\displaystyle \mathbf{x}_{i+1}=\mathbf{x}_{i}+\Delta \mathbf{x}_{i}\;,$     (4.7)

where
$\displaystyle \mathbf{J}(\mathbf{x}_{i}) \cdot \Delta \mathbf{x}_{i} = -\mathbf{f}(\mathbf{x}_{i})\;,$     (4.8)

and $ \mathbf{J}(\mathbf{x}_{i})=\left[\frac{\partial f_j}{\partial x_k}\right]$ is the Jacobian matrix of (4.1) [69].

Advantages of the Newton's method are its quadratic convergence and simplicity of implementation. Disadvantages are that for each root a good initial approximation is required, otherwise the method may diverge. Also the method cannot by itself provide full assurance that all roots have been found.

Example 4.2.1. Let us solve the intersection of two circles discussed in Example 4.1.1 using Newton's method. The Jacobian matrix is evaluated as follows:

$\displaystyle [J]_i = \begin{pmatrix}\frac{\partial f_1}{\partial x_1} & \frac{... ...trix}_i = \begin{pmatrix}2x_1 & 2x_2 \cr 2(x_1-1) & 2x_2 \cr \end{pmatrix}_i\;.$      

Thus the iteration scheme becomes
$\displaystyle \begin{pmatrix}x_1 \cr x_2 \cr \end{pmatrix}_{i+1} = \begin{pmatr... ...matrix}_{i} + \begin{pmatrix}\Delta x_1 \cr \Delta x_2 \cr \end{pmatrix}_{i}\;,$      

where $ \Delta x_1$ and $ \Delta x_2$ are obtained from the solution of the following linear system
$\displaystyle \begin{pmatrix}2x_1 & 2x_2 \cr 2(x_1-1) & 2x_2 \cr \end{pmatrix}_... ...a x_2 \cr \end{pmatrix}_i = - \begin{pmatrix}f_1 \cr f_2 \cr \end{pmatrix}_i\;.$      

next up previous contents index
Next: 4.3 Classification of global Up: 4. Nonlinear Polynomial Solvers Previous: 4.1 Introduction   Contents   Index
December 2009