4.2.4 線化代數(shù)方程組的迭代解法[教資優(yōu)擇]

1、4.2.4 線化代數(shù)方程組的 迭代解法 胡 茂 彬 http:/ / 1基礎(chǔ)課件 多維情況求解特點(diǎn)和難點(diǎn) 1. 系數(shù)可能是求解函數(shù)的函數(shù)，而使方程具有非 線性性質(zhì)，需要線化迭代求解 外迭代：反復(fù)更新非線性方程的系數(shù)而使方程線 化求解的過(guò)程 2. 線化的代數(shù)方程組，系數(shù)矩陣不再是三對(duì)角陣， 而是一個(gè)大型稀疏矩陣，不能TDMA直接求解。 Gauss消元法，需很大的內(nèi)存，且計(jì)算效率低 內(nèi)迭代：求解線化方程而使用迭代方法的過(guò)程 2基礎(chǔ)課件 建立控制方程、確 定初始與邊界條件 流 程 圖 （非穩(wěn)態(tài)情況） 解域離散、方程離散 初邊條件離散 給出節(jié)點(diǎn)初始溫度值 計(jì)算系數(shù)，固定， 線化代數(shù)方程 求解離散的 線

2、化的代數(shù)方程組 進(jìn)入下一時(shí)層求解 解收斂否？ Yes No 以新溫度值 替代老溫度值 外迭代 3基礎(chǔ)課件 建立控制方程、確 定初始與邊界條件 流 程 圖 解域離散、方程離散 初邊條件離散 給出節(jié)點(diǎn)初始溫度值 計(jì)算系數(shù)，固定， 線化代數(shù)方程 求解離散的 線化的代數(shù)方程組 進(jìn)入下一時(shí)層求解 解收斂否？ Yes No 以新溫度值 替代老溫度值 線化方程的 迭代解法 (內(nèi)迭代) 外迭代 4基礎(chǔ)課件 1迭代求解的基本思想迭代求解的基本思想 方程組的矩陣形式： 構(gòu)造向量(即求解函數(shù)T的序列) ATb ( )n T n *1 TA b 試探解 真實(shí)解 迭代收斂過(guò)程 5基礎(chǔ)課件 構(gòu)造向量的方法 也稱(chēng)為“迭代方

3、式” 從 n-1 迭代層，經(jīng)過(guò)一次迭代(與A,b相關(guān))， 演進(jìn)到 n 迭代層 ( )(1) F( , ,) nn TA b T 6基礎(chǔ)課件 收 斂 條 件 或者： (1)( ) , ( ) , max nn i ji j n i j TT T (1)( ) , 1 ( ) , , nn i ji j n i j i j TT T 1 N 36 1010 7基礎(chǔ)課件 “迭代”是求解線化了的代數(shù) 方程組的方法 在算法地位上與TDMA方法類(lèi)似 8基礎(chǔ)課件 迭代推進(jìn)一層與時(shí)間演進(jìn)一步 的區(qū)別 迭代是求解方程的方法，迭代推進(jìn)一層并 非時(shí)間演進(jìn)一步 迭代收斂之后才表示該方程組已經(jīng)求解， 此時(shí)表示該次的內(nèi)迭

4、代求解過(guò)程結(jié)束 只有在方程為線性的情況下，迭代收斂才 意味著時(shí)間演進(jìn)了一步 9基礎(chǔ)課件 2常用的迭代求解方法常用的迭代求解方法 三類(lèi)迭代方法：點(diǎn)迭代(顯式迭代)、塊迭代 (隱式迭代)和交替方向線迭代 三種實(shí)施方式：簡(jiǎn)單(Jacob)迭代、Gauss- Seidel迭代和逐次松弛迭代 10基礎(chǔ)課件 以直角坐標(biāo)下二維非穩(wěn)態(tài)導(dǎo)熱 離散方程為例(全隱式) P PE EW WNNS S a Ta Ta Ta Ta Tb 11基礎(chǔ)課件 特別注意 雖然差分離散格式方程為全隱式，但其迭 代求解方法可以是顯式迭代(點(diǎn)迭代)，隱式 迭代(塊迭代/線迭代)，或者交替方向隱式迭 代(交替方向線迭代)。 差分離散方程為

5、時(shí)間層演進(jìn)，上標(biāo)為n, n+1 迭代格式代表迭代層演進(jìn)，上標(biāo)(k),(k+1) 12基礎(chǔ)課件 1) 點(diǎn)迭代法點(diǎn)迭代法 (顯式迭代顯式迭代) i 簡(jiǎn)單迭代：簡(jiǎn)單迭代：又稱(chēng)Jacobi迭代 優(yōu)點(diǎn)：構(gòu)造簡(jiǎn)單 缺點(diǎn)：收斂很慢 (1)( )( )( )( )nnnnn PEEWWNNSSP Ta Ta Ta Ta Tba 13基礎(chǔ)課件 1) 點(diǎn)迭代法點(diǎn)迭代法 (顯式迭代顯式迭代) ii Gause-Seidel(G-S)迭代迭代: 立即立即啟用新值啟用新值 收斂速度明顯加快。收斂速度還與掃描方向 有關(guān)。越是能把邊界條件的影響盡快引入 迭代的方向，越有利于加快收斂。 (1)( )(1)( )(1)nnnn

6、n PEEWWNNSSP Ta Ta Ta Ta Tba 14基礎(chǔ)課件 1) 點(diǎn)迭代法點(diǎn)迭代法 (顯式迭代顯式迭代) iii 逐次松弛迭代逐次松弛迭代(SOR/SUR): 將將簡(jiǎn)單迭代或者G-S迭代之值，與上一輪迭代 值加權(quán)平均 基于簡(jiǎn)單迭代： 或基于G-S：(從左往右，從下往上) (1)( )( )( )( )( ) (1) nnnnnn PPEEWWNNSSP TTa Ta Ta Ta Tba (1)( )( )(1)( )(1) (1) nnnnnn PPEEWWNNSSP TTa Ta Ta Ta Tba 15基礎(chǔ)課件 松弛因子 逐次超松弛(SOR) 逐次欠松弛(SUR) 1 1 02

7、 16基礎(chǔ)課件 一般形式 相鄰兩輪的迭代值之差恒為正或負(fù)時(shí)，采 用超松弛能加速收斂。 當(dāng)相鄰兩輪的迭代值之差的符號(hào)無(wú)規(guī)變化 時(shí)，采用亞松弛，可以避免迭代發(fā)散 (1) (1)( )( ) , 02 n nnn P PPP TTTT GS或簡(jiǎn)單迭代結(jié)果 17基礎(chǔ)課件 2) 塊迭代法(隱式迭代) 將解域分成為由一條網(wǎng)格線或數(shù)條網(wǎng)格線組 成的若干個(gè)塊，每個(gè)塊內(nèi)節(jié)點(diǎn)值以隱式方法 相互關(guān)聯(lián)，用 TDMA 得到其解，格塊之間則 按迭代方式推進(jìn) 按列掃描 按行掃描 18基礎(chǔ)課件 特別注意 雖然差分離散格式方程為全隱式，但其迭 代求解方法可以是顯式迭代，隱式迭代， 或者交替方向隱式迭代。 差分離散方程為時(shí)間層演

8、進(jìn)，上標(biāo)為n, n+1 迭代格式代表迭代層演進(jìn)，上標(biāo)(n),(n+1) 19基礎(chǔ)課件 2) 塊迭代法(隱式迭代) i 簡(jiǎn)單線迭代簡(jiǎn)單線迭代 逐列掃描逐列掃描： (1)(1)(1)( )( )nnnnn SSPPNNEEWW a Ta Ta Ta Ta Tb 20基礎(chǔ)課件 2) 塊迭代法(隱式迭代) i 簡(jiǎn)單線迭代簡(jiǎn)單線迭代 逐行掃描逐行掃描： (1)(1)(1)( )( )nnnnn WWPPEENNSS a Ta Ta Ta Ta Tb 21基礎(chǔ)課件 實(shí)施 引入邊界條件后，均可用TDMA直接求解。 整個(gè)解域逐線掃描一遍后，完成一輪迭代 22基礎(chǔ)課件 2) 塊迭代法(隱式迭代) ii Gaus

9、s-Seidel線迭代線迭代:立即啟用新值 從左往右逐列掃描：從左往右逐列掃描： (1)(1)(1)( )(1)nnnnn SSPPNNEEWW a Ta Ta Ta Ta Tb 23基礎(chǔ)課件 2) 塊迭代法(隱式迭代) ii Gauss-Seidel線迭代線迭代:立即啟用新值 從下往上逐行掃描：從下往上逐行掃描： (1)(1)(1)( )(1)nnnnn WWPPEENNSS a Ta Ta Ta Ta Tb 24基礎(chǔ)課件 2) 塊迭代法(隱式迭代) iii 逐次松弛線迭代逐次松弛線迭代(SOR/SUR) 在完成簡(jiǎn)單或G-S線迭代計(jì)算過(guò)程后，將其所 算之值與上一輪迭代之值作加權(quán)平均，所 得值

10、才算新一輪迭代的新值 25基礎(chǔ)課件 直接寫(xiě)成一步計(jì)算 (1)(1)(1)()()(1) (1) nnnnnn SSPPNNPPEEWW a Ta Ta Ta Ta Ta Tb 26基礎(chǔ)課件 3) 交替方向隱式迭代(ADI) 此法掃描方向可以變化，且有多種組合。 27基礎(chǔ)課件 3 判斷迭代格式收斂的 幾個(gè)常用條件 28基礎(chǔ)課件 正定矩陣 對(duì)任意具有n個(gè)分量的非零矢量函數(shù)x ,1 0 n T ijij i j a x x x Ax 29基礎(chǔ)課件 不可約矩陣 矩陣A不能通過(guò)行的次序調(diào)換和其相應(yīng)列的 次序調(diào)換而成為： 1112 22 0 AA A 30基礎(chǔ)課件 對(duì)角優(yōu) 矩陣A對(duì)角線上的元素滿足 1 , 1,2, n iiij j j i aain 31基礎(chǔ)課件 迭代收斂判斷定理 1 若方程組的系數(shù)矩陣A不可約，且對(duì)角優(yōu)， 則簡(jiǎn)單迭代和Gauss-Seidel迭代