Teck-Cheong Lim

(1)

Volume 2010, Article ID 821928,13pages doi:10.1155/2010/821928

Research Article

Nonexpansive Matrices with Applications to Solutions of Linear Systems by Fixed Point Iterations

Teck-Cheong Lim

Department of Mathematical Sciences, George Mason University, 4400, University Drive, Fairfax, VA 22030, USA

Correspondence should be addressed to Teck-Cheong Lim,[email protected] Received 28 August 2009; Accepted 19 October 2009

Academic Editor: Mohamed A. Khamsi

Copyrightq2010 Teck-Cheong Lim. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

We characterizeimatrices which are nonexpansive with respect to some matrix norms, andii matrices whose average iterates approach zero or are bounded. Then we apply these results to iterative solutions of a system of linear equations.

Throughout this paper,Rwill denote the set of real numbers,Cthe set of complex numbers, andM_nthe complex vector space of complexn×nmatrices. A function · :M_n → Ris a matrix norm if for allA, B∈M_n, it satisfies the following five axioms:

1A ≥0;

2A0 if and only ifA0;

3cA|c|Afor all complex scalarsc;

4AB ≤ AB;

5AB ≤ A B.

Let| · |be a norm onCⁿ. Define · onMnby Amax

|x|1|Ax|. 1

This norm onMnis a matrix norm, called the matrix norm induced by| · |. A matrix norm on Mnis called an induced matrix norm if it is induced by some norm onCⁿ. If · 1is a matrix norm onM_n, there exists an induced matrix norm · 2onM_nsuch thatA2 ≤ A1for all

(2)

A∈Mncf.1, page 297. Indeed one can take · 2to be the matrix norm induced by the norm| · |onCⁿdefined by

|x|Cx₁, 2

whereCxis the matrix inM_nwhose columns are all equal tox. ForA∈M_n,ρAdenotes the spectral radius ofA.

Let | · |be a norm in Cⁿ. A matrix A ∈ Mn is a contraction relative to | · |if it is a contraction as a transformation fromCⁿintoCⁿ; that is, there exists 0≤λ <1 such that

Ax−Ay≤λx−y, x, y∈Cⁿ. 3 Evidently this means that for the matrix norm · induced by| · |,A < 1. The following theorem is well knowncf.1, Sections 5.6.9–5.6.12.

Theorem 1. For a matrixA∈M_n, the following are equivalent:

aAis a contraction relative to a norm inCⁿ; bA<1 for some induced matrix norm · ; cA<1 for some matrix norm · ;

dlim_k_{→ ∞}A^k0;

eρA<1.

Thatbfollows fromcis a consequence of the previous remark about an induced matrix norm being less than a matrix norm. Since all norms onMn are equivalent, the limit ind can be relative to any norm onM_n, so thatdis equivalent to all the entries ofA^kconverge to zero ask → ∞, which in turn is equivalent to lim_k_{→ ∞}A^kx0 for allx∈Cⁿ.

In this paper, we first characterize matrices inMnthat are nonexpansive relative to some norm| · |onCⁿ, that is,

Ax−Ay≤x−y, x, y∈Cⁿ. 4

Then we characterize thoseA∈Mnsuch that

A_k 1 k

IAA²· · ·A^k−1

5

converges to zero ask → ∞, and those that{Ak:k0,1,2, . . .}is bounded.

Finally we apply our theory to approximation of solution ofAx busing iterative methodsfixed point iteration methods.

(3)

Theorem 2. For a matrixA∈Mn, the following are equivalent:

aAis nonexpansive relative to some norm onCⁿ; bA ≤1 for some induced matrix norm · ; cA ≤1 for some matrix norm · ;

d{A^k:k0,1,2, . . .}is bounded;

eρA≤1, and for any eigenvalueλofAwith|λ|1, the geometric multiplicity is equal to the algebraic multiplicity.

Proof. As in the previous theorem,a,b, andcare equivalent. Assume thatbholds. Let the norm · be induced by a vector norm| · |ofCⁿ. Then

A^kx≤A^k|x| ≤ A^k|x| ≤ |x|, k0,1,2, . . . , 6

proving thatA^kxis bounded in norm| · |for everyx∈Cⁿ. Takingxei, we see that the set of all columns ofA^k, k0,1,2, . . . ,is bounded. This proves thatA^k, k0,1,2, . . . ,is bounded in maximum column sum matrix norm1, page 294, and hence in any norm inM_n. Note that the last part of the proof also follows from the Uniform Boundedness Principlesee, e.g., 2, Corollary 21, page 66

Now we prove thatdimpliese. Suppose thatAhas an eigenvalueλwithλ > 1.

Letxbe an eigenvector corresponding toλ. Then

A^kx|λ|^kx −→ ∞ 7

ask → ∞, where · is any vector norm ofCⁿ. This contradictsd. Hence|λ| ≤ 1. Now suppose thatλis an eigenvalue with|λ| 1 and the Jordan block corresponding toλis not diagonal. Then there exist nonzero vectorsv1, v2such thatAv1 λv1, Av2 v1λv2. Let uv1v2. Then

A^kuλ^k−1λkv1λ^kv2, 8

and A^ku ≥ kv1 − v1 − v2. It follows that A^ku, k 0,1,2, . . . , is unbounded, contradictingd. Hencedimpliese.

Lastly we prove thateimpliesc. Assume thateholds.Ais similar to its Jordan canonical form J whose nonzero oﬀ-diagonal entries can be made arbitrarily small by similarity 1, page 128. Since the Jordan block for each eigenvalue with modulus 1 is diagonal, we see that there is an invertible matrix S such that the l1-sum of each row of SAS⁻¹is less than or equal to 1, that is,SAS⁻¹∞≤1, where · ∞is the maximum row sum matrix norm1, page 295. Define a matrix norm · byMSMS⁻¹_∞. Then we have A ≤1.

Letλbe an eigenvalue of a matrixA∈Mn. The index ofλ, denoted by indexλis the smallest value ofkfor which rankA−λI^krankA−λI^k11, pages 148 and 131. Thus conditioneabove can be restated asρA≤1, and for any eigenvalueλofAwith|λ|1, indexλ 1.

(4)

LetA∈Mn. Consider

A_k 1 k

IA· · ·A^k−1

. 9

We callAk thek-average of A. As with A^k, we have Akx → 0 for every xif and only if A_k → 0 inM_n, and thatA_kxis bounded for everyxif and only ifA_kis bounded inM_n. We have the following theorem.

Theorem 3. LetA∈Mn. Then

aA_k, k1,2, . . . ,converges to 0 if and only ifA ≤1 for some matrix norm · and that 1 is not an eigenvalue ofA,

bAk, k 1,2, . . . ,is bounded if and only ifρA≤ 1,indexλ≤2 for every eigenvalueλ with|λ|1 and that index1 1 if 1 is an eigenvalue ofA.

Proof. First we prove the suﬃciency part ofa. Letxbe a vector inCⁿ. Let y_k 1

k

IA· · ·A^k−1

x. 10

ByTheorem 2for any eigenvaluesλofAeither|λ|<1 or|λ|1 and indexλ 1.

If Ais written in its Jordan canonical formA SJS⁻¹, then the k-average ofA is SJS⁻¹, whereJis thek-average ofJ.Jis in turn composed of thek-average of each of its Jordan blocks. For a Jordan block ofJof the form

⎛

⎜⎜

⎝ λ 1

λ 1

· ·

· 1 λ

⎞

⎟⎟

⎠

, 11

|λ|must be less than 1. Itsk-average has constant diagonal and upper diagonals. LetD_jbe the constat value of itsjth upper diagonalD0being the diagonaland let Sj kDj. Then Cm, n 0 forn > m

S0 1−λ^k 1−λ , S_jC

j, j C

j1, j

λ· · ·C

k−1, j

λ^k−1−j, j 1,2, . . . , n−1.

12

Using the relationCm1, j−Cm, j Cm, j−1, we obtain S_j−λS_jS_j−1−λ^k−jC

k, j

. 13

Thus, we haveS0 → 1/1−λask → ∞. By induction, using13above and the fact that λ^k−jCk, j → 0 ask → ∞, we obtainSj → 1/1−λ^j1ask → ∞. ThereforeDj Sj/k O1/kask → ∞.

(5)

If the Jordan block is diagonal of constant valueλ, thenλ /1,|λ| ≤1 and thek-average of the block is diagonal of constant value1−λ^k/k1−λ O1/k.

We conclude thatAkO1/kand henceyk ≤ AkxO1/kask → ∞.

Now we prove the necessity part of a. If 1 is an eigenvalue of A and x is a corresponding eigenvector, thenA_kxx /0 for everykand of courseB_kxfails to converge to 0. Ifλis an eigenvalue ofAwith|λ|>1 andxis a corresponding eigenvector, then

A_kx λ^k−1

kλ−1

x ≥ |λ|^k−1

k|λ−1| x. 14

which approaches to ∞ as k → ∞. If λ is an eigenvalue of A with |λ| 1, λ /1, and indexλ≥2, then there exist nonzero vectorsv1, v2such thatAv1 λv1, Av2 v1λv2. Then by using the identity

12λ3λ²· · · k−1λ^k−2 1−λ^k−1

1−λ² −k−1λ^k−1

1−λ 15

we get

Akv2

1−λ^k−1 k1−λ² −

1− 1

k λ^k−1

1−λ

v1 1−λ^k

k1−λv2. 16

It follows that lim_k_{→ ∞}Akv2does not exist. This completes the proof of parta.

Suppose that A satisfies the conditions in b and that A SJS⁻¹ is the Jordan canonical form of A. Let λ be an eigenvalue of A and let v be a column vector of S corresponding to λ. If |λ| < 1, then the restriction B of A to the subspace spanned by v, Av, A²v, . . . is a contraction, and we have A_kv B_kv ≤ v. If |λ| 1, and λ /1, then by conditions in b either Av λv, or there exist v1, v2 with v v2 such that Av1 λv1, Av2 v1λv2. In the former case, we haveAk ≤ vand in the latter case, we see from16thatA_kv A_kv2is bounded. Finally ifλ1 then since index1 1, we haveAvvand henceA_kvv. In all cases, we proved thatA_kv, k0,1,2, . . . ,is bounded.

Since column vectors ofSform a basis forCⁿ, the suﬃciency part ofbfollows.

Now we prove the necessity part ofb. If Ahas an eigenvalue λ with|λ| > 1 and eigenvectorv, then as shown aboveA_kv → ∞ask → ∞. IfAhas 1 as an eigenvalue and index1 ≥ 2, then there exist nonzero vectorsv1, v2 such thatAv1 v1 andAv2 v1v2. ThenAkv2 k−1/2v2which is unbounded. Ifλis an eigenvalue ofAwith|λ|1, λ /1 and indexλ≥3, then there exist nonzero vectorsv1, v2andv3such thatAv1λv1, Av2

v1λv2andAv3 v2λv3. By expandingA^jv3, j0,1,2, . . . , k−1 and using the identity

k−1

j2

C j,2

λ^j−2 1 1−λ²

1−λ^k−2 1−λ 1

2k−2λ^k−2k−1λ−k1

, 17

(6)

we obtain

A_kv3

1 1−λ²

1−λ^k−2 k1−λ1

2k−2λ^k−2 k−1

k λ−k1 k

v1

1−λ^k−1 k1−λ² −

1− 1

k λ^k−1

1−λ

v2 1−λ^k k1−λv3

18

which approaches to∞ask → ∞. This completes the proof.

We now consider applications of preceding theorems to approximation of solution of a linear systemAxb, whereA∈M_nandba given vector inCⁿ. LetQbe a given invertible matrix inMn.xis a solution ofAx bif and only ifxis a fixed point of the mappingT defined by

Tx

I−Q⁻¹A

xQ⁻¹b. 19

T is a contraction if and only if I −Q⁻¹A is. In this case, by the well known Contraction Mapping Theorem, given any initial vector x0, the sequence of iterates x_k T^kx0, k 0,1,2, . . . ,converges to the unique solution ofAx b. In practice, givenx0, each successive x_kis obtained fromx_k−1by solving the equation

Qxk Q−Axk−1b. 20

The classical methods of Richardson, Jacobi, and Gauss-Seidelsee, e.g.,3haveQ I, D, and L respectively, where I is the identity matrix, D the diagonal matrix containing the diagonal of A, andL the lower triangular matrix containing the lower triangular portion ofA. Thus byTheorem 1we have the following known theorem.

Theorem 4. LetA, Q ∈ Mn, with Qinvertible. Letb, x0 ∈ Cⁿ. IfρI −Q⁻¹A < 1, thenA is invertible and the sequencex_k, k1,2, . . . ,defined recursively by

Qxk Q−Axk−1b 21

converges to the unique solution ofAxb.

Theorem 4fails ifρI−Q⁻¹A 1, For a simple 2 × 2 example, letQI, b0, A2I andx0any nonzero vector.

We need the following lemma in the proof of the next two theorems. For a matrix A∈Mn, we will denoteRAandNAthe range and the null space ofArespectively.

Lemma 5. LetAbe a singular matrix inM_nsuch that the geometric multiplicity and the algebraic multiplicity of the eigenvalue 0 are equal, that is, index0 1. Then there is a unique projection PAwhose range is the range ofAand whose null space is the null space ofA, or equivalently,Cⁿ RA⊕NA. Moreover,Arestricted toRAis an invertible transformation fromRAontoRA.

(7)

Proof. IfASJS⁻¹is a Jordan canonical form ofAwhere the eigenvalues 0 appear at the end portion of the diagonal ofJ, then the matrix

PAS

⎡

⎢⎢

⎢⎣ 1

·

· 1

0

·

· 0

⎤

⎥⎥

⎥⎦

S⁻¹ 22

is the required projection. ObviouslyAmapsRAintoRA. Ifz∈RAandAz 0, then z∈NA∩RA {0}and soz0. This proves thatAis invertible onRA.

Remark 6. Under the assumptions ofLemma 5, we will call the component of a vectorcin NAthe projection ofconNAalongRA. Note that by definition of index, the condition in the lemma is equivalent toNA² NA.

Theorem 7. LetAbe a matrix inM_nandba vector inCⁿ. LetQbe an invertible matrix inM_nand letB I−Q⁻¹A. Assume thatρB ≤ 1 and that indexλ 1 for every eigenvalueλofBwith modulus 1, that is,Bis nonexpansive relative to a matrix norm. Starting with an initial vectorx0in Cⁿdefinex_krecursively by

Qxk Q−Axk−1b 23

fork1,2, . . . .Let

y_k x0x1· · ·x_k−1

k . 24

IfAx bis consistent, that is, has a solution, thenyk, k 1,2, . . . ,converge to a solution vectorz with rate of convergenceyk−zO1/k. IfAxbis inconsistent, then lim_kxklim_kyk

∞. More precisely, lim_kx_k/kcand lim_ky_k/kc/2, wherecQ⁻¹bandcis the projection ofc onNA NQ⁻¹AalongRQ⁻¹A.

Proof. First we assume thatAis invertible so thatI−BQ⁻¹Ais also invertible. LetTbe the mapping defined byTxBxc. ThenT^kxB^kxcBc· · ·B^k−1c. LetscBc· · ·B^k−1c.

Thens−Bsc−B^kcand hences I−B⁻¹c−I−B⁻¹B^kc I−B⁻¹c−B^kI−B⁻¹c. Let z I−B⁻¹cA⁻¹b.zis the unique solution ofAxband

T^kxB^kxz−B^kzB^kx−z z. 25

(8)

Since the sequencexkin the theorem isT^kx0, we have y_k 1

k

IB· · ·B^k−1

x0−z zB_kx0−z z. 26

SinceI−Bis invertible, 1 is not an eigenvalue ofB, and byTheorem 3 partayk−z Bkx0−z → 0 ask → ∞. Moreover, from the proof of the same theorem,yk−zO1/k.

Next we consider the case when Ais not invertible. Since Q is invertible, we have RQ⁻¹A Q⁻¹RAandNQ⁻¹A NA. The index of the eigenvalue 0 ofQ⁻¹Ais the index of eigenvalue 1 ofBI−Q⁻¹A. Thus byLemma 5,CⁿQ⁻¹RA⊕NA. For every vectorv ∈ Cⁿ, let v^r andvⁿ denote the component ofvin the subspaceQ⁻¹RAand NA, respectively.

Assume thatAxbis consistent, that is,b∈RA. Thenc∈RQ⁻¹A. ByLemma 5, the restriction ofQ⁻¹Aon its range is invertible, so there exists a uniquezinRQ⁻¹Asuch thatQ⁻¹Azc, or equivalently,I−Bzc. For any vectorx, we have

T^kxB^kxcBc· · ·B^k−1c B^K

x^rxⁿ

IB· · ·B^k−1

I−Bz B^k

x^r

xⁿz−B^k z B^k

x^r−z

xⁿz.

27

SinceBmapsRQ⁻¹AintoRQ⁻¹AandI−BQ⁻¹Arestricted toRQ⁻¹Ais invertible, we can apply the preceding proof and conclude that the sequenceykas defined before converges tozx₀ⁿzandyk−zO1/k. NowAzAxⁿ₀ Az Az Qcb, showing thatzis a solution ofAxb.

Assume now thatb /∈RA, that is,Ax bis inconsistent. Thenc /∈RQ⁻¹Aandc c^rcⁿwithcⁿ/0.As in the preceding case there exists a uniquez∈RQ⁻¹Asuch that I−Bz c^r. Note that for ally∈NA,By I−Q⁻¹Ay y. Thus for any vectorx and any positive integerj

xj T^jx

B^jxcBc· · ·B^j−1c B^j

x^rxⁿ

IB· · ·B^j−1

I−Bzjcⁿ B^j

x^r

xⁿz−B^j z

jcⁿ B^j

x^r−z

xⁿzjcⁿ, y_k 1

k

xTx· · ·T^k−1x

B_k

x^r−z

xⁿzk−1 2 cⁿ,

28

(9)

whereBk IB· · ·B^k−1. As in the preceding case,B^kx^r−z, k0,1,2, . . .is bounded andB_kx^r−z, k1,2, . . . ,converges to 0. Thus lim_k_{→ ∞}x_k/k cnand lim_k_{→ ∞}y_k/k cⁿ/2, and hence limk→ ∞xklim_{k→ ∞}yk∞. This completes the proof.

Next we consider another kind of iteration in which the nonlinear case was considered in Ishikawa 4. Note that the type of mappings in this case is slightly weaker than nonexpansivitysee conditioncin the next lemma.

Lemma 8. LetBbe ann×nmatrix. The following are equivalent:

afor every 0< μ <1, there exists a matrix norm · _μsuch thatμI 1−μB_μ≤1, bfor every 0< μ <1, there exists an induced matrix norm·μsuch thatμI1−μBμ≤1, cρB≤1 and index1 1 if 1 is an eigenvalue ofB.

Proof. As in the proof ofTheorem 2,aandbare equivalent. For 0 < μ < 1, denoteμI 1−μBbyBμ. Suppose now thataholds. Letλ be an eigenvalue ofB. Thenμ 1− μλ is an eigenvalue of Bμ. By Theorem 2 |μ 1 −μλ| ≤ 1 for every 0 < μ < 1 and hence|λ| ≤1. If 1 is an eigenvalue ofB, then it is also an eigenvalue ofBμ. ByTheorem 2, the index of 1, as an eigenvalue of Bμ, is 1. Since obviously B and Bμ have the same eigenvectors corresponding to the eigenvalue 1, the index of 1, as an eigenvalue ofB, is also 1. This provesc.

Now assumecholds. Since|μ 1−μλ| < 1 for|λ| 1, λ /1, every eigenvalue of Bμ, except possibly for 1, has modulus less than 1. Reasoning as above, if 1 is an eigenvalue ofBμ, then its index is 1. Therefore byTheorem 2,aholds. This completes the proof.

Theorem 9. LetA ∈ M_nandb ∈ Cⁿ. LetQbe an invertible matrix inM_n, andB I−Q⁻¹A.

SupposeρB≤1 and that index1 1 if 1 is an eigenvalue ofB. Let 0< μ <1 be fixed. Starting with an initial vectorx0, definexk, yk, k0,1,2, . . . ,recursively by

y0x0, Qxk Q−A

yk−1 b, y_kμy_k−1

1−μ x_k.

29

IfAxbis consistent, thenyk, k 0,1,2, . . . ,converges to a solution vectorzofAxbwith rate of convergence given by

y_k−zo ζ^k

, 30

whereζis any number satisfying

maxμ 1−μ

λ:λan eigenvalue ofB, λ /1

< ζ <1. 31

(10)

IfAxbis inconsistent, then lim_k_{→ ∞}yk∞; more precisely,

k→ ∞lim y_k

k 1−μ

cⁿ, 32

wherecⁿis the projection ofconNAalong RQ⁻¹A.

Proof. Letc Q⁻¹b, B1 μI 1−μB I−1−μQ⁻¹A, andTx B1x 1−μc. Then y_kT^kx0.

First we assume thatAis invertible. ThenI−B1 1−μQ⁻¹Ais invertible and 1 is not an eigenvalue ofB1; thusρB1<1. Letz 1−μI−B1⁻¹cA⁻¹b. We have

ykT^kx0

B^k₁x0 1−μ

cB1c· · ·B^k−1₁ c B^k₁x0

1−μ 1 1−μ

IB1· · ·B₁^k−1

I−B1z B^k₁x0−z z.

33

By a well known theoremsee, e.g.1,yk−zoζ^kfor everyζ > ρB1.

Assume now thatAis not invertible andb ∈ RA. Thenc is in the range ofQ⁻¹A.

Since B I − Q⁻¹A satisfies the condition in Lemma 8, Q⁻¹A satisfies the condition in Lemma 5. Thus the restriction ofQ⁻¹Aon its range is invertible and there existszinRQ⁻¹A such that Q⁻¹Az c, or equivalently, I −B1z 1−μc. For any vector x x0, we have

ykT^kx B₁^kx

1−μ

cB1c· · ·B^k−1₁ c B₁^k

x^rxⁿ

IB1· · ·B₁^k−1

I−B1z B₁^k

x^r

xⁿz−B^k₁ z B₁^k

x^r−z

xⁿz.

34

SinceB1mapsRQ⁻¹AintoRQ⁻¹AandI−BQ⁻¹Arestricted toRQ⁻¹Ais invertible, we can apply the preceding proof and conclude that the sequenceyk, k0,1,2, . . .converges toz xⁿzandyk−z oζ^k.zsolvesAx bsinceAz Axⁿ Az Az Qcb.

(11)

Assume lastly thatb /∈RA, that is,Ax b is inconsistent. Thenc /∈RQ⁻¹Aand cc^rcⁿwithcⁿ/0. As before there existsz∈RQ⁻¹Asuch thatI−b1z 1−μc^r. Note thatB1p pforp∈NA. Then

ykT^kx B^k₁x

1−μ

cB1c· · ·B^k−1₁ c B^k₁

x^rxⁿ

IB1· · ·B^k−1₁

I−B1zk 1−μ

cⁿ B^k₁

x^r−z

xⁿzk 1−μ

cⁿ.

35

SinceB^k₁x^r−z, k0,1,2, . . . ,converges to 0, we have

k→ ∞lim y_k

k 1−μ

cⁿ, 36

and hence lim_k_{→ ∞}y_k∞. This completes the proof.

By takingQIand considering only nonexpansive matrices in Theorems7and9, we obtain the following corollary.

Corollary 10. LetAbe ann×nmatrix such thatI−A ≤1 for some matrix norm · . Letbbe a vector inCⁿ. Then:

astarting with an initial vectorx0inCⁿdefinexkrecursively as follows:

xk I−Axk−1 b 37

fork1,2, . . . .Let

yk x0x1· · ·xk−1

k 38

fork 1,2, . . . .IfAxbis consistent, thenyk, k 1,2, . . . ,converges to a solution vectorzwith rate of convergence given by

y_k−zO 1

k

. 39

IfAxbis inconsistent, then lim_k_{→ ∞}xklim_{k→ ∞}yk∞.

blet 0< μ <1 be a fixed number. Starting with an initial vectorx0, let y0x0,

x_k I−A y_k−1

b, ykμyk−1

1−μ xk.

40

(12)

yk−zo ζ^k

41

whereζis any number satisfying maxμ

1−μ

< ζ <1. 42

IfAxbis inconsistent, then lim_k_{→ ∞}yk∞.

Remark 11. If in the previous corollary,I−A<1, andμ0 in partb, the sequenceykxk

converges to a solution. This is the Richardson method, see for example,3. Even in this case, our method in partbmay yield a better approximation. For example if

A

1 0.9

−0.9 1

, 43

b 0, and x0 e1, then the nth iterate in the Richardson method is 0.9ⁿ away from the solution 0, while thenth iterate using the method in the corollary partbwithμ1/2 is less than0.5^n/2.

Ann×nmatrixA a_ijis called diagonally dominant if

|a_ii| ≥ ⁿ

j1,j /i

a_ij 44

for alli1, . . . , n. IfAis diagonally dominant withaii/0 for everyiand ifQDorL, where D is the diagonal matrix containing the diagonal ofA, and Lthe lower triangular matrix containing the lower triangular entries of A, then it is easy to prove thatI−Q⁻¹A_∞ ≤ 1 where · ∞ denotes the maximum row sum matrix norm; see, for example,1,3. The following follows from Theorems7and9.

Corollary 12. LetAbe a diagonally dominantn×nmatrix witha_ii/0 for alli1, . . . , n. LetQD orL, whereDis the diagonal matrix containing the diagonal ofA, andLthe lower triangular matrix containing the lower triangular entries ofA. Letbbe a vector inCⁿ. Then:

astarting with an initial vectorx0inCⁿdefinex_krecursively as follows:

Qxk Q−Axk−1 b 45

fork1,2, . . . .Let

yk x0x1· · ·xk−1

k 46

(13)

fork 1,2, . . . .IfAx bis consistent, thenyk, k 1,2, . . .converges to a solution vectorzwith rate of convergence given by

y_k−zO 1

k

. 47

IfAxbis inconsistent, then lim_k_{→ ∞}xklim_{k→ ∞}yk∞.

bLet 0< μ <1 be a fixed number. Starting with an initial vectorx0, let y0x0,

Qx_k Q−A y_k−1

b, y_kμy_k−1

1−μ x_k.

48

y_k−zo ζ^k

, 49

whereζis any number satisfying maxμ

1−μ

< ζ <1. 50 IfAxbis inconsistent, then lim_k_{→ ∞}y_k∞.

References

1 R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985.

2 N. Dunford and J. T. Schwartz, Linear Operators, Part I, Interscience Publishers, New York, NY, USA, 1957.

3 D. Kincaid and W. Cheney, Numerical Analysis, Brooks/Cole, Pacific Grove, Calif, USA, 1991.

4 S. Ishikawa, “Fixed points and iteration of a nonexpansive mapping in a Banach space,” Proceedings of the American Mathematical Society, vol. 59, no. 1, pp. 65–71, 1976.