# Convergence of Relaxed Matrix Parallel Multisplitting Chaotic Methods forH-Matrices

Authors: Li-Tao Zhang; Jian-Lei Li; Tong-Xiang Gu; Xing-Ping Liu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Based on the methods presented  by Song and Yuan (1994), we construct relaxed matrix parallel multisplitting chaotic generalized USAOR-style methods by introducing more relaxed parameters and analyze the convergence of our methods when coefficient matrices areH-matrices or irreducible diagonally dominant matrices. The parameters can be adjusted suitably so that the convergence property of methods can be substantially improved. Furthermore, we further study some applied convergence results of methods to be convenient for carrying out numerical experiments. Finally, we give some numerical examples, which show that our convergence results are applied and easily carried out.


---

## Body

## 1. Introduction

For solving the large sparse linear system(1)Ax=b,
where A is an n×n real nonsingular matrix and x,b∈Rn, an iterative method is usually considered. The concept of matrix multisplitting solution of linear system was introduced by O’Leary and White [1] and further studied by many other authors. Frommer and Mayer [2] studied extrapolated relaxed matrix multisplitting methods and matrix multisplitting SOR method. Mas et al. [3] analyzed nonstationary extrapolated relaxed and asynchronous relaxed methods. Gu et al. [4, 5] further studied relaxed nonstationary two-stage matrix multisplitting methods and the corresponding asynchronous schemes.As we know, matrix multisplitting iterative method for linear systems takes two basic forms. When all of the processors wait until they are updated with the results of the current iteration, it is synchronous. That is to say, when they begin the next iteration of asynchronous, they may act more or less independently of each other and use possibly delayed iterative values of the output of the other processors. In view of the potential time saving inherent in them, asynchronous iterative methods, or chaotic as they are often called, have attracted much attention since the early paper of Chazan and Miranker [6] introduced them in the context of point iterative schemes. Naturally, a number of convergence results [7–21] have been obtained. Recently, the convergence of three relaxed matrix multisplitting chaotic AOR methods has been investigated in [11, 13, 14].A collection of triples(Ml,Nl,El), l=1,2,…,s, is called a multisplitting of A if A=Ml-Nl is a splitting of A for l=1,2,…,s, and El’s, called weighting matrices, are nonnegative diagonal matrices such that ∑l=1sEl=I.The unsymmetric accelerated overrelaxation (USAOR) method was proposed in [22], if the diagonal elements of the matrix A are nonzero. Without the loss of generality, let the matrix A be split as
(2)A=I-L-U,
where I, L, and U are nonsingular diagonal, strictly lower triangular and upper triangular parts of A. The iterative scheme of the USAOR method is defined by
(3)x(k+(1/2))=H(ω1,ω2)x(k)+ω1(I-ω2L)-1b,x(k+1)=H(ω3,ω4)x(k+(1/2))+ω3(I-ω4U)b;
that is,
(4)x(k+1)=HUSAORx(k)+GUSAOR,k=0,1,…,
where
(5)HUSAOR=H(ω3,ω4)H(ω1,ω2),H(ω1,ω2)=(I-ω2L)-1×[(1-ω1)I+(ω1-ω2)L+ω1U],H(ω3,ω4)=(I-ω4U)-1[(1-ω3)I+(ω3-ω4)U+ω3L],GUSAOR=(I-ω4U)-1[(ω1+ω3-ω1ω3)I+ω3(ω1-ω2)L+ω1(ω3-ω4)U](I-ω2L)-1b,
and αi,βi(i=1,2) are real parameters.In this paper, we will extend the point USAOR iterative method to matrix multisplitting chaotic generalized USAOR method and analyze their convergence forH-matrices and irreducible diagonally dominant matrices.Based on matrix multisplitting chaotic generalized AOR method [23], the matrix multisplitting chaotic generalized USAOR method is given by
(6)x(k+1)=HGUSAORx(k)+GGUSAOR,k=0,1,2,…,
where
(7)HGUSAOR=H(β,ψ)H(α,ϕ),H(α,ϕ)=(I-αϕL)-1[I-ϕ+(1-α)ϕL+ϕU]H(β,ψ)=(I-βψU)-1[I-ψ+(1-β)ψU+ψL],GGUSAOR=(1-βψU)-1[2I-ψ+(ψ-αϕ)Lmmmmmmmmm+(1-β)ψU](I-αϕL)-1b,
is an iteration matrix and ϕ=diag⁡(β1,β2,…,βn), ψ=diag⁡(γ1,γ2,…,γn) with βi≥0, γi≥0(i=1,2,…,n) and α, β real parameters.Remark 1.
Forβ=γi=0, i=1,2,…,n, then GUSAOR method reduces to GAOR method [11]; For ϕ=ω1I, α=ω2/ω1, ψ=ω3I, β=ω4/ω3, the GUSAOR method reduces to the USAOR method [22].The remainder of this paper is organized as follows. In Section2, we introduce some notations and preliminaries. In Section 3, we present relaxed matrix parallel multisplitting chaotic GUSAOR-style methods for solving large nonsingular system, when the coefficient matrix A is an H-matrix or irreducible diagonally dominant matrix, and analyze the convergence of our methods. In Section 4, we further study some applied convergence results of methods to be convenient for carrying out numerical experiments. In Section 5, we give some numerical examples, which show that our convergence results are easily carried out. Finally, we draw some conclusions.


## 2. Notation and Preliminaries

We will use the following notation. LetC=(cij)∈Rn×n be an n×n matrix. By diag(C) we denote the diagonal matrix coinciding in its diagonal with C. For A=(aij), B=(bij)∈Rn×n, we write A≥B if aij≥bij holds for all i,j=1,2,…,n. Calling Anonnegative if A≥0, we say that B≤C if and only if -B≥-C. These definitions carry immediately over to vectors by identifying them with n×1 matrices. By |A|=(|aij|) we define the absolute value of A∈Rn×n. We denote by 〈A〉=(〈aij〉) thecomparison matrix of A∈Rn×n where 〈aij〉=|aij| for i=j and 〈aij〉=-|aij| for i≠j, i,j=1,2,…,n.Spectral radius of a matrix A is denoted by ρ(A). It is well known that if A≥0 and there exists a vector x>0 such that Ax<αx, then ρ(A)<α.Definition 2 (see [24]).
LetA∈Rn×n. It is called an(1)
L-matrix if aii>0 for i=1,2,…,n, and aij≤0 for i≠j, i,j=1,2,…,n;(2)
M-matrix if it is a nonsingular L-matrix satisfying A-1≥0;(3)
H-matrix if 〈A〉 is an M-matrix.Lemma 3 (see [13]).
IfA is an H-matrix, then (1)
|A-1|≤〈A〉-1;(2)
there exists a diagonal matrixP whose diagonal entries are positive such that 〈A〉Pe>0 with e=(1,1,…,1)T.Lemma 4 (see [13]).
LetA be an M-matrix and let the splitting A=M-N be an M-splitting. If P is the diagonal matrix defined in Lemma 3, then ∥P-1M-1NP∥∞<1.Finally, a sequence of setsPi with Pi⊆{1,…,s} isadmissible if every integer 1,2,…,s appears infinitely often in the Pi, while such an admissible sequence is regulated if there exists a positive integer T such that each of the integers appears at least once in any T consecutive sets of the sequence.


## 3. Relaxed Matrix Multisplitting Parallel Chaotic Methods

Using the given models in [7, 11, 13] and (4), we may describe the corresponding three algorithms of relaxed matrix multisplitting chaotic GUSAOR-style methods, which are as follows.Algorithm 5 (given the initial vector).
Fork=0,1,…, until convergence. Parallel computing the following iterative scheme
(8)x(k+1)=∑l=1s‍El(HGUSAOR)lμl,k(x(k)),(HGUSAOR)l(x(k))=H(β,ψ)lH(α,ϕ)lx(k)+(GGUSAOR)lb,H(α,ϕ)l=(I-αϕLl)-1[I-ϕ+(1-α)ϕLl+ϕUl],H(β,ψ)l=(I-βψUl)-1[I-ψ+(1-β)ψUl+ψLl],(GGUSAOR)l=(I-βψUl)-1×[2I-ψ+(ψ-αϕ)Ll+(1-β)ψUl]×(I-αϕLl)-1,
with α≥0, β≥0, βi>0, γi>0, and μl,k≥1, where (HGUSAOR)lμl,k is the μl,kth composition of the affine mapping satisfying
(9)(HGUSAOR)lμl,k={(HGUSAOR)l⋯(HGUSAOR)l,μl,k≥1,I,μl,k=0,B=Ll+Ul,l=1,2,…,s.Remark 6.
In Algorithm5, by using a suitable positive relaxed parameter ω, then we can get the following relaxed Algorithm 7.Algorithm 7 (given the initial vector).
Fork=0,1,…, until convergence. Parallel computing the following iterative scheme
(10)x(k+1)=ω∑l=1s‍El(HGUSAOR)lμl,k(x(k))+(1-ω)x(k),
with ω>0, α≥0, β≥0, βi>0, γi>0, and μl,k≥1, where (HGUSAOR)lμl,k(x(k)) is defined such as Algorithm 5.Remark 8.
In Algorithm7, we assume that the index sequence {Pi} is admissible and regulated; then we can get the following Algorithm 9 with the case of relaxed chaotic GUSAOR method.Algorithm 9 (given the initial vector).
Fork=0,1,…, until convergence. Parallel computing the following iterative scheme
(11)x(k+1)=(I-ω)∑l∈Pi‍El+ω∑l∈Pi‍El(HGUSAOR)lμl,k(x(k-rk+1)),
with ω>0, α≥0, β≥0, βi>0, γi>0, μl,k≥1, and Pi⊆{1,…,s}, where (HGUSAOR)l(x(k)) of Algorithm 5 are replaced by (HGUSAOR)l(x(k-rk+1)) and x(k-rk+1)=(x1(k-r(1,k)),x2(k-r(2,k)),…,xn(k-r(n,k)))T.Remark 10.
Relaxed matrix multisplitting chaotic GUSAOR-style methods introduce more relaxed factors, so our methods are the generalization of [5, 12, 13]. The parameters can be adjusted suitably so that the convergence property of method can be substantially improved.Using Lemmas3 and 4, we can get the following convergence result according to Algorithm 5.Theorem 11.
LetA∈Rn×n be an H-matrix and (I-Ll,Ul,El), l=1,2,…,s, a multisplitting of A. Assume that for l=1,2,…,s, we have the following.(1)
Ll are the strictly lower triangular matrices and Ul are the matrices such that the equalities A=I-Ll-Ul hold.(2)
〈A〉=|I|-|Ll|-|Ul|=|I|-|B|, where |B|=|Ll|+|Ul|.Then the sequence {x(k)} generated by Algorithm 5 converges for any initial x(0) if and only if (α,β,βi,γi), i=1,2,…n∈W1, ρ=(|B|), where
(12)W1={21+ρ(α,β,βi,γi)∈R4:0≤α,β≤1,mm0<βi,γi<21+ρ,i=1,2,…,n}.Proof.
Define the iteration matrix in Algorithm5(13)(HGUSAOR)k=∑l=1s‍El{H(β,ψ)lH(α,ϕ)l}μl,k,
where
(14)H(α,ϕ)l=(I-αϕLl)-1[I-ϕ+(1-α)ϕLl+ϕUl],H(β,ψ)l=(I-βψUl)-1[I-ψ+(1-β)ψUl+ψLl].
Obviously, we have to find a constant σ with 0≤σ<1 and some norm, which are independent of k, such that for k≥1, ∥HGUSAOR(α,β,ϕ,ψ)k∥≤σ.
We first note that the matricesI-αϕLl and I-βψUl are H-matrices for l=1,2,…,s. Thus by Lemma 3 we have the following inequalities:
(15)|(I-αϕLl)-1|≤〈I-αϕLl〉-1=(I-αϕ|Ll|)-1,|(I-βψUl)-1|≤〈I-βψUl〉-1=(I-βψ|Ul|)-1.
From this relation, it follows that
(16)|H(β,ψ)lH(α,ϕ)l|=|(I-βψUl)-1×[I-ψ+(1-β)ψUl+ψLl]×(I-αϕLl)-1×[I-ϕ+(1-α)ϕLl+ϕUl]|≤〈I-βψUl〉-1×|I-ψ+(1-β)ψUl+ψLl|×〈I-αϕLl〉-1×|I-ϕ+(1-α)ϕLl+ϕUl|≤(I-βψ|Ul|)-1×[|I-ψ|+|1-β|ψ|Ul|+ψ|Ll|]×(I-αϕ|Ll|)-1×[|I-ϕ|+|1-α|ϕ|Ll|+ϕ|Ul|].
Case
1. Let 0<βi≤1, 0<γi≤1, i=1,2,…,n. Then
(17)|I-ψ|+|1-β|ψ|Ul|+ψ|Ll|=I-ψ+ψ|Ul|-βψ|Ul|+ψ|Ll|.|I-ϕ|+|1-α|ϕ|Ll|+ϕ|Ul|=I-ϕ+ϕ|Ll|-αϕ|Ll|+ϕ|Ul|.
Define
(18)Ml1(β,ψ)=I-βψ|Ul|,Ml2(α,ϕ)=I-αϕ|Ll|,Nl1(β,ψ)=|I-ψ|+(1-β)ψ|Ul|+ψ|Ll|,Nl2(α,ϕ)=|I-ϕ|+(1-α)ϕ|Ll|+ϕ|Ul|.
So, for l=1,2,…,s, we have the following relations
(19)Ml1(β,ψ)-Nl1(β,ψ)=ψ-ψ|Ul|-ψ|Ll|=ψ(I-|B|).Ml2(α,ϕ)-Nl2(α,ϕ)=ϕ-ϕ|Ll|-ϕ|Ul|=ϕ(I-|B|).
Since forl=1,2,…,s, Ml1(β,ψ) and Ml2(α,ϕ) are both M-matrices and Nl1(β,ψ)≥0, Nl2(α,ϕ)≥0, the splittings Ml1(β,ψ)-Nl1(β,ψ) and Ml2(α,ϕ)-Nl2(α,ϕ) are M-splittings of ψ(I-|B|) and ϕ(I-|B|), respectively, which are M-matrices. So, from Lemma 4 we may complete the proving courses, which are listed subsequently.
Case
2. Let 1<βi<2/(1+ρ), 1<γi<2/(1+ρ), i=1,2,…,n.
Assume thatβmax⁡=max⁡1≤i≤n{βi}, γmax⁡=max⁡1≤i≤n{γi}. Then we have
(20)|I-ψ|+(1-β)ψ|Ul|+ψ|Ll|≤(γmax⁡-1)I+(1-β)γmax⁡|Ul|+γmax⁡|Ll|,|I-ϕ|+(1-α)ϕ|Ll|+ϕ|Ul|≤(βmax⁡-1)I+(1-α)βmax⁡|Ll|+βmax⁡|Ul|,(I-βψ|Ul|)-1≤(I-βγmax⁡|Ul|)-1,(I-αϕ|Ll|)-1≤(I-αβmax⁡|Ll|)-1.
Similar toCase1, we define
(21)Ml3(β,γmax⁡)=I-βγmax⁡|Ul|,Ml4(α,βmax⁡)=I-αβmax⁡|Ll|,Nl3(β,γmax⁡)=(γmax⁡-1)I+(1-β)γmax⁡|Ul|+γmax⁡|Ll|,Nl4(α,βmax⁡)=(βmax⁡-1)I+(1-α)βmax⁡|Ll|+βmax⁡|Ul|.
Then
(22)Ml3(β,γmax⁡)-Nl3(β,γmax⁡)=(2-β)I-β|B|,Ml4(α,βmax⁡)-Nl4(α,βmax⁡)=(2-α)I-α|B|.
It is clear,(2-β)I-β|B| and (2-α)I-α|B| are both M-matrices. Since, for l=1,2,…,s, Ml1(β,ψ) and Ml2(α,ϕ) are M-matrices, Nl1(β,ψ)≥0 and Nl2(α,ϕ)≥0, the splittings Ml1(β,ψ)-Nl1(β,ψ) and Ml2(α,ϕ)-Nl2(α,ϕ) are M-splittings of the matrices (2-β)I-β|B| and (2-α)I-α|B|, respectively.
Thus, forCases  1 and 2, from Lemma 4, we have
(23)∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞<1,l=1,2,…,s,∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞<1,l=1,2,…,s,
So
(24)P1-1|(HGUSAOR)k|P1e=∑l=1s‍El{P1-1H(β,ψ)lH(α,ϕ)lP1}μl,ke≤∑l=1s‍El{P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)(Ml2)-1mmmmmmm×(α,ϕ)Nl2(α,ϕ)P1(Ml2)-1}μl,ke=∑l=1s‍El{P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)mmmmmmm×P1P1-1P2P2-1(Ml2)-1mmmmmmm×(α,ϕ)Nl2(α,ϕ)P2P2-1P1{P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)(Ml1)-1}μl,ke=max⁡1≤l≤s{∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞mmmmmm×∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞}e.
which implies
(25)∥P1-1(HGUSAOR)kP1∥∞≤max⁡1≤l≤s{∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞mmmmmm×∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞}<1,|(HGUSAOR)k|P1e=P1(P1-1|HGUSAOR(α,β,ϕ,ψ)k|P1)e≤P1∥P1-1HGUSAOR(α,β,ϕ,ψ)kP1∥∞e≤max⁡1≤l≤s{∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞×∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞}P1e.
If we define
(26)σ=max⁡1≤l≤s{∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞mmmmm×∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞}.
Then we have
(27)∥(HGUSAOR)k∥≤σ<1.According to Algorithm7, we can also get the following result.Theorem 12.
LetA∈Rn×n be an H-matrix and (I-Ll,Ul,El), l=1,2,…,s, a multisplitting of A. Assume that for l=1,2,…,s, we have the following.(1)
Ll are the strictly lower triangular matrices and Ul are the matrices such that the equalities A=I-Ll-Ul hold.(2)
〈A〉=|I|-|Ll|-|Ul|=|I|-|B|, where |B|=|Ll|+|Ul|.(3)
P is diagonal matrix defined in Lemma 3 and Ml1(β,ψ), Nl1(β,ψ), Ml2(α,ϕ), and Nl2(α,ϕ) in Theorem 11.Then the sequence {x(k)} generated by Algorithm 7 converges for any initial x(0) if and only if (α,β,βi,γi,ω), i=1,2,…,n∈W2, with ρ=(|B|) and θ=max⁡1≤l≤s{∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞}, where
(28)W2={21+ρ(α,β,βi,γi,ω)∈R5:0≤α,β≤1,0<βi,mmmγi<21+ρ,0<ω<21+θ,i=1,2,…,n.}.Proof.
Define the iteration matrix in Algorithm7(29)(HGUSAOR)k=ω(HGUSAOR)k+(1-ω)I,
where
(30)(HGUSAOR)k=∑l=1s‍El{H(β,ψ)lH(α,ϕ)l}μl,k.H(α,ϕ)l=(I-αϕLl)-1[I-ϕ+(1-α)ϕLl+ϕUl],H(β,ψ)l=(I-βψUl)-1[I-ψ+(1-β)ψUl+ψLl].
Obviously, similar to Theorem 11 we only need to find a constant σ with 0≤σ<1, which is independent of k, such that K=∥P1-1HGUSAOR(α,β,ϕ,ψ,ω)kP1∥∞≤σ. From the proof of Theorem 11, we can get
(31)K≤ω∥P1-1(HGUSAOR)kP1∥∞+|1-ω|≤ωmax⁡1≤l≤s{∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞mmmmmm×∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞}+|1-ω|=ωθ+|1-ω|.
Now let σ denote the last item in above inequalities. Clearly, if 0<βi<2/(1+ρ), 0<γi<2/(1+ρ), 0<ω<2/(1+θ), then
(32)∥(HGUSAOR)k∥≤σ<1.Using the proving process of Theorems11 and 12 and [13, Theorem 2.8] we have the following convergence result about Algorithm 9.Theorem 13.
LetA∈Rn×n be an H-matrix and (I-Ll,Ul,El), l=1,2,…,s, a multisplitting of A. Assume that for l=1,2,…,s, we have the following.(1)
Ll are the strictly lower triangular matrices and Ul are the matrices such that the equalities A=I-Ll-Ul hold.(2)
〈A〉=|I|-|Ll|-|Ul|=|I|-|B|, where |B|=|Ll|+|Ul|.(3)
P is diagonal matrix defined in Lemma 3 and Ml1(β,ψ), Nl1(β,ψ), Ml2(α,ϕ) and Nl2(α,ϕ) in Theorem 11.(4)
The index sequence{Pi} is admissible and regulated.Then the sequence {x(k)} generated by Algorithm 9 converges for any initial x(0) if and only if (α,β,βi,γi,ω), i=1,2,…n∈W3, with ρ=(|B|) and θ=max⁡1≤l≤s{∥P1-1(Ml1)-1(β,ψ)Nl1(β,ψ)P1∥∞∥P2-1(Ml2)-1(α,ϕ)Nl2(α,ϕ)P2∥∞}, where
(33)W3={21+ρ(α,β,βi,γi,ω)∈R5:0≤α,β≤1,0<βi,mmγi<21+ρ,0<ω<21+θ,i=1,2,…,n.}.Remark 14.
It is known that anM-matrix or a symmetric positive definite L-matrix is also H-matrix. Therefore, the convergence results in Theorems 11, 12, and 13 are valid.Remark 15.
Since a strictly or an irreducible diagonally dominant matrix is also satisfying the condition of Theorems11, 12, and 13, our methods are also valid for these kinds of matrices. Furthermore, for strictly or irreducible diagonally dominant matrices, ∥B∥∞ can take the place of ρ in Theorems 11, 12, and 13.


## 4. Applied Convergence of Relaxed Chaotic Methods

In Theorems12 and 13 of this paper, we find that θ is difficult to compute when carrying out numerical experiments. So for irreducible diagonally dominant matrices, we also have the following applied results of convergence according to Algorithms 7 and 9, respectively.Theorem 16.
LetA∈Rn×n be an irreducible diagonally dominant matrix and (I-Ll,Ul,El), l=1,2,…,s, a multisplitting of A. Assume that for l=1,2,…,s, we have the following.(1)
Ll are the strictly lower triangular matrices and Ul are the matrices such that the equalities A=I-Ll-Ul hold.(2)
〈A〉=|I|-|Ll|-|Ul|=|I|-|B|, where |B|=|Ll|+|Ul|.(3)
P is diagonal matrix defined in Lemma 3 and Ml1(β,ψ), Nl1(β,ψ), Ml2(α,ϕ), and Nl2(α,ϕ) in Theorem 11.Then the sequence {x(k)} generated by Algorithm 7 converges for any initial x(0) if and only if (α,β,βi,γi,ω),  i=1,2,…,n∈W4, with θ′=max⁡1≤l≤n{(|1-γi|+γi∥B∥∞)}max⁡1≤l≤n{(|1-βi|+βi∥B∥∞)}, where
(34)W4={21+θ′21+∥B∥∞(α,β,βi,γi,ω)∈R5:0≤α,β≤1,0<βi,mmγi<21+∥B∥∞,0<ω<21+θ′}.Proof.
We only prove|(HGUSAOR)k|x<θ′′x(k=1,2,…,0≤θ′≤1). Let us define the iteration matrix in Algorithm 7(35)(HGUSAOR)k=ω(HGUSAOR)k+(1-ω)I.
From the proving process of Theorem 11, we may define
(36)T1=(I-βψ|Ul|)-1[|I-ψ|+(1-β)ψ|Ul|+ψ|Ll|],T2=(I-αϕ|Ll|)-1[|I-ϕ|+(1-α)ϕ|Ll|+ϕ|Ul|].
At first, we need to prove ρ(T1)<1. Similarly, we may also prove ρ(T2)<1. Assume that
(37)0≤α,β≤1,0<βi,γi<21+ρ.
With (36), we know that T1 is nonnegative, so according to [24, Theorem 2.7], there exists an eigenvector x≥0, x≠0, such that T1x=ρ(T1)x hold; that is,
(38)[|I-ψ|+(1-β)ψ|Ul|+ψ|Ll|]x=ρ(T1)(I-βψ|Ul|)x.
Multiplying by ψ-1, it holds that
(39)[ρ(T1)ψ-1-|I-ψ-1|]x={[1-β+βρ(T1)]|Ul|+|Ll|}x.
As [1-β+βρ(T1)]|Ul|+|Ll|≥0, it follows by [5, Theorem 11] that
(40)min⁡1≤l≤n{γi-1ρ(T1)-|1-γi-1|}≤ρ([1-β+βρ(T1)]|Ul|+|Ll|).
From the proof of [3, Theorem 3.1], we have ρ(T1)<1, 0≤1-β+βρ(T1)<1. Since the matrices A, B, and [1-β+βρ(T1)]|Ul|+|Ll| are irreducible, by [24, Theorem 2.1], it follows that
(41)ρ([1-β+βρ(T1)]|Ul|+|Ll|)<ρ(|Ll|+|Ul|)=ρ(|B|)≤∥B∥∞.
With (40) and (41) and M being irreducible diagonally dominant by rows, we have
(42)ρ(T1)<max⁡1≤l≤n{|1-γi|+γi∥B∥∞}.
Notice that if γi≤1, we may obtain
(43)|1-γi|+γi∥B∥∞=1-γi+γi∥B∥∞<1.
While if 1<γi<2/(1+∥B∥∞), we also have
(44)|1-γi|+γi∥B∥∞=-1+γi+γi∥B∥∞=γi(1+∥B∥∞)-1<21+∥B∥∞(1+∥B∥∞)-1=1,
From (42), (43), and (44), we can get
(45)ρ(T1)<max⁡1≤l≤n{|1-γi|+γi∥B∥∞}<1,ρ(T2)<max⁡1≤l≤n{|1-βi|+βi∥B∥∞}<1.
From Theorem 11, we have
(46)(HGUSAOR)k≤|(HGUSAOR)k|=|∑l=1s‍H(β,ψ)lH(α,ϕ)l|≤∑l=1s‍|H(β,ψ)l||H(α,ϕ)l|≤∑l=1s‍T1T2.
From (35) and the above proof, we have
(47)(HGUSAOR)kx≤ω|(HGUSAOR)k|x+|1-ω|x≤ω|∑l=1s‍ElH(β,ψ)lH(α,ϕ)l|x+|1-ω|x≤ω∑l=1s‍El|H(β,ψ)l||H(α,ϕ)l|x+|1-ω|x≤∑l=1s‍ElT1T2x+|1-ω|x=ρ(T2)ω∑l=1s‍ElT1x+|1-ω|x=ωρ(T1)ρ(T2)∑l=1s‍Elx+|1-ω|x=ωρ(T1)ρ(T2)x+|1-ω|x<ωmax⁡1≤l≤n{|1-γi|+γi∥B∥∞}×max⁡1≤l≤n{|1-βi|+βi∥B∥∞}x+|1-ω|x=(ωθ′+|1-ω|)x=θ′′x,
where θ′=max⁡1≤l≤n{|1-γi|+γi∥B∥∞}max⁡1≤l≤n{|1-βi|+βi∥B∥∞}, 0<ω<2/(1+θ′), θ′′=ωθ′+|1-ω|<1.Remark 17.
Obviously, convergence results of Theorem16 are convenient for carrying out numerical experiments. Using the proving process of Theorems 11 and 16 and [13, Theorem 2.8], we can get the following result about Algorithm 9.Theorem 18.
LetA∈Rn×n be an irreducible diagonally dominant matrix and (I-Ll,Ul,El), l=1,2,…,s, a multisplitting of A. Assume that for l=1,2,…,s, we have the following.(1)
Ll are the strictly lower triangular matrices and Ul are the matrices such that the equalities A=I-Ll-Ul hold.(2)
〈A〉=|I|-|Ll|-|Ul|=|I|-|B|, where |B|=|Ll|+|Ul|.(3)
P is diagonal matrix defined in Lemma 3 and Ml1(β,ψ), Nl1(β,ψ), Ml2(α,ϕ), and Nl2(α,ϕ) in Theorem 11.(4)
The index sequence{Pi} is admissible and regulated.Then the sequence {x(k)} generated by Algorithm 9 converges for any initial x(0) if and only if (α,β,βi,γi,ω),  i=1,2,…,n∈W5, with θ′=max⁡1≤l≤n{(|1-γi|+γi∥B∥∞)}max⁡1≤l≤n{(|1-βi|+βi∥B∥∞)}, where
(48)W5={21+θ′21+∥B∥∞(α,β,βi,γi,ω)∈R5:0≤α,β≤1,0<βi,mmγi<21+∥B∥∞,0<ω<21+θ′}.Remark 19.
As a special case, for the relaxed matrix multisplitting chaotic GSSOR-style methods, we have the corresponding convergence results, whereα=1, β=1, ϕ=diag⁡(β1,β2,…,βn), ψ=diag⁡(γ1,γ2,…,γn) with βi≥0, γi≥0(i=1,2,…,n) and ω real parameters.


## 5. Numerical Examples

Example 1.
By using difference discretization of partial differential equation, we can obtain the corresponding coefficient matrix of the linear system(n=6), which is as follows:
(49)A=[1-14000011340000131-13000034110000141-14000011],b=[34114311412].Now, we will apply the results of Theorem16 according to Algorithm 7. From Algorithm 7, we can get the iterative matrix
(50)H=ω∑l=1s‍El[H(β,ψ)lH(α,ϕ)l]+(1-ω).
Here, we assume that s=3, μl,k≡1. By direct calculations with Matlab 7.1, we have
(51)∥B∥∞=1.75,21+∥B∥∞=0.7273.
In Table 1, we show that convenience results of Section 4 are convenience for carrying out numerical experiments, where ρ(H) denote the spectral radius of iterative matrix H:
(52)E1=diag⁡(1,1,0,0,0,0),E2=diag⁡(0,0,1,1,0,0),E3=diag⁡(0,0,0,0,1,1).L1=[000000120000001300000032000000014000000-0.40],L2=[000000-3400000016000000720000000180000000.20],L3=[0000000.30000000.5000000-0.30000003400000000.40],Ul=I-Ll-A,l=1,2,3.Table 1
Convergence results of Theorems16 and 18.
(
α
,
β
,
β
i
,
γ
i
,
ω
)
2
1
+
∥
B
∥
∞
2
1
+
θ
′
ρ
(
H
)
(
0.2,0.8,0.6,0.5,1.1
)
0.7273
1.3793
0.5711
(
0.3,0.8,0.7,0.5,1.1
)
0.7273
1.3115
0.6133
(
0.4,0.7,0.6,0.5,0.8
)
0.7273
1.3793
0.8365
(
0.6,0.5,0.4,0.6,0.9
)
0.7273
1.3793
0.69393
(
0.8,0.2,0.3,0.7,1.1
)
0.7273
1.3115
0.6053
(
0.9,0.1,0.25,0.65,1.1
)
0.7273
1.3445
0.7154Remark 20.
Obviously,θ′ of Theorems 16 and 18 is applied and easily calculated when carrying out numerical experiments.Example 2.
Consider a matrixA∈Rn×n of the form
(53)A=[100⋯0-ν-ν10⋯000-ν1⋯00⋮⋮⋱⋮⋮⋮000⋯10000⋯-ν1]=[100⋯00010⋯00001⋯00⋮⋮⋱⋮⋮⋮000⋯10000⋯01]-[000⋯0νν00⋯000ν0⋯00⋮⋮⋱⋮⋮⋮000⋯00000⋯ν0],
where ρ(|D|-1|B|)=ν, ν is a real number, satisfying |ν|<1.In Theorem11, let 0≤α, β≤1, 0<βi, γi<2/(1+ν), i=1,2,…,n; then Algorithm 5 converges for any initial vector x(0). In Theorems 12 and 13, let 0≤α, β≤1, 0<βi, γi<2/(1+ν), 0<ω<2/(1+θ), i=1,2,…,n; then Algorithms 7 and 9 converge for any initial vector x(0). In Theorems 16 and 18, let 0≤α, β≤1, 0<βi, γi<2/(1+ν), 0<ω<2/(1+θ′), i=1,2,…,n; then Algorithms 7 and 9 converge for any initial vector x(0), where θ′=max⁡1≤l≤n{(|1-γi|+νγi)}max⁡1≤l≤n{(|1-βi|+νβi)}.If we chooseν=1/5, in Theorem 11, let 0≤α, β≤1, 0<βi, γi<5/3, i=1,2,…,n; then Algorithm 5 converges for any initial vector x(0). In Theorems 12 and 13, let 0≤α, β≤1, 0<βi, γi<5/3, 0<ω<2/(1+θ), i=1,2,…,n; then Algorithms 7 and 9 converge for any initial vector x(0). In Theorems 16 and 18, let 0≤α, β≤1, 0<βi, γi<5/3, 0<ω<2/(1+θ′), i=1,2,…,n; then Algorithms 7 and 9 converge for any initial vector x(0), where θ′=max⁡1≤l≤n{(|1-γi|+(1/5)γi)}max⁡1≤l≤n{(|1-βi|+(1/5)βi)}.


## 6. Conclusions

In this paper, we consider relaxed matrix parallel multisplitting chaotic GUSAOR-style methods for solving linear systems of algebraic equationsAx=b, in which the coefficient A is an H-matrix or an irreducible diagonally dominant matrices, and analyze the convergence of our methods, which use more relaxed factors and are the generalization of [11, 13, 14]. The parameters can be adjusted suitably so that the convergence property of method can be substantially improved. Furthermore, we further study some applied convergence results of methods to be convenient for carrying out numerical experiments. Finally, we give some applied examples, which show that our convergence results are applied and easily calculated when carrying out numerical experiments.Particularly, one may discuss how to choose the set of relaxed parameters in order to really accelerate the convergence of the considered method. Furthermore, The optimal choice of this set of relaxed parameters is valuably studied.



---

*Source: 594185-2014-07-17.xml*