河海大學(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ì)算的主要過(guò)程：實(shí)際問(wèn)題數(shù)學(xué)模型數(shù)值計(jì)算方法程序設(shè)計(jì)上機(jī)計(jì)算求出結(jié)果

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

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

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

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

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

誤差的來(lái)源與分類(lèi)：（1）模型誤差；（2）觀(guān)察誤差；（3）截?cái)嗾`差（也稱(chēng)方法誤差）；例如：其截?cái)嗾`差：

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

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

若該位到的第一位非零數(shù)字共有n位，就說(shuō)有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ì)誤差限，則（證明見(jiàn)黑板）

例2

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

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

例3

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

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

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

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

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

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

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

例4

利用中心差商公式計(jì)算在處的導(dǎo)數(shù)值。（詳見(jiàn)黑板）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ū)間。則稱(chēng)是的插值函數(shù)。點(diǎn)稱(chēng)為

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

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

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

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

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

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

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

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

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

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

定理1

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

證明只要證明唯一性。

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

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

定理2

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

例2

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

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

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

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

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

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

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

定義2

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

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

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

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

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

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

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

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

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

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

仿照拉格朗日插值，令

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

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

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

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

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

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

例4

設(shè)是Hermite插值基函數(shù)，證明：（見(jiàn)黑板）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ā)散。（如圖，見(jiàn)黑板）

鑒于此，實(shí)際上很少使用6、7次以上插值?？捎梅侄蔚痛尾逯?。下面只介紹最簡(jiǎn)單的分段線(xiàn)性插值，和分段Hermite插值。

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

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

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

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

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

定理3

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

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

定義4

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

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

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

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

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

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

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

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

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

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

定義2

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

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

（1-范數(shù)）

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

定義3

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

（Cauchy-Schwarz定理）

定理3

設(shè)（內(nèi)積空間），則Gram矩陣非奇異的充要條件是線(xiàn)性無(wú)關(guān)。（證明見(jià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]（可以是無(wú)限）上的非負(fù)函數(shù)滿(mǎn)足：（1）存在有限；（2）對(duì)[a，b]上的非負(fù)連續(xù)函數(shù)，若有則稱(chēng)為[a，b]上的一個(gè)權(quán)函數(shù)。例2C[a，b]上內(nèi)積

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

定義5

若

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

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

特別的，當(dāng)是n次多項(xiàng)式時(shí)，則稱(chēng)是[a，b]上帶權(quán)的n次正交多項(xiàng)式。對(duì)于利用Schmidt正交化構(gòu)造正交多項(xiàng)式這里的滿(mǎn)足：（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]，，則上述稱(chēng)勒讓德多項(xiàng)式，記，用導(dǎo)數(shù)可表示為（1814年由羅德利克給出）注意，它不是首一的，首一的Legendre多項(xiàng)式~Legendre多項(xiàng)式具有下列性質(zhì)：（1）正交性：

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

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

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

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

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

定義7

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

定義8

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

定理4

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

定義9

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

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

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

定理5

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

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

定理6

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

例3

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

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

例4

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

例5

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

定理9

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

例5

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

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

定義10

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

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

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

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

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

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

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

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

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

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

定義1

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

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

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

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

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

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

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

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

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

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

書(shū)中表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ù)精度。

（證明見(jiàn)黑板）

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

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

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

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

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

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

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

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

例2

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

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

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

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

例4

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

定理5插值型求積公式的節(jié)點(diǎn)是高斯點(diǎn)的充分必要條件是與任何次數(shù)不超過(guò)n次的多項(xiàng)式帶權(quán)正交，即（證明見(jià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)的見(jià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ě)出高斯-切比雪夫求積公式：其余項(xiàng)

例5

用三點(diǎn)高斯-切比雪夫公式計(jì)算：（見(jiàn)黑板）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線(xiàn)性方程組的直接解法5.1引言與預(yù)備知識(shí)（略）5.2高斯消去法

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

下面我們用高斯消去法的矩陣表寫(xiě)來(lái)給出矩陣的三角分解。

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

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

定理7

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

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

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

用高斯列主元素消去法解線(xiàn)性方程組（見(jiàn)黑板）

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

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

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

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

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

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

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

上述的三角分解稱(chēng)為杜利特爾（Doolittle）分解法。

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

用Doolittle分解法求解（見(jiàn)黑板）2、喬累斯基分解法

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

定理10

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

定理11

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

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

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

當(dāng)其系數(shù)矩陣滿(mǎn)足所謂的“對(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得

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

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

定義2

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

滿(mǎn)足：

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

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

（1-范數(shù)）

（2-范數(shù)）

（p-范數(shù)）

其中三角不等式稱(chēng)Minkowski不等式。

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

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

定義4

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

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

定義5

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

定理17

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

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

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

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

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

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

定義6

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

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

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

例6

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

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

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

設(shè)方程組

記為Ax=b，其精確解

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

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

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

定義7

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

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

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

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

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

定義8

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

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

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

一般的，當(dāng)（1）A的三角約化時(shí)出現(xiàn)小主元；（2）A的行列式值很小或某些行近似線(xiàn)性相關(guān)；（3）A的元素差異很大且無(wú)規(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、初等反射陣其中，也稱(chēng)Householder矩陣（變換）。H是對(duì)稱(chēng)正交矩陣。（定理25）Householder變換的幾何意義（見(jiàn)黑板）。2、平面旋轉(zhuǎn)矩陣（變換）也稱(chēng)Givens變換。顯然，P是正交矩陣。3、矩陣的QR分解

定理30（矩陣的QR分解）

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

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

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

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

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

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

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

例10

求超定線(xiàn)性方程組的最小二乘解。其中（見(jiàn)黑板）

值得注意的是，法方程組往往是病態(tài)的?？衫镁仃嚨腝R分解直接從原超定方程組解得最小二乘解。

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

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

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

常見(jiàn)的有雅可比迭代法、高斯-塞德?tīng)柕?、超松弛迭代法。引?

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

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

迭代法中需要考慮的問(wèn)題是：

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

（2）精度如何說(shuō)明。

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

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

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

在Jacobi迭代格式中，將用來(lái)代替，可得這就是Gauss-Seidel迭代法。（也稱(chēng)異步迭代）

下面給出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)平均）代入即得這就是逐次超松弛迭代法。（其中稱(chēng)為松弛因子）

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

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

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

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

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

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

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

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

（3）

（4）（證明見(jiàn)黑板）

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

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

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

定義4若矩陣的元素經(jīng)若干次行列重排可化為，則稱(chēng)是可約矩陣，否則稱(chē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迭代收斂，則。（證明見(jiàn)黑板）

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

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

例6

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

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

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

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

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

定理1

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

定理2

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

此外，還有

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

代替。

定義1

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

定理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é)果見(jiàn)page271）

定義2

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

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

定理4

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

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

例3迭代法收斂于，問(wèn)迭代是幾階收斂的。（見(jiàn)黑板）7.3迭代收斂的加速方法

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

（2）斯蒂文森加速方法

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

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

定理5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定理11

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

（2）

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

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

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

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