迭代法的收斂條件

迭代法的收斂條件第1頁，共43頁，2023年，2月20日，星期四2解線性方程組的迭代法由特征值的定義容易得出，矩陣矩陣的譜半徑與范數(shù)有以下關(guān)系。的譜是因而第2頁，共43頁，2023年，2月20日，星期四3解線性方程組的迭代法定理3.3

設(shè)A為任意n階方陣，為任意由向量范數(shù)誘導(dǎo)出的矩陣范數(shù)，則[證明]對的任一特征值及相應(yīng)的特征向量都有因?yàn)闉榉橇阆蛄?，于是有由的任意性即得?頁，共43頁，2023年，2月20日，星期四4解線性方程組的迭代法定理3.4設(shè)A為n階方陣，則對任意正數(shù)存在一種矩陣范數(shù)使得證明參看［１］

.對任意n

階方陣

A,一般不存在矩陣范數(shù)使得但若A為對稱矩陣，則下面的結(jié)論對建立迭代法的收斂性條件非常重要。第4頁，共43頁，2023年，2月20日，星期四5解線性方程組的迭代法定理3.5

設(shè)A為n階方陣，則［證明］必要性.若而于是由極限存在準(zhǔn)則，有由定義3.2得的充要條件為所以第5頁，共43頁，2023年，2月20日，星期四6解線性方程組的迭代法充分性.若取由定理3.4存在一種存在一種使得所以而于是第6頁，共43頁，2023年，2月20日，星期四7解線性方程組的迭代法3.5.2迭代法的收斂條件定理３.６對任意初始向量和右端項(xiàng)由迭代格式產(chǎn)生的向量序列收斂的充要條件是［證明］設(shè)存在n維向量使得則滿足p9第7頁，共43頁，2023年，2月20日，星期四8解線性方程組的迭代法由迭代公式(3-24),有于是有因?yàn)闉槿我鈔維向量,因此上式成立必須由定理3.5第8頁，共43頁，2023年，2月20日，星期四9解線性方程組的迭代法反之，若則不是M的特征值，因而有于是對任意n維向量g,方程組有唯一解，記為即并且又因?yàn)樗裕瑢θ我獬跏枷蛄慷加屑从傻?3-24)產(chǎn)生的向量序列收斂.p7第9頁，共43頁，2023年，2月20日，星期四10解線性方程組的迭代法由定理3.4即得推論１在定理3.6的條件下,若則收斂.推論２

松弛法收斂的必要條件是［證明］設(shè)松弛法的迭代矩陣有特征值

因?yàn)橛啥ɡ?.6，松弛法收斂必有p19第10頁，共43頁，2023年，2月20日，星期四11解線性方程組的迭代法又因?yàn)橛谑怯兴缘?1頁，共43頁，2023年，2月20日，星期四12解線性方程組的迭代法定理3.6表明，迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量及方程組的右端項(xiàng)無關(guān)。對同一方程組，由于不同的迭代法迭代矩陣不同，因此可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形.第12頁，共43頁，2023年，2月20日，星期四13解線性方程組的迭代法例３

討論用Jacobi迭代法與Gauss-Seidel迭代法求解方程組的收斂性．［解］由定理3.6，迭代法是否收斂等價于迭代矩陣的譜半徑是否小于１，因?yàn)楣蕬?yīng)先求迭代矩陣。第13頁，共43頁，2023年，2月20日，星期四14解線性方程組的迭代法Jacobi迭代法的迭代格式為迭代矩陣為p16第14頁，共43頁，2023年，2月20日，星期四15解線性方程組的迭代法其特征方程為因此有于是所以Jacobi迭代法收斂.第15頁，共43頁，2023年，2月20日，星期四16解線性方程組的迭代法如果用Gauss-Seidel迭代，容易求出于是迭代矩陣為其中又p14第16頁，共43頁，2023年，2月20日，星期四17解線性方程組的迭代法其特征方程為特征值為故所以，Gauss-Seidel迭代法發(fā)散.第17頁，共43頁，2023年，2月20日，星期四18解線性方程組的迭代法例３也說明了確實(shí)只是松弛法收斂的必要條件，而非充要條件，因?yàn)镚auss-Seidel迭代即為的情形.定理3.6雖然給出了判別迭代法收斂的充要條件，但實(shí)際使用是很不方便。因?yàn)榍竽婢仃嚭吞卣髦档碾y度并不亞于用直接方法求解線性方程組。推論１與推論２使用起來方便得多，但它們分別給出收斂的充分條件與必要條件，許多情形下，不能起作用.第18頁，共43頁，2023年，2月20日，星期四19解線性方程組的迭代法如例３中，兩個方法均有由推論１無法判別收斂性。特殊的系數(shù)矩陣給出幾個常用的判斂條件。下面對一些定義3.4

(1)(嚴(yán)格對角占優(yōu))設(shè)如果A滿足則稱A為嚴(yán)格對角占優(yōu)陣.第19頁，共43頁，2023年，2月20日，星期四20解線性方程組的迭代法且至少有一個i值，使上式中不等號嚴(yán)格成立，則稱為A弱對角占優(yōu)陣。定義3.5

如果矩陣Ａ不能通過行的互換和相應(yīng)列的互換成為形式(2)

若n階方陣滿足其中為方陣，則稱A為不可約.第20頁，共43頁，2023年，2月20日，星期四21解線性方程組的迭代法如例３的系數(shù)矩陣矩陣是可約的.為n階方陣若存在非空集使得當(dāng)而顯然,若A是可約的,則A所對應(yīng)的線性方程組可化為低階方程組.時有則A是可約陣.是不可約的.而一般地，設(shè)第21頁，共43頁，2023年，2月20日，星期四22解線性方程組的迭代法幾個常用的收斂條件.設(shè)有線性方程組下列結(jié)論成立：1.若A為嚴(yán)格對角占優(yōu)陣或不可約弱對角占優(yōu)陣,則Jacobi迭代法和Gauss-Seidel迭代法均收斂.2.若A為嚴(yán)格對角占優(yōu)陣,則松弛法收斂.3.

若A為對稱正定陣,則松弛法收斂.因此有:若A為對稱正定陣,則松弛法收斂的充分必要條件是4.若A為對稱正定陣,則Gauss-Seidel迭代法收斂.第22頁，共43頁，2023年，2月20日，星期四23解線性方程組的迭代法例:考慮A為嚴(yán)格對角占優(yōu)陣，故Jacobi迭代法與Gauss-Seidel迭代均收斂.又如例２中，系數(shù)矩陣非嚴(yán)格對角占優(yōu),但A為對稱正定矩陣,故松弛法收斂。上述結(jié)論的證明可參看[1],[7].其中第23頁，共43頁，2023年，2月20日，星期四例對線性方程組討論Jacobi迭代法及Gauss-Seidel迭代法的收斂性.解:Jacobi迭代的迭代矩陣為故Jacobi迭代法收斂.第24頁，共43頁，2023年，2月20日，星期四Gauss-Seidel迭代矩陣故Gauss-Seidel迭代法收斂.第25頁，共43頁，2023年，2月20日，星期四26解線性方程組的迭代法討論用三種迭代法求解的收斂性。解:例4設(shè)有方程組其中第26頁，共43頁，2023年，2月20日，星期四27解線性方程組的迭代法故不能用條件1判別Jacobi迭代的收斂性.因A為對稱矩陣,且其各階主子式皆大于零,故A為對稱正定矩陣,由判別條件3,Gauss-Seidel迭代法與松弛法均收斂.A不是弱對角占優(yōu),Jacobi迭代法的迭代矩陣為故推論1不能用第27頁，共43頁，2023年，2月20日，星期四28解線性方程組的迭代法其特征方程第28頁，共43頁，2023年，2月20日，星期四29解線性方程組的迭代法值得指出的是，改變方程組中方程的次序，即將系系數(shù)矩陣作行交換，會改變迭代法的收斂性。例如方程組的系數(shù)矩陣為有根因而由定理3.6Jacobi迭代法不收斂.第29頁，共43頁，2023年，2月20日，星期四30解線性方程組的迭代法Jacobi迭代與Gauss-Seidel迭代的迭代矩陣分別為它們的譜半徑為由定理3.6這兩種迭代均不收斂.但若交換兩個方程的次序得原方程組的同解方程組其中第30頁，共43頁，2023年，2月20日，星期四31解線性方程組的迭代法顯然,是嚴(yán)格對角占優(yōu)陣,因而對方程組用Jacobi迭代與Gauss-Seidel迭代求解均收斂.第31頁，共43頁，2023年，2月20日，星期四32解線性方程組的迭代法3.5.3誤差估計(jì)定理3.7設(shè)有迭代格式若收斂于則有誤差估計(jì)式證明:因?yàn)楣视谑谴嬖?方程組(即有惟一解)且從而有p35第32頁，共43頁，2023年，2月20日，星期四33解線性方程組的迭代法取范數(shù)得第33頁，共43頁，2023年，2月20日，星期四34解線性方程組的迭代法又因?yàn)橛谑侨》稊?shù)得移項(xiàng)得又第34頁，共43頁，2023年，2月20日，星期四35解線性方程組的迭代法將(3-28)代入(3-27)得有了誤差估計(jì)(3-26),根據(jù)事先給定的精度可以估算出迭代的次數(shù)kp32第35頁，共43頁，2023年，2月20日，星期四36解線性方程組的迭代法例如對迭代格式其中取有代入式(3-29)得第36頁，共43頁，2023年，2月20日，星期四37解線性方程組的迭代法所以需要迭代13次才能保證各分量誤差絕對值不超過實(shí)際計(jì)算時,常常采用事后估計(jì)誤差的方法,即利用相鄰兩次迭代值之差是否達(dá)到精度作為停機(jī)準(zhǔn)則.因而下面的結(jié)論比定理3.7更實(shí)用.第37頁，共43頁，2023年，2月20日，星期四38解線性方程組的迭代法定理3.8在定理3.7的條件下,有證明:因?yàn)樗缘?8頁，共43頁，2023年，2月20日，星期四39解線性方程組的迭代法由定理3.8,為使只要即可.實(shí)際計(jì)算時,當(dāng)不太接近1時,可用作為停機(jī)準(zhǔn)則,即為滿足精度之近似解.第39頁，共43頁，2023年，2月20日，星期四拉格朗日(Lagrange)插值牛頓(Newton)插值分段線性插值第5章插值法

樣條插值埃爾米特(Hermite)插值快速傅里葉變換(FFT)應(yīng)用實(shí)例1第40頁，共43頁，2023年，2月20日，星期四生產(chǎn)實(shí)踐中常常出現(xiàn)這樣的問題：給出一批離散樣點(diǎn),要求作出一條通過這些點(diǎn)的光滑曲線，以便滿足設(shè)計(jì)要求或進(jìn)行加工.反映在數(shù)學(xué)上，既已知函數(shù)在一些點(diǎn)上得值，尋求它的分析表達(dá)式.因?yàn)橛珊瘮?shù)的表格形式不能直接得出表中未列點(diǎn)處的函數(shù)值，也不便于研究函數(shù)的的性質(zhì).此外，有些函數(shù)雖然有表達(dá)式，但因式子復(fù)雜，不易計(jì)算其值和進(jìn)行理論分析，也需要構(gòu)造一個簡單函數(shù)來近似它.解決這種問題的方法有兩種：插值法2第41頁，共43頁，2023年，2月20日，星期四一類是給出函數(shù)的一些點(diǎn)值，選定一個便于計(jì)算的函數(shù)形式，如多項(xiàng)式，分式線性函數(shù)和三角多項(xiàng)式等，要求它通過已知樣點(diǎn)，由此確定函數(shù)作為的近似.這就是插值法。另一類方法在選定近似函數(shù)形式后,不要求近似函數(shù)過已知樣點(diǎn),只要求在某種意義下它