五代數(shù)方程的求解ppt課件

1、(五五) 代數(shù)方程的求解代數(shù)方程的求解 5.1 代數(shù)方程系統(tǒng) 5.2 直接法 5.3 主要迭代法 5.4 其他迭代方法5.1 代數(shù)方程系統(tǒng) 有限差分(體積)離散格式提供一個(gè)網(wǎng)格點(diǎn)(單元的代數(shù)方程, 以線性代數(shù)方程為例： P點(diǎn)和周圍鄰居點(diǎn)構(gòu)成計(jì)算模板(比差分基架還大 計(jì)算模板(計(jì)算分子;解元SE)(1) lPllPPQAA5.1 代數(shù)方程系統(tǒng): 計(jì)算模板2D 2階模板2D 3階模板3D 2階模板5.1 代數(shù)方程系統(tǒng): 整體方程系統(tǒng) 流場中每一點(diǎn)都有一個(gè)方程(小組), 整個(gè)計(jì)算域就有一個(gè)大型稀疏方程系統(tǒng)向東，向上。從西南角開始，向北，在結(jié)構(gòu)網(wǎng)格上的排序：的排序。其結(jié)構(gòu)依賴于稀疏方陣, :(2) A

2、QA5.1 代數(shù)方程系統(tǒng): 系數(shù)矩陣的存儲(chǔ)只存儲(chǔ)非零的對(duì)角元素2維5點(diǎn)格式： 5 Ni *Nj3維7點(diǎn)格式： 7 Ni *Nj*NkAl,l-Nj=WAl,l-1 =SAl,l =PAl,l+1 =NAl,l+Nj=E PQEENNPPSSWWAAAAA5.2 直接法5.2.1 Gauss elimination5.2.2 LU decomposition5.2.3 Tridiagonal system5.2.4 Cyclic reduction5.2.1 Gauss EliminationBy backward substitution, we havefromRequire O(n3/3)

3、 arithmetic operationBackward substitution O(n2/2)Pivoting Rarely used in CFDforward elimination5.2.2 LU decompositionQA 的所有元素）（可求出UL, ALU QLU YU QLY whereletthenRequire O(2n2) arithmetic operationBasis of other iterative methods5.2.3 Tridiagonal system (TDMA)*Gives upper bi-diagonal matrix. By back

4、ward substitution, we getelimination:*5.2.3 Tridiagonal system:塊三對(duì)角方程組 1*1*11*11*11:onsubstitutiback and:neliminatioiiEiiPiiiPiWiiiEiPiWiPiPiiiEiiPiiWAQAQAAQQAAAAAQAAA5.2.3 Tridiagonal system (cont) 計(jì)算量 O (n) 周期三對(duì)角方程組 三對(duì)角方程組的并行化解法 cyclic reduction, recursive doubling, SPP 五對(duì)角方程組類似三對(duì)角 5.3 迭代法 5.3.1 根

5、本概念 5.3.2 收斂速度 5.3.3 一些根本方法 5.3.4 不完全LU 分解方法 5.3.5 ADI 和其他分裂方法 5.3.6 Conjugate gradient methods 5.3.7 Bi-conjugate gradients,CGSTAB, GMRES 5.3.8 Multigrid methods迭代誤差迭代解的收斂：Matrix A is sparse 設(shè)n次迭代的近似解為 , 不滿足上述方程，帶入上述方程后有殘量 ：nn5.3.1 根本概念根本概念0or , 0實(shí)踐計(jì)算中:速度預(yù)處理矩陣，加速收斂PPQPA5.3.2 收斂性 Consider an iterati

6、ve scheme for a linear system上兩式相減或n 這里M稱為迭代矩陣設(shè)特征向量完備，那么1is the largest eigenvalue迭代次數(shù)：5.3.2 收斂性續(xù)趨于零的充要條件：1k5.3.2 收斂性：收斂速度0,NAMNMAQA要想收斂快，要求：Jacobi method:iikikikiAR1nixAxAQRnijkjijijkjijiki,.,2 , 1,111Gauss-Seidel Method:iikikikiAR1nijkjijijkjijikixAxAQR1111Successive Over-relaxation (SOR if w1):Us

7、eful for solving linear systems occurring in certain PDEsiikikikiAR1nijkjijijkjijikixAxAQR111For positive definite matrix, the SOR converges for . 20Converge slow2 times as fast as Jacobi5.3.3 一些根本迭代方法GS 和SOR的普通方式ijijiiijijiipppppppaaiiaaXUXbLXSORUXbLXUXbLXGSULAbAX有且至少對(duì)一個(gè)收斂條件：,)1 (:,11111GS迭代法的運(yùn)用：LU

8、-SGSpppppppppppppppXUXDXDeiXUXLAXbXDXLAXbXDAXbXUDLXXXUDLAbAX*1 .:SweepU:SweepL)(,則奇次迭代步從左下角開場，偶次迭代步就從右上角開場GS迭代法的運(yùn)用：線-SGSjinjinjnjinjinjnjifuuuBuuuAybBxaAfyubxua,11,111, 111, 1222222)2()2(GS, ：線定義對(duì)于方程GS迭代法的運(yùn)用：并行的Red-black5.3.4 不完全LU 分解方法 (ILU)在PDE中的運(yùn)用：SIP方法LU method是通用方法，但沒有利用原矩陣的稀疏性質(zhì)；是通用方法，但沒有利用原矩陣的

9、稀疏性質(zhì)；ILU: 非準(zhǔn)確分解，非準(zhǔn)確分解，i.e. M=LU =A+N;在在ILU中中,假設(shè)迭代矩陣假設(shè)迭代矩陣M盡量接近原矩陣盡量接近原矩陣A，那么收斂快，那么收斂快.ILU method for CFD is Strongly Implicit Procedure (SIP)，by Stone. N 含有含有 兩個(gè)對(duì)角線的非零元素，而在兩個(gè)對(duì)角線的非零元素，而在 A卻為零卻為零.M中的元素由矩陣相乘得出：中的元素由矩陣相乘得出：M=LU公用的2D五點(diǎn)格式：LM=A+NUStandard ILU:收斂慢！Stone (1968):SIP N在7條對(duì)角線都可以有元素 N和向量相的結(jié)果盡量接近

10、零N* :要求：SIP: (cont)帶入 (5.39)，并等于5.38)，可以得到N的一切元素，并令M=A+N,可得到SIP的LU.(5.40)僅對(duì)PDE的點(diǎn)離散格式有效。SIP求解用更新變量： SIP求解由L-sweep和U-sweep組成 收斂所用迭代次數(shù)少,但計(jì)算L和U的任務(wù)量大，總體效率較高3D 七對(duì)角線和2D 九對(duì)角線(九點(diǎn)格式的程序見Peric書附件。ppAQLU15.3.5 ADI 和其他分裂方法 主要解對(duì)多維拋物型方程，也可以解擬時(shí)間的拋物型方程- 橢圓形方程Crank-Nicholson Discretizationwhere2D拋物型方程改寫成The last term

11、is proportion to and can be neglected.3)( t只需求解兩個(gè)坐標(biāo)坐標(biāo)方向的三對(duì)角線方程。2D無條件穩(wěn)定。3D有條件穩(wěn)定。特殊方式可以無條件穩(wěn)定。增量方式ADI稱為 approximate factorization (AF)。優(yōu)點(diǎn): 收斂性快, 計(jì)算量不大，缺陷：中間變量的邊境條件不知道。5.3.6 Conjugate gradient methods 線性代數(shù)方程和極小化： 對(duì)于對(duì)稱正定矩陣A，求解共軛 :0212211021PPPPAAFFPP是共軛的：關(guān)于矩陣如果這兩個(gè)方向意一個(gè)方向做極小化，我們只需要針對(duì)其中任：平面內(nèi)極小化假設(shè)在等價(jià)于找到 , 使

12、F極小化： i5.3.6 Conjugate gradient methods (cont)最速下降法：收斂慢，搜索方向能夠反復(fù)共軛梯度法：新的搜索方向要求和過去一切的搜索方向共軛 n*n矩陣，n次搜索就可以收斂 CG的收斂速度依賴于A的條件數(shù) CFD問題的條件數(shù) Ni*2 改良其實(shí)對(duì)一切方法都有效): 預(yù)處置minmaxCACCQCCACC精心選擇共軛梯度法應(yīng)用于11111(1) M=C-1, C為為pre-conditioning matrix. The choice of M is incomplete cholesky LU對(duì)稱正定矩陣方程的 Conjugate gradient me

13、thod(Golub and van Loan, Matrix computation, 1990) 非對(duì)稱矩陣方程的 Bi-conjugate gradient method CG 方法只適用于對(duì)稱系統(tǒng)(如Poisson方程) 把非對(duì)稱轉(zhuǎn)化為對(duì)稱：0AQAT第一個(gè)方程：原始方程第二個(gè)方程：轉(zhuǎn)置方程，與解無關(guān)。When preconditioned CG method is applied to above system , the following bi-conjugate gradient method results:適用于非對(duì)稱 矩陣的Bi-conjugate gradient 算法

14、如下:2倍于CG的計(jì)算量，一樣的收斂速度，魯棒性好其他解法 CGSTAB (穩(wěn)定化的CG) GMRES (Saad and Shultz, 1986)5.3.8 Multigrid methods 大多數(shù)迭代法在細(xì)網(wǎng)格上可以很快消除誤差的高頻分量，但低頻分量相當(dāng)頑固?？梢栽诖志W(wǎng)格上消除這些低頻分量。10031)(2)2()2(GS, ,1,111, 111, 1222222GGBABeAeBABeAeGfuuuBuuuAybBxaAfyubxuaiiiijinjinjnjinjinjnji，有，對(duì)于低頻分量，有且對(duì)誤差放大因子迭代法：點(diǎn)中心差分定義對(duì)于方程典型V循環(huán)式多重網(wǎng)格法的粗網(wǎng)格、限制和

15、插值算子兩級(jí)線性多重網(wǎng)格法步驟多級(jí)多重網(wǎng)格法：繼續(xù)向更粗的網(wǎng)格限制，直到無更粗的網(wǎng)格為止。在最粗網(wǎng)格上準(zhǔn)確求解修正方程。公式描畫:線性方程(3) )(I,)2(.(2) )(R,(1) cfcfoldfnewcffhfcfchfhffffffffhfcffLELLQQL可以得到，將此更新插值到細(xì)網(wǎng)格的近似解是設(shè)的誤差方程該方程逼近于細(xì)網(wǎng)格上網(wǎng)格上求解差比較光滑，可以在粗當(dāng)收斂較慢時(shí)，表明殘殘差為更新近似解細(xì)網(wǎng)格上需解方程：公式描畫:非線性方程(6) )(I(5) )(R)(R:(4) foldcfcfcfoldfnewfcfhfcfchfhffhhffhRLLLQLLQLccff網(wǎng)格上的誤差方

16、程差比較光滑，可以在粗當(dāng)收斂較慢時(shí)，表明殘細(xì)網(wǎng)格上殘差誤差方程細(xì)網(wǎng)格上需解方程：限制和插值算子:對(duì)于eq (5.63)1/2*eq(i-1)+*eq(i+1)+eq(i) results in:Comparison of count for convergence On 2D Poisson equation, k*k grid, n=k2, unknown Method Cost Gaussian elimination O(n3) GS O(n2logn) CG O(n1.5) FFT/Cyclic reduction O(nlogn) Multigrid O(n)optimal 選擇so

17、lver MG+SIP or MG +GS ICCG SIP ADI GS GMRES+MG 沒有MG時(shí)， ICCGSIP ADI GS5.4 其他迭代法coupled equations (system of nonlinear equations) Simultaneous approach: All equations are considered part of a single system. Sequential approach: Each equation is solved for its dominant variable, treating the other as kn

18、own, and one iterates through the equations until the solution of the coupled system is obtained. Iterations performed on each equation are called inner iteration. In order to obtain a solution which satisfy all equations, the coefficient matrices and source vector must be updated after each cycle ad the process repeated. The cycle are called outer iteration.Sequential solution: Under-RelaxationOn the nth iteration the equation for generic variable is Pat