The Continuous Analogy of Newton’s Method for Solving a System of Linear Algebraic Equations ()
1. Introduction
We consider a system of linear algebraic equations
(1)
For a numerical solving of Equation (1) we consider an iterative process:
(2)
Of course, the quality of iterative process Equation (2) essentially depends on the choices of matrix B and of iteration parameter ![](https://www.scirp.org/html/6-7401206\ba81564a-e3c8-4077-b68f-7e4cdb5afd3d.jpg)
Let H be a linear space of m-dimensional vectors. We will denote the Euclidean vector norm in H by
, as well as the corresponding norm of matrices.
Theorem 1.1. Let
Then a necessary and sufficient condition for the
to be decreasing
is that
![](https://www.scirp.org/html/6-7401206\c3c3072a-41c4-43c7-9b2e-c06b67c00e5a.jpg)
Proof. From Equation (2) we obtain
![](https://www.scirp.org/html/6-7401206\4b57c9fa-006d-4439-9c8c-ee1cc69f5318.jpg)
Hence we have
(3)
The assertion follows from (3).
The interval
we call τ-region of convergence of the iteration method (2). Thus we have to choose
from this region. Moreover, it is desirable that the
to be optimal in some sense. Further we will use wellknown assertions to study the convergence of (2).
Theorem 1.2. [1]. Let S be an m × m matrix. Then the successive approximations
(4)
converge for each
and each
if and only if
(5)
where
is a spectral radius of the matrix S.
It is easy to show that the iteration process (2) can be rewritten as (4) with iteration matrix
(6)
Here E is an m × m unit matrix.
Theorem 1.3. [2]. The iteration process (2) with parameter
given by
(7)
converges to
for any
. The following a posteriori estimate holds true:
(8)
where
![](https://www.scirp.org/html/6-7401206\8c1609d0-47b6-4a42-b1ca-1c80e2f1df49.jpg)
We call the nonzero value of
defined by (10) the optimal one in the sense that it yields the minimum value of functional
.
2. The Continuous Analogy of Newton’s Method
The continuous analogy of Newton’s method is also applicable to (1) and leads to [2]
(9a)
(9b)
It should be mentioned that not only the convergence, but also the convergence rate of iteration (9) depends on the choice of the parameter
. We have the following:
Lemma 2.1. The sufficient condition for
to be decreasing is ![](https://www.scirp.org/html/6-7401206\48c8d4b5-56d9-4948-98db-b815666095c6.jpg)
Lemma 2.2. Suppose that
for all
. Then the iteration process (2) gives two-sided approximations to
, i.e.,
![](https://www.scirp.org/html/6-7401206\bdb35f6c-f741-4766-a723-ccdd784d16a6.jpg)
or
![](https://www.scirp.org/html/6-7401206\e6b35694-a51b-4949-8006-53fc4f36b28d.jpg)
The proofs are immediately followed from the equalities
![](https://www.scirp.org/html/6-7401206\0a18ef99-0a10-4f8b-a549-32ec427ab58b.jpg)
At each step of iterations one can solve the system (9a) by means of some iterative methods. We call this inner iteration. We consider the following decomposition of
:
![](https://www.scirp.org/html/6-7401206\db72aa2b-e3c9-458e-9a63-88320379ed53.jpg)
in which the matrix
is simple and invertible. For finding the correction
we use inner iteration
(10)
Theorem 2.3. Suppose that
(11)
Then the inner iteration (10) converges and holds the following estimate
(12)
Proof. The linear system (10) can be rewritten as
(13)
By assumption (11) there exists
and the following series representation is valid
(14)
Then from (13) it follows that
(15)
In a similar way, from (10) we have
(16)
From (15) and (16) immediately follows (14).
The estimate (12) means that the inner iteration (10) converges under condition (11). In real computations we have to terminate the inner iteration before convergence. We will restrict the number of inner iteration by k. Then the whole iteration process looks like:
(17a)
(17b)
We now formulate the convergence theorems for these methods.
Theorem 2.4. Suppose that the condition (11) is satisfied and the iteration parameter
is given by
(18)
Then the iteration process (17) converges for any
and for arbitrary chosen starting
.
Proof. We rewrite the iteration process (17) as (2) with
![](https://www.scirp.org/html/6-7401206\2fca7c8b-2927-401c-8462-8ae15db53bb9.jpg)
By Theorem 1.3, such a process converges if we choose
by (7), in which the
is replaced by
.
Obviously the number k may be different for each n. From (12) it is evident, that it suffices to restrict the number of inner iteration only by k = 0 or 1, when the residual norm
is small enough.
Theorem 2.5. Suppose that the condition (11) is satisfied. Then the iteration process (17) with
converges for any
and for arbitrary chosen starting
. The following inequality holds:
(19)
Proof. From (17) we get
![](https://www.scirp.org/html/6-7401206\6849530d-6bcf-437b-9c3a-63d4a207f7a7.jpg)
Using (11) and (16) we rewrite the last expression as
(20)
If
, then from (20) we obtain
![](https://www.scirp.org/html/6-7401206\27f9b4da-b2bb-402b-aa0f-f372033b4ff8.jpg)
According to (11), we have
. The convergence of (17) follows from (19).
Corollary 2.6. Let the condition (11) fulfill, and
is given by [3]
![](https://www.scirp.org/html/6-7401206\a8c8274c-fae9-45a6-a42f-73e84cdef739.jpg)
Then the iteration (17) converges.
Remark 2.7. In proofs of Theorems 2.3-2.5 the condition (11) is essentially used. In particular, it may be fulfilled if the matrix A of the system (1) is a strongly diagonally dominant and A1 is chosen as
![](https://www.scirp.org/html/6-7401206\52777c4b-0b66-4bce-9918-f7230b63909d.jpg)
Theorem 2.8. Suppose that the condition (11) is satisfied and that the eigenvalues of matrix
are real. Then the spectral radius of iteration matrices of the iterations (17) is decreasing with respect to k when
.
Proof. The iterations (17) can be rewritten as (4) with iteration matrices
(21)
We denote by
the eigenvalues of D. If
, then
![](https://www.scirp.org/html/6-7401206\b640e9de-8d2d-4f92-beff-bf4e0b7cee86.jpg)
Therefore, we have
![](https://www.scirp.org/html/6-7401206\1e026a0d-e383-450a-b95e-a867bac88df1.jpg)
By virtue of (11) we obtain
. Since the spectrums of matrices C and D coincide, we also have
![](https://www.scirp.org/html/6-7401206\7d18ef3e-fd1c-4e7b-9872-c61acf01d8fa.jpg)
By definition we get
![](https://www.scirp.org/html/6-7401206\9d088ae0-a8ef-444e-9cfb-8dca567f1648.jpg)
which is valid for all
Thus we have
(22)
Obviously, from (21) it is clear that
is a continuous function of
. Therefore, (22) is valid for
.
The iteration (17) with a few small k represents a special interest from a computational view point. Moreover, it is worth to stay at (17) with k = 0 in detail. The iteration (17) with k = 0 and
leads to the well-known Jacobi iteration with relaxation parameter
. It is also known that [1] the Jacobi method with optimal relaxation parameter
(23)
converges under the assumption that the Jacobi matrix
has real eigenvalues and spectral radius less than one. Here by
and
denoted are the smallest and largest eigenvalues of B. Fortunately, we can prove the convergence of Jacobi method with relation parameter under a mild condition than the above mentioned assumption. Namely, we have.
Corollary 2.9. Suppose that the condition (11) is satisfied. Then the Jacobi method with relaxation parameter:
(24)
converges for any starting.
From (24) it is clear that the relaxation parameter changes depending on n. Therefore the iteration (17) with k = 0, and
and with
given by (24) we call nonstationary Jacobi method with optimal relaxation parameters. The iteration (17) with k = 0 and with a lower triangular matrix
leads to GaussSeidel with one parameter.
The Formula (18) can be rewritten as:
(25)
where
From this it is clear that
as
. This means that whole iteration (17) with the parameter given by (18) converges quadratically in the limit.
Since
as
, then τ-region of convergence for iterations (17) leads to
![](https://www.scirp.org/html/6-7401206\5e291f09-2a4c-4b80-97d6-3d4eb018c1c2.jpg)
The number of outer iteration n depends on the number of inner iteration k, i.e.,
. In general, n is a decreasing function of k, i.e., ![](https://www.scirp.org/html/6-7401206\28ca339a-0935-4ef3-9611-f0d7875d2160.jpg)
On the other hand, the iteration (17) can be considered as a defect correction iteration [1]
(26)
where
defined by
(27)
is a reasonable approximation to
since
(28)
for large k. The choice of parameter
given by (25) allows us to decrease the residual norm from iteration to iteration. By this reason we call (26) as a minimal defect (or residual) correction iteration.
From (26) it follows that
(29)
From (29) and
, it follows that
![](https://www.scirp.org/html/6-7401206\8e3e167e-bf43-45dc-bddc-21da7e5bf04f.jpg)
Therefore we have
![](https://www.scirp.org/html/6-7401206\7b4951e2-f517-4002-ac2e-ca2fd9aac693.jpg)
This means that the spectral radius of matrix
depends on the number of inner iteration k, i.e.,
. Therefore we have
as
, because
as
and from (11)
![](https://www.scirp.org/html/6-7401206\bdf08927-1ec0-482d-baf0-0f3213cde5bc.jpg)
Above we considered the cases, where the inner iteration number k is fixed at each outer iteration. It is desirable that the termination criterion for the inner iteration must be chosen carefully to preserve the superlinear convergence rate of the outer iteration. We stay at this problem in more detail. When
, the iteration (17) is, indeed, inexact Newton (IN) method for (1). Therefore, iteration (17) with parameter
given by formula (18) we call inexact damped Newton method (IDN). According to IN method [4,5], we must choose
and continue the inner iteration until satisfy the condition
(30)
Thus (30) is a stopping criterion for inner iteration (17a). There are several choices of forcing term
in inexact Newton method [4-6]. For examples, in [6] two choices of
were proposed:
(31)
with
![](https://www.scirp.org/html/6-7401206\eb2bb1eb-15ee-408b-88e5-3a7dbce5798f.jpg)
and
(32)
Since we have formula (18) for
, one can use the second choice (14) with no additional calculations. We can also use formula for
[7]. Therefore, according to (32), we get
(33)
3. Numerical Results
The quality of the proposed iteration was checked up for numerous examples. We express the matrix A as
![](https://www.scirp.org/html/6-7401206\a38bee43-d13a-4337-bab5-df7941946dce.jpg)
where
, and AL, AU are lower and upper triangular matrices, respectively. All examples are calculated with an accuracy
.
The numerical calculations are performed on Acer, CPU 1.8 GHz, 1 GB RAM, and using a software MATLAB R2007a for the Windows XP system.
Example 1. We consider a system of Equation (1) with matrix A and f given by
![](https://www.scirp.org/html/6-7401206\6a3ac3e9-5445-492d-9edf-c17ccf99db9f.jpg)
which was solved by the proposed iteration method (17), (18). For comparison, it was solved by Jacobi and successive over relaxation (SOR) iterations with a parameter
.
Example 2.
![](https://www.scirp.org/html/6-7401206\6e14e0d4-0be6-49c5-930a-e1466c4e3476.jpg)
Example 3.
![](https://www.scirp.org/html/6-7401206\559501b8-e03a-4ff6-93df-13ebc8c3595f.jpg)
Example 4.
![](https://www.scirp.org/html/6-7401206\541891d2-3659-4363-929f-a1c68016ad44.jpg)
where
and
![](https://www.scirp.org/html/6-7401206\a0a4bc50-a58c-4f68-bf8d-6d86a58fe700.jpg)
Such a system arises in discretization of two dimensional Poisson equation [8]:
![](https://www.scirp.org/html/6-7401206\0f6df7b9-f3d1-47f3-8daf-08f2272e1e7c.jpg)
The exact value of
is [9]
(34)
The properties of matrix for examples 1-4 are shown in Table 1. From this we see that the considered examples represent a wide range of typical systems.
The numbers of Jacobi and SOR iterations versus the dimension m of example 1 are presented in Table 2. Here k is the number of inner iteration in (17) (18). From this example we see that the proposed iteration (17), (18) can compete with SOR iteration with optimal relaxation parameter and seem to be superior to the Jacobi iteration. The behavior of the iteration parameter
given by (18) at m = 10 is explained in Table 3. From this we see that the iteration parameter
tends to 1 as k increases.
The number n of outer iteration (17), (18) with fixed number k of inner iterations, and CPU time for examples 2 and 3 are shown in Table 4. From this we see that they are in example 2 considerable less than example 3. This explained by reason that matrix of this system has a strictly diagonally dominant. The number n of outer iteration, the total number k of inner iteration when forcing terms
was chosen by formulas (32) and (33), and CPU time are displayed in Table 5. Here it is observed similar situations as in the previous case.
Monotonic convergence of the calculated values
to exact value (34) versus the dimension N of the example 4 is shown in Table 6. The number n of outer iteration with fixed and unfixed number k of inner iteration and CPU time versus the dimension N of the example 4 are presented in Tables 7 and 8, respectively.
Table 1. The properties of matrix for examples 1-4.
![](https://www.scirp.org/html/6-7401206\f965a7dc-594a-4642-895e-2858ce81fd9d.jpg)
Table 2. The numbers of Jacobi and SOR iterations versus the dimension
of example 1. Here
is the number of inner iteration in (17), (18).
![](https://www.scirp.org/html/6-7401206\3ebde10e-5716-4ff6-953a-6988b8a5752e.jpg)
Table 3. The behavior of the iteration parameter τn given by (18) for example 1. Here n and k are the numbers of outer and inner iterations in (17), respectively.
![](https://www.scirp.org/html/6-7401206\b3692f9a-ed24-4a57-89dd-9a8317969a8a.jpg)
Table 4. The number n of outer iteration with fixed number k of inner iteration, and CPU time CT for examples 2 and 3.
![](https://www.scirp.org/html/6-7401206\4bb9d65b-5f6b-49b5-98bf-b303f5462b22.jpg)
Table 5. The number n of outer iteration, the total number k of inner iteration when forcing terms ηn was chosen by formulas (32) and (33), and CPU time CT.
![](https://www.scirp.org/html/6-7401206\55dab145-dfd2-4580-b9e2-30c0ddf8bf28.jpg)
4. Conclusions
Our method with inner iteration is quadratically convergent and therefore it can compete with other iterations such as SOR with an optimal relaxation parameter for a strictly diagonally dominant system. Moreover, our method is also applicable not only for the system with a strictly diagonal dominant matrix, but also for system, the matrix of which is not Hermitian and positive definite.
This work was partially sponsored by foundation for science and technology of Ministry of Education, Culture, and Science (Mongolia).
Table 6. A comparison of the calculated values u(1/2, 1/2) and an exact value (34) versus the dimension N of the example 4.
![](https://www.scirp.org/html/6-7401206\9bef51a0-e22e-450f-a8ea-52fbbfd27c07.jpg)
Table 7. The number n of outer iteration with fixed number k of inner iteration, and CPU time CT versus the dimension N of the example 4.
![](https://www.scirp.org/html/6-7401206\0e1ca0b4-bcec-4ec8-a523-3b9139030a06.jpg)
Table 8. The number n of outer iteration with unfixed number k of inner iteration, the itration parameter τn, and CPU time CT versus the dimension N of the example 4.
![](https://www.scirp.org/html/6-7401206\528b95c2-a0e1-46a0-8819-f663271c045e.jpg)
O. Chuluunbaatar acknowledges a financial support from the RFBR Grant No. 11-01-00523, and the theme 09-6-1060-2005/2013 “Mathematical support of experimental and theoretical studies conducted by JINR”.
NOTES