數值分析

編者李慶揚等

課件董祖引

Ch1緒論1.1數值分析研究對象與特點

科學技術領域的三大環節：（1）實驗；（2）科學計算；（3）理論。

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

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

（2）數值微分和數值積分；

（3）非線性方程（組）數值解；

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

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

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

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

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

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

它可表示為：

例1

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

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

例2

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

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

例3

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

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

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

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

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

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

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

例4

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

例5

計算多項式的值。

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

設在區間上有意義，且已知在點上的值若存在簡單函數，使得

插值區間。則稱是的插值函數。點稱為

插值節點。其他點稱為插值點。稱為

若是次數不超過n的多項式，即則稱為插值多項式。相應的方法稱為多項式插值。

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

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

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

注意：它與無關。

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

特別的，當n=1，稱線性插值。當n=2，稱拋物插值二次插值。

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

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

定理1

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

證明只要證明唯一性。

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

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

定理2

設在上連續，在內存在，則，有（證明見黑板）若，則截斷誤差限

例2

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

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

最后，關于插值多項式的數值計算的穩定性，我們有結論：

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

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

其中為待定系數，

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

定義2

稱為關于點的一階均差；稱為的二階均差；一般的，稱為的k階均差。

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

（1）（對稱性）均差與節點的排序無關，即（2）

（3）若在上存在n階導數，則（證明略）

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

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

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

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

埃爾米特插值不僅要求節點處函數值相等，且對應的導數（甚至高階導數）值也相等。具體地，設

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

仿照拉格朗日插值，令

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

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

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

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

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

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

例4

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

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

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

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

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

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

如果還知道節點處的導數值可構造一個導數連續的分段插值函數，滿足在每個小區間上是次數不超過三次的多項式。

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

定理3

設，則當時，在上一致收斂到。2.7三次樣條插值（簡介）

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

定義4

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

判斷下列函數是否為三次樣條函數：

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

要求出，在每個小區間上的要確定4個待定系數，共4n個參數。

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

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

根據上述條件，利用分段三次Hermite插值(此處假定)可得關于的一個三對角線性方程組（具體過程略，見54）。轉化為(7.8)式。可用追趕法解之。

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

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

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

定義2

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

（-范數，最大范數）

（1-范數）

（2-范數）中常用范數

定義3

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

（Cauchy-Schwarz定理）

定理3

設（內積空間），則Gram矩陣非奇異的充要條件是線性無關。（證明見黑板）由內積可誘導出一個范數：

例1

的內積誘導出2-范數加權內積對應導出范數中的內積

定義4

設[a，b]（可以是無限）上的非負函數滿足：（1）存在有限；（2）對[a，b]上的非負連續函數，若有則稱為[a，b]上的一個權函數。例2C[a，b]上內積

導出范數當，則3.2正交多項式

定義5

若

則稱在[a，b]上帶權正交。若函數族滿足：

則稱是[a，b]上帶權的正交函數族。又若，則稱為標準正交函數族。三角函數族：1，cosx，sinx，cos2x，sin2x，……是上的正交函數族。

特別的，當是n次多項式時，則稱是[a，b]上帶權的n次正交多項式。對于利用Schmidt正交化構造正交多項式這里的滿足：（1）是首一的n次多項式。（2）任一n次多項式均可表為

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

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

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

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

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

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

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

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

定義7

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

定義8

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

定理4

設，則存在s.t.（證明略）

定義9

設，若在處有則稱是的偏差點。

當時，稱“正”偏差點。

當時，稱“負”偏差點。介值定理保證偏差點總是存在的。

定理5

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

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

定理6

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

例3

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

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

例4

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

例5

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

定理9

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

例5

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

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

定義10

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

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

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

當時，稱線性擬合，當時，是病態的。

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

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

結束Ch4數值積分與數值微分4.1引言

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

一般的，數值積分具有下列形式：其中，稱為求積節點，稱為求積系數（也稱為節點的權），它僅與有關，而與無關。

關于數值積分的精度問題我們引入：

定義1

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

事實上，只要對準確成立，而對不準確成立即可。

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

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

構造求積公式的最基本方法是所謂插值型的求積公式。設給定節點

以插值函數近似代替，則

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

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

定理2若求積公式中系數，則此公式是穩定的。（證明是簡單的，略，見page122）4.2牛頓-柯特斯公式

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

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

注意，當時，出現負值，此時不能保證求積公式的穩定性。

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

（證明見黑板）

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

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

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

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

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

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

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

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

例2

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

在求積公式中，適當選擇節點有望提高其代數精度。更一般的，考慮帶權函數的插值型求積公式

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

定義4如果求積公式具有2n+1次代數精度，則稱節點為高斯點，相應的公式稱為高斯公式。

例4

構造下列的高斯求積公式：（見黑板）

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

定理5等價于：

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

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

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

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

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

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

例5

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

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

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

從截斷誤差看，h越小越好，但從舍入誤差看，h太小，有效數字嚴重損失。

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

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

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

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

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

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

定理7

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

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

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

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

再通過一個算例說明高斯-約當消去法。例2

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

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

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

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

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

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

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

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

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

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

定理10

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

定理11

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

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

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

當其系數矩陣滿足所謂的“對角占優”條件時，即則用高斯消去法或杜利特爾（克魯特）分解法求解此方程組時，可略去許多的中間步驟（但計算機不會！）。

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

設A=LU，即令

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

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

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

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

定義2

如果向量的某個實值函數

滿足：

則稱是上的一個向量范數。等號成立當且僅當中常用范數

（-范數，最大范數）

（1-范數）

（2-范數）

（p-范數）

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

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

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

定義4

如果矩陣的某個實值函數

滿足：等號成立當且僅當則稱是上的一個矩陣范數。

定義5

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

定理17

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

對應于向量x的、1、2-范數，我們有常用的矩陣范數（定理18）：

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

（4）F-范數例4

設4階阿達瑪（Hadamard）矩陣求：，，，。（見黑板）例5

設A為n階實矩陣，證明：（證明見黑板）

定義6

設的特征值為，稱為的A的譜半徑。

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

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

例6

設A，B是n階實對稱矩陣，證明：

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

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

設方程組

記為Ax=b，其精確解

現常數項帶有微小變化，考察方程組

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

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

定義7

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

下面我們來尋找病態的原因以及刻畫病態的度量。

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

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

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

定義8

設A是非奇異矩陣，稱為矩陣A的條件數。常用的條件數：當A為對稱矩陣時，條件數具有下列性質：（3）若A為正交矩陣，則例8

求三階Hilbert矩陣的條件數：解：類似可得可見高階Hilbert矩陣是嚴重病態的。

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

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

例9

方程組系數矩陣A的條件數

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

也用列主元素消去法（計算到三位數字）得很好的結果迭代改善法簡介：先從解得近似解，記。再解得近似解。最后改善。可重復進行。當是精確解時，則由知道是的精確解。

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

定理30（矩陣的QR分解）

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

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

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

設超定線性方程組令

為殘差向量，求使得即關于x求導，并令其為零，得即（稱為法方程組）

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

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

例10

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

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

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

結束Ch6線性方程組的迭代法6.1引言

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

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

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

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

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

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

（2）精度如何說明。

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

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

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

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

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

設，代入得即得迭代格式或由得

例2

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

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

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

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

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

當時，S.O.R即為G-S迭代。取時，稱為超松弛。取時，稱為亞（低）松弛。統稱超松弛。

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

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

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

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

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

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

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

（3）

（4）（證明見黑板）

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

當方程組的系數矩陣為對角占優或對稱正定時，我們可直接從知道常用迭代的收斂性。定義3（1）若矩陣的元素滿足則稱嚴格對角占優；

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

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

定理6若是嚴格對角占優，或不可約弱對角占優，則非奇異。（證明，略）

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

定理8

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

定理10若是嚴格對角占優，或不可約弱對角占優，則當時，解方程組的SOR迭代收斂。

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

例6

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

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

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

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

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

定理1

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

定理2

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

此外，還有

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

代替。

定義1

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

定理3

設是的不動點，在的某領域連續，且,則迭代局部收斂。

（證明是簡單的）

例2

方程，其根為，構造下列迭代法：（1），則（事實上，此迭代發散）

（2），則

（此迭代也發散）

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

定義2

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

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

定理4

設迭代，如果在的某領域連續，且

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

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

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

（2）斯蒂文森加速方法

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

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

定理5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對于實對稱矩陣，有下列結果：

定理11

設為實對稱矩陣，則（1）

（2）

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

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

設具有完全的特征向量組，記及分別為的特征值及對應的特征向量，且的主特征值是實根，滿足構造迭代向量序列設則由于故從而故當k充分大時，有

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