\(^\ast \)School of Mathematics and Computer Science, National University of Mongolia, Ulan-Bator, Mongolia, e-mail: tzhanlav@yahoo.com, chuka@jinr.ru, anxaa\(\_ \)w@yahoo.com.

\(^\S \)Joint Institute for Nuclear Research, Dubna, 141980 Moscow region, Russia.

1 Introduction

Consider a nonlinear system

where \(F:D\subseteq \mathbb {R}^{n}\rightarrow \mathbb {R}^{n}\) is a continuously differentiable nonlinear mapping. Among all kinds of methods for solving the nonlinear equations (1), the Newton method is perhaps the most elementary, popular and important [ 1 , 2 , 3 , 4 , 5 , 6 ] . One of the advantages of the method is its local quadratic convergence. However, its computational cost is expensive, particularly when the size of the problem is very large, because the Newton equations

should be solved at each iteration step. To reduce the computational cost of the Newton method, Dembo, Eisenstat and Steihaug [ 7 ] proposed an inexact Newton (IN) method,

The terms \(r_{k}\in \mathbb {R}^{n}\) represent the residuals of the approximate solutions \(\bar s_{k}\) of the Newton equation (2), i.e., inexactly solve the Newton equation (2) and obtain a step \(\bar s_{k}\) such that

where \(\eta _{k}\in [0,1) \) is the forcing term. In each iteration step of the IN method, a real number \(\eta _{k}\) should be chosen first, and then an IN step \(\bar s_{k}\) is obtained by solving the Newton equations approximately with an efficient iteration solver for systems of linear equations. The forcing terms play an important role both in reducing the residuals of Newton equations and in increasing accuracy of the method. In particular, if \(\eta _{k}=0\) for all \(k\), then the IN method reduces to the Newton method. The IN method, like the Newton method, is locally convergent.

In [ 8 ] it is shown that the IN, inexact perturbed and quasi-Newton methods are equivalent models. At present there are some strategies for choosing the forcing terms [ 9 , 10 , 11 ] .

2 The continuous analogy of Newton’s method (CANM)

One of the modifications of Newton method is the well known CANM or damped Newton method [ 1 , 4 , 5 , 6 ]

where \(\tau _{k}{\gt}0\) is an iteration parameter. The suitable choice of the parameter allows us to speed-up the convergence and to enlarge the convergence domain. If \(\tau _{k}\equiv 1\) for all \(k\), then CANM reduces to Newton method. There exists a closed relationship between the CANM and the IN iterates. Indeed, the CANM (8) can be considered as the IN iteration (3) with the residual

From here we get

with

We have a local and semi-local convergence results:

Let \(D_{0}\) be a convex set with \(\overline{D}_{0}\subseteq D\), and \((F'(x))^{-1}\) exists for all \(x\in D_{0}\).

where \(\xi _{k}=\theta x_{k}+(1-\theta )x_{k+1}\), \(\theta \in (0,1).\) If we use the assumption (iv), then from (13) it follows that

under condition (12), i.e., \(\{ \| F(x_{k})\| \} \) is a decreasing sequence provided the iteration parameter \(\tau _{k}\) is chosen in the interval \(\left( 0, \tfrac {-1+\sqrt{1+4a_{k}}}{a_{k}} \right)\).

3 Some choices of iteration parameters

From (13) it follows that

and

Then by Remark 2.2, one can choose \(\tau _{k},\) such that

or

which allows us the quadratic convergence of CANM. The formulas (16) can be rewritten in term of the forcing term \(\eta _{k}\) as

and respectively

where

Assume that

Then \(\alpha _{k}{\gt}1\) and \(\alpha _{k}~ \eta _{k-1}\geq 1.\) As a consequence, the minimum of the possible choices (17) is

If the inequality (19) is not true, then (17) give us \(\eta _{n}=1-\eta _{k-1}\alpha _{k}.\) Thus we have

The second choice in (20) allows us to decrease \(\eta _{k}\), i.e., \(0{\lt}\eta _{k}{\lt}\eta _{k-1},~ \) while the first choice in (20) implies that \(0{\lt}\eta _{k}{\lt}1. \) In both cases we have \(0{\lt}\eta _{k}{\lt}1.\) According to (4), it is possible that (19) is true and thereby the second choice in (20) allows us to decrease \(\eta _{k}\), i.e., \(\eta _{k}\rightarrow 0\) as \(k\rightarrow \infty \). In terms of \(\tau _{k}\) we have the following choice

From this it follows that, if \(0{\lt}\eta _{k}{\lt}1\) and \(\eta _{k}\rightarrow 0\) as \(k\rightarrow \infty \), then we have \(0{\lt}\tau _{k}{\lt}2\) and \(\tau _{k}\rightarrow 1\) as \(k\rightarrow \infty \). Thus, the choice of the iteration parameter given by (20), (21) can be used in CANM.

In [ 6 ] another choice for CANM was proposed:

According to (21), the formula (22) in term of \(\eta _n\) reads as

which can be used in the IN as a forcing term. From (20) we see that the inexact Newton method with forcing term given by (20) is locally Q-superlinearly convergent, while IN with forcing term given by (23) converges quadratically because of \(\eta _n=O(\| F(x_n)\| )\) (see theorem 1.3).

4 Numerical experiments

In this section we present numerical examples to demonstrate the efficiency of the new strategies to choose forcing terms. We compare the strategies with some known strategies on their numerical behavior.

We have used three test problems that are typical systems of nonlinear equations in literature, with each of its own name and standart initial guess, say \(x_s\). The problems are listed as follows [ 11 ] :

Problem 4.1 (Generalized function of Rosenbrock)

with \(c=2\) and \(x_s=(1.2, 1.2,...,1.2)^T\).

Problem 4.2 (Tridiagonal system)

with \(x_s=(12, 12,...,12)^T\).

Problem 4.3 (Five-diagonal system)

with \(x^s=(-2, -2,...,-2)^T\).

We test the case \(n=100\). Besides the standard initial guess \(x^s\), also test other initial guesses such as \(x^0=\pm jx^s\), \(j= 2, 3\). It is easy to see that \(e=(1, 1, ... ,1)^T\) is a solution to each of the above three problems. For the convenience of reporting the results of different forcing terms, the following notations are used in Table 1:

EW1 : the first strategy given by Eisenstat and Walker [ 10 ] ,

EW2 : the second strategy given by Eisenstat and Walker [ 10 ] ,

APR : the actual reduction and the predicted reduction strategy given in [ 11 ] as well as strategies defined by formulas (20) and (23),

Str (20) : strategy given by (20),

Str (23) : strategy given by (23),

NI : denotes the total number of nonlinear iterations,

GI : denotes the total number of GMRES iterations,

CT : denotes \(10^2\times \)(CPU time).

The norm in our test is the Euclidean norm \(\| \cdot \| _2\) and the stoping criteria is

The initial forcing term \(\eta _0=0.5\) and additional parameters of \(\eta _k\) are chosen following [ 11 ] , for all the above iterations EW1, EW2, APR, Strategies (20) and (23).

The comparison of GMRES with different forcing terms was made by CPU time. From Table 1 we see that GMRES with the forcing term given by (23) is better than those with other forcing terms.

From Table 2 we see that the forcing term given by (23) decreases more rapidly than the forcing term APR that halved at each iteration. As results, the residual norm \(\| F(x^k)\| \) in the first case decreases as rapidly as the forcing term.