線性方程組數(shù)值解法

線性方程組Ax

b即求解下面的方程組：自然科學(xué)和工程計(jì)算中,很多問題最終都需要求解一個(gè)線性代數(shù)方程組A

Rmn

,

b

Rn21

1

22

2

2n

n

22a11x1

a12

x2am1x1

am2

x2

amn

xn

bn

a1nxn

b1a x

a

x

a

x

b

3應(yīng)用：生產(chǎn)計(jì)劃安排(1)問題：一制造商生產(chǎn)三種不同的化學(xué)產(chǎn)品A、B、C。每一產(chǎn)品必須經(jīng)過兩部機(jī)器M，N的制作，而生產(chǎn)每一噸不同的產(chǎn)品需要使用兩部機(jī)器不同的時(shí)間：機(jī)器產(chǎn)品A產(chǎn)品B產(chǎn)品CM234N223機(jī)器M每星期最多可使用80小時(shí)，而機(jī)器N每星期最多可使用60小時(shí)。假設(shè)制造商可以賣出每周所制造出來的所有產(chǎn)品。經(jīng)營者不希望使昂貴的機(jī)器有空閑時(shí)間，因此想知道在一周內(nèi)每一產(chǎn)品須制造多少才能使機(jī)器被充分地利用。4應(yīng)用：生產(chǎn)計(jì)劃安排(2)求解：設(shè)x1,x2

,x3分別表示每周內(nèi)制造產(chǎn)品A、B、C的噸數(shù)。為充分利用機(jī)器，有：

2

x1

3

x2

4

x3

80求解可得：若追求最佳利潤：線性規(guī)劃2

x

2

x

2

x

60

1

2

3

x1

10

1

x

20

k

2

, (0

k

10)2

x3

0

2

應(yīng)用：曲線擬合（超定方程組）年196019611962196319641965196619671968人口29.7230.6131.5132.1332.3432.8533.5634.2034.83世界人口 問題:據(jù)統(tǒng)計(jì)，六十年代世界人口數(shù)據(jù)如下:世界人口統(tǒng)計(jì)表(單位：億)根據(jù)表中數(shù)據(jù)，

公元2000年世界人口。分析：數(shù)據(jù)擬合采用下面的擬合函數(shù)y

e

a

b

t5應(yīng)用：壓縮傳感（欠定方程組）6應(yīng)用：壓縮傳感（欠定方程組）7線性方程組（本章：恰定方程組）方程組的矩陣形式為：

x1

b1

2122a1n

a11

a12

x

2

n

b

2

n

a2n

n1

n

2nn

A

a

a

ax

x

b

b

a

aAx

=

b增廣矩陣為：（A

|

b）方程組有解的充要條件是系數(shù)矩陣與其增廣矩陣有相等的秩。低階稠密矩陣大型稀疏矩陣8線性方程組解法線性方程組的數(shù)值解法可以分為直接法和迭代法兩類。－直接法：用有限步計(jì)算得到準(zhǔn)確解－迭代法：給出一個(gè)近似解序列，逐步

近直接法Gauss消去法Gauss主元消去法矩陣直接分解法Jacobi迭代法迭代法Gauss-Seidel迭代法9Gauss消去法－基本思想x1

x2

x3

62

3(1)(2)(3)4x

x

52x1

2x2

x3

14x2

x3

11(4)x1

x2

x3

64x2

x3

53

2x

6

與原方程組等價(jià)的三角形方程組x3

32x

2x1

110Gauss消去法－基本思想5

r2r3r300

01A

|

b

01

1

|

4

1

|2

2

1

|6

15

(2)r1

3r3r

05

11

1

| 6

4

1

|

0

4

1

|

111

1

1

| 6

4

1

|

2

|

611Gauss

消去法

a21

x1

a22

x2an1x1

an2

x2...

a2nxn

b2

...

annxn

bn考慮n

階線性方程組：

a11x1

a12

x2

...

a1nxn

b1Ax

b矩陣形式消去法的主要思路：將系數(shù)矩陣A

化為上三角矩陣，然后回代求解=12Gauss消去法第一步（第一次消元）

11211122

21222|||1n22nn

2a1ba2a2ab

a1b

0

02

nn

n

A

|

b

|2aa

a2

a1

m

a1ij

ij i1

1

jb2

b1

m

b1i

i i1

1i,j

2,3,,

n13Gauss消去法第k

步（第k

次消元）

1

11112221n

|

12n

2kkkkk

k

nka1ba2ak

ak

b

a1ak

|

bk

nn

n

A

|

b

a

a2

|

b2

|

kn||k

aak

1

ak

m

ak

ij

ij

ik

kjbk

1

bk

m

bk

i

i ik

ki,

j

k

1,,

n14Gauss消去法繼續(xù)這一過程直到完成

n-1

次消元

111121221nnna1xa2b

a1

b1

1

x2

b2

xa

n

nn

n

aa2

2n

2—消元過程—回代過程k

n

1,

n

2,,1n

bn

ann

nnk

nk

k

kxkjakk

ba

xj

xk要求:A非奇異求解此三角形方程組的公式為：j

k

115Gauss消去法的工作量第一步（第一次消元）

1

1111222

22

2||1n

1n

2a1ba2a2ab

a1

0

02nn

n

A

|

b

2n

2

|

aa2

|

b2

a2

a1

m

a1ij

ij i1

1

jb2

b1

m

b1i

i i1

1i,j

2,3,,

nn

1

次除法n

12

次乘法n

12

次減法n

1

次乘法n

1

次減法16幾點(diǎn)注記主元：aGauss

消去法能進(jìn)行到底的條件：主元全不為0定理：(i)iia

0

（i=1,2,...,n）的充要條件是A

的順序主子式不為零，即D1

a11

0,

Di

a11

a1i

0,

i

1,

2,,

nai1

aiii1推論：a(1)

D

,11

1a(i

)

DiiD

,

i

2,,

ni17Gauss消去法的工作量第k

步（第k

次消元）n

k

2

次乘法n

k

2

次減法n

k

次乘法n

k

次減法n

k

次除法ak

1

ak

m

a

k

ij

ij

ik

kjbk

1

bk

m

bk

i

i ik

ki,

j

k

1,,

n18Gauss消去法的工作量—消元過程n1—乘法：n

k

2

n

n

12n

1

6k

1n1—減法：n

k

2

n

n

12n

1

6k

1—乘法：n

k

n

n

1

2k

1n1—減法：n

k

n

n

1

2k

1n1n1—除法：n

k

n

n

1

2k

1MD

n

n

12n

5

6;AS

n

n2

1

319Gauss消去法的工作量—回代過程

k

n

1,

n

2,,1n

bn

an

n

nnnkkxkjkka

xak

j

j

k

1

bkxk1次除法n

k

次乘法；n

k

次加減法；1次除法n120n1MD

1

n

k

1

n

n

1

2k

1AS

n

k

n

n

1

2k

1Gauss消去法的工作量1

3—消元過程MD

n

n

12n

5

6;AS

n

n2—回代過程MD

n

n

1

2;AS

n

n

1

2MD

n3

3

n2

n

3

n3

3AS

n

n

12n

5

6

n3

321LU

分解換個(gè)角度看Gauss

消去法矩陣的三角分解過程矩陣分解，即將一個(gè)較復(fù)雜的矩陣分解成若干結(jié)構(gòu)簡單的矩陣的乘積，是矩陣計(jì)算中的一個(gè)很重要的技術(shù)2223LU

分解則A(k)與A(k+1)

之間的關(guān)系式可以表示為：kA(k

1)

L

A(k

)其中：n,k1mk1,k1k1mL

1m

a(k)

a(k

)ik

ik

kk(i

=k

+

1,

…,

n

)將Gauss

消去過程中第

k-1

步消元后的系數(shù)矩陣記為：11A(k

)

nka(k

)a(k

)a(k

)a(1)

a(1)a(1)

1n

nn

1k

a(k

)

kk

kn

(

k

=

1,

…,

n-1)1

2

nA

LUU

A(n)，則LU

分解其中：L

---單位下三角矩陣，U

---非奇異上三角矩陣n1

2

1于是有：A(n)

L

L

L

A(1)2

1n1A

A(1)

(L

L

L

)1

A(n)n,k241mk

1,km11k容易驗(yàn)證：

1L1

記：L

L1L1

L1,

(

k

=

1,…,

n-1)LU分解存在唯一性LU

分解存在kka(k

)

0消去法不被中斷定理：A存在唯一的LU分解的充要條件是A

的所有順序主子式都不為零。（證：板書）所有順序主子式不為零25列主元Gauss

消去法例：解線性方程組0 1

x1

11

10x2

為什么要選主元？Gauss

消去法有效的條件是

主元全不為零！26列主元Gauss

消去法①先選取列主元：27|

=(k)ikk|

a

(k

)ikmax

|

akin|

0②if

ik

k

then

交換第k

行和第ik行③消元列主元Gauss

消去法在第k

步消元時(shí)，在第k

列的剩余部分選取主元28列主元Gauss

消去法算法(列主元Gauss消去法)for

k=1

to

n-1

(k)ikk(k

)ikkin|

a

| =

max

|

a|

0if

a(k)

=0then

stopikkif

ik

k

then

swap

k-th

and

ik