大學計算方法（C）講義課件

大學計算方法（C）講義課件

目錄

第1章緒論

1.1數(shù)值計算

1.2數(shù)值方法的分析

1.2.1計算機上數(shù)的運算

1.2.2算法分析

第2章線性代數(shù)方程組

2.1Gauss消去法

2.1.1消去法

2.1.2主元消去法

2.2矩陣分解

2.2.1Gauss消去法的矩陣意義

2.2.2矩陣的LU分解及其應用

2.2.3其他類型矩陣的分解

2.2.4解三對角矩陣的追趕法

2.3線性方程組解的可靠性

2.3.1向量和矩陣范數(shù)

2.3.2殘向量與誤差的代數(shù)表征

2.4解線性方程組解的迭代法

2.4.1基本迭代法

2.4.2迭代法的矩陣表示

2.4.3收斂性

第3章數(shù)據(jù)近似

3.1多項式插值

3.1.1插值多項式

3.1.2Lagrange插值多項式

3.1.3Newton插值多項式

3.1.4帶導數(shù)條件的插值多項式

3.1.5插值公式的余項

3.2最小二乘近似

3.2.1最小二乘問題的法方程

3.2.2正交化算法

第4章數(shù)值微積分

4.1內插求積，Newton-Cotes公式

4.1.1Newton-Cotes公式

4.1.2復化求積公式

4.1.3步長的選取

4.1.4Romberg方法

4.1.5待定系數(shù)法

4.2數(shù)值微分

4.2.1插值公式方法

4.2.2Taylor公式方法（待定系數(shù)法）

4.2.3外推法

第5章非線性方程求解

5.1解一元方程的迭代法

5.1.1簡單迭代法

5.1.2Newton法

5.1.3害峨法

5.1.4區(qū)間方法

5.2收斂性問題

5.2.1簡單迭代一一不動點

5.2.2收斂性的改善

5.2.3Newton法的收斂性

5.2.4收斂速度

第1章緒論

1.1數(shù)值計算

現(xiàn)代科學的發(fā)展，己導致科學與技術的研究從定性前進到定量，尤其是現(xiàn)代

數(shù)字計算機的出現(xiàn)及迅速發(fā)展，為復雜數(shù)學問題的定量研究與解決，提供了強有

力的基礎。

通常我們面對的理論與技術問題，絕大多數(shù)都可以從其物理模型中抽象出數(shù)

學模型，因此，求解這些數(shù)學模型已成為我們面臨的重要任務。

一、本課程的任務：

尋求解決各種數(shù)學問題的數(shù)值方法一一如何將高等數(shù)學的問題回歸到初等

數(shù)學（算術）的方法求解一一了解計算的基礎方法，基本結構（否則只須知道數(shù)

值軟件）一一并研究其性質。

立足點：

面向數(shù)學一一解決數(shù)學問題

面向計算機一一利用計算機作為工具

充分發(fā)揮計算機的功能，設計算法，解決數(shù)學問題

例如：迭代法、并行算法

二、問題的類型

1、離散問題：例如，求解線性方程組Ax=b一一從離散數(shù)據(jù)：矩陣A和

向量b,求解離散數(shù)據(jù)x；

2、連續(xù)問題的離散化處理：例如，數(shù)值積分、數(shù)值微分、微分方程數(shù)值解;

3、離散問題的連續(xù)化處理：例如，數(shù)據(jù)近似，統(tǒng)計分析計算；

1.2數(shù)值方法的分析

在本章中我們不具體討論算法，首先討論算法分析的基礎一一誤差。

一般來講，誤差主要有兩類、三種（對科學計算）：

1）公式誤差一一“截斷誤差”，數(shù)學一計算，算法形成一一主觀（人為）：

數(shù)學問題-數(shù)值方法的轉換，用離散公式近似連續(xù)的數(shù)學函數(shù)進行計算時，一般

都會發(fā)生誤差，通常稱之為“截斷誤差”；一一以后討論

2）舍入誤差及輸出入誤差一一計算機，算法執(zhí)行一一客觀（機器）：由于計

算機的存儲器、運算器的字長有限，在運算和存儲中必然會發(fā)生最末若干位數(shù)字

的舍入，形成舍入誤差；在人機數(shù)據(jù)交換過程中，十進制數(shù)和二進制數(shù)的轉換也

會導致誤差發(fā)生，這就是輸入誤差。這兩種誤差主要是由于計算機的字長有限，

采用浮點數(shù)系所致。

首先介紹浮點數(shù)系

1.2.1計算機上的運算一一浮點運算

面向計算機設計的算法，則先要討論在計算機上數(shù)的表示?？茖W記數(shù)法一一

浮點數(shù)：約定尾數(shù)中小數(shù)點之前的數(shù)全為零，小數(shù)點后第一個數(shù)不能為零。

目前，一般計算機都采用浮點數(shù)系，一個存儲單元分成首數(shù)和尾數(shù)：

XX—±XXXXX

首數(shù)/尾數(shù)"位)

其中首數(shù)存放數(shù)的指數(shù)(或“階”)部分，尾數(shù)存放有效數(shù)字。對于進制，尾

數(shù)字長為t位的浮點數(shù)系尸(/7,/,L,U)中的(浮點)數(shù)，可以用以下形式表示：

4%dj\<d.</3

—

fl(x)=±(1+?,,—)xB門」］,Q?/-)Q

八B02pt//=2,3,…"T

此處，指數(shù)/(稱為階)限制在LW/WU范圍內。

以下記實數(shù)系中的實數(shù)為XGR,它在浮點數(shù)系F^,t,L,U)中對應的浮點數(shù)

記為0(x)eF(0,t,L,U)——萬進制，r尾數(shù)位數(shù)，階的范圍。

幾乎所有近代計算機都采用“二進制"(即用=2)：位、字節(jié)和字分別是指

位數(shù)不同的二進制數(shù)。例如

十進制轉換二進制

11=2°00000001

22=2'00000010

44=2200000100

88=2300001000

99=23+2°00001001

1010=23+2'00001010

2727=16+8+2+1=24+23+2'+2°00011011

1季節(jié)

位是一個二進制數(shù)(即0或1);字節(jié)是8個二進制數(shù)字；上表的最后一列

是字節(jié)。

單精度浮點數(shù)(singleprecision)按32位存儲，雙精度浮點數(shù)｛double

precision)按64位存儲。精度用于指明每個浮點數(shù)保留多少位以及尾數(shù)和階數(shù)

各分配多少位。單精度浮點數(shù)的尾數(shù)為23位、階數(shù)為8位；雙精度浮點數(shù)的尾

數(shù)為53位（包含符號位）、階數(shù)為11位（包含符號位）。雙精度浮點數(shù)的等價二

進制數(shù)如下所示：

64位

'幼蛆…幼~>ddd…gd嬴,

1指數(shù)，含符1位）符,位'—52位瓶數(shù)

浮點數(shù)的特點：

1、實數(shù)轉換到浮點數(shù)——浮點化，〈缺點：〉總會產生誤差（除極個別的情

況：尤=2’，/=0,±1,±2,…）

按四舍五入，絕對誤差：|x-力（x）|wg，-'（舉例），

〈優(yōu)點：〉浮點化產生的相對誤差有界（與數(shù)字本身的數(shù)量級無關）

|心）卜匕等<17?-

注：設實數(shù)xeR,則按夕進制可表達為:

d、dd]i\<d[</3

X=±(—++…+,+Z+,+…)X"

邛//X+10<d.</，j=2,3,…U+1…

按四舍五入的原則，當它進入浮點數(shù)系尸（尸",心。）時，若d,+i<gs，則

力(x)=±(-+-|■+…d......-)Xj

P片

1ddd+\

若4+12彳夕，則力(x)=±(T+T+…+'丁)x〃

2pp2-y

對第一種情況:

k一力⑸=（熱+…）x〃號分/=#

對第二種情況：

卜一）（何=一…X，=；夕一

pP乙乙

就是說總有：|x-77（x）|wgp~

有,喝夕

另一方面，由浮點數(shù)要求的14&<，，,將此兩者相除，便得

x一力（x）4IgiT

xT

2、每一個浮點數(shù)系的數(shù)字有限：2（，一1）夕T（U-￡+1）+1

3、浮點數(shù)系中的運算非自封閉，（因為數(shù)字有限、尾數(shù)字長有限、指數(shù)數(shù)字

有限等）

3

例：在「（10,4,-5,5）中，*=.5420x10。=2Q01x10,運算x*y和x/y,

的結果顯然已不在此浮點數(shù)系內，而x+y或x-y也不在此浮點數(shù)系內，需

fl（xoy）結果才在此浮點數(shù)系內。

浮點運算應注意：

1）避免產生大結果的運算，尤其是避免小數(shù)作為除數(shù)參加運算；

2）避免“大”“小”數(shù)相加減；

3）避免相近數(shù)相減，防止大量有效數(shù)字損失；

4）盡可能簡化運算步驟，減少運算次數(shù)。

原因：

記△=max|b（x）|=max,由上一力（刈4可乂，可得：

|（Xoy）--/7（xoy）|<A|xoy|（“。”表示任意一種四則運算）

此處△是由機器字長（實質上是尾數(shù)字長f的大?。┐_定的常數(shù)（它反映

了實際運算的精度）。

顯然，若要求運算的舍入誤差小，應使運算結果（如：X土較小。

尤其是小分母運算："-土=白，小y=大誤差。

yyy

其次，當浮點數(shù)系中兩個數(shù)量級相差較大的數(shù)相加（或減），注意到由于浮

點數(shù)系中數(shù)字字長的有限性，可能導致“大數(shù)吃小數(shù)”。例如，尸（10,4,-5,5）中

x=.8231xl03,y=.2317xl（）-',則

x±y=.8231xl03±.2317xl0-1=.8231x103±.0000x103=x

似乎y（沒有參加運算。

第三，同樣，由于浮點數(shù)系中數(shù)字字長的有限性，當兩個相近數(shù)相減時：例

如，在"10,8,-5,5）中，x=.82317844x1（）382317832x1（）3,兩數(shù)相減：

=.12000000x10-3,計算結果僅剩2位有效數(shù)字，而原來參加運算的數(shù)字有8

位有效數(shù)字，這將嚴重影響最終計算結果的精度。

1.2.2算法分析

作為一個可用的算法，必須考慮其效率和可靠性，

定義：計算機完成一個乘法和一個加法，稱為一個浮點運算（記為flop）；

注：由于計算機在運算時，加（減）法所耗時間遠少于乘（除）法，所以

通常只須計算乘法的次數(shù)，因此也有“一個算法需要多少個‘乘法'”這一提法。

1、計算效率——可計算性（計算復雜性——空間、時間）

例：解線性方程組Ax=b的Grammar方法：%,.」人八，「其中|A|是方程

組系數(shù)矩陣A對應的行列式，而|4|則是以右端向量b替代A的第i列所得矩陣

對應的行列式。由線性代數(shù)知識可知，若A=（ap,則

IA|=＞一1嚴""四,既…血,，

其中心",…,露是由｛1,2,…川變換到｛Z,,Z2，…。｝所需的置換次數(shù)?？梢娒?/p>

計算一個行列式，需要（〃一1）.〃!個浮點運算；因此，按Grammar方法解方程組

約需個浮點運算。當〃=20時N*9.70728x1（）2。，用一個運算

速度為1（）8/秒的計算機進行求解，約需3.078x105年（日前報道我國計算機己達

到3840x103秒，這仍需近10年）。而n=20的方程組應該說是一個小型的方程

組。因此Grammar方法是一個不能接受的算法，它缺乏可計算性。第二章將介

紹的Gauss消去法和迭代法就有較高的效率，具有很好的可計算性。

2、計算可靠性

作為算法，除了考慮其效率外，必須重視可靠性，它包括兩方面：

問題的性態(tài)和方法的穩(wěn)定性

?問題的性態(tài)

所計算的問題當原始數(shù)據(jù)發(fā)生小擾動時，問題的解一般也發(fā)生擾動。問題的

性態(tài)——問題的解對原始數(shù)據(jù)發(fā)生變化的敏感性.

'小擾動——問題是良態(tài)的

原始數(shù)據(jù)小擾動n問題解

大變化——問題是病態(tài)的

例：線性方程組:

11U

為-%+-

236

11+11

-匹-+-

1一3

234.

1玉+11.12

--+-.47一

345

60

若將方程組的系數(shù)改寫成具有2位有效數(shù)字的小數(shù):

1.00X1+0.50x2+O.33x=1.8(-6.22}

的解則變成：X=

<0.50xj+0.33X2+0.25巧=1138.25

33.65,

0.33西+0.25X2+0.20X3=0.78

這是一個典型的病態(tài)方程組。

一般：由原始數(shù)據(jù)Xn計算結果/（X）,

擾動后的數(shù)據(jù)xn計算結果/（工）,

若對問題/存在常數(shù)m,滿足關系式：

/（X）-/G）<mx-H

/（X）~mX

f(x)-f(x)

f(x)

或m=sup-------—

x-x

x

則稱（相對誤差之比的上界）m為該問題的條件數(shù)，記作m=cond（f）；

由微積分中值定理知識容易計算出，當》”亍時，cond（f）x。

稍后我們在第二章將對線性方程組的性態(tài)作進一步的分析。

?算法的數(shù)值穩(wěn)定性：

1

例：計算/”=JxZZx,〃=0,1，…,8；

0

解：由微積分知識，可得計算公式，①/“=1-叫I,②/“T=_L（1—/“）,

n

我們將準確值與計算結果列表如下：

方法/()/八17

2，516A

準確值.6321.3679.2642.2073.1709.1455.1268.1124.1010

①.6321.3679.2642.2074.1704.1480.1120.2160-.7280

②.6320.3680.2643.2073.1709.1455.1268.1124.1010

由上表可見，方法①中，原始步的誤差，隨著計算步數(shù)的增加被嚴重地放大,

特別是A竟變成負數(shù)（注意：被積函數(shù)是非負函數(shù)），而方法②則相反；這是因

為方法①中，若前步有誤差6：I-=/j+§，則

=

1k=1-kl卜-11-kl1I—k3=I卜-kb,

說明的誤差3,經一步計算后被擴大了左倍，隨著女的增大，誤差將被大大

地擴大；而通過同樣的分析可知：方法②中人的誤差則被縮小2倍。

算法的數(shù)值穩(wěn)定性：算法對初始誤差導致的最終誤差的可控性,如果最終

誤差被有效地控制，則稱算法是穩(wěn)定的，否則就是不穩(wěn)定的。

第二章線性方程組求解

線性方程組：

allxl+%2而+…自

小5=卜內+。22心+…+。2”巧=不

(2.1)

an\X\+a?2x2+?-?+annxn=pn

其中

??劭「

a\\a\2?力

a2\a22,

A=9X=,b=A

一%2.,,a*Pn

2.1Gauss消去法

2.1.1消去法

設計方法原則：面向計算機(事先未知元素，編制程序)，例:

2x}+x2=3

2xl+々=3

3_3=x2=1=X]=1

Xj-x2=0一5"一一5

基本思想：降維一一N維問題轉化為N-1維問題一一逐次降維，依次進行

消去過程一一對方程組(2.1)由上而下逐步消去對角元%*(%=1,2,…，〃-1)

以下的aik(i=k+l,-,n),使之轉化為如下等價形式，達到目標：

岡內+%2々+…=川

+…+%/“=四

,(2.2)

????????????

%/“=/3?

從而，可進入回代過程，再由下而上，逐步解得4=…,2,1)：

這兒的akk(k=1,2,-??,/?-1)------主元

對問題(2.1)設a”？0,目標：將第2?n方程的可的系數(shù)a?”…,見“轉化

為0；方法：“第左個方程”-3x“第1個方程”(女=2,3,…㈤,得到

?n

anX]+al2x2+---+ainxn=.

嫂巧+…+a如”=姨

<

???????????????

姍電+???+%*%"=￡『

現(xiàn)在只須關心由第2?n方程形成的n-1維方程組，以后可仿此進行。

消去：第左步（氏=1,2,…，〃-1）：設名女。0,以第%行為基準，消去以下各

/y

行中4歹以下的％。=左+1,…,〃），令4=*，施行：第攵行一&X第i行

%

=>新的第女行，元素變化：（akk=0）,a..=a..-likakj,與=/3i-lik/3k,經過〃-1

步消去（注意：a““以下無元可消），得到（2.2）式?！醋⒁猓好坑嬎?個兒,%）?,分

僅需1個浮點運算〉

回代：第一步演=&，

第二步九』"一％"弘，…，

/Un-\,n-\

第〃-Z+1步4J乩一（叼+“+…+4"無"%女=〃—1,…，2,1;

運算量：

消元：n元方程組：第1步消元：對第ia=2,3,…,〃）行，共n-1行；

每1行：計算。（i=2,3,…,〃），1個乘除法（或“浮點運算”），

計算新的曙=…邱）=4?-4歷共（n-D+l個

乘除法（或“浮點運算”），

第1次元共（〃-1）口+（〃-1）+1]=〃2一1個乘除法，因此，消元的運算量

Z（心1）=Z（1T）=2>一吟+〉》；

k=nk=\k=\326

回代：第1步，求X”需要1個乘除法（或“浮點運算”），即：第2步求

用2個乘除法（或“浮點運算”），一般，第上步求乙_八1用改個浮點運算，因此,

回代的運算量力=々〃+1）；

I23

Gm/ss消去法的總運算量：T=-+n2--。

33

例2-1：解線性方程組

+無

X]+2X23=0

2%|+212+3巧=3

-%i-3X22

解:利用增廣矩陣（因為線性方程組的解僅與系數(shù)與右端常數(shù)項相關）

210、210、210C、

2233-213-213nX=-1

-302八一-1I左=%

2>%XJ\7

'2-112、(%]

例:-65-33;解1=%

、4054,-3

\7

-2I032、'1、C-21032、1

-441-102121-7-4

;解1=

252-22-13-131-121

-2I2457,10-21人55,

20134、(\（2013

431725213-11

2-364-91-1I42

66518607、3211人5

'12342'1234

1491610I12612

18276444131624

1681256190J7624

(\23430、1234

23454021-1-2-3

344543321-1-1

、455757,431

2-207\1、I2-2071

-1-341-10-11-1212

0-277-402135

、12-11-14210-31人11

2.1.2（列）主元消去法

算法中，若第左步：i）akk=0

或ii)\akk\?|aA|i=k+\,---,n

則按照原來的簡單Gm/ss消去法算法可能無法執(zhí)行，也可能出現(xiàn)大誤差:

例：在浮點數(shù)系廠(10,5,-10,10)中計算；方程組

10-520.250001875

準確解：x

0.499998749

解：按Gauss消去法解：

’.10000*107.20000*10'.10000*101八尸02。0011d、

.20000*10'.30000*10'.20000*lO'J'

10000*10-4.20000*10'.10000*10,)

、-.40000*106-.20000*106J

x=(.00000*10°.50000*10°)r

誤差大，原因：若有誤差akj=>akj+3,J3k=>/3k+3則

西=A=A-LA，則演變?yōu)?/p>

2=%-4(%+m=瑪+lik3,A=以一4(乩+磔=自+/*；

這說明前步各元素的誤差均被放大4倍。克服方法，將按絕對值最大的元素交換

到主元位置，使心|41,使前步的誤差不再被放大。

「10000*1()720000*10'.10000*10'^"3日

1k.20000*10'.30000*10'.20000*lOj-'

".20000*10'.30000*10'.20000*10，⑵-期小、

..10000*10^.20000*10'.10000*101-'

[20000*1()1.30000*10'.20000*10'"

1.20000*10'.10000*101

x=(.25000?10°.50000*10")'

消元過程中，第攵步消元(4=1,2,…，〃-1)以第女行為基準，消去其后的

〃-攵個方程的為(系數(shù)矩陣第々列以下的元素)，Gwss消去法要求主元

%*#0。為避免出現(xiàn)%*=0作為主元，并使前步的誤差不被放大，應使上設1,

為此應使：\akk\=Max\\akk\,\ak+u\,---\ank\},通常采用按列選主元的列主元消去

法：若"/=林詞%/,|%+|31%/},便將第左行與第加行交換,使％“與心

交換位置，使新的第人行執(zhí)行在原始Ga“ss消去法中的角色，保證將作為除數(shù)的

主元|%/4腐|i=Z+l,…，〃，從而，/4I,重復前述的Ga“ss消去過程。

列主元消去法的效果：

1.算法穩(wěn)定，即計算誤差能被有效控制;

2.當矩陣A的行列式網(wǎng)H0時，算法總可以執(zhí)行完成；

注：若矩陣A是對稱正定或嚴格對角占優(yōu)，則不選主元，消去法也是穩(wěn)定的;

矩陣嚴格對角占優(yōu)的定義：對角元的絕對值大于該行其他元的絕對值之和,

即同>￡同；

7=1

評

問題：為什么系數(shù)矩陣A嚴格對角占優(yōu)時，不選主元的消去法也是穩(wěn)定的？

為保證消去法是穩(wěn)定的，計算應如何進行?

注意：第一步消元,=>a.-aiy—,由于占優(yōu):<1,

即?.i?n

它的效果與主元消去法的圈W1一樣，誤差不會被放大。但因此算法也應適當改

變，應先對第一行計算此值，然后從第2列起逐列從上到下計算。且第一步消元

后生成的右下方("-1)*("-1)階矩陣仍是嚴格對角占優(yōu)，以第二列為例：

%

>*(X2j=j?21—=>+

四1K-I-K-IKI劭-

??力必人力引+H必忤=勿%|+|編6力%卜

六3六3六3[_|%1]」j=3“川j=3

這回+曷|5佃2|+￡|%力卜1%|62<X］。2j|+|%11-|。211/2

六3|斯|〔；=3jI%；=36I

a—>|<z|-|a|。12。12

又\21\%2一%12221>I%」+2D-1%|

aii斯斯

|522|>￡|52;|即新的第二行的對角元絕對占優(yōu),其他也可同樣證明。

例2-2：列主元消去法求解例2-1

210、223322

2233->12101

1行“2行2行3彳了

、一1-302,-302-2

2232233

-2%-2%%

，32=-%%M

同樣得到原方程組的解x=（l-11）J

2.2矩陣分解

2.2.1Gauss消去法的矩陣意義—矩陣的三角分解

若將Gauss消去法解方程過程中產生的"（i〉/）作為一個單位下三角矩陣

—其對角元為1,對角線上的元素均為0——L的對應元素；將Ga依s消去法

消元過程最后得到的上三角矩陣——對角線以下元素均為0-記作7或U（僅

考慮方程的系數(shù)矩陣部分）；如例2.1,再將L與"或U相乘：

'1Y1210)(1210、

LU=21-213=2233

%為1一1-302,

JX1

八

/

1121(12、

或LU=21—21=22

J%1

7\

顯然d7相乘得到的正是原始所求解的方程的增廣矩陣，而LU相乘得到的

正是原始所求解的方程的系數(shù)矩陣。反過來，一個矩陣也可以通過Gauss求解的

過程獲得這樣的“LU分解”，其中L為單位下三角矩陣，。為上三角矩陣。

這樣將一個矩陣分解成一個下三角矩陣和一個上三角矩陣的乘積形式，稱為

矩陣的三角（Doolittle）分解。

1）消去法的矩陣意義：以例2-1說明

1210、210、

-213

I-1-302）一112,

與以下矩陣乘法是一樣的:

Y12101(1210、

2233=-213

_302)、T14

可見，一般的第一步消元是:

A\A

小

a>囚%

1al~lal~l

A即

oal:l

a‘4/

1二

==…

…

?…?::

:?

:all~二

all

Ao夕

a>囚%

17

若記第左步消元后形成的矩陣為《特別：卬4,勿=（心,即）》

則第i步消元是將以下初等矩陣左乘矩陣（A"f,af）形成（A"）,陰＞）

(、

1

L,=

"1

、T"k1,

因此，Gauss消去過程從矩陣運算的角度來看，是

L?_lLn_2-L2Ll(A,b)=(U,y)

其中U為上三角矩陣，y為向量：

,4114112…41〃

rT"22…"2〃

2.2.2矩陣分解4=七(7

注意到初等矩陣人具有性質：

(、

4=/,及犯，…

因此，我們有(4,力=￡71”〃二,心力=心①力

根據(jù)矩陣乘積的性質，有A=LU

這就是基本的矩陣三角分解一一Doolittle分解一一將矩陣分解為單位下三

角矩陣L與上三角矩陣U的乘積。

從矩陣乘法與行列式的關系可知，若矩陣A三角分解得到A=LU,則有：

detA=detL*detU,由于下三角矩陣或上三角矩陣的行列式是全部對角元的乘

積，因此可利用三角分解求矩陣對應的行列式的值。例如：上述例2.1方程組系

數(shù)矩陣對應的行列式的值是-1,下例2.3對稱正定矩陣對應的行列式的值為144o

當系數(shù)矩陣為A的方程組可以順利求解(不必選主元)時，解的過程顯然是

唯一的，因此它的Doolittle分解必然也是唯一的，從而可以通過待定系數(shù)的方法

獲得該矩陣的Doolittle分解(通常稱為“直接分解”或“緊湊格式”)。

2.2.3其他三角分解

除了上述的單位下三角矩陣與上三角矩陣的乘積形式以外，還有其他類型的

分解，例如下三角矩陣和單位上三角矩陣的乘積，單位下三角矩陣與對角矩陣、

單位上三角矩陣的乘積LDM'對于對稱矩陣，可以分解成LOII矩陣分解的形

式，特別是對稱正定矩陣，可以分解成GG「形式（稱為Cholesky分解），其中G

為下三角矩陣《由Doolittle分解的唯一性可知這些形式的分解也是唯一的》。這

些不同的分解都可以通過矩陣乘積的方法取得。下面例2.3以對稱正定矩陣為例,

說明通過矩陣乘積的方法取得矩陣分解的不同形式。

當然，當矩陣的Doolittle分解存在唯一時，這些不同的分解分別時唯一的,

因此可以通過待定系數(shù)的方法取得，也即通過直接分解的方法取得這些分解。

例2-3：

4-20-20-20-204、

-22-3I-31-31-33

0-313-313442

41-73-729)

由此可知:

’4-20

-22-31

0-313-70-3

23j1

、41-73

A1.%01

1-33

1%

9J

-33

1%

1)

f-x0

、(2

11-33

221%

3人V

進一步可以考察矩陣左上方各階順序主子式與三角分解所得矩陣的左上方

的各階順序主子式的關系：若記矩陣A的各階順序主子矩陣為4,A⑵,…，

同樣的記號也適用于矩陣L,U,則有4的=￡位7陽，從而矩陣A的各階順序主子

式的值等于U的相應的順序主子式的值：det（A,*））=det^Zw）僅=1,2,…,〃），

（因為det（L“。）三1）。以例2-3矩陣分解為例，容易得到：

'4-2、(1、’4-2、

4=1*4,=1/

卜％14/

「24;/

'4-20]'1,4-20、

-22-3=11-3

0

、-3、°-3"k4,

由此，也很容易看到，一個對稱矩陣通過Gauss消去過程得到的LU分解（其

中心為單位下三角，U為上三角矩陣），當U的對角元全部為正數(shù)時，該對稱矩

陣必為對稱正定矩陣。

由Ga如s消去的過程可知各次主元是“22,…（矩陣U的對角元），可

知當矩陣A的各階順序主子式均非零時，（原始的）消去法可以順利完成,

這是因為當各階順序主子式均非零時，4”,〃22,…,〃”“均非零，即Gauss消去法可

以順利完成。因此得：

定理2.1若〃階方陣的各階順序主子行列式均非零,則存在唯一的LU分解,

其中L為單位下三角矩陣，U為上三角矩陣。

進一步，當矩陣A非奇時，列主元Gauss消去法必可順利完成：因為當矩陣

A非奇時，4的第一列必不全為零，故通過選主元，可進行第一步消元，即算法

乙尸14可執(zhí)行，得到〃?產0,且其下方全為零，因為det（L/*）=detAwO,所以〃||

的代數(shù)余子式detA：也非零，（?/detA=det（LlP,A）-/jiidet^0）,即矩陣A：非

奇，因此下一步列主元消去可進行，由此，可完成全部消元過程。

2.2.4解三對角矩陣的追趕法

XX???X

X

J上帶寬q:j>i+qa(j=0

X*下帶寬p:i>j+qa,j-0

x

x…xx.

定理2.2若4=L。分解），則“下）帶寬p,U（上）帶寬紜

證明：對二和三階矩陣顯然.(確定p,q),對矩陣的階作歸納證明:設對〃-1階

矩陣結論成立.令

aw

A==(v2???v+10?-?0),皿7=(卬2??1W+i00),

㈠B)

可驗證(介紹分塊運算)：

由歸納假設,3-工27=因此

a

最后的矩陣乘法：前者是初等矩陣左乘〈實際上是Gauss變換矩陣相乘〉，后者

按分塊運算容易得到。特殊情況,p=L4=1——三對角矩陣：

，仇c\、

a2b2c2

T=??????,

a

n-\"_ICn_1

<冊)

由前述的方法，很容易將它分解成兩個特殊的下、上三角矩陣的乘積:

其中〈因為未講矩陣的直接分解，此處可由確定分解形式、待定系數(shù)方式取得〉：

.二瓦,

兒=°九_]'uk=bk-lkck-\，女=2,3,…，〃

從而，在解方程組公=d,其中1=(442,…,弘)7時，可以將該方程組轉化為

求解兩個簡單方程組：Tx=doLy=d,Ux=y,通常被稱為“追趕法”：

|力=4X”

\yk=dk-hyk-\k=23…,n，=(yk-ckyk+xy女=…，2,1,

這只是Gauss消去法的一個具體應用，在計算機上的應用可以節(jié)約存儲空

間，減少運算量。若手工計算，實際只需應用Gauss消去法即可。例

"12、’1、"2、

23121-11

-342=3112

47141-11

<一56,、51>、1

2.3線性方程組解的可靠性——向量與矩陣范數(shù)，誤差的代數(shù)表征

3.1向量與矩陣范數(shù)

向量范數(shù)由二維或三維向量的長度概念推廣而來一一工具。

1、向量范數(shù)向量》=(為,％2…X")7"eR”,與之相應的一個非負實數(shù),

記作H，如果它滿足條件：

1)非負性H>0,H=0ox=0,VxeRn,

2)正齊性||ar||=|?|||^||,\/aeR,xeRn,

3)三角不等式||x+y||<||x|+||y||,Vx,yeR"；

常用的范數(shù)

L范數(shù)網(wǎng)=周+同+…+k”|，1

2-范數(shù)||%||2=(卜1/+同「+…+“，)2,

-范數(shù)IkL=max胤卜2卜-，|芍|)，

注：一般若不指某特定的范數(shù)，則范數(shù)符號不作下標，記為|卜|；

2、矩陣范數(shù)矩陣AeL(Rg"),與之相應的一個非負實數(shù)，記作風,

如果它滿足條件：

1)非負性同20,M|=0OA=0,VAWZXRE),

2)正齊性1M|=同網(wǎng)，Vae/?,VAeL(7?mxn),

3)三角不等式M+M4M|+|同，

4)阿，VAe"RM"),

因為矩陣與向量相乘仍是向量，因此：特別要求一種矩陣范數(shù)與一種向量范數(shù):

5)|囹區(qū)同同，VAGZXDXGR"——矩陣與范數(shù)的相容性;

與前述三種向量范數(shù)分別相容的常用的三種矩陣范數(shù)：

1-范數(shù)|可1=maxZkJ，(最大列和)

jZ=11

2-范