第五章線性方程組迭代法

地球物理計(jì)算方法

地球物理與信息技術(shù)學(xué)院習(xí)題課2第三章常微分方程差分法+第四章方程求根專題：壓縮映像原理作業(yè)點(diǎn)評(píng)，P153，習(xí)題四，4，7，9

方程求根迭代法弦截法牛頓法收斂性：壓縮映像原理迭代法的加速二分法方程求根迭代法牛頓法的改進(jìn)與推廣簡(jiǎn)化牛頓法：導(dǎo)數(shù)項(xiàng)取常數(shù)值下山法：牛頓法局部微調(diào)弦截法：去掉導(dǎo)數(shù)項(xiàng)快速弦截法：弦截法加速重根：修正的牛頓法

例題選講4.3牛頓法誤差分析（P147-149）牛頓法的改進(jìn)與推廣簡(jiǎn)化牛頓法：導(dǎo)數(shù)項(xiàng)取常數(shù)值下山法：牛頓法局部微調(diào)弦截法：去掉導(dǎo)數(shù)項(xiàng)快速弦截法：弦截法加速重根：修正的牛頓法定義1

若有x*滿足(x*)=0，則稱x*為方程的根或函數(shù)f(x)的零點(diǎn)，特別地，如果函數(shù)f(x)可分解為f(x)=(x

x*)mg(x)

且g(x*)0,則稱x*是f(x)的m重零點(diǎn)或f(x)=0的m重根。當(dāng)m=1時(shí)，稱x*是f(x)的單根或單零點(diǎn)。

定理1

若是f(x)的m重零點(diǎn)，且g(x)充分光滑，則有當(dāng)m為奇數(shù)時(shí)，f(x)在點(diǎn)處變號(hào)，當(dāng)m為偶數(shù)時(shí)，f(x)在點(diǎn)處不變號(hào)。重根的情形例給定方程：x-sinx=0,問(wèn)x*=0是幾重零點(diǎn).解：設(shè)f(x)=x-sinx,則f(0)=0;f’(x)=1-cosx,f’(0)=0;f’’(x)=sinx,f’’(0)=0;f(3)(x)=cosx,f

(3)(0)=1;由定理1,x*=0是3重零點(diǎn).重根情形下，牛頓法僅為線性收斂。（P149，題1）為了改善重根時(shí)Newton法的收斂性，有如下兩種方法：（1）改為取此時(shí)迭代至少二階收斂.（P150，題2）12這種方法也是至少二階收斂的.所以，x*是的單零點(diǎn).可將Newton法的迭代函數(shù)修改為（2）令,由x*是f(x)的m重零點(diǎn)，有重根例題：P150，題3-4.牛頓法其他的改進(jìn)與推廣形式：擬牛頓法（平方收斂）P150，題5Steffenson方法（平方收斂）P151，題6預(yù)報(bào)-校正型牛頓公式（三階收斂）P152，題7-8.總結(jié)：不同方法的收斂性牛頓法：局部收斂，開(kāi)方公式在（0，+∞）上收斂；單根至少平方收斂；重根線性收斂；弦截法：?jiǎn)胃€性收斂；快速弦截法：超線性收斂（p=1.618）；修正的牛頓法：平方收斂.

15《地球物理計(jì)算方法》

第5章線性方程組迭代法大部分?jǐn)?shù)值問(wèn)題需要解線性方程組數(shù)值計(jì)算問(wèn)題都轉(zhuǎn)換為線性代數(shù)的求解：三次樣條插值最小二乘擬合機(jī)械求積公式的構(gòu)造常微分方程差分格式的構(gòu)造……問(wèn)題的提出17樣條插值，需要解三轉(zhuǎn)角方程/三彎矩方程解出mi，帶入樣條插值公式得到三對(duì)角型系數(shù)矩陣18最小二乘擬合多項(xiàng)式的系數(shù)aj所滿足的方程組，稱為正則方程組或法方程組。機(jī)械求積公式的構(gòu)造，求取求積系數(shù)/權(quán)系數(shù)20常微分方程邊值問(wèn)題線性方程組的解法大致分為直接法和迭代法兩大類。直接法：經(jīng)過(guò)有限步算術(shù)運(yùn)算，可求得線性方程組精確解的方法。實(shí)際計(jì)算中由于舍入誤差的存在，這種方法求得的是線性方程組的近似解。迭代法：用某種極限過(guò)程逐步逼近線性方程組精確解的方法。優(yōu)點(diǎn)：算法簡(jiǎn)單，需要存儲(chǔ)單元較少，編制程序比較容易，原始系數(shù)矩陣在計(jì)算過(guò)程中保持不變；缺點(diǎn)：要求方程組的系數(shù)矩陣具有某種特殊性質(zhì)，以保證迭代過(guò)程的收斂性。迭代法是解大型稀疏矩陣方程組（矩陣階數(shù)高且零元素較多）的重要方法。地球物理問(wèn)題的科學(xué)計(jì)算中也會(huì)經(jīng)常遇到解線性方程組的問(wèn)題。因此，線性方程組的解法占有非常重要的地位。A為n×n階實(shí)矩陣，x,b為n維實(shí)向量.當(dāng)A非奇異，即detA≠0時(shí)，方程組有唯一解，并可用Cramer法則將解用公式表示出來(lái)，但由于計(jì)算量太大，因此不能用于實(shí)際求解，需要借助數(shù)值方法求解。n個(gè)變量n個(gè)線性方程的方程組求解，其表達(dá)式為

通常用向量矩陣表示，則上述方程可寫成

第5章線性方程組的迭代法1迭代公式的建立

2向量和矩陣的范數(shù)3迭代過(guò)程的收斂性

1、迭代公式的建立1雅可比迭代公式例1求解方程組從方程中分離x1,x2,x3，建立迭代公式，設(shè)初值：隨著迭代次數(shù)k增加，迭代值逼近解析解：收斂到方程的根1.1,1.2.1.3解線性方程組迭代法的基本思想是將聯(lián)立方程組的求解歸結(jié)為重復(fù)計(jì)算一組彼此獨(dú)立的線性表達(dá)式，這就使問(wèn)題得到了簡(jiǎn)化。

考察一般形式的線性方程組，或：282930從上式中分離出變量xi，將它改寫成()或：其中即得到解方程組的雅可比迭代公式:

分量計(jì)算表達(dá)式或：迭代終止條件：雅可比迭代算法流程圖雅可比迭代公式雅可比迭代算法需要同時(shí)存儲(chǔ)前后兩次迭代的數(shù)組，是否可以進(jìn)一步改進(jìn)算法以減少存儲(chǔ)空間？2、高斯-賽德?tīng)柕皆诘匠讨?，用?jì)算出的新值代替舊值得到新的迭代公式：?。旱K止條件：1、迭代過(guò)程中依次計(jì)算序列：迭代過(guò)程：2、迭代第i個(gè)分量時(shí)，前面已經(jīng)計(jì)算的分量用k+1次的值代替3738對(duì)于一般形式的方程組：高斯-賽德?tīng)柕ㄌ攸c(diǎn)：只需要n個(gè)單元存儲(chǔ)近似解分量。

3、超松弛法

松弛法實(shí)質(zhì)是高斯—塞德?tīng)柕囊环N加速方法。它將前一步的結(jié)果與高斯—塞德?tīng)柕颠m當(dāng)加權(quán)平均：

高斯-塞德?tīng)柕降铀偈街邢禂?shù)稱為松弛因子。為保證迭代收斂，要求。由于迭代值通常比精確，所以加大它的比重，取松弛因子，這種方法稱為超松弛法（SOR，SuccessiveOver-Relaxation）。兩項(xiàng)合并得到：4、迭代公式的矩陣表示一般形式的線性方程組可用矩陣符號(hào)簡(jiǎn)記為，將系數(shù)矩陣A分解：其中，D為對(duì)角陣，L,U為嚴(yán)格下三角和上三角陣。其中D為對(duì)角陣，L和U分別為嚴(yán)格下三角和嚴(yán)格上三角陣。如果將所給方程改寫為據(jù)此建立的迭代公式即為雅可比迭代公式，其中，L+U=A-D，考察一般的線性方程組，設(shè)將系數(shù)矩陣A分解為A=L+D+U;或：44454647如果改寫為據(jù)此建立的迭代公式由此解出，則有即為高斯—塞德?tīng)柕健?9SOR方法的計(jì)算表達(dá)式為,令A(yù)=L+D+U，則對(duì)應(yīng)于上式的矩陣形式為，整理之后的超松弛法的矩陣形式為，綜合上述幾個(gè)迭代公式，可以看到它們都可以用如下迭代形式表示，稱G為迭代公式的迭代矩陣，對(duì)于不同的迭代公式，G不同；這類迭代公式的收斂性與矩陣G的性態(tài)有關(guān)；或：第5章線性方程組的迭代法1迭代公式的建立

2向量和矩陣的范數(shù)3迭代過(guò)程的收斂性

為了研究迭代過(guò)程的收斂性，需要對(duì)向量“大小”引入某種度量。任給向量，其范數(shù)記為，它是一個(gè)實(shí)數(shù)，1、向量范數(shù)（非負(fù)性）（齊次性）且滿足：