河海大學(xué)研究生數(shù)值分析課件

數(shù)值分析

編者李慶揚(yáng)等

課件董祖引

Ch1緒論1.1數(shù)值分析研究對(duì)象與特點(diǎn)

科學(xué)技術(shù)領(lǐng)域的三大環(huán)節(jié)：（1）實(shí)驗(yàn)；（2）科學(xué)計(jì)算；（3）理論。

所謂的科學(xué)計(jì)算是指使用計(jì)算機(jī)進(jìn)行數(shù)值計(jì)算的工作，它可以部分地替代科學(xué)實(shí)驗(yàn)?？茖W(xué)計(jì)算的主要過程：實(shí)際問題數(shù)學(xué)模型數(shù)值計(jì)算方法程序設(shè)計(jì)上機(jī)計(jì)算求出結(jié)果

其中數(shù)值計(jì)算方法是數(shù)值分析研究的對(duì)象。主要包括：（1）函數(shù)的數(shù)值逼近（包括插值法）；

（2）數(shù)值微分和數(shù)值積分；

（3）非線性方程（組）數(shù)值解；

（4）數(shù)值線性代數(shù)（如線性方程組數(shù)值解、矩陣特征值特征向量的計(jì)算）；

（5）（偏）微分方程數(shù)值解。數(shù)值分析的主要特點(diǎn)：（1）可行性；（2）時(shí)效性；（3）可靠性；（4）實(shí)驗(yàn)性。1.2數(shù)值計(jì)算的誤差

誤差的來源與分類：（1）模型誤差；（2）觀察誤差；（3）截?cái)嗾`差（也稱方法誤差）；例如：其截?cái)嗾`差：

（4）舍入誤差（包括由十進(jìn)制轉(zhuǎn)換為二進(jìn)制引起的誤差）。例如：其舍入誤差：絕對(duì)誤差：其中是的一個(gè)近似值。（絕對(duì)）誤差限：并記：相對(duì)誤差：實(shí)際計(jì)算中通常用相對(duì)誤差限：

若近似值的誤差限是某一位的半個(gè)單位，就說“精確”到這一位。

若該位到的第一位非零數(shù)字共有n位，就說有n位有效數(shù)字。

它可表示為：

例1

按四舍五入原則下列各數(shù)：187.9325，0.03785551，8.000033，2.7182818，2/3具有5位有效數(shù)字的近似值分別為：187.93，0.037856，8.0000，2.7183，0.66667定理1

設(shè)近似數(shù)表示為：若具有n位有效數(shù)字，則相對(duì)誤差限至少具有n位有效數(shù)字。反之，若的相對(duì)誤差限，則（證明見黑板）

例2

要使的近似值的相對(duì)誤差限小于0.1%，要取幾位有效數(shù)字。（見黑板）

以、記、的絕對(duì)誤差限，則一般的，利用Taylor展式，有

例3

測(cè)量得某場(chǎng)地長(zhǎng)l的值為m，寬d

的值為m，試求面積s=ld的絕對(duì)誤差限與相對(duì)誤差限。（見黑板）1.3誤差定性分析與避免誤差危害

一般的，誤差的定量分析是困難的，我們考慮下列三各方面的定性分析。（1）病態(tài)問題與條件數(shù)。

若輸入數(shù)據(jù)有微小擾動(dòng)（即誤差），引起輸出數(shù)據(jù)（即問題的解）相對(duì)誤差很大，則稱為病態(tài)問題。

病態(tài)程度可用相對(duì)誤差比值來描述，如：并稱為計(jì)算函數(shù)值問題的條件數(shù)。

例如，，則。它表示相對(duì)誤差大約放大n倍。(2)算法的數(shù)值穩(wěn)定性。

一個(gè)算法如果輸入數(shù)據(jù)有誤差，而在計(jì)算過程中舍入誤差不增長(zhǎng)，則稱此算法是數(shù)值穩(wěn)定的。比如，page9例5的A算法是數(shù)值不穩(wěn)定的，B算法是穩(wěn)定的。(3)避免誤差危害的若干原則。1.避免小數(shù)作除數(shù)。2.避免兩相近數(shù)相減。

例4

利用中心差商公式計(jì)算在處的導(dǎo)數(shù)值。（詳見黑板）3.防止大數(shù)“吃”小數(shù)。4.簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)。

例5

計(jì)算多項(xiàng)式的值。

直接計(jì)算共需要做次乘法和n次加法。若用秦九韶算法只要n次乘法和n次加法即可。Ch2插值法2.1引言

設(shè)在區(qū)間上有意義，且已知在點(diǎn)上的值若存在簡(jiǎn)單函數(shù)，使得

插值區(qū)間。則稱是的插值函數(shù)。點(diǎn)稱為

插值節(jié)點(diǎn)。其他點(diǎn)稱為插值點(diǎn)。稱為

若是次數(shù)不超過n的多項(xiàng)式，即則稱為插值多項(xiàng)式。相應(yīng)的方法稱為多項(xiàng)式插值。

若是分段多項(xiàng)式，則稱分段多項(xiàng)式插值。

常用的有拉格朗日插值、牛頓插值、埃爾米特插值、埃特金插值、三次樣條插值等。2.2拉格朗日插值定義1

若n次多項(xiàng)式在n+1個(gè)節(jié)點(diǎn)上滿足則稱為節(jié)點(diǎn)上的n次（拉格朗日）插值基函數(shù)。

注意：它與無關(guān)。

事實(shí)上，拉格朗日插值基函數(shù)令則滿足：稱為拉格朗日插值多項(xiàng)式。

特別的，當(dāng)n=1，稱線性插值。當(dāng)n=2，稱拋物插值二次插值。

若引入記號(hào)則拉格朗日插值多項(xiàng)式可寫成如下的緊湊形式：例1

已知的觀察值數(shù)據(jù)x01320-4求的二次插值。（見黑板）

定理1

滿足插值條件的n次插值多項(xiàng)式是存在唯一的。

證明只要證明唯一性。

假設(shè)還有次數(shù)不超過n的多項(xiàng)式滿足則這與代數(shù)基本定理（n次多項(xiàng)式至多有n個(gè)零點(diǎn)）矛盾。特別的，若令則得又若則

關(guān)于截?cái)嗾`差，也稱拉格朗日插值余項(xiàng)，我們有

定理2

設(shè)在上連續(xù)，在內(nèi)存在，則，有（證明見黑板）若，則截?cái)嗾`差限

例2

已給sin0.32=0.314567，sin0.34=0.333487，sin0.36=0.352274，試用拋物插值計(jì)算sin0.3367，并估計(jì)截?cái)嗾`差。（見黑板）

一般說來，不易求得，可用下述的誤差的事后估計(jì)法。（詳見黑板）

最后，關(guān)于插值多項(xiàng)式的數(shù)值計(jì)算的穩(wěn)定性，我們有結(jié)論：

（1）線性插值數(shù)值計(jì)算是穩(wěn)定的；（2）高次（非線性）插值數(shù)值計(jì)算是不穩(wěn)定的。（詳見黑板）2.3均差與牛頓插值公式

牛頓插值法的思想是將插值多項(xiàng)式表寫成

其中為待定系數(shù)，

可由插值條件確定。它們正好是下述定義的均差。

定義2

稱為關(guān)于點(diǎn)的一階均差；稱為的二階均差；一般的，稱為的k階均差。

利用歸納法可以證明：均差具有如下基本性質(zhì)：

（1）（對(duì)稱性）均差與節(jié)點(diǎn)的排序無關(guān)，即（2）

（3）若在上存在n階導(dǎo)數(shù)，則（證明略）

具體計(jì)算時(shí)可列均差表（詳見黑板）。

根據(jù)均差的定義，并把x看作上一點(diǎn)，則將后式代入前式，即得其中顯然滿足插值條件，稱為牛頓（均差）插值多項(xiàng)式。插值余項(xiàng)

注意：根據(jù)插值多項(xiàng)式的存在唯一性定理，牛頓插值與拉格朗日插值結(jié)果（包括余項(xiàng)）是一致的，只是形式不同而已。

與拉格朗日插值比較，牛頓插值計(jì)算量省，且便于程序設(shè)計(jì)。在增加節(jié)點(diǎn)時(shí)牛頓插值是很方便的。（算例見page34，略）2.5埃爾米特插值

埃爾米特插值不僅要求節(jié)點(diǎn)處函數(shù)值相等，且對(duì)應(yīng)的導(dǎo)數(shù)（甚至高階導(dǎo)數(shù)）值也相等。具體地，設(shè)

要求次數(shù)不超過2n+1的插值多項(xiàng)式，使得

仿照拉格朗日插值，令

其中，是量組基函數(shù)，為2n+1次，且滿足

利用拉格朗日插值基函數(shù)可求出。（詳見黑板）

容易證明，埃爾米特插值多項(xiàng)式是唯一的，且余項(xiàng)為

實(shí)際常用兩點(diǎn)三次埃爾米特插值（即n=1），用矩陣表示為其中，，。

對(duì)于節(jié)點(diǎn)比較多時(shí)，可分段三次埃爾米特插值。（略，詳見50）例3

求滿足的插值多項(xiàng)式，及余項(xiàng)表達(dá)式。（見黑板）

例4

設(shè)是Hermite插值基函數(shù)，證明：（見黑板）2.6分段低次插值

高次插值有時(shí)會(huì)發(fā)生所謂的龍格(Runge)現(xiàn)象。例如在上解析。在[-5,5]上取n+1個(gè)等距節(jié)點(diǎn)作Lagrange插值龍格證明了，當(dāng)時(shí)，只在時(shí)，當(dāng)時(shí)，發(fā)散。（如圖，見黑板）

鑒于此，實(shí)際上很少使用6、7次以上插值。可用分段低次插值。下面只介紹最簡(jiǎn)單的分段線性插值，和分段Hermite插值。

從幾何上看，分段線性插值就是依次連接節(jié)點(diǎn)的折線。

設(shè)節(jié)點(diǎn)上的函數(shù)值為。記，求折線函數(shù)：在每個(gè)小區(qū)間上是線性函數(shù)則稱是分段線性插值函數(shù)。易知且有誤差估計(jì)其中，（由Lagrange插值余項(xiàng)可得）以及其中，（由page59習(xí)題5的結(jié)果可得）

可以證明，當(dāng)時(shí)，在上一致收斂到。（詳見page48）

如果還知道節(jié)點(diǎn)處的導(dǎo)數(shù)值可構(gòu)造一個(gè)導(dǎo)數(shù)連續(xù)的分段插值函數(shù)，滿足在每個(gè)小區(qū)間上是次數(shù)不超過三次的多項(xiàng)式。

上述稱為分段三次Hermite多項(xiàng)式。它的具體表達(dá)式為（由5.10，5.8，5.9）可以證明，從而有

定理3

設(shè)，則當(dāng)時(shí)，在上一致收斂到。2.7三次樣條插值（簡(jiǎn)介）

工程制圖中，把富有彈性的細(xì)木條（樣條）用壓鐵固定在樣點(diǎn)上，在其他地方讓它自由彎曲，所成曲線稱為樣條曲線。數(shù)學(xué)上，定義如下：

定義4

若函數(shù)，且在每個(gè)小區(qū)間上是次數(shù)不超過三次的多項(xiàng)式，其中，是給定節(jié)點(diǎn)，則稱是以為節(jié)點(diǎn)的三次樣條函數(shù)。若在節(jié)點(diǎn)上還滿足則稱是的三次樣條插值函數(shù)。例4

判斷下列函數(shù)是否為三次樣條函數(shù)：

注意，要確定定義4中的三次樣條插值函數(shù)，還需要加上邊界條件，如：或：等。

要求出，在每個(gè)小區(qū)間上的要確定4個(gè)待定系數(shù)，共4n個(gè)參數(shù)。

在節(jié)點(diǎn)處還要滿足連續(xù)性（光滑性）條件：共有3(n-1)個(gè)條件。再滿足共有4n-2個(gè)條件。還需要2個(gè)條件，通常在區(qū)間端點(diǎn)上各加一個(gè)（邊界）條件，常見的有3種：特別的，（自然邊界條件）

（3）當(dāng)是以為周期的周期函數(shù)時(shí)，要求也是周期函數(shù)。邊界滿足：但此時(shí)，，并稱此時(shí)的為周期樣條函數(shù)。

根據(jù)上述條件，利用分段三次Hermite插值(此處假定)可得關(guān)于的一個(gè)三對(duì)角線性方程組（具體過程略，見54）。轉(zhuǎn)化為(7.8)式?？捎米汾s法解之。

關(guān)于它的誤差界與收斂性，見定理4（page57），效果極佳。Ch3函數(shù)逼近與快速傅里葉變換3.1基本概念及預(yù)備知識(shí)線性空間，基，維數(shù)。如（n維向量空間）（次數(shù)不超過n的多項(xiàng)式空間，n+1維）（區(qū)間[a，b]上連續(xù)函數(shù)空間，無限維）定理1

（Weierstrass定理）設(shè)，則即在[a，b]上一致成立。伯恩斯坦多項(xiàng)式（1912年給出）

其中滿足Weierstrass定理要求，但收斂很慢。此外，以及

定義2

設(shè)S線性空間，，定義一實(shí)值函數(shù)，它滿足：等號(hào)成立當(dāng)且僅當(dāng)則稱是S上的范數(shù)。S與稱賦范線性空間。中常用范數(shù)

（-范數(shù)，最大范數(shù)）

（1-范數(shù)）

（2-范數(shù)）中常用范數(shù)

定義3

設(shè)X是數(shù)域K（R或C）上的線性空間，，定義內(nèi)積滿足：等號(hào)成立當(dāng)且僅當(dāng)X連同稱為內(nèi)積空間。若，稱u，v正交。定理2

（Cauchy-Schwarz定理）

定理3

設(shè)（內(nèi)積空間），則Gram矩陣非奇異的充要條件是線性無關(guān)。（證明見黑板）由內(nèi)積可誘導(dǎo)出一個(gè)范數(shù)：

例1

的內(nèi)積誘導(dǎo)出2-范數(shù)加權(quán)內(nèi)積對(duì)應(yīng)導(dǎo)出范數(shù)中的內(nèi)積

定義4

設(shè)[a，b]（可以是無限）上的非負(fù)函數(shù)滿足：（1）存在有限；（2）對(duì)[a，b]上的非負(fù)連續(xù)函數(shù)，若有則稱為[a，b]上的一個(gè)權(quán)函數(shù)。例2C[a，b]上內(nèi)積

導(dǎo)出范數(shù)當(dāng)，則3.2正交多項(xiàng)式

定義5

若

則稱在[a，b]上帶權(quán)正交。若函數(shù)族滿足：

則稱是[a，b]上帶權(quán)的正交函數(shù)族。又若，則稱為標(biāo)準(zhǔn)正交函數(shù)族。三角函數(shù)族：1，cosx，sinx，cos2x，sin2x，……是上的正交函數(shù)族。

特別的，當(dāng)是n次多項(xiàng)式時(shí)，則稱是[a，b]上帶權(quán)的n次正交多項(xiàng)式。對(duì)于利用Schmidt正交化構(gòu)造正交多項(xiàng)式這里的滿足：（1）是首一的n次多項(xiàng)式。（2）任一n次多項(xiàng)式均可表為

（3）當(dāng)時(shí)，，且與任一次數(shù)小于k的多項(xiàng)式正交。（4）遞推公式其中（證明略）

（5）[a，b]上帶權(quán)正交多項(xiàng)式在（a，b）內(nèi)恰有n個(gè)不同實(shí)根。（證明略）

特別的，取[a，b]=[-1，1]，，則上述稱勒讓德多項(xiàng)式，記，用導(dǎo)數(shù)可表示為（1814年由羅德利克給出）注意，它不是首一的，首一的Legendre多項(xiàng)式~Legendre多項(xiàng)式具有下列性質(zhì)：（1）正交性：

（證明見page72）（2）奇偶性：（3）遞推關(guān)系：（證明見黑板）（4）在[-1，1]內(nèi)有n個(gè)不同實(shí)零點(diǎn)。利用遞推關(guān)系可得：

取，此時(shí)正交化得到的稱為切比雪夫（Chebyshev）多項(xiàng)式。切比雪夫多項(xiàng)式用三角函數(shù)表為（不是首一的）：切比雪夫多項(xiàng)式滿足：（5）遞推關(guān)系：事實(shí)上，

由此可得，（6）在[-1，1]上帶權(quán)正交，且事實(shí)上，令

（7）只含x的偶次冪，只含x的奇次冪。

（8）在[-1，1]上的n個(gè)零點(diǎn)為實(shí)用上，可用表示為還有其他正交多項(xiàng)式：1、第二類切比雪夫多項(xiàng)式取令第二類切比雪夫多項(xiàng)式具有遞推公式：2、拉蓋爾多項(xiàng)式取區(qū)間，權(quán)函數(shù)。遞推公式：3、埃爾米特多項(xiàng)式取區(qū)間，權(quán)函數(shù)。遞推公式：3.3最佳一致逼近多項(xiàng)式設(shè)，求s.t.這就是最佳一致逼近或切比雪夫逼近問題。

定義7

設(shè)稱為與在[a，b]上的偏差。稱為在[a，b]上的最小偏差。

定義8

設(shè)，若存在s.t.，則稱是在[a，b]上的最佳一致逼近多項(xiàng)式（最小偏差逼近多項(xiàng)式），簡(jiǎn)稱最佳逼近多項(xiàng)式。最佳逼近多項(xiàng)式總是存在的，即

定理4

設(shè)，則存在s.t.（證明略）

定義9

設(shè)，若在處有則稱是的偏差點(diǎn)。

當(dāng)時(shí)，稱“正”偏差點(diǎn)。

當(dāng)時(shí)，稱“負(fù)”偏差點(diǎn)。介值定理保證偏差點(diǎn)總是存在的。

定理5

是的最佳逼近多項(xiàng)式的充分必要條件是：在[a，b]上至少有n+2個(gè)輪流為“正”，“負(fù)”的偏差點(diǎn)。即有n+2個(gè)點(diǎn)使得并稱為切比雪夫交錯(cuò)點(diǎn)組。（只證充分性，見黑板）

推論若，則在中存在唯一的最佳逼近多項(xiàng)式。（證明略）

定理6

在[-1，1]上所有最高次系數(shù)為1的n次多項(xiàng)式中，與零的偏差最小。（證明見黑板）

例3

求在[-1，1]上的最佳2次逼近多項(xiàng)式。（見黑板）

一般來說，要求最佳逼近多項(xiàng)式是困難的，但在一定條件下的最佳1次逼近多項(xiàng)式是容易的。（詳見黑板）

例4

求在[0，1]上最佳1次逼近多項(xiàng)式。（見黑板）

例5

求在[0，1]上1次最佳平方逼近多項(xiàng)式。解法方程得故平方誤差最大誤差用正交函數(shù)族作最佳平方逼近。為正交函數(shù)族，則故均方誤差

定理9

在[-1，1]上所有最高次系數(shù)為1的n次多項(xiàng)式中，首一的Legendre多項(xiàng)式與零的偏差最小。（證明見黑板）

例5

求在[-1，1]上的三次最佳平方逼近多項(xiàng)式。（見黑板）當(dāng)區(qū)間為[a，b]時(shí)，可作變換將區(qū)間化為[-1，1]，用Legendre多項(xiàng)式逼近。3.5曲線擬合的最小二乘法

給定的一組值要求使得誤差平方和這里的也可以加權(quán)平方和記令記則稱法方程，記注意，可能是奇異的。

定義10

設(shè)的任意線性組合在點(diǎn)集上至多只有n個(gè)不同的零點(diǎn)，則稱在點(diǎn)集上滿足哈爾（Haar）條件。

顯然，在任意個(gè)點(diǎn)上滿足哈爾條件。

可以證明，當(dāng)在滿足哈爾條件時(shí)，法方程唯一解。

當(dāng)時(shí)，稱線性擬合，當(dāng)時(shí)，是病態(tài)的。

某些擬合可通過適當(dāng)變換化為線性的，如取對(duì)數(shù)得具體算例見page94例7、例8。（略）

注：曲線擬合的最小二乘法即為超定線性方程的最小二乘解（取）。（ch5中介紹）

結(jié)束Ch4數(shù)值積分與數(shù)值微分4.1引言

積分的計(jì)算，有著名的Newton-Leibniz公式：本公式在理論上有重大意義，但在實(shí)際使用中往往是困難的。因?yàn)榈脑瘮?shù)通常不易得到，甚至只是一張數(shù)表。為此，我們有必要研究積分的數(shù)值計(jì)算問題，比如：梯形公式：（中）矩形公式：

一般的，數(shù)值積分具有下列形式：其中，稱為求積節(jié)點(diǎn)，稱為求積系數(shù)（也稱為節(jié)點(diǎn)的權(quán)），它僅與有關(guān)，而與無關(guān)。

關(guān)于數(shù)值積分的精度問題我們引入：

定義1

如果某個(gè)求積公式對(duì)所有不高于m次的多項(xiàng)式準(zhǔn)確成立，而對(duì)某個(gè)m+1次多項(xiàng)式不準(zhǔn)確成立，則稱該公式具有m次代數(shù)精度。

事實(shí)上，只要對(duì)準(zhǔn)確成立，而對(duì)不準(zhǔn)確成立即可。

不難驗(yàn)證，T及R都為一次代數(shù)精度。例1

確定，使得的代數(shù)精度盡可能高。（見黑板）

構(gòu)造求積公式的最基本方法是所謂插值型的求積公式。設(shè)給定節(jié)點(diǎn)

以插值函數(shù)近似代替，則

記，則稱為插值型求積公式。插值型求積公式的余項(xiàng)

定理1求積公式至少具有n次代數(shù)精度的充分必要條件它是插值型求積公式。（證明見黑板）

定理2若求積公式中系數(shù)，則此公式是穩(wěn)定的。（證明是簡(jiǎn)單的，略，見page122）4.2牛頓-柯特斯公式

牛頓-柯特斯求積公式是將積分區(qū)間[a，b]n等分。（具體推導(dǎo)見黑板）則這就是Newton-Cotes公式。其中，稱為柯特斯系數(shù)，它只與n有關(guān)，與[a，b]及無關(guān)。特別地，當(dāng)n=1，即梯形公式。當(dāng)n=2，，即Simpson公式，也稱拋物線公式。當(dāng)n=4，并稱為柯特斯公式。

書中表4-1（page124）給出了n=1~8的柯特斯系數(shù)。

注意，當(dāng)時(shí)，出現(xiàn)負(fù)值，此時(shí)不能保證求積公式的穩(wěn)定性。

定理3當(dāng)n為偶數(shù)時(shí)，牛頓-柯特斯求積公式至少具有n+1次代數(shù)精度。

（證明見黑板）

特別地，Simpson公式具有三次代數(shù)精度。

利用積分中值定理，我們可得到（過程略）梯形公式的余項(xiàng)Simpson公式的余項(xiàng)Cotes公式的余項(xiàng)4.3復(fù)化求積公式（1）復(fù)化梯形公式。

將[a，b]n等分，分點(diǎn)在每個(gè)小區(qū)間上采用梯形公式，則記并稱為復(fù)化梯形公式。

不難證明，其余項(xiàng)為由此可知，

由于的求積系數(shù)為正，故數(shù)值計(jì)算穩(wěn)定。（2）復(fù)化Simpson公式。將[a，b]n等分，在每個(gè)小區(qū)間上采用Simpson公式，記，則記并稱為復(fù)化Simpson公式。

其余項(xiàng)為顯然，且數(shù)值計(jì)算穩(wěn)定。（具體算例見page130例1，略）類似可得：(3)復(fù)化Cotes公式。4.4龍貝格求積公式由假定，則有于是，（誤差的事后估計(jì)）令可以期望其結(jié)果更好。事實(shí)上，類似的，

進(jìn)一步，并稱為Romberg公式。一般的，也稱為Romberg公式。

注意，當(dāng)時(shí)，Romberg公式已不屬于Newton-Cotes公式的范疇。逐步二分的Romberg算法可列表（見黑板）。

例2

用Romberg算法計(jì)算（二分4次）。（見黑板）4.5高斯求積公式

在求積公式中，適當(dāng)選擇節(jié)點(diǎn)有望提高其代數(shù)精度。更一般的，考慮帶權(quán)函數(shù)的插值型求積公式

例3帶權(quán)的插值型求積公式，其代數(shù)精度最高不超過2n+1次。（見黑板）

定義4如果求積公式具有2n+1次代數(shù)精度，則稱節(jié)點(diǎn)為高斯點(diǎn)，相應(yīng)的公式稱為高斯公式。

例4

構(gòu)造下列的高斯求積公式：（見黑板）

定理5插值型求積公式的節(jié)點(diǎn)是高斯點(diǎn)的充分必要條件是與任何次數(shù)不超過n次的多項(xiàng)式帶權(quán)正交，即（證明見黑板）高斯求積公式的余項(xiàng)為

定理5等價(jià)于：

插值型求積公式的節(jié)點(diǎn)是高斯點(diǎn)的充分必要條件是它是積分區(qū)間上帶權(quán)的n+1次的正交多項(xiàng)式的零點(diǎn)。

高斯求積公式是穩(wěn)定的（定理6及其推論），也是收斂的（定理7）。

對(duì)于，積分區(qū)間[-1，1]，由于勒讓德多項(xiàng)式在[-1，1]上正交，故的零點(diǎn)即為高斯點(diǎn)。比如（兩點(diǎn)高斯-勒讓德求積公式）

注意，對(duì)于一般的積分區(qū)間[a，b]，可作變換而將積分區(qū)間化為[-1，1]。（三點(diǎn)高斯-勒讓德求積公式）（四、五點(diǎn)的見page145表4-7）高斯-勒讓德求積公式的余項(xiàng)為當(dāng)n=1時(shí)，

對(duì)于，積分區(qū)間[-1，1]，由于切比雪夫多項(xiàng)式在[-1，1]上帶權(quán)正交，故的零點(diǎn)即為高斯點(diǎn)。進(jìn)一步可算得

為方便計(jì)，用n個(gè)節(jié)點(diǎn)寫出高斯-切比雪夫求積公式：其余項(xiàng)

例5

用三點(diǎn)高斯-切比雪夫公式計(jì)算：（見黑板）4.6數(shù)值微分（簡(jiǎn)介）

最簡(jiǎn)單的數(shù)值微分是用差商近似代替微商，如（中點(diǎn)公式）

中點(diǎn)公式誤差階為，即對(duì)二次多項(xiàng)式精確成立。記由得

從截?cái)嗾`差看，h越小越好，但從舍入誤差看，h太小，有效數(shù)字嚴(yán)重?fù)p失。

若令與的舍入誤差為，，則計(jì)算的舍入誤差限從而計(jì)算的誤差限：取為最優(yōu)步長(zhǎng)。

完Ch5線性方程組的直接解法5.1引言與預(yù)備知識(shí)（略）5.2高斯消去法

高斯消去法是解線性方程組的古老而有效的方法之一。這里只是將這一方法公式化，程序化罷了。（具體略）

下面我們用高斯消去法的矩陣表寫來給出矩陣的三角分解。

設(shè)系數(shù)矩陣A的各順序主子式都不為零（這是高斯消去法能進(jìn)行的充分條件）。原方程經(jīng)過第一次消元得，相當(dāng)于左乘矩陣即

一般的，經(jīng)第k次消元得相當(dāng)于左乘矩陣即依次下去，最后得到記上三角矩陣，則其中為單位下三角矩陣。

定理7

（矩陣的LU分解）設(shè)A為n階矩陣，如果A的直到n-1階順序主子式不為零，則A可分解為一個(gè)單位下三角矩陣L和一個(gè)上三角矩陣U的乘積，且分解法唯一。

（只要證明唯一性，見黑板）5.3高斯主元素消去法（簡(jiǎn)介）

通過一個(gè)算例說明高斯列主元素消去法。例1

用高斯列主元素消去法解線性方程組（見黑板）

再通過一個(gè)算例說明高斯-約當(dāng)消去法。例2

用高斯-約當(dāng)消去法解線性方程組（見黑板）

當(dāng)然，在高斯-約當(dāng)消元之前也可以先選列主元。5.4矩陣三角分解法

主要介紹直接三角分解法（杜利特爾分解法），對(duì)稱正定方程組的喬累斯基分解法，三對(duì)角線方程組的追趕法。1、直接三角分解法

若有A=LU，則方程組Ax=b化為L(zhǎng)Ux=b。令LUx=b。由Ly=b

解出y。再由Ux=y解出x。其中

從A的元素可直接給出計(jì)算L，U的元素的遞推公式。（詳細(xì)見黑板）

上述的三角分解稱為杜利特爾（Doolittle）分解法。

如果取L為下三角矩陣，U為單位上三角矩陣，則類似可得A的三角分解A=LU，并稱為克魯特（Crout）分解法。例3

用Doolittle分解法求解（見黑板）2、喬累斯基分解法

當(dāng)方程組Ax=b的系數(shù)矩陣為正定矩陣時(shí)，則A的三角分解可以進(jìn)一步簡(jiǎn)化。

定理10

（對(duì)稱矩陣的三角分解）設(shè)A為n階對(duì)稱矩陣，且A的各順序主子式都不為零，則A可唯一分解為其中L為單位下三角矩陣，D為對(duì)角陣。（證明見黑板）

定理11

（對(duì)稱正定矩陣的Cholesky分解）

設(shè)A為n階對(duì)稱正定矩陣，則存在一個(gè)實(shí)的非奇異下三角矩陣L，使得當(dāng)限定L的對(duì)角元為正時(shí)，分解是唯一的。（證明見黑板）

下面給出L的元素的計(jì)算遞推公式。（詳細(xì)見黑板）3、追趕法設(shè)三對(duì)角線方程組簡(jiǎn)記為Ax=f。

當(dāng)其系數(shù)矩陣滿足所謂的“對(duì)角占優(yōu)”條件時(shí)，即則用高斯消去法或杜利特爾（克魯特）分解法求解此方程組時(shí)，可略去許多的中間步驟（但計(jì)算機(jī)不會(huì)?。?。

為此，直接給出“化簡(jiǎn)后的克魯特分解法”——追趕法。

設(shè)A=LU，即令

比較即得容易驗(yàn)證，在對(duì)角占優(yōu)條件下，故有遞推公式

求解Ax=f等價(jià)于求解Ly=f及Ux=y。解Ly=f得解Ux=y得

這就是追趕法。其中稱計(jì)算及的過程為“追”。稱計(jì)算的過程為“趕”。

追趕法的計(jì)算量很小，大約為8n次乘除法，而且數(shù)值是穩(wěn)定的。5.5向量和矩陣范數(shù)

定義2

如果向量的某個(gè)實(shí)值函數(shù)

滿足：

則稱是上的一個(gè)向量范數(shù)。等號(hào)成立當(dāng)且僅當(dāng)中常用范數(shù)

（-范數(shù)，最大范數(shù)）

（1-范數(shù)）

（2-范數(shù)）

（p-范數(shù)）

其中三角不等式稱Minkowski不等式。

容易證明，范數(shù)N(x)是向量x的連續(xù)函數(shù)。

向量序列的收斂性等價(jià)于（定理16）（定理14）任意兩種范數(shù)是所謂等價(jià)的，即存在常數(shù)，使得對(duì)一切，有（定理15）

定義4

如果矩陣的某個(gè)實(shí)值函數(shù)

滿足：等號(hào)成立當(dāng)且僅當(dāng)則稱是上的一個(gè)矩陣范數(shù)。

定義5

設(shè)，，給定向量范數(shù)，相應(yīng)地定義一個(gè)矩陣的實(shí)函數(shù)（可以驗(yàn)證它滿足定義4），則是上的矩陣范數(shù)，并稱為的算子范數(shù)（從屬范數(shù)）。

定理17

上述定義的確實(shí)是上的矩陣范數(shù)，且滿足下列的相容條件：（證明見黑板）

對(duì)應(yīng)于向量x的、1、2-范數(shù)，我們有常用的矩陣范數(shù)（定理18）：

（1）行范數(shù)（2）列范數(shù)（3）2-范數(shù)其中表示的最大的特征值。此外還有

（4）F-范數(shù)例4

設(shè)4階阿達(dá)瑪（Hadamard）矩陣求：，，，。（見黑板）例5

設(shè)A為n階實(shí)矩陣，證明：（證明見黑板）

定義6

設(shè)的特征值為，稱為的A的譜半徑。

定理19（特征值上界）譜半徑不超過A的任一算子范數(shù)，即。（對(duì)也成立）（證明見黑板）

定理20如果A是實(shí)對(duì)稱矩陣，則（證明見黑板）

例6

設(shè)A，B是n階實(shí)對(duì)稱矩陣，證明：

定理20如果，則非奇異，且（為算子范數(shù)）（證明見黑板）5.6誤差分析

線性方程組Ax=b中A或b通常帶有觀察誤差以及（計(jì)算過程中產(chǎn)生的）舍入誤差。下面來分析這些微小誤差對(duì)解的影響。引例7

設(shè)方程組

記為Ax=b，其精確解

現(xiàn)常數(shù)項(xiàng)帶有微小變化，考察方程組

可記為，其中其精確解為。

比較原方程組的解，變化很大。這樣的方程組稱為病態(tài)的，要引起特別注意。

定義7

如果矩陣A或常數(shù)項(xiàng)b的微小變化，引起方程組Ax=b解的巨大變化，則稱此方程組（或矩陣A）是病態(tài)的，否則是良態(tài)的。

下面我們來尋找病態(tài)的原因以及刻畫病態(tài)的度量。

設(shè)方程組Ax=b的精確解為x，先討論A是精確的，b有誤差。即方程組其解為，則故而故于是，（定理22）

這說明常數(shù)項(xiàng)的相對(duì)誤差在解中可能放大倍。

對(duì)于b是精確的，A有誤差，類似的有由此可見，刻畫病態(tài)的程度。

定義8

設(shè)A是非奇異矩陣，稱為矩陣A的條件數(shù)。常用的條件數(shù)：當(dāng)A為對(duì)稱矩陣時(shí)，條件數(shù)具有下列性質(zhì)：（3）若A為正交矩陣，則例8

求三階Hilbert矩陣的條件數(shù)：解：類似可得可見高階Hilbert矩陣是嚴(yán)重病態(tài)的。

對(duì)于病態(tài)方程組可采用高精度，或用同解變換以減少系數(shù)矩陣的條件數(shù)，也可用“迭代改善法”。

一般的，當(dāng)（1）A的三角約化時(shí)出現(xiàn)小主元；（2）A的行列式值很小或某些行近似線性相關(guān)；（3）A的元素差異很大且無規(guī)則時(shí)，通常A是病態(tài)的。

例9

方程組系數(shù)矩陣A的條件數(shù)

用列主元素消去法（計(jì)算到三位數(shù)字）得很壞的結(jié)果其同解方程組系數(shù)矩陣B的條件數(shù)

也用列主元素消去法（計(jì)算到三位數(shù)字）得很好的結(jié)果迭代改善法簡(jiǎn)介：先從解得近似解，記。再解得近似解。最后改善?？芍貜?fù)進(jìn)行。當(dāng)是精確解時(shí)，則由知道是的精確解。

注意：嚴(yán)重病態(tài)時(shí)，迭代法可能不收斂。5.7矩陣的正交三角化及應(yīng)用1、初等反射陣其中，也稱Householder矩陣（變換）。H是對(duì)稱正交矩陣。（定理25）Householder變換的幾何意義（見黑板）。2、平面旋轉(zhuǎn)矩陣（變換）也稱Givens變換。顯然，P是正交矩陣。3、矩陣的QR分解

定理30（矩陣的QR分解）

（1）設(shè)，且列滿秩，則其中R為非奇異上三角陣。

（2）設(shè)，且滿秩，則有。其中Q為正交矩陣，R為上三角陣。當(dāng)R具有正對(duì)角元時(shí)，分解法唯一。

定理31（Givens變換的QR分解）設(shè)為非奇異，則（1）R為上三角陣。（2）Q為正交矩陣。當(dāng)R具有正對(duì)角元時(shí)，分解法唯一。4、求解超定線性方程組

設(shè)超定線性方程組令

為殘差向量，求使得即關(guān)于x求導(dǎo)，并令其為零，得即（稱為法方程組）

容易證明，為對(duì)稱正定矩陣。

法方程組有唯一解這就是超定線性方程組的最小二乘解。

例10

求超定線性方程組的最小二乘解。其中（見黑板）

值得注意的是，法方程組往往是病態(tài)的。可利用矩陣的QR分解直接從原超定方程組解得最小二乘解。

利用正交約化定理，選擇初等反射陣同時(shí)令，為正交陣，則且故當(dāng)為的解時(shí)，有此時(shí)，由得（算例見page227例12，略）

結(jié)束Ch6線性方程組的迭代法6.1引言

設(shè)線性方程組，是其精確解，所謂迭代法是構(gòu)造序列并按某種精度要求取k，以近似代替。

常見的有雅可比迭代法、高斯-塞德爾迭代法、超松弛迭代法。引例1

設(shè)線性方程組其精確解為。將原方程組改寫為建立迭代格式取初值，可計(jì)算得已很接近精確解。一般的，迭代格式用矩陣可表示為并賦予初值。

稱為迭代矩陣，為常向量（它們與k無關(guān)，稱為定常迭代）。

迭代法中需要考慮的問題是：

（1）什么樣的迭代格式及初值保證。

（2）精度如何說明。

（3）收斂時(shí)，收斂速度的快慢。6.2基本迭代法

設(shè)，其中為非奇異矩陣，令，其中非奇異，得或于是，由此構(gòu)造一階定常迭代格式：令，則

這就是Jacobi迭代法。其中。若引進(jìn)記號(hào)則Jacobi迭代格式可寫為具體的，Jacobi迭代格式為引例1的迭代法是Jacobi迭代。

在Jacobi迭代格式中，將用來代替，可得這就是Gauss-Seidel迭代法。（也稱異步迭代）

下面給出Gauss-Seidel迭代法的矩陣表示。

設(shè)，代入得即得迭代格式或由得

例2

用Gauss-Seidel迭代法求解解：迭代公式取初值，可計(jì)算得

比較即知，G-S迭代比J-迭代收斂更快。注意：此結(jié)論一般不成立。

下面給出逐次超松弛迭代法（S.O.R）。

作為G-S迭代的一種加速法，它由S.P.Frankel及D.Young于五十年代提出。

由G-S迭代引入加速迭代公式（加權(quán)平均）代入即得這就是逐次超松弛迭代法。（其中稱為松弛因子）

當(dāng)時(shí)，S.O.R即為G-S迭代。取時(shí)，稱為超松弛。取時(shí)，稱為亞（低）松弛。統(tǒng)稱超松弛。

下面給出S.O.R迭代的矩陣表示。即得故

關(guān)于松弛因子的確定無一般方法，可以試驗(yàn)，如等。6.3迭代法的收斂性

向量序列的收斂是指按分量收斂，同樣，矩陣序列的收斂是指按元素收斂。例4矩陣序列當(dāng)時(shí)，定理1（證明是簡(jiǎn)單的，略）定理2對(duì)任意向量，有（證明見黑板）定理3設(shè)，則（證明要用到Jardon標(biāo)準(zhǔn)形，參見p245，略）

定理4（迭代法基本定理）一階線性定常迭代對(duì)于任意初始向量迭代收斂的充分必要條件是（證明見黑板）

推論J-迭代、G-S迭代、SOR迭代收斂的充分必要條件是它們的迭代矩陣的譜半徑小于1。例5討論方程組的J-迭代、G-S迭代的收斂性。（見黑板）

一般的，求譜半徑是困難的，由于，只要某一個(gè)算子范數(shù)，則迭代收斂，具體地我們有下述定理。

定理5設(shè)方程組及一階線性定常迭代。若的某種算子范數(shù)，則（1）迭代法收斂，即對(duì)任給初始向量，有且（2）

（3）

（4）（證明見黑板）

定理5的結(jié)論(3)說明用描述迭代精度是合理的。可以用來控制迭代次數(shù)。結(jié)論(4)可預(yù)計(jì)所需要迭代次數(shù)。

當(dāng)方程組的系數(shù)矩陣為對(duì)角占優(yōu)或?qū)ΨQ正定時(shí)，我們可直接從知道常用迭代的收斂性。定義3（1）若矩陣的元素滿足則稱嚴(yán)格對(duì)角占優(yōu)；

（2）若矩陣的元素滿足且至少有一個(gè)不等式嚴(yán)格成立，則稱弱對(duì)角占優(yōu)；

定義4若矩陣的元素經(jīng)若干次行列重排可化為，則稱是可約矩陣，否則稱不可約的。

定理6若是嚴(yán)格對(duì)角占優(yōu)，或不可約弱對(duì)角占優(yōu)，則非奇異。（證明，略）

定理7若是嚴(yán)格對(duì)角占優(yōu)，或不可約弱對(duì)角占優(yōu)，則解方程組的J-迭代與G-S迭代均收斂。（證明略）

定理8

（SOR迭代收斂的必要條件）設(shè)方程組的SOR迭代收斂，則。（證明見黑板）

定理10若是嚴(yán)格對(duì)角占優(yōu)，或不可約弱對(duì)角占優(yōu)，則當(dāng)時(shí)，解方程組的SOR迭代收斂。

定理9若是對(duì)稱正定方程組，則SOR迭代收斂。（證明略）（證明略）

例6

若是n階非奇異矩陣，則通過同解變換總可以用G-S方法求解。（見黑板）Ch7非線性方程求根7.1方程求根與二分法（略）7.2迭代法及其收斂性

將方程改寫為等價(jià)形式，若，則稱為函數(shù)的一個(gè)不動(dòng)點(diǎn)。

建立迭代公式，并選擇初值，若，則稱迭代公式收斂，即為函數(shù)的一個(gè)不動(dòng)點(diǎn)。故也稱不動(dòng)點(diǎn)迭代法。例1

方程改寫成建立迭代公式取，計(jì)算到可作為方程的近似根。

但若改寫成，建立迭代公式取，迭代顯然發(fā)散。

定理1

設(shè)滿足：（映內(nèi)性）（壓縮性）則在上存在唯一的不動(dòng)點(diǎn)。（證明見黑板）

定理2

在定理1的條件下，，有并有誤差估計(jì)（證明見黑板）

此外，還有

一般的，L不易知道，條件（2）常用

代替。

定義1

設(shè)是的不動(dòng)點(diǎn)，若迭代序列，且收斂到，則稱迭代法局部收斂。

定理3

設(shè)是的不動(dòng)點(diǎn)，在的某領(lǐng)域連續(xù)，且,則迭代局部收斂。

（證明是簡(jiǎn)單的）

例2

方程，其根為，構(gòu)造下列迭代法：（1），則（事實(shí)上，此迭代發(fā)散）

（2），則

（此迭代也發(fā)散）

（3），則（4），則（3），（4）均收斂，但（4）更快（結(jié)果見page271）

定義2

設(shè)迭代收斂到的不動(dòng)點(diǎn)，記迭代誤差，如果

則稱迭代是p階收斂的。p=1時(shí)，稱線性收斂；p>1時(shí)，稱超線性收斂；特別當(dāng)p=2時(shí)，稱平方收斂。

定理4

設(shè)迭代，如果在的某領(lǐng)域連續(xù)，且

則迭代在附近是p階收斂的。（證明見黑板）

例3迭代法收斂于，問迭代是幾階收斂的。（見黑板）7.3迭代收斂的加速方法

（1）埃特金加速方法設(shè)，由中值定理假設(shè)（變化不大），則相除得得記稱埃特金加速方法?？梢宰C明的收斂速度比更快。

（2）斯蒂文森加速方法

把埃特金加速方法用到不動(dòng)點(diǎn)迭代：這便是Steffensen迭代。

它只是“二合一”的不動(dòng)點(diǎn)迭代。Steffensen迭代也可寫為其中

定理5

若是的不動(dòng)點(diǎn)，則也是的不動(dòng)點(diǎn)。反之，若是的不動(dòng)點(diǎn)，又存在，且，則是的不動(dòng)點(diǎn)，且Steffensen迭代是二階的。（證明，略）

例1中迭代公式是發(fā)散的。但用Steffensen迭代是收斂的。（計(jì)算結(jié)果見page275）。

更進(jìn)一步，若原迭代是p階收斂的，則Steffensen迭代是p+1階收斂的。（證略）7.4牛頓法

對(duì)于方程，若，構(gòu)造迭代這就是牛頓迭代法（也稱切線法）。（見黑板圖）牛頓法的迭代函數(shù)

設(shè)是的單根，即從而，故牛頓法至少是平方收斂的。且由得例4用牛頓法解二次方程得迭代公式對(duì)于任意，可證明（page278)如求，取，可計(jì)算得（具有精度）從，得，建立迭代公式迭代函數(shù)為若，即，則迭代法局部收斂。取，得稱簡(jiǎn)化的牛頓法（也稱平行弦法）。（見黑板圖）

注意，牛頓法或簡(jiǎn)化牛頓法對(duì)某些初值可能發(fā)散。為此，附加條件：滿足此單調(diào)性條件的算法稱下山法。對(duì)于Newton迭代作加權(quán)平均（，稱下山因子），代入即得Newton下山法：

對(duì)于的選擇可以從逐次減半試算直到滿足單調(diào)性要求。Newton法也適用重根情形。（詳見黑板）7.5弦截法與拋物線法

在Newton法中，以差商代替微商，即得弦截法：此方法需要給出雙初值，。定理6說明，弦截法是超線性收斂的，（拋物線法略）7.6解非線性方程組的Newton迭代法設(shè)非線性方程組記則方程組簡(jiǎn)記為。

利用多元函數(shù)的泰勒展開（取線性部分），有由得構(gòu)造迭代公式：這也是Newton迭代法。并稱為Jacobi矩陣。結(jié)束Ch8矩陣特征值問題計(jì)算8.1引言

如果矩陣A有一個(gè)重?cái)?shù)為k的特征值而對(duì)應(yīng)的特征向量線性無關(guān)的個(gè)數(shù)少于k，則稱A是虧損矩陣。此時(shí)A不可對(duì)角化。虧損矩陣的理論和計(jì)算都是困難的。關(guān)于特征值界的估計(jì)有下列的

Gerschgorin圓盤定理（1）A的每一個(gè)特征值必屬于下述某個(gè)圓盤之中（復(fù)平面中）

（2）如果A有m個(gè)圓盤組成一個(gè)連通的并集S，且S與余下的n-m個(gè)圓盤是分離的，則S內(nèi)恰好包含A的m個(gè)特征值。特別的，如果某個(gè)Di

與其他圓盤是分離，則Di中恰好包含A的一個(gè)特征值。例1

估計(jì)矩陣的特征值范圍。（見黑板）

矩陣經(jīng)過相似變換特征值不變。Schur定理設(shè)，則存在酉矩陣U，使得其中為A的特征值（可能是復(fù)數(shù)）。酉矩陣U滿足：

實(shí)Schur分解定理設(shè)，則存在正交矩陣Q，使得其中為一階或二階方陣，且每個(gè)一階是A的實(shí)特征值，二階的兩個(gè)特征值是A的兩個(gè)共軛復(fù)特征值。

對(duì)于實(shí)對(duì)稱矩陣，有下列結(jié)果：

定理11

設(shè)為實(shí)對(duì)稱矩陣，則（1）

（2）

（3）其中稱為對(duì)應(yīng)于向量的瑞利商。8.2冪法及反冪法

冪法是用于計(jì)算矩陣主特征值及對(duì)應(yīng)的特征向量的迭代方法。

設(shè)具有完全的特征向量組，記及分別為的特征值及對(duì)應(yīng)的特征向量，且的主特征值是實(shí)根，滿足構(gòu)造迭代向量序列設(shè)則由于故從而故當(dāng)k充分大時(shí)，有

作為的特征向量的近似值（除一個(gè)因子外）。以表示的第i個(gè)分量，則