計(jì)算方法講義

XJTU

西安交通大學(xué)

-計(jì)算方法B講義—

XJTU

2010/11/16

第一章緒論

1.1數(shù)值計(jì)算

現(xiàn)代科學(xué)的發(fā)展，己導(dǎo)致科學(xué)與技術(shù)的研究從定性前進(jìn)到定量，尤其是現(xiàn)代

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

力的基礎(chǔ)。

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

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

一、本課程的任務(wù)：

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

數(shù)學(xué)（算術(shù)）的方法求解一一了解計(jì)算的基礎(chǔ)方法，基本結(jié)構(gòu)（否則只須知道數(shù)

值軟件）一一并研究其性質(zhì)。

立足點(diǎn)：

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

面向計(jì)算機(jī)一一利用計(jì)算機(jī)作為工具

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

例如：迭代法、并行算法

二、問題的類型

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

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

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

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

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

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

一般來講，誤差主要有兩類、三種（對科學(xué)計(jì)算）：

1）公式誤差一一“截?cái)嗾`差”，數(shù)學(xué)3計(jì)算，算法形成一一主觀（人為）:

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

都會發(fā)生誤差，通常稱之為“截?cái)嗾`差”；一一以后討論

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

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

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

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

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

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

一、計(jì)算機(jī)上的運(yùn)算一一浮點(diǎn)運(yùn)算

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

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

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

XX+XXXXX

首數(shù)/尾數(shù)（f位）

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

字長為t位的浮點(diǎn)數(shù)系/（夕/,乙“）中的（浮點(diǎn)）數(shù)，可以用以下形式表示：

d、%d,l<cL<P

/（x）=±（/+%+…"）xp（）嗎“，）=2,3,…,r

此處，指數(shù)/（稱為階）限制在〈。范圍內(nèi)。

以下記實(shí)數(shù)系中的實(shí)數(shù)為xeR，它在浮點(diǎn)數(shù)系尸中對應(yīng)的浮點(diǎn)數(shù)

記為H（x）eF（0,t,L,U）一一夕進(jìn)制，，尾數(shù)位數(shù)，階的范圍。

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

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

十進(jìn)制轉(zhuǎn)換二進(jìn)制

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+21+2°00011011

1季節(jié)

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

是字節(jié)。

單精度浮點(diǎn)然singleprecision）板32位存儲，雙精度浮點(diǎn)數(shù)｛doubleprecision）

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

位。單精度浮點(diǎn)數(shù)的尾數(shù)為23位、階數(shù)為8位；雙精度浮點(diǎn)數(shù)的尾數(shù)為53位（包

含符號位）、階數(shù)為11位（包含符號位）。雙精度浮點(diǎn)數(shù)的等價(jià)二進(jìn)制數(shù)如下所

示：

64位

bbbb…bbf*id…gdddd,

11位指數(shù)（含符號位）符菖位52位尾數(shù)

浮點(diǎn)數(shù)的特點(diǎn)：

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

況：x=2，,/=0,±1,±2,???）

按四舍五入，絕對誤差：|x—#（x）區(qū);夕T（舉例），

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

I3（x）1=1力“）

注：設(shè)實(shí)數(shù)xeH,則按4進(jìn)制可表達(dá)為：

X一+々41%+11}xBl1&d\〈B

）

6,2+…/+/+1+…x￡0<J■<P,j=2,3,???,/,/+1???

+i<?,則

按四舍五入的原則，當(dāng)它進(jìn)入浮點(diǎn)數(shù)系尸時(shí)，若4

,（x）=±（，+，+..*）x/

P伏伊

1d.d,.d+\.

若d,以則〃（x）=±（W+W+…—）x0

2B鏟伊

對第一種情況：

卜曲川=（"薪+…）：（；）x.

pP乙乙

對第二種情況：

|x-#（x）|=-…X夕=?尸

fjfj乙乙

就是說總有：

另一方面，由浮點(diǎn)數(shù)要求的144</,有國N1少

,將此兩者相除，便得

r

2、每一個浮點(diǎn)數(shù)系的數(shù)字有限：2（^-l）^-'（t/-A+l）+l

3、浮點(diǎn)數(shù)系中的運(yùn)算非自封閉，（因?yàn)閿?shù)字有限等）

例：在尸（10,4,-5,5）中，x=.5420x10-2）=.2001x1（）3,運(yùn)算x*歹和x/y,

的結(jié)果顯然已不在此浮點(diǎn)數(shù)系內(nèi)，而x+y或x-y也不在此浮點(diǎn)數(shù)系內(nèi)，需

/7（x。y）結(jié)果才在此浮點(diǎn)數(shù)系內(nèi)。

浮點(diǎn)運(yùn)算應(yīng)注意：

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

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

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

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

原因：

記△=maxM（x）|=max~,由卜-力（刈47乂，可得：

|（%。歹）-#*。m＜小。R|（“.”表示任意一種四則運(yùn)算）

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

了實(shí)際運(yùn)算的精度）。

顯然，若要求運(yùn)算的舍入誤差小，應(yīng)使運(yùn)算結(jié)果（如：較小。

尤其是小分母運(yùn)算：±-小歹=大誤差。

yyy

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

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

x=.8231xl03,^=.2317xl0-1,則

x±^=.8231xl03±.2317x1（）7=.8231x1（）3+.（）（）0（）xl03=x

似乎J（沒有參加運(yùn)算。

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

如，在廠（10,8,-5,5）中，x=.82317844X103，^=.82317832X103,兩數(shù)相減：

x-y=.120000（）（）x10-3,計(jì)算結(jié)果僅剩2位有效數(shù)字，而原來參加運(yùn)算的數(shù)字有8

位有效數(shù)字，這將嚴(yán)重影響最終計(jì)算結(jié)果的精度。

二、算法分析

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

定義：計(jì)算機(jī)完成一個乘法和一個加法，稱為一個浮點(diǎn)運(yùn)算（記為flop）;

注：由于計(jì)算機(jī)在運(yùn)算時(shí)，加（減）法所耗時(shí)間遠(yuǎn)少于乘（除）法，所以

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

1、計(jì)算效率一一可計(jì)算性(計(jì)算復(fù)雜性——空間、時(shí)間)

例：解線性方程組4r=6的Grammar方法：x,」'尤「其中|川是方程

組系數(shù)矩陣，對應(yīng)的行列式，而|4|則是以右端向量6替代N的第，?列所得矩陣

對應(yīng)的行列式。由線性代數(shù)知識可知，若，=(%),則

|川=2?一1嚴(yán)而乜)劭產(chǎn)24…即；，

其中“；兒,…，)是由“，2,｝變換到｛J%i?｝所需的置換次數(shù)?？梢娒?/p>

計(jì)算一個行列式，需要(〃-1)-〃！個浮點(diǎn)運(yùn)算；因此，按Grammar方法解方程組

約需N=(r-1>〃！個浮點(diǎn)運(yùn)算。當(dāng)〃=2()時(shí)9.70728x102。，用一個運(yùn)算

速度為IO15/秒的計(jì)算機(jī)進(jìn)行求解，約需3.078x105年(日前報(bào)道我國計(jì)算機(jī)已達(dá)

到3840x108/秒，這仍需近io年)。而n=20的方程組應(yīng)該說是一個小型的方程

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

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

2、計(jì)算可靠性

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

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

?問題的性態(tài)

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

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

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

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

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

例：線性方程組:

-1-1

6

13

-一

12

47

-一

60

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

1.OOxj+0.50X2+0.33x=1.8(_6.221

<O.5Oxj+0.33X+0.25X=1.1的解則變成：斤=38.25

23-33.65J

0.33x,+0.25X2+0.20X3=0.78

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

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

擾動后的數(shù)據(jù)%=計(jì)算結(jié)果/（工）,

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

/(X)-/⑴,x-x

<m----

fix)x

f(x)-fG)

f(x)

或m=sup------—

x-x

x

則稱（相對誤差之比的上界）m為該問題的條件數(shù)，記作m=co〃d⑺;

由微積分中值定理知識容易計(jì)算出，當(dāng)x-M時(shí)，co〃d（J）=》人電|o

./W|

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

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

I

nx

例：計(jì)算ln=e-'\xedx,〃=0,1,…,8；

0

解：由微積分知識，可得計(jì)算公式，①7?=1，②=工（1一/“）,

n

我們將準(zhǔn)確值與計(jì)算結(jié)果列表如下：

方法I。A4h17A

準(zhǔn)確值.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

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

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

為方法①中，若前步有誤差3：7M=4T+6，則

了k=1-近1---防,

說明的誤差3,經(jīng)一步計(jì)算后被擴(kuò)大了左倍，隨著%的增大，誤差將被大大

地?cái)U(kuò)大；而通過同樣的分析可知：方法②中人的誤差則被縮小左倍。

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

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

第二章線性方程組求解

線性方程組：

%1陽+anx2+…+%,/“

a\X\+ax+---+ax=/3

Ax-b22222nn2(2.1)

an\X\+an2X2+'"+0CnnXn~Pn

其中

a12,??斯「邛,

%]%2.??%”x2A

A=，X=,b=

42.??

2.1Gauss消去法

2.1.1消去法

設(shè)計(jì)方法原則：面向計(jì)算機(jī)（事先未知元素，編制程序），例:

2x+x=3

2xj+x=3l2

233=X,=1=M=1

x,-x=0------X=------"1

2222

基本思想：降維一一N維問題轉(zhuǎn)化為N-1維問題一一逐次降維，依次進(jìn)行

消去過程一一對方程組（2.1）由上而下逐步消去對角元（女=1,2，…，〃-1）

以下的aik（i=k+l,-,n）,使之轉(zhuǎn)化為如下等價(jià)形式，達(dá)到目標(biāo)：

a11x1+a12x2+---+a,?x?=^,

42x2a2nXn~夕2。、

5（2.2）

annXn~

從而，可進(jìn)入回代過程，再由下而上，逐步解得乙（%=〃,〃-1,…，2,1）：

這兒的（左=1,2,…,〃-1）-----主元

對問題（2.1）設(shè)a”/0,目標(biāo)：將第2?n方程的X］的系數(shù)。21，…,a,“轉(zhuǎn)化

為0；方法：”第1個方程”一組x”第1個方程”a=2,3,…㈤,得到

即

劭西+%2彳2+…+劭/“=。\

嫂3+…+吟%=敘

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

^*2+…+。％”=敘

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

消去：第Z步（攵=1,2,…，〃一1）：設(shè)4*。。，以第%行為基準(zhǔn)，消去以下各

行中左列劭.以下的《*"=左+1，…，〃），令4=絲，施行：第〃行一4,x第"亍

akk

n新的第左行，元素變化：（akk=0）,/=%-4劭,耳=￡一%瓦，經(jīng)過

步消去（注意：a““以下無元可消），得到（2.2）式?！醋⒁猓好坑?jì)算1個/g田八月

僅需1個浮點(diǎn)運(yùn)算〉

回代：第一步與=區(qū)，

%”

第二步％=協(xié)一%L%一，???，

第n-k+1步

[4?一（%

Xk左=〃一1,…，2,1;

運(yùn)算量：

消元:n元方程組:第1步消元:對第，（元2,3,…行,共n-1行；

每1行：計(jì)算/,??=2,3,…,〃），1個乘除法（或“浮點(diǎn)運(yùn)算”），

計(jì)算新的*=%-（/=2,3,,…力⑴=毋-/,[才共（〃-1）+1個

乘除法（或“浮點(diǎn)運(yùn)算”），

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

Z（左2—l）=Z（左2—1）=1>2

k=nA=1A=1326

回代：第1步，求工〃需要1個乘除法（或“浮點(diǎn)運(yùn)算”），即：第2步求X〃_1

用2個乘除法（或“浮點(diǎn)運(yùn)算”），一般，第左步求用左個浮點(diǎn)運(yùn)算，因此，

回代的運(yùn)算量之左，（〃+1）；

hl2

Go〃ss消去法的總運(yùn)算量：T=—4-/12o

33

例2-1：解線性方程組

X]+2X2+X3=0

<2a+2X2+3X3=3

2

.-^i-3X2

解:利用增廣矩陣（因?yàn)榫€性方程組的解僅與系數(shù)與右端常數(shù)項(xiàng)相關(guān)）

'1210、fl210、210、

，21=2(1、

2233—>-213->-213=x=-1

2，3I=T-1%%

-30J12,

'2-112、

例:-65-33;解*=%

054,-3

-21032'1、-21032、‘1、

-441-102121-7-41

;解*=

252-22-13-131-1211

-2124570-21人55J

20134\(1\20134、’-1\

431725213-11175

解X=

2-364-91-11424；0

66518607211人52,27

'12342、1Y12342、;、

14916101126128

;解》=

1827644413162418

1681256190?761人2424,

(\23430、’123430、

23454021-1-2-3-20

;解》=

344543321-1-1-7

、455757,<4311人14

2-207、1、2-207、1、

-1-341-10-11-121-32

;X=

0-277-4021352-1

J2-11—142，10-31人11

2.1.3（列）主元消去法

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

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

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

例：在浮點(diǎn)數(shù)系E(10,5,-10,10)中計(jì)算；方程組

(IO-2丫范)⑴*r0.250001875]

(23大刈[0.499998749

解：按Gai/ss消去法解：

’.10000*1()7.20000*10'.10000*10';,,=020000.106

、.20000*1()1.30000*10'.20000*10'J-

.10000*1()7.20000*10'.10000*10,

-.40000*106-.20000*10%

x=(.00000?10°.50000*10°)7

誤差大，原因：若有誤差他=他+6,片=月+3則

%=%-4%，A=戊一44，則演變?yōu)?/p>

%=%-4(%+6)=&+46,6=d-l*(Bk+6)=A+likS；

這說明前步各元素的誤差均被放大4倍?？朔椒?，將按絕對值最大的元素交

換到主元位置，使上|<1，使前步的誤差不再被放大。

r.10000*10^.20000*10'.10000*10。儕*,

.20000*10'.30000*10'.20000*10］；

f.20000*10'.30000*10'.20000*10。⑵TOOOO*K)T

//I-八“尸I",

、.10000*1()7.20000*10'.10000*10、

".20000*10'.30000*10'.20000*10''

、.20000*10'.10000*10^

土=(.25000?10°.50000*10°)r

消元過程中，第左步消元(左=1,2,…，〃-1)以第〃行為基準(zhǔn)，消去其后的

〃-上個方程的4*(系數(shù)矩陣第上列出,以下的元素)，Ga“ss消去法要求主元

akk#0。為避免出現(xiàn)&*=0作為主元，并使前步的誤差不被放大，應(yīng)使心|41，

為此應(yīng)使：|%*|=腦7刈%|,|%+|小-舊/},通常采用按列選主元的列主元消去

法：若|%/=腦刈劭|,|%*|,…同/},便將第上行與第，〃行交換,使名,“與心

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

主元|沏」4%|i=k+1,…，〃，從而重復(fù)前述的Ga〃ss消去過程。

列主元消去法的效果：

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

2.當(dāng)矩陣/的行列式Ml*0時(shí)，算法總可以執(zhí)行完成；

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

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

即I知>￡同；

戶,

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

為保證消去法是穩(wěn)定的，算法應(yīng)如何進(jìn)行？

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

tj%iX斯即

它的效果與主元消去法的一樣，誤差不會被放大。但因此算法也應(yīng)適當(dāng)改

變，應(yīng)先對第一行計(jì)算此值，然后從第2列起逐列從上到下計(jì)算。且第一步消元

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

v弱=囪-%%n甌

名1四1

???E均<E%+E%'J=Za2j+a2iE%

/=3J=3六3a1]y=3a"六3

a

又|?22|=?22-?21—^K|-I21|—>1^2^+EK|"KI—

%斯六3Ja”

&22>七制/即新的第二行的對角元絕對占優(yōu)，其他也可同樣證明。

7=3

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

210、[223312233

2233-121

I行<~>2行

<~1-302-1-30

同樣得到原方程組的解X=(l-1l)r；

2.2矩陣分解

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

若將Gm/ss消去法解方程過程中產(chǎn)生的幻(，＞力作為一個單位下三角矩陣

——其對角元為1,對角線上的元素均為0——L的對應(yīng)元素；將Gm/ss消去法

消元過程最后得到的上三角矩陣——對角線以下元素均為0―記作守或。(僅

考慮方程的系數(shù)矩陣部分);如例2.1,再將￡與［7或。相乘:

1V12210、

LU=2-22233

-11C-302,

/

1121，121、

或LU21-2223

%1-1-3°)

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

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

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

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

矩陣的三角(Doolittle)分解。

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

’1210、210、

2233-213

5=2，/3l==-l

-\-302,-112,

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

Y1210)(1210、

-212233=-213

JI-1-302)、

、1-112,

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

、A

°11斯■??四1%斯???四

~hi1%%-??斯A0得?函

L](A,b)==:

1

/

、一卻斯.?.%?11?

若記第左步消元后形成的矩陣為（4",對）），《特別：”4b）=（a,a）》

則第步消元是將以下初等矩陣左乘矩陣（w,f,M-D）形成（/?小））

因此，Gauss消去過程從矩陣運(yùn)算的角度來看，是

Ln_,Ln_2-L2L,(A,b)=(U,y)

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

>nAin??1Ai/

力

422為

Uy=

\yn)

2.2.2矩陣分解/=LU

注意到初等矩陣。具有性質(zhì):

I、

1

2,1

以=反匕;匕；…UL=L=

/+1,/1

n-1,11

「1

H.n-1J

因此，我們有(/,〃)=L■:用…匚3(U,y)=L(U,y)

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

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

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

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

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

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

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

當(dāng)系數(shù)矩陣為力的方程組可以順利求解（不必選主元）時(shí)，解的過程顯然

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

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

2.2.3其他三角分解

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

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

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

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

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

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

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

當(dāng)然，當(dāng)矩陣的Doolittle分解存在唯一時(shí)，這些不同的分解分別時(shí)唯一的，

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

例2-3：

4-204、f4-204、

-22-33

0-3132

41-79,

由此可知:

'1

"4-204、

-%

-22-311

0-313-70-3

、41-723,、13

-%1

4

0

「％0

1-3

21

3j%

02、

-33

21

3,

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

的各階順序主子式的關(guān)系:若記矩陣A的各階順序主子矩陣為“⑴，/⑵

同樣的記號也適用于矩陣LU,則有/的=從而矩陣4的各階順序主子

式的值等于U的相應(yīng)的順序主子式的值：det（4*））=det（t/.）（A=1,2,

（因?yàn)閐et（l嚴(yán)）三1）。以例2-3矩陣分解為例,容易得、到:

4—2、14-2y

4=1*4,

414

7、7/

'4-2014-20

-2211

,0-313J0-3U47

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

為單位下三角，。為上三角矩陣），當(dāng)U的對角元全部為正數(shù)時(shí)，該對稱矩陣必

為對稱正定矩陣。

由Gauss消去的過程可知各次主元是〃（矩陣U的對角元），可

知當(dāng)矩陣N的各階順序主子式均非零時(shí)，（原始的）Gauss消去法可以順利完成，

這是因?yàn)楫?dāng)各階順序主子式均非零時(shí)，均非零，即Ga“ss消去法

可以順利完成。進(jìn)一步，當(dāng)矩陣Z非奇時(shí)，列主元Gauss消去法必可順利完成:

因?yàn)楫?dāng)矩陣N非奇時(shí)，N的第一列必不全為零，故通過選主元，可進(jìn)行第一步消

元，即算法“P那可執(zhí)行，得到小尸0,且其下方全為零，因?yàn)?/p>

det（L///）=det/r0,所以〃”的代數(shù)余子式det4；也非零，

（;detN=det（，/尸源）=4udetN：/0）,即矩陣非奇，因此下一步列主元Ga〃ss

消去可進(jìn)行，由此，可完成全部消元過程。

2.2.5帶狀矩陣的分解

XX???X

fx

P\：'1''C上帶寬4-j>i+q%=0

A-y<

XI下帶寬p:i>j+qaij=0

x

、x…xx

定理2.5若Z=LU（Z）oo〃〃/e分解），則"下）帶寬p,U（上）帶寬q.

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

矩陣結(jié)論成立.令

TT

A-,v=（v2…V+10…0）,w=（卬2…%+10…°），

可驗(yàn)證（介紹分塊運(yùn)算）：

aw、

1>

由歸納假設(shè),5-，0|/=乙6,因此

a

最后的矩陣乘法：前者是初等矩陣左乘（實(shí)際上是Gauss變換矩陣相乘〉，后者

按分塊運(yùn)算容易得到。特殊情況,2=1,4=1——三對角矩陣：

&C\

。2b?C*2

T=??**.**.

、an0,

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

其中〈因?yàn)槲粗v矩陣的直接分解，此處可由確定分解形式、待定系數(shù)方式取得）:

=仇，

c

,uk=bk—lkk-\，k=2,3,…，n

從而，在解方程組7k=d,其中d=（4,刈,…,"”）r時(shí)，可以將該方程組轉(zhuǎn)化為

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

=d\「〃二%”。

d

\yk^k-hyk-\k=2,3,…,n，^（yk-ckyk+xy左=2,1,

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

間，減少運(yùn)算量。若手工計(jì)算,實(shí)際只需應(yīng)用Gauss消去法即可。例

2Y12、

23121-11

-342=3112

47141-11

—56,、5A1

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

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

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

1、向量范數(shù)向量X=（X],'2…x"）7wR",與之相應(yīng)的一個非負(fù)實(shí)數(shù),

記作人||,如果它滿足條件：

1)非負(fù)性H>0,悶=()=x=0,VxeR",

2)正齊性僮|=|討國,VaeR,x&Rn,

3)三角不等式卜+“區(qū)帆+帆，Vx,j/eRn；

常用的范數(shù)

1-范數(shù)M=卜1|+卜2|+…+卜”|']

2-范數(shù)|他=(|可『+卜2『+…+"『)2,

8-范數(shù)|丸=max(㈤,,2],)，

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

2、矩陣范數(shù)矩陣/以曖⑼)，與之相應(yīng)的一個非負(fù)實(shí)數(shù)，記作慟，

如果它滿足條件：

1)非負(fù)性p||>0,M=0ON=0,VAeL(Rmx"),

2)正齊性||<z4||=|a|p||,Vae/?,V^eURmxn),

3)三角不等式||J+5||<M+||5||,,

4)歸同，V^eUR'nx"),5eL(R"Xp),

因?yàn)榫仃嚺c向量相乘仍是向量，因此：特別要求一種矩陣范數(shù)與一種向量范數(shù):

5)|px||<|p||H，\/AwW),xeR"一一矩陣與范數(shù)的相容性；

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

n

1-范數(shù)=maxf|aj,(最大列和)

2-范數(shù)雙=(/7的最大特征值)；，

8-范數(shù)同8=maxZ|%J,(最大行和)；

17=1

注：作為矩陣的特例一一向量，這些范數(shù)定義無矛盾。

例：第2章Ex-14(79頁)卜|-范數(shù)，=國,“=口以上范數(shù)，

=>MM=|比4/->矩陣范數(shù)，其中〃-非奇矩陣

3、范數(shù)的等價(jià)性：

IHL引4vblkL，力凰引丸<11x11,,IHL<H2??L，

4、矩陣譜半徑：p(4)=max｛同，4為4全體的特征值,i=1,2,??.,〃｝；

有(對任何一種范數(shù))"(4)<同，

Ax=Ax,xw()n|yl|||x||<||2r||=px||<m|||x||=>|2|<||^||=>p(A)<p||

2.3.2殘向量與誤差誤差的代數(shù)表征(矩陣的條件數(shù))：

若記方程組(2.1)的準(zhǔn)確解x*,近似解亍；則有

T

近似解文的誤差：e=x*-x=(e],e2,---,en),

近似解亍的殘向量：r=b-Axo

|r|小=|同小？

,r1.0002.000、(3.000、*m(2、

例z」。.4991.001/=[1,500j5*1J

r=b-Ax=[°]

(0.00⑸

比較：方程組Ax=b與Ax=b-r,從前者到后者僅是右端6產(chǎn)生誤差

T,而對應(yīng)的解則由x*變?yōu)椋?，即也產(chǎn)生誤差e；它們之間有關(guān)系：

￡1wA-'

x

注意以上公式：由6=4rn||Z>||=px||<||/4||||x||=>W

H-r以及

1

r=b—Ax=Ax—Ax=A(x-x)=Aene=ATrnM<MH得到。

從本質(zhì)上反映了方程組右端的相對誤差[4導(dǎo)致解的相對

此處,

1111PII

誤差r

的數(shù)值關(guān)系，反映了方程組原始數(shù)據(jù)發(fā)生擾動時(shí)，方程組解發(fā)生變化

bll

的大小。比較前已提到的“問題的