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

數(shù)值分析

編者李慶揚等

課件董祖引

Ch1緒論1.1數(shù)值分析研究對象與特點

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

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

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

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

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

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

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

誤差的來源與分類：（1）模型誤差；（2）觀察誤差；（3）截斷誤差（也稱方法誤差）；例如：其截斷誤差：

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

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

若該位到的第一位非零數(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ù)字，則相對誤差限至少具有n位有效數(shù)字。反之，若的相對誤差限，則（證明見黑板）

例2

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

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

例3

測量得某場地長l的值為m，寬d

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

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

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

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

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

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

例4

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

例5

計算多項式的值。

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

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

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

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

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

若是分段多項式，則稱分段多項式插值。

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

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

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

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

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

若引入記號則拉格朗日插值多項式可寫成如下的緊湊形式：例1

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

定理1

滿足插值條件的n次插值多項式是存在唯一的。

證明只要證明唯一性。

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

關(guān)于截斷誤差，也稱拉格朗日插值余項，我們有

定理2

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

例2

已給sin0.32=0.314567，sin0.34=0.333487，sin0.36=0.352274，試用拋物插值計算sin0.3367，并估計截斷誤差。（見黑板）

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

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

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

牛頓插值法的思想是將插值多項式表寫成

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

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

定義2

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

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

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

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

具體計算時可列均差表（詳見黑板）。

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

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

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

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

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

仿照拉格朗日插值，令

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

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

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

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

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

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

例4

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

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

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

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

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

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

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

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

定理3

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

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

定義4

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

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

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

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

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

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

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

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

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

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

定義2

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

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

（1-范數(shù)）

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

定義3

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

（Cauchy-Schwarz定理）

定理3

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

例1

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

定義4

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

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

定義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次多項式時，則稱是[a，b]上帶權(quán)的n次正交多項式。對于利用Schmidt正交化構(gòu)造正交多項式這里的滿足：（1）是首一的n次多項式。（2）任一n次多項式均可表為

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

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

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

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

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

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

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

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

定義7

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

定義8

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

定理4

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

定義9

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

當(dāng)時，稱“正”偏差點。

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

定理5

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

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

定理6

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

例3

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

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

例4

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

例5

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

定理9

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

例5

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

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

定義10

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

顯然，在任意個點上滿足哈爾條件。

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

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

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

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

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

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

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

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

定義1

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

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

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

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

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

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

記，則稱為插值型求積公式。插值型求積公式的余項

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

定理2若求積公式中系數(shù)，則此公式是穩(wě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)時，出現(xiàn)負(fù)值，此時不能保證求積公式的穩(wěn)定性。

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

（證明見黑板）

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

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

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

不難證明，其余項為由此可知，

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

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

進一步，并稱為Romberg公式。一般的，也稱為Romberg公式。

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

例2

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

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

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

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

例4

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

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

定理5等價于：

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

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

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

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

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

為方便計，用n個節(jié)點寫出高斯-切比雪夫求積公式：其余項

例5

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

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

中點公式誤差階為，即對二次多項式精確成立。記由得

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

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

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

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

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

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

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

定理7

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

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

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

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

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

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

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

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

若有A=LU，則方程組Ax=b化為LUx=b。令LUx=b。由Ly=b

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

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

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

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

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

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

定理10

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

定理11

（對稱正定矩陣的Cholesky分解）

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

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

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

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

設(shè)A=LU，即令

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

求解Ax=f等價于求解Ly=f及Ux=y。解Ly=f得解Ux=y得

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

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

定義2

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

滿足：

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

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

（1-范數(shù)）

（2-范數(shù)）

（p-范數(shù)）

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

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

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

定義4

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

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

定義5

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

定理17

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

對應(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階實矩陣，證明：（證明見黑板）

定義6

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

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

定理20如果A是實對稱矩陣，則（證明見黑板）

例6

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

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

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

設(shè)方程組

記為Ax=b，其精確解

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

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

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

定義7

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

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

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

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

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

定義8

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

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

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

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

例9

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

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

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

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

定理30（矩陣的QR分解）

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

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

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

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

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

容易證明，為對稱正定矩陣。

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

例10

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

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

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

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

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

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

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

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

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

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

（2）精度如何說明。

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

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

這就是Jacobi迭代法。其中。若引進記號則Jacobi迭代格式可寫為具體的，Jacobi迭代格式為引例1的迭代法是Jacobi迭代。

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

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

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

例2

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）

（4）（證明見黑板）

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

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

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

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

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

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

定理8

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

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

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

例6

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

將方程改寫為等價形式，若，則稱為函數(shù)的一個不動點。

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

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

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

定理1

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

定理2

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

此外，還有

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

代替。

定義1

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

定理3

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

（證明是簡單的）

例2

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

（2），則

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

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

定義2

設(shè)迭代收斂到的不動點，記迭代誤差，如果

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

定理4

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

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

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

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

（2）斯蒂文森加速方法

把埃特金加速方法用到不動點迭代：這便是Steffensen迭代。

它只是“二合一”的不動點迭代。Steffensen迭代也可寫為其中

定理5

若是的不動點，則也是的不動點。反之，若是的不動點，又存在，且，則是的不動點，且Steffensen迭代是二階的。（證明，略）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定理11

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

（2）

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

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

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

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