《代數(shù)方程的求解》PPT課件

《《代數(shù)方程的求解》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《代數(shù)方程的求解》PPT課件（46頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

2、: (2) A QA 5 5.1 代數(shù)方程系統(tǒng): 系數(shù)矩陣的存儲只存儲非零的對角元素 2維5點(diǎn)格式： 5 Ni *Nj 3維7點(diǎn)格式： 7 Ni *Nj*Nk Al,l-Nj=W Al,l-1 =S Al,l =P Al,l+1 =N Al,l+Nj=E PQ EENNPPSSWW AAAAA 6 5.2 直接法5.2.1 Gauss elimination5.2.2 LU decomposition5.2.3 Tridiagonal system5.2.4 Cyclic reduction 7 5.2.1 Gauss EliminationBy backward substitution,

3、we havefromRequire O(n 3/3) arithmetic operationBackward substitution O(n2/2)Pivoting Rarely used in CFD forward elimination 8 5.2.2 LU decompositionQA的所有元素）（可求出UL, ALU QLU YUQLY whereletthenRequire O(2n 2) arithmetic operationBasis of other iterative methods 9 5.2.3 Tridiagonal system (TDMA)* Gives

4、 upper bi-diagonal matrix. By backward substitution, we getelimination: * * 10 5.2.3 Tridiagonal system:塊三對角方程組 1*1* *11* 11* 11 :onsubstitutiback and :neliminatio iiEiiPi iiPiWii iEiPiWiPiP iiiEiiPiiW AQA QAAQQ AAAAA QAAA 11 5.2.3 Tridiagonal system (cont)計(jì)算量 O (n)周期三對角方程組三對角方程組的并行化解法 cyclic reduct

5、ion, recursive doubling, SPP 五對角方程組（類似三對角） 12 5.3迭代法 5.3.1 基本概念 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 13迭代誤差迭代解的收斂： Matrix A is sparse 設(shè)n次迭代的近似解為 , 不滿足上述方程，帶入上述方程后有殘量 ：nn 5.3.1 基本

6、概念 0or ,0 實(shí)際計(jì)算中:速度預(yù)處理矩陣，加速收斂P PQPA 14 5.3.2 收斂性 Consider an iterative scheme for a linear system上兩式相減或 n 這里M稱為迭代矩陣 15 設(shè)特征向量完備，則 1 is the largest eigenvalue迭代次數(shù)： 5.3.2 收斂性（續(xù)）趨于零的充要條件：1 k 16 5.3.2 收斂性：收斂速度0, NAMNMA QA要想收斂快，要求： 17 Jacobi method:iikikiki AR 1 nixAxAQR nij kjijij kjijiki ,.,2,1,111 Gauss

7、-Seidel Method: iikikiki AR 1 nij kjijij kjijiki xAxAQR 111 1 Successive Over-relaxation (SOR if w1):Useful for solving linear systems occurring in certain PDEsiikikiki AR 1 nij kjijij kjijiki xAxAQR 11 1For positive definite matrix, the SOR converges for .20 Converge slow2 times as fast as Jacobi 5

8、.3.3 一些基本迭代方法 18 GS 和SOR的一般形式 ij ijii ij ijii ppp pp pp aa iiaa XUXbLXSOR UXbLX UXbLXGS ULA bAX有且至少對一個收斂條件：, )1(: , 11 11 1 19 GS迭代法的應(yīng)用：LU-SGS ppp pppp ppp pp ppp XUXDXDei XUXLAXbXD XLAXbXD AXbXUDL XXX UDLA bAX * * 1 . :SweepU :SweepL )( ,則奇次迭代步從左下角開始，偶次迭代步就從右上角開始 20 GS迭代法的應(yīng)用：線-SGS jinjinjnjin jinjn

9、 ji fuuuBuuuA ybBxaA fyubxua ,11,111,111,1 222222 )2()2(GS , ：線定義 對于方程 21 GS迭代法的應(yīng)用：并行的Red-black 22 5.3.4 不完全LU 分解方法 (ILU)在PDE中的應(yīng)用：SIP方法 LU method是通用方法，但沒有利用原矩陣的稀疏性質(zhì)； ILU: 非精確分解，i.e. M=LU =A+N;在ILU中,如果迭代矩陣M盡量接近原矩陣A，則收斂快. ILU method for CFD is Strongly Implicit Procedure (SIP)，by Stone. N 含有 兩個對角線的非零元

10、素，而在 A卻為零.M中的元素由矩陣相乘得出：M=LU專用的2D五點(diǎn)格式：L M=A+NU 23 Standard ILU:收斂慢！ 24 Stone (1968):SIP N在7條對角線都可以有元素 N和向量相的結(jié)果盡量接近零N* :要求： 25 SIP: (cont)帶入 (5.39)，并等于（5.38)，可以得到N的所有元素，并令M=A+N,可得到SIP的LU. (5.40)僅對PDE的點(diǎn)離散格式有效。 SIP求解用更新變量： SIP求解由L-sweep和U-sweep組成 收斂所用迭代次數(shù)少,但計(jì)算L和U的工作量大，總體效率較高 3D 七對角線和2D 九對角線(九點(diǎn)格式）的程序見Per

11、ic書附件。 pp AQLU 1 26 5.3.5 ADI 和其他分裂方法 主要解對多維拋物型方程，也可以解擬時間的拋物型方程- 橢圓形方程Crank-Nicholson Discretizationwhere2D拋物型方程 27 改寫成The last term is proportion to and can be neglected.3)( t 只需求解兩個坐標(biāo)坐標(biāo)方向的三對角線方程。2D無條件穩(wěn)定。3D有條件穩(wěn)定。特殊形式可以無條件穩(wěn)定。增量形式ADI稱為 approximate factorization (AF)。優(yōu)點(diǎn): 收斂性快, 計(jì)算量不大，缺點(diǎn)：中間變量的邊界條件不知道。 2

12、8 5.3.6 Conjugate gradient methods 線性代數(shù)方程和極小化： 對于對稱正定矩陣A，求解共軛 : 021 22110 21 PP PPA AF FPP是共軛的：關(guān)于矩陣如果這兩個方向意一個方向做極小化，我們只需要針對其中任：平面內(nèi)極小化假設(shè)在等價于找到 , 使F極小化： i 29 5.3.6 Conjugate gradient methods (cont)最速下降法：收斂慢，搜索方向可能重復(fù)共軛梯度法：新的搜索方向要求和過去所有的搜索方向共軛 n*n矩陣，n次搜索就可以收斂 CG的收斂速度依賴于A的條件數(shù) CFD問題的條件數(shù) Ni*2 改進(jìn)（其實(shí)對所有方法都有效

13、): 預(yù)處理 minmax C ACCQCCACC精心選擇共軛梯度法應(yīng)用于11111 (1) 30M=C-1, C為pre-conditioning matrix. The choice of M is incomplete cholesky LU 對稱正定矩陣方程的 Conjugate gradient method(Golub and van Loan, Matrix computation, 1990) 31 非對稱矩陣方程的 Bi-conjugate gradient method CG 方法只適用于對稱系統(tǒng)(如Poisson方程)把非對稱轉(zhuǎn)化為對稱： 0A QAT第一個方程：原始方程

14、第二個方程：轉(zhuǎn)置方程，與解無關(guān)。When preconditioned CG method is applied to above system , the following bi-conjugate gradient method results: 32 適用于非對稱 矩陣的Bi-conjugate gradient 算法如下: 2倍于CG的計(jì)算量，相同的收斂速度，魯棒性好 33 其他解法 CGSTAB (穩(wěn)定化的CG) GMRES (Saad and Shultz, 1986) 34 5.3.8 Multigrid methods大多數(shù)迭代法在細(xì)網(wǎng)格上可以很快消除誤差的高頻分量，但低頻分

15、量相當(dāng)頑固?？梢栽诖志W(wǎng)格上消除這些低頻分量。 1 0031 )(2 )2()2( GS, , ,1,111,111,1 222222 GG BA BeAeBA BeAeG fuuuBuuuA ybBxaA fyubxua ii ii jinjinjnjin jinjn ji，有，對于低頻分量，有且對誤差放大因子迭代法：點(diǎn)中心差分定義對于方程 35 典型V循環(huán)式多重網(wǎng)格法的粗網(wǎng)格、限制和插值算子 36 兩級線性多重網(wǎng)格法步驟多級多重網(wǎng)格法：繼續(xù)向更粗的網(wǎng)格限制，直到無更粗的網(wǎng)格為止。在最粗網(wǎng)格上精確求解修正方程。 37 公式描述:線性方程 (3) )(I ,)2( .(2) )(R , (1)

16、cfcfoldfnew c ffhfcfch fhff ffff ffh fc ff LEL LQQL 可以得到，將此更新插值到細(xì)網(wǎng)格的近似解是設(shè)的誤差方程該方程逼近于細(xì)網(wǎng)格上網(wǎng)格上求解差比較光滑，可以在粗當(dāng)收斂較慢時，表明殘殘差為更新近似解細(xì)網(wǎng)格上需解方程： 38 公式描述:非線性方程 (6) )(I (5) )(R)(R: (4) foldcfcfcfoldfnew fcfhfcfch fhffhh ffh RLL LQLL QL cc ff 網(wǎng)格上的誤差方程差比較光滑，可以在粗當(dāng)收斂較慢時，表明殘細(xì)網(wǎng)格上殘差誤差方程細(xì)網(wǎng)格上需解方程： 39 限制和插值算子:對于eq (5.63) 1/2

17、*eq(i-1)+*eq(i+1)+eq(i) results in: 40 Comparison of count for convergence On 2D Poisson equation, k*k grid, n=k2, unknown Gaussian elimination O(n3)GS O(n2logn)CG O(n1.5)FFT/Cyclic reduction O(nlogn)Multigrid O(n)optimal 41 選擇solver MG+SIP or MG +GS ICCG SIP ADI GS GMRES+MG 沒有MG時， ICCGSIP ADI GS 42

18、 5.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 known, and one iterates through the equations until the solution of t

19、he 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. 43 Se

20、quential solution: Under-RelaxationOn the nth iteration the equation for generic variable is Patankar 1980對SIMPLE采用, 穩(wěn)定求解，但可能降低收斂率時間相關(guān)法就是一種松馳法。 44 5.4.2延遲修正辦法deferred-correction approaches對于高階差分離散，如果左端項(xiàng)用高階差分,則計(jì)算復(fù)雜如果左端項(xiàng)只保留相鄰點(diǎn)的項(xiàng)，遠(yuǎn)鄰點(diǎn)移到右端，則計(jì)算可能發(fā)散為克服上述困難，可用延遲修正: 高階差分移到右端，同時在左右兩端加僅涉及相鄰點(diǎn)的低階差分：用途：可以處理隱式高階差分、交叉導(dǎo)數(shù)項(xiàng)、非正交相等。但不能處理高階導(dǎo)數(shù)項(xiàng)。 45 第5次課閱讀提示傅計(jì)算流體力學(xué)第5章全部。 Peric書Chapter 5 全部。 46 第五次課后作業(yè)實(shí)踐Peric書附的代數(shù)方程求解程序（待具體 化）