有限元法基礎(chǔ)-7線(xiàn)性代數(shù)方程組的解法

1、第七章 線(xiàn)性代數(shù)方程組的解法 7.1 高斯消去法及其變化7.2 帶狀系數(shù)矩陣的直接法7.3 利用外存的直接法7.4 迭代解法7. 線(xiàn)性代數(shù)方程組的解法 本章要點(diǎn)本章要點(diǎn)lGaussGauss消去法和三角分解法的原理和算法步驟消去法和三角分解法的原理和算法步驟l二維等帶寬存儲(chǔ)和一維變帶寬存儲(chǔ)的特點(diǎn)二維等帶寬存儲(chǔ)和一維變帶寬存儲(chǔ)的特點(diǎn)l分塊解法的原理和實(shí)施方案分塊解法的原理和實(shí)施方案l幾種迭代解法幾種迭代解法 有限元法基礎(chǔ)7. 線(xiàn)性代數(shù)方程組的解法 關(guān)鍵概念關(guān)鍵概念高斯循環(huán)消去法高斯循環(huán)消去法 三角分解法三角分解法二維等帶寬存儲(chǔ)二維等帶寬存儲(chǔ) 一維變帶寬存儲(chǔ)一維變帶寬存儲(chǔ)分塊解法分塊解法 迭代解法

2、迭代解法 超松弛迭代法超松弛迭代法梯度法梯度法 共軛梯度法共軛梯度法 預(yù)條件共軛梯度法預(yù)條件共軛梯度法 有限元法基礎(chǔ)7. 線(xiàn)性代數(shù)方程組的解法 彈性力學(xué)的有限元方程為彈性力學(xué)的有限元方程為對(duì)于彈性（本構(gòu)關(guān)系線(xiàn)性）小變形（幾何方程線(xiàn)性）問(wèn)對(duì)于彈性（本構(gòu)關(guān)系線(xiàn)性）小變形（幾何方程線(xiàn)性）問(wèn)題題K與與q無(wú)關(guān)，無(wú)關(guān)，為常數(shù)矩陣，方程組為線(xiàn)性代數(shù)方程組。為常數(shù)矩陣，方程組為線(xiàn)性代數(shù)方程組。求解是有限元方程分析中費(fèi)時(shí)最多的步驟。求解是有限元方程分析中費(fèi)時(shí)最多的步驟。 有限元法基礎(chǔ)KqQ7. 線(xiàn)性代數(shù)方程組的解法 線(xiàn)性代數(shù)方程組的解法分為兩大類(lèi)，即線(xiàn)性代數(shù)方程組的解法分為兩大類(lèi)，即直接解法直接解法和和迭迭代法

3、代法。 直接法的特點(diǎn)是，事先可按規(guī)定的算法步驟計(jì)算出它直接法的特點(diǎn)是，事先可按規(guī)定的算法步驟計(jì)算出它所需要的算術(shù)運(yùn)算操作數(shù)，直接給出最后的結(jié)果。所需要的算術(shù)運(yùn)算操作數(shù)，直接給出最后的結(jié)果。 迭代法的特點(diǎn)是，首先假定初始解，然后按一定的算迭代法的特點(diǎn)是，首先假定初始解，然后按一定的算法進(jìn)行迭代，在每次的迭代過(guò)程檢查解的誤差，通過(guò)多法進(jìn)行迭代，在每次的迭代過(guò)程檢查解的誤差，通過(guò)多次迭代直至滿(mǎn)足解的精度要求。次迭代直至滿(mǎn)足解的精度要求。 有限元法基礎(chǔ)7. 線(xiàn)性代數(shù)方程組的解法 有限元法基礎(chǔ)直接解法直接解法 以高斯消去法為基礎(chǔ)，以高斯消去法為基礎(chǔ)， 求解效率高，適用于小于求解效率高，適用于小于 一定階

4、數(shù)的方程組，根據(jù)計(jì)算機(jī)和軟件的不同有所一定階數(shù)的方程組，根據(jù)計(jì)算機(jī)和軟件的不同有所不同，比如不同，比如1 1萬(wàn)萬(wàn)1010萬(wàn)階方程組。萬(wàn)階方程組。迭代解法迭代解法當(dāng)方程組階數(shù)過(guò)高當(dāng)方程組階數(shù)過(guò)高 時(shí)，由于計(jì)算機(jī)有效位數(shù)的限時(shí)，由于計(jì)算機(jī)有效位數(shù)的限制，直接解法中舍入制，直接解法中舍入 誤差的積累影響精度，誤差的積累影響精度， 采用采用迭代迭代 解法。解法。 7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)一一. .高斯循序消去法高斯循序消去法對(duì)于對(duì)于n n階線(xiàn)性方程組階線(xiàn)性方程組1.1.消元消元 1112111212222212nnnnnnnnkkkaPkkkaPkkkaP *( 1)1111211

5、*( 1)22222*( 1)000nnnnnnnnnakkkPakkPakP 7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)對(duì)于對(duì)于n階線(xiàn)性方程組，共需進(jìn)行階線(xiàn)性方程組，共需進(jìn)行n-1次消元：次消元：l第第m次消元：次消元：以第以第m-1次消元結(jié)果為基礎(chǔ)次消元結(jié)果為基礎(chǔ)第第m行元素為消元行，行元素為消元行， 為主元為主元僅對(duì)僅對(duì)m+1 n行元素進(jìn)行元素進(jìn) 行元，并將行元，并將m列元素中列元素中 m+1 n消為消為0 0 1mmmK7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)l對(duì)對(duì)i行行m列（列（im）消元）消元, ,將將m列從列從m+1列的元素列的元素消為消為0 0 稱(chēng)為高斯消去因子稱(chēng)為高斯消

6、去因子7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)l因此消元過(guò)程可以寫(xiě)為因此消元過(guò)程可以寫(xiě)為 最終的最終的 為上三角陣。其中為上三角陣。其中(0)(1)(0)(1),nnKLKPLP(1)nK2131321211210010,1nnnlllll LLL LL(1)(1)(1)(1)(1)(1),1,2,/,1,2,1,nnniiiinnniiijiidKinKKKinji in為對(duì)角陣單位上三角陣KDKD7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)l因此因此 因?yàn)橐驗(yàn)镵 K(0)(0)為對(duì)稱(chēng)矩陣，所以為對(duì)稱(chēng)矩陣，所以 (0)(1)nKLDK(1)nTKL(0)TKLDL三角分解法的基礎(chǔ)三角分解

7、法的基礎(chǔ)7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)l特點(diǎn)特點(diǎn)原系數(shù)矩陣是對(duì)稱(chēng)的，則每次消元后矩陣依然是對(duì)稱(chēng)原系數(shù)矩陣是對(duì)稱(chēng)的，則每次消元后矩陣依然是對(duì)稱(chēng)的，只需存儲(chǔ)一半的矩陣的，只需存儲(chǔ)一半的矩陣消元結(jié)果中，消元結(jié)果中， 和和 中的第中的第i i行就是（行就是（i-1)i-1)次次消元的結(jié)果消元的結(jié)果 (1)nP(1)nK(1)(1)(1)(1),1,2,1,niniijijiiKKPPinji in7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)載荷列陣載荷列陣 消元用到的元素都是矩陣消元用到的元素都是矩陣 中的元素，中的元素，因此，因此， 的消元過(guò)程隨時(shí)可進(jìn)行，對(duì)于多載荷工況，可的消元過(guò)程隨

8、時(shí)可進(jìn)行，對(duì)于多載荷工況，可以利用消元后的以利用消元后的 矩陣進(jìn)行消元和回代求解。這樣可矩陣進(jìn)行消元和回代求解。這樣可大量節(jié)省求解所需的計(jì)算時(shí)間。大量節(jié)省求解所需的計(jì)算時(shí)間。 這是直接法相對(duì)迭代法的一個(gè)優(yōu)點(diǎn)。這是直接法相對(duì)迭代法的一個(gè)優(yōu)點(diǎn)。 P(1)nKPK7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)2.2.回代求解回代求解回代公式回代公式 (1)(1)(1)(1)(1)11,2,2,1()/nnnnnnnnnniiijjiij iPaKinnaPKaK 7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)l例例: :用高斯消元法求下列矩陣的解用高斯消元法求下列矩陣的解7.1 高斯消去法及其變化形式

9、有限元法基礎(chǔ)44320/7( 20/7)5/32,45/615/7aaa 34232112/5( 16/5)2( 4)3,214/55aaaaaa 回代求解得：回代求解得：7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)二二. . 三角分解法三角分解法由高斯消去法能得到對(duì)由高斯消去法能得到對(duì) 的三角分解的三角分解設(shè)設(shè)KTKLDL下三角陣下三角陣對(duì)角陣對(duì)角陣TDLS上三角陣上三角陣7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)由代數(shù)方程由代數(shù)方程可分解為可分解為高斯消元法相當(dāng)于高斯消元法相當(dāng)于令令KaPK = LS單位下三角陣單位下三角陣上三角陣上三角陣LSaP11L LSaL P1L PVP P在消

10、元后的結(jié)果在消元后的結(jié)果7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)l三角分解后的代數(shù)方程求解步驟三角分解后的代數(shù)方程求解步驟KaPTLDL a = P1V = L P1TL a = D V1Ta = L D V7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)l三角分解的遞推公式三角分解的遞推公式 K K 中任意元素中任意元素 TKLDL7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)按行分解按行分解 i i = =1 1 i i = =2 2 7.1 高斯消去法及其變化形式 有限元法基礎(chǔ) i i = =3,4,n3,4,n 7.1 高斯消去法及其變化形式 有限元法基礎(chǔ) 按行分解存儲(chǔ)情況按行分解存儲(chǔ)情

11、況7.1 高斯消去法及其變化形式 有限元法基礎(chǔ)按列分解按列分解 j=1j=1j j =2,=2,3,n3,n 7.1 高斯消去法及其變化形式 有限元法基礎(chǔ) 按列分解存儲(chǔ)情況按列分解存儲(chǔ)情況7.1 高斯消去法及其變化形式 有限元法基礎(chǔ) l關(guān)于三角分解法關(guān)于三角分解法稱(chēng)為改進(jìn)稱(chēng)為改進(jìn)CholeskiCholeski法，經(jīng)典方法法，經(jīng)典方法比高斯消去法效率更高比高斯消去法效率更高只是改變了高斯消去法的循環(huán)循序和存儲(chǔ)只是改變了高斯消去法的循環(huán)循序和存儲(chǔ) TKUU 按行三角分解按行三角分解 Do 15 i = 1, n Do 15 j = 1, n Do 15 m = 1, i-1 K(i,j )= K

12、(i,j) K(m,i) * K(m,j) /K(m,m)15 continue高斯循環(huán)消去法高斯循環(huán)消去法 Do 15 m = 1, n-1 Do 15 i = m+1, n Do 15 j = i, n K(i,j )= K(i,j) K(m,i) * K(m,j) /K(m,m)15 continue7.2 帶狀系數(shù)矩陣的直接法 有限元法基礎(chǔ) 系數(shù)矩陣在計(jì)算機(jī)中的存儲(chǔ)方法系數(shù)矩陣在計(jì)算機(jī)中的存儲(chǔ)方法l 等帶寬存儲(chǔ)等帶寬存儲(chǔ)K的特點(diǎn)：的特點(diǎn)：對(duì)稱(chēng)、帶狀、稀疏對(duì)稱(chēng)、帶狀、稀疏7.2 帶狀系數(shù)矩陣的直接法 有限元法基礎(chǔ) 二維等帶寬存儲(chǔ)二維等帶寬存儲(chǔ)(nND)7.2 帶狀系數(shù)矩陣的直接法 有限元

13、法基礎(chǔ) l相關(guān)節(jié)點(diǎn)：相關(guān)節(jié)點(diǎn)：所有與節(jié)點(diǎn)所有與節(jié)點(diǎn)i i共單元的節(jié)點(diǎn)共單元的節(jié)點(diǎn)稱(chēng)為節(jié)點(diǎn)稱(chēng)為節(jié)點(diǎn)i i的相關(guān)節(jié)點(diǎn)的相關(guān)節(jié)點(diǎn)如果節(jié)點(diǎn)如果節(jié)點(diǎn)j j是節(jié)點(diǎn)是節(jié)點(diǎn)i i的相關(guān)節(jié)點(diǎn)的相關(guān)節(jié)點(diǎn)則則如果不是相關(guān)節(jié)點(diǎn)如果不是相關(guān)節(jié)點(diǎn)則則0ijK0ijK 7.2 帶狀系數(shù)矩陣的直接法 有限元法基礎(chǔ) l一維變列高存儲(chǔ)主對(duì)角線(xiàn)位置主對(duì)角線(xiàn)位置MM：1 1，2 2，4 4，6 6，1010，1212，1616，1818，2222j j列上最上面非零元素行號(hào)列上最上面非零元素行號(hào)在一維存儲(chǔ)中得位置在一維存儲(chǔ)中得位置( )M jji7.2 帶狀系數(shù)矩陣的直接法 有限元法基礎(chǔ) l兩種存儲(chǔ)方式比較二維等帶寬存儲(chǔ)二維等帶寬存

14、儲(chǔ)一維變帶寬存儲(chǔ)一維變帶寬存儲(chǔ)占內(nèi)存較多占內(nèi)存較多乘除法計(jì)算量相對(duì)較多乘除法計(jì)算量相對(duì)較多編程簡(jiǎn)單編程簡(jiǎn)單尋址時(shí)間較少尋址時(shí)間較少占內(nèi)存較少占內(nèi)存較少乘除法計(jì)算量相對(duì)較少乘除法計(jì)算量相對(duì)較少程序編制復(fù)雜程序編制復(fù)雜尋址時(shí)間較多尋址時(shí)間較多變列高變列高找元素找元素7.2 帶狀系數(shù)矩陣的直接法 有限元法基礎(chǔ) 二.二維等帶寬的高斯消去法l工作三角形工作三角形 由于系數(shù)矩陣呈帶狀由于系數(shù)矩陣呈帶狀 每次消元只涉及包括每次消元只涉及包括 主元在內(nèi)的一個(gè)三角主元在內(nèi)的一個(gè)三角 形內(nèi)的元素，稱(chēng)為工形內(nèi)的元素，稱(chēng)為工作三角形作三角形 。 7.2 帶狀系數(shù)矩陣的直接法 有限元法基礎(chǔ) l二維等帶寬高斯消去法公式7

15、.2 帶狀系數(shù)矩陣的直接法 二維等帶寬存儲(chǔ)二維等帶寬存儲(chǔ)(n(nND)ND)采用按行分解采用按行分解I=i , J=j-i+1I=i , J=j-i+1新的循環(huán)界：新的循環(huán)界：r=max(j-ND+1, i-1)r=max(j-ND+1, i-1)有限元法基礎(chǔ) l二維等帶寬三角分解7.2 帶狀系數(shù)矩陣的直接法 有限元法基礎(chǔ) 三.一維變列高存儲(chǔ)高斯消去法l采用按列分解7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 主要解決計(jì)算機(jī)內(nèi)存不足的問(wèn)題，充分利用外存保存分解后的系數(shù)矩陣與未分解的系數(shù)矩陣，以達(dá)到小內(nèi)存算大問(wèn)題的目的。7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 一.高斯消去法的特點(diǎn)1）第m次

16、消元過(guò)程中，所涉及的元素僅在三角形次消元過(guò)程中，所涉及的元素僅在三角形工作區(qū)內(nèi)工作區(qū)內(nèi)消元行元素消元行元素7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 2）在）在m次消元過(guò)程中，前面的元素不再參加消元，次消元過(guò)程中，前面的元素不再參加消元，后面的元素尚未參加消元。后面的元素尚未參加消元。3）在整個(gè)消元過(guò)程中，工作區(qū)自上向下運(yùn)動(dòng)。）在整個(gè)消元過(guò)程中，工作區(qū)自上向下運(yùn)動(dòng)。 為分塊解法奠定基礎(chǔ)為分塊解法奠定基礎(chǔ)7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 二二.分塊解法分塊解法 設(shè)允許使用內(nèi)存為設(shè)允許使用內(nèi)存為NANA=NQ ND行數(shù)NAND要求 在每一分塊，在每一分塊，NQNQNDND行集成完畢，

17、可進(jìn)行消元修行集成完畢，可進(jìn)行消元修正，最后的正，最后的NDND行進(jìn)入到下一塊系數(shù)矩陣一起集成，行進(jìn)入到下一塊系數(shù)矩陣一起集成，消元修正。消元修正。7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) l 分塊解法的特點(diǎn)分塊解法的特點(diǎn)在每一分塊中，系數(shù)矩陣的元素是先集成后消在每一分塊中，系數(shù)矩陣的元素是先集成后消元修正元修正從求解的全過(guò)程看，系數(shù)矩陣的集成和消元修從求解的全過(guò)程看，系數(shù)矩陣的集成和消元修正是交替進(jìn)行正是交替進(jìn)行7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 分塊解法簡(jiǎn)單框圖分塊解法簡(jiǎn)單框圖7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 三三. .波前法（波前法（Front MethodFr

18、ont Method） 高斯循序消去法和三角分解法的求解規(guī)模與高斯循序消去法和三角分解法的求解規(guī)模與帶寬帶寬NDND有關(guān)。有些情況下帶寬會(huì)很大，占用內(nèi)存有關(guān)。有些情況下帶寬會(huì)很大，占用內(nèi)存很大，限制了計(jì)算機(jī)的求解能力。很大，限制了計(jì)算機(jī)的求解能力。 波前法和分塊解法基本思想都是基于對(duì)高斯波前法和分塊解法基本思想都是基于對(duì)高斯消去法的再分析，由先集成后消元修正，發(fā)展到消去法的再分析，由先集成后消元修正，發(fā)展到集成和消元修正交替進(jìn)行。集成和消元修正交替進(jìn)行。 7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 三三. .波前法（波前法（Front MethodFront Method） 高斯循序消去法和

19、三角分解法的求解規(guī)模與高斯循序消去法和三角分解法的求解規(guī)模與帶寬帶寬NDND有關(guān)。有些情況下帶寬會(huì)很大，占用內(nèi)存有關(guān)。有些情況下帶寬會(huì)很大，占用內(nèi)存很大，限制了計(jì)算機(jī)的求解能力。很大，限制了計(jì)算機(jī)的求解能力。 波前法和分塊解法基本思想都是基于對(duì)高斯波前法和分塊解法基本思想都是基于對(duì)高斯消去法的再分析，由先集成后消元修正，發(fā)展到消去法的再分析，由先集成后消元修正，發(fā)展到集成和消元修正交替進(jìn)行。集成和消元修正交替進(jìn)行。 7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) l波前法的特點(diǎn)波前法的特點(diǎn)1 1）剛度矩陣）剛度矩陣K K和載荷矩陣和載荷矩陣P P不按自然編號(hào)進(jìn)入內(nèi)存，不按自然編號(hào)進(jìn)入內(nèi)存，而是按

20、計(jì)算時(shí)參加運(yùn)算的順序排列而是按計(jì)算時(shí)參加運(yùn)算的順序排列2 2）在內(nèi)存中保留盡可能少的一部分）在內(nèi)存中保留盡可能少的一部分K K和和P P中的元素中的元素3 3）完成消元修正的行保存在外存）完成消元修正的行保存在外存 求解的自然編號(hào)是節(jié)點(diǎn)順序求解的自然編號(hào)是節(jié)點(diǎn)順序 參加運(yùn)算的順序是單元順序參加運(yùn)算的順序是單元順序7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 內(nèi)存內(nèi)存最大工作三角塊（波前區(qū)）最大工作三角塊（波前區(qū)）三角形直角邊為波前數(shù)三角形直角邊為波前數(shù)W最大波前數(shù)最大波前數(shù)W ND需要存儲(chǔ)大量信息，以用于恢復(fù)完成集成，消元需要存儲(chǔ)大量信息，以用于恢復(fù)完成集成，消元的自由度號(hào)的自由度號(hào) 7.3

21、利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) l波前法的計(jì)算過(guò)程波前法的計(jì)算過(guò)程1 1）按單元順序掃描計(jì)算單元?jiǎng)偠染仃?，并送入?nèi)）按單元順序掃描計(jì)算單元?jiǎng)偠染仃嚕⑺腿雰?nèi)存進(jìn)行集成存進(jìn)行集成2 2）檢查那些）檢查那些DOFDOF已完成集成，將集成完畢的已完成集成，將集成完畢的DOFDOF作為主元，對(duì)其他行、列進(jìn)行消元修正作為主元，對(duì)其他行、列進(jìn)行消元修正3 3）完成消元修正后，將主）完成消元修正后，將主DOFDOF行有關(guān)的行有關(guān)的K K和和P P中的中的元素移到外存元素移到外存4 4）重復(fù)）重復(fù)1 13 3步，將全部單元掃描完畢步，將全部單元掃描完畢5 5）按消元順序，由后向前依次回代求解）按消元順序

22、，由后向前依次回代求解 7.3 利用計(jì)算機(jī)外存的直接法 有限元法基礎(chǔ) 波前法一度是有限元研究者廣泛采用的方法波前法一度是有限元研究者廣泛采用的方法與分塊解法相比，波前法利用內(nèi)存更少與分塊解法相比，波前法利用內(nèi)存更少由于頻繁使用內(nèi)外存交換求解效率低由于頻繁使用內(nèi)外存交換求解效率低編程復(fù)雜，以效率換取求解規(guī)模編程復(fù)雜，以效率換取求解規(guī)模隨著計(jì)算機(jī)硬件的發(fā)展，目前已較少應(yīng)用隨著計(jì)算機(jī)硬件的發(fā)展，目前已較少應(yīng)用 7.4 迭代法 有限元法基礎(chǔ) 一一. .雅克比迭代法雅克比迭代法方程組為方程組為方程組非奇異，且方程組非奇異，且 0(1,2, )iiain7.4 迭代法 有限元法基礎(chǔ) 方程組可改寫(xiě)為方程組可

23、改寫(xiě)為雅克比迭代法雅克比迭代法 設(shè)初始解設(shè)初始解 迭代方程迭代方程 0(1,2, )ixin7.4 迭代法 有限元法基礎(chǔ) 為了便于編程，方程組可改寫(xiě)為為了便于編程，方程組可改寫(xiě)為精度檢查準(zhǔn)則精度檢查準(zhǔn)則 為允許誤差為允許誤差當(dāng)系數(shù)矩陣為嚴(yán)格對(duì)角優(yōu)勢(shì)矩陣時(shí)，方法收斂當(dāng)系數(shù)矩陣為嚴(yán)格對(duì)角優(yōu)勢(shì)矩陣時(shí)，方法收斂 1(0,1,2,)kkkxxxk1(1,2, )niiijjj iaain7.4 迭代法 有限元法基礎(chǔ) 例例1 1：用雅克比迭代法求解方程組：用雅克比迭代法求解方程組 Ax=b,Ax=b,其中其中相對(duì)誤差控制為相對(duì)誤差控制為初始解取為初始解取為精確解為精確解為經(jīng)過(guò)經(jīng)過(guò)3030次迭代可達(dá)到精度要

24、求。次迭代可達(dá)到精度要求。 61000,0,0,0Tx 1,2,3,4Tx 7.4 迭代法 有限元法基礎(chǔ) 例例2 2：用雅克比迭代法求解方程組：用雅克比迭代法求解方程組 Ax=b,Ax=b,其中其中相對(duì)誤差控制為相對(duì)誤差控制為初始解取為初始解取為精確解為精確解為雅克比迭代法不收斂。原因：不滿(mǎn)足嚴(yán)格對(duì)角優(yōu)勢(shì)。雅克比迭代法不收斂。原因：不滿(mǎn)足嚴(yán)格對(duì)角優(yōu)勢(shì)。 61000,0,0,0Tx 1,2,3,4Tx 7.4 迭代法 有限元法基礎(chǔ) 二二. .高斯賽德?tīng)柛咚官惖聽(tīng)?Gauss(Gauss-Seidel)迭代法迭代法雅克比迭代式雅克比迭代式在計(jì)算在計(jì)算 時(shí)，時(shí)， 為已知量，將迭為已知量，將迭代式修改

25、為代式修改為 1kix1(1,2,1)kjxji7.4 迭代法 有限元法基礎(chǔ) 三三. .超松弛超松弛迭代法迭代法 逐次超松弛迭代是逐次超松弛迭代是G-C迭代的一種加速收斂算法，迭代的一種加速收斂算法，引入松弛因子引入松弛因子 111G-C迭代法迭代法低松弛迭代法低松弛迭代法超松弛迭代法超松弛迭代法7.4 迭代法 有限元法基礎(chǔ) 三三. .超松弛超松弛迭代法迭代法 逐次超松弛迭代是逐次超松弛迭代是G-C迭代的一種加速收斂算法，迭代的一種加速收斂算法，引入松弛因子引入松弛因子 111G-C迭代法迭代法低松弛迭代法低松弛迭代法超松弛迭代法超松弛迭代法7.4 迭代法 有限元法基礎(chǔ) 例例3 3：松弛因子：

26、松弛因子迭代法求解例迭代法求解例1 其余條件與例其余條件與例1 相同，考察松弛因子對(duì)收斂相同，考察松弛因子對(duì)收斂性的影響。性的影響。 7.4 迭代法 有限元法基礎(chǔ) 例例4 4：松弛因子：松弛因子迭代法求解例迭代法求解例2 其余條件與例其余條件與例2 相同，考察松弛因子對(duì)收斂相同，考察松弛因子對(duì)收斂性的影響。性的影響。 可見(jiàn)，當(dāng)系數(shù)矩陣不是嚴(yán)格的對(duì)角優(yōu)勢(shì)，算法也可見(jiàn)，當(dāng)系數(shù)矩陣不是嚴(yán)格的對(duì)角優(yōu)勢(shì)，算法也收斂。通常取收斂。通常取 。 1.27.4 迭代法 有限元法基礎(chǔ) 四四. .共軛梯度法共軛梯度法 共軛梯度法由共軛梯度法由Hestenes和和Stiefel提出，可以提出，可以看作是稱(chēng)為最速下降法

27、的梯度法發(fā)展而來(lái)，看作是稱(chēng)為最速下降法的梯度法發(fā)展而來(lái)，簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)CG法（法（Conjugate Gradient Method）。）。 7.4 迭代法 有限元法基礎(chǔ) 1.1.梯度法梯度法 對(duì)與很多數(shù)學(xué)物理問(wèn)題，如果方程是自伴隨的，對(duì)與很多數(shù)學(xué)物理問(wèn)題，如果方程是自伴隨的，可等效為求解對(duì)應(yīng)的二次泛函的極值問(wèn)題?？傻刃榍蠼鈱?duì)應(yīng)的二次泛函的極值問(wèn)題。線(xiàn)性方程組線(xiàn)性方程組 對(duì)應(yīng)的二次泛函對(duì)應(yīng)的二次泛函在在xk處的梯度為處的梯度為記負(fù)梯度方向記負(fù)梯度方向 1( )2TTfxx Ax -b xAx = b( )kkfx xxAx -bxkkrb- Ax7.4 迭代法 有限元法基礎(chǔ) 設(shè)設(shè) xk 為為 的一

28、個(gè)近似解，利用最速下降法的一個(gè)近似解，利用最速下降法改善近似值：改善近似值：在在 的方向移動(dòng)的方向移動(dòng)xk ，即，即再選擇再選擇 使使 取得極小值，即令取得極小值，即令 Ax = b-grad f()x1kkk=-grad f()xxxk1()kfx()/0kk kkdf+dxrTkkkTkkr rr Ar7.4 迭代法 有限元法基礎(chǔ) l迭代公式迭代公式初始解初始解 x0 0 可任意選取?？扇我膺x取。實(shí)際計(jì)算中發(fā)現(xiàn)收斂速度不高。實(shí)際計(jì)算中發(fā)現(xiàn)收斂速度不高。10,1,2,kkk kkkTkkkTkk=+kxxrrb- Axr rr Ar7.4 迭代法 有限元法基礎(chǔ) 2.2.共軛梯度法共軛梯度法 定義：向量定義：向量 pi i 和和 pj j , ,若若稱(chēng)為關(guān)于稱(chēng)為關(guān)于A正交或共軛。正交或共軛。 使用共軛梯度方向搜索近似解使用共軛梯度方向搜索近似解xk1 ，可加快收，可加快收斂速度。斂速度。 0()Tijijp Ap近似解為近似解為共軛梯度方向共軛梯度方向選擇選擇 求二次泛函極值求二次泛函極值7.4 迭代法 有限元法基礎(chǔ) 1kkkk=+xxp110kkkkTkkprpp Apk7.4 迭代法 有限元法基礎(chǔ) l共軛梯度法迭代公式共軛梯度法迭代公式111111kkkkkkkkTkkkTk