計算方法第3章解線性方程組迭代法

3.5.1矩陣的譜半徑第三章解線性方程組的迭代法§3.5迭代法的收斂條件3.5.2迭代法的收斂條件3.5.3誤差估計復習：1、矩陣的特征值與特征向量的定義與計算；設A為方陣，Au

=

λu

(u

≠

0)即λ是方程|λI

-A|=0的根2、矩陣的特征值的性質det(

A)

=

l1l2

...ln3、Ak

=AA…A的特征值是lk

,lk

,...,lk1

2

n3.5.1

迭代法的譜半徑x(

k

+1)

=

Bx

(

k

)

+

g稱迭代公式定義：中的矩陣B

為迭代矩陣.定義3.3：設A為n階方陣，λi(i=1,…,n)為A的特征值，稱特征值模的最大值為矩陣A的譜半徑，記為r(

A)

=

max{|

li

|}1￡i￡n{l1

,

l2

,...,

ln

}稱為矩陣A的譜.性質：若矩陣A的譜為{l1

,l2

,...,ln

}譜半徑為1￡i￡nr(

A)

=

max{|

li

|}則Ak

=AA…Ak個的譜為{lk

,

lk

,...,

lk

}1

2

n(k

=

1,2,

…)譜半徑為ir(

Ak

)

=

max{|

lk

|}

=[r(

A)]k1￡i￡n定理3.3：設A為任意n階方陣，||.||為任意由向量范數(shù)誘導出的矩陣的范數(shù)，則r(

A)

￡||

A

||證明：對A的任一特征值λi

及相應的特征向量ui，都有|

li

| ||

ui

||=

||

li

ui

||=||

Aui

||

￡||

A

|| ||

ui

||因為ui為非零向量，即||ui||≠0，于是有|

li

|￡||

A

||由λi

的任意性得r(

A)

￡||

A

||定理3.4：設A為n階方陣，則對任意正數(shù)ε，存在一種矩陣范數(shù)||.||，使得||

A

||￡

r(

A)

+

e注：對n階方陣，一般不存在矩陣范數(shù)||.||，使得r(

A)

=||

A

||但若A為對稱矩陣，則有r(

A)

=||

A

||2下面的定理對建立迭代法的收斂條件十分重要.定理3.5：設A為n階方陣，則lim

Ak

=

0kfi

￥的充要條件為證明：必要性。若kfi

￥r(

A)

<

1lim

Ak

=

0lim

||

Ak

||=

0則而k

fi

￥0

￡

r(

Ak

)

=

[r(

A)]k

￡||

Ak

||于是由極限存在準則，有l(wèi)im[r(

A)]k

=

0kfi

￥r(

A)

￡

Ar(

AK

)

￡

AK故r(A)<1r(

A)

<

1,充分性。若

取2e

=

1

-

r(

A)

>

0則存在一種矩陣范數(shù)||.||，使得2||

A

||￡

r(

A)

+

e

=

1

+

r(

A)

<

1而||

Ak

||￡||

A

||k于是lim

||

Ak

||￡

lim

||

A

||k

=

0k

fi

￥

k

fi

￥所以lim

Ak

=

0kfi

￥3.5.2

迭代法的收斂條件定理3.6：對任意初始向量x(0)和右端項g，由迭代格式x(k+1)

=Mx(k)

+g產(chǎn)生的向量序列收斂的充要條件為r(

M

)

<

1必要性證明：設存在n維向量x*，使得kfi

￥lim

x(

k

)

=

x*則x*

滿足x*

=

Mx*

+

g于是有k

fi

￥

k

fi

￥由迭代公式有x(

k

)

-

x*

=

Mx(

k

-1)

+

g

-

Mx*

-

g=

M

(

x(

k

-1)

-

x*)

=

M

2

(

x(

k

-2)

-

x*)=

M

k

(

x(0)

-

x*)lim(x(

k

)

-

x*)

=

lim

M

k

(x(0)

-

x*)

=

0因為x(0)為任意向量，因此上式成立必須lim

M

k

=

0kfi

￥即r(M

)

<1充分性。若r(M

)

<

1,則λ=1不是M的特征值，所以|I－Ｍ|≠0于是對任意n維向量g，方程組(I－M)x=g有唯一解，記為x*，即x*

=

Mx*

+

g并且lim

M

k

=

0kfi

￥又因為x(

k

)

-

x*

=

M

(

x(

k

-1)

-

x*)

=

M

k

(

x(0)

-

x*)故對任意初始向量x(0)，都有l(wèi)im(

x(

k

)

-

x*)

=

lim

M

k

(

x(0)

-

x*)

=

0kfi

￥

kfi

￥即由迭代公式產(chǎn)生的向量序列{x(k)}收斂。推論1：若迭代矩陣滿足||M||<1，則迭代公式產(chǎn)生的向量序列{x(k)}收斂。推論2：松弛法收斂的必要條件是0<ω<2因為證明:

設松弛法的迭代矩陣M有特征值l1

,

l2

,...,

ln|

det(

M

)

|=|

l1l2

...ln

|￡

[r(

M

)]n由定理，松弛法收斂必有|

det(

M

)

|<

1又因為|

det(

M

)

|=|

(

D

-

w

L)-1

|

|

(1

-

w

)D

+

w

U

|而1a11a22

...ann|

(

D

-

w

L)-1

|=|

(1

-

w

)D

+

w

U

|=

(1

-

w

)n

a11a22

...ann于是有|

det(

M

)

|=|

(1

-

w

)n

|<

1所以0

<

w

<

2注：定理表明，迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量及方程組的右端項無關。對同一方程組，由于不同的迭代法迭代矩陣不同，因此可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。1

2

3

x

+

x

+

x

=

2舉例：解方程組

x1

+

2

x2

-

2

x3

=

12

x1

+

2

x2

+

x3

=

3討論Jacobi法與Gauss-Seidel法的收斂性。解：由定理，迭代法是否收斂等價于迭代矩陣的譜半徑是否＜１，故應先求迭代矩陣。而1

1

2

-

2A

=

1

1

2

2

1

故A分解后的各矩陣分別為1

1

2

-

2A

=

1

1

2

2

1

11D

=

10

0

0

0L

=

-

1

0

-

2

-

2

00

-

2 2

U

=

0

0

-

1

0

0 0

Jacobi迭代法的迭代矩陣為其特征方程為=

l3

=

0

0

-

2 2

B

=

I

-

D-1

A

=

-

1

0

-

1

-

2

-

2 0

l

2

-

2l

12

2

l|

lI

-

B

|=

1因此有r(B)=0

<1,故Jacobi法收斂如果用Gauss-Seidel迭代，由01

0

0D

-

L

=

1

1

2

2

1可得0于是迭代矩陣為

1

0

0

(

D

-

L)-1

=

-

1

1

0

-

2

10

-

2

2

2

-

30

0

2

M

=

(

D

-

L)-1U

=

0其特征方程為|

lI

-

M

|=

0=

l(l

-

2)2

=

0l

2

-2l

-

2

30

0

l

-

2故r(B)

=

2

>

1,所以Gauss-Seidel迭代法發(fā)散。判斷迭代法收斂的方法||M||<1迭代法收斂松弛法收斂0<ω<2r(

M

)

<

1迭代法收斂下面對一些特殊的系數(shù)矩陣給出幾個常用的判斷收斂的條件。定義3.4：若n階方陣A=(aij)滿足n(i

=1,2,...,

n)|

aii

|?

|

aij

|j

=1j

?i且至少有一個i值，使上式中大于號成立，則稱A為弱對角占優(yōu)陣。若對所有i，上式均為大于號，則稱A為嚴格對角占優(yōu)陣。例如：矩陣10

-

1

-

2A

=

-

1是嚴格對角占優(yōu)陣

10

-

2-

1

-

1

5

2

-

1 0

2

-

1

0

-

1 2

矩陣B

=-1不是嚴格對角占優(yōu)陣，是弱對角占優(yōu)陣定義3.5：如果矩陣A不能通過行的互換和相應列的互換成為形式

22

0

A

A11

A12

其中A11，A22為方陣，則稱A為不可約.例如：判斷下列矩陣是否可約？矩陣A

=10

是可約的。是不可約的。1

1

2

-

2矩陣

A

=

1

1

2

2

1

1

1

0

1

101

1

0

2

1

0

1

0

1

2交換第1與3行(列)設有線性方程組Ax=b，下列結論成立：

若A為嚴格對角占優(yōu)陣或不可約弱對角占優(yōu)陣，則Jacobi迭代法和Gauss-Seidel迭代法均收斂。若A為嚴格對角占優(yōu)陣，0<ω≤1，則松弛法 收斂。若A為對稱正定陣，0<ω<2，則松弛法收斂. 即：若A是對稱正定陣，則松弛法收斂的 充要條件為0<ω<2。歸納判斷迭代法收斂的方法如下：首先根據(jù)方程組的系數(shù)矩陣A的特點判斷；可根據(jù)迭代矩陣的范數(shù)判斷；只好根據(jù)迭代矩陣的譜半徑判斷；舉例例1：設有方程組Ax=b，其中1122

11

21

1

2

2A

=

1

112討論用三種迭代法求解的收斂性。解：首先Ａ不是對角占優(yōu)陣，但Ａ是對稱陣，且其各階順序主子式均大于０，故Ａ為對稱正定陣，由判別條件３可得Gauss-Seidel法與松弛法(0<ω<2)均收斂。由因為Jacobi迭代法的迭代矩陣為-0

0221121

-

12220

--

1

-

1

B

=

-故||B||1=||B||∞=1，因

此不能用范數(shù)判斷。下面計算迭代矩陣的譜半徑。解特征方程2=

(l

-

1

)2

(l

+

1)

=

01212l12l12l1212|

lI

-

B

|=可得譜半徑r(B)

=

1故Jacobi迭代法不收斂。值得注意的是：改變方程組中方程的順序，即將系數(shù)矩陣作行交換，會改變迭代法的

收斂性。9-

10-

4

例2：設方程組Ax=b的系數(shù)矩陣為A

=3則Jacobi法與Gauss-Seidel法的迭代矩陣分別是-

9

/

4

00

-

10

/

3B

=

010

/

315

/

2M

=

0其譜半徑分別為2230

,r(

M

)

=

15r(B)

=故這兩種迭代法均不收斂。但若交換兩個方程的次序，得原方程組的同解方程組3-

4

-

10A￠x

=b￠,

其中A￠=9顯然Aˊ是嚴格對角占優(yōu)陣，因此對方程組Ax

=

b用Jacobi法和Gauss-Seidel法均收斂。例3：設線性方程組Ax=b的系數(shù)矩陣為2

a

1

3A

=

1

a

-

3

2

a試求能使Jacobi方法收斂的a的取值范圍解：當a

≠0時，Jacobi法的迭代矩陣為0

-

1

/

a

-

3

/

a

0

-

2

/

a

3

/

a

-

2

/

a

0B

=

-

1

/

a解特征方程2

/

a

=

0l

1

/

a

3

/

a

l

-

3

/

a

2

/

a

l

|

lI

-

B

|=

1

/

a得2,31|

a

|l

=

0

,

l

=

–

4故|

a

|r(B)

=

4由r(B)<1得|

a

|>

4故當|

a

|>4

時，Jacobi迭代法收斂。定理3.7

設有迭代格式x(k+1)=Mx(k)+g若||M||<1，{x(k)}收斂于x*，則有誤差估計式3.5.3

誤差分析(

k

)||

M

||k||

x

-

x*

||￡

||

x(1)

-

x*

||1-

||

M

||證明：因為r(M)≤||M||<1故||I-M||?0，于是(I-M)-1存在，方程組x=Mx+g有唯一解x*，且

x*=(I-M)-1g從而有x(k)-

x*=M(x(k-1)-

x*)=

M

k(x(0)

-x*)=

M

k[x(0)-(I-M)-1g]=

M

k(I-M)-1

[(I-M)x(0)-g]=