五代數(shù)方程的求解LSEC.ppt

1,(五)代數(shù)方程的求解,5.1代數(shù)方程系統(tǒng)5.2直接法5.3主要迭代法5.4其他迭代方法,2,5.1代數(shù)方程系統(tǒng),有限差分(體積)離散格式提供一個(gè)網(wǎng)格點(diǎn)(單元）的代數(shù)方程,以線性代數(shù)方程為例：P點(diǎn)和周圍鄰居點(diǎn)構(gòu)成計(jì)算模板(比差分基架還大）計(jì)算模板(計(jì)算分子;解元SE),3,5.1代數(shù)方程系統(tǒng):計(jì)算模板,2D2階模板,2D3階模板,3D2階模板,4,5.1代數(shù)方程系統(tǒng):整體方程系統(tǒng),流場中每一點(diǎn)都有一個(gè)方程(小組),整個(gè)計(jì)算域就有一個(gè)大型稀疏方程系統(tǒng),5,5.1代數(shù)方程系統(tǒng):系數(shù)矩陣的存儲(chǔ),只存儲(chǔ)非零的對角元素2維5點(diǎn)格式：5Ni*Nj3維7點(diǎn)格式：7Ni*Nj*NkAl,l-Nj=WAl,l-1=SAl,l=PAl,l+1=NAl,l+Nj=E,6,5.2直接法,5.2.1Gausselimination5.2.2LUdecomposition5.2.3Tridiagonalsystem5.2.4Cyclicreduction,7,5.2.1GaussElimination,Bybackwardsubstitution,wehave,from,RequireO(n3/3)arithmeticoperationBackwardsubstitutionO(n2/2)PivotingRarelyusedinCFD,forwardelimination,8,5.2.2LUdecomposition,where,let,then,RequireO(2n2)arithmeticoperationBasisofotheriterativemethods,9,5.2.3Tridiagonalsystem(TDMA),*,Givesupperbi-diagonalmatrix.Bybackwardsubstitution,weget,elimination:,*,*,*,10,5.2.3Tridiagonalsystem:塊三對角方程組,11,5.2.3Tridiagonalsystem(cont),計(jì)算量O(n)周期三對角方程組三對角方程組的并行化解法cyclicreduction,recursivedoubling,SPP五對角方程組（類似三對角）,12,5.3迭代法,5.3.1基本概念5.3.2收斂速度5.3.3一些基本方法5.3.4不完全LU分解方法5.3.5ADI和其他分裂方法5.3.6Conjugategradientmethods5.3.7Bi-conjugategradients,CGSTAB,GMRES5.3.8Multigridmethods,13,迭代誤差,迭代解的收斂：,MatrixAissparse,設(shè)n次迭代的近似解為,不滿足上述方程，帶入上述方程后有殘量：,5.3.1基本概念,實(shí)際計(jì)算中:,14,5.3.2收斂性,Consideraniterativeschemeforalinearsystem,上兩式相減,或,M稱為迭代矩陣,15,設(shè)特征向量完備，則,isthelargesteigenvalue,迭代次數(shù)：,5.3.2收斂性（續(xù)）,趨于零的充要條件：,16,5.3.2收斂性：收斂速度,17,Jacobimethod:,Gauss-SeidelMethod:,SuccessiveOver-relaxation(SORifw1):UsefulforsolvinglinearsystemsoccurringincertainPDEs,Forpositivedefinitematrix,theSORconvergesfor,Convergeslow,2timesasfastasJacobi,5.3.3一些基本迭代方法,18,GS和SOR的一般形式,19,GS迭代法的應(yīng)用：LU-SGS,奇次迭代步從左下角開始，偶次迭代步就從右上角開始,20,GS迭代法的應(yīng)用：線-SGS,21,GS迭代法的應(yīng)用：并行的Red-black,22,5.3.4不完全LU分解方法(ILU)在PDE中的應(yīng)用：SIP方法,LUmethod是通用方法，但沒有利用原矩陣的稀疏性質(zhì)；ILU:非精確分解，i.e.M=LU=A+N;在ILU中,如果迭代矩陣M盡量接近原矩陣A，則收斂快.ILUmethodforCFDisStronglyImplicitProcedure(SIP)，byStone,.,N含有兩個(gè)對角線的非零元素，而在A卻為零.M中的元素由矩陣相乘得出：M=LU,專用的2D五點(diǎn)格式：,L,M=A+N,U,23,StandardILU:,收斂慢！,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)格式）的程序見Peric書附件。,26,5.3.5ADI和其他分裂方法,主要解對多維拋物型方程，也可以解擬時(shí)間的拋物型方程-橢圓形方程,Crank-NicholsonDiscretization,where,2D拋物型方程,27,改寫成,Thelasttermisproportiontoandcanbeneglected.,只需求解兩個(gè)坐標(biāo)坐標(biāo)方向的三對角線方程。2D無條件穩(wěn)定。3D有條件穩(wěn)定。特殊形式可以無條件穩(wěn)定。增量形式ADI稱為approximatefactorization(AF)。優(yōu)點(diǎn):收斂性快,計(jì)算量不大，缺點(diǎn)：中間變量的邊界條件不知道。,28,5.3.6Conjugategradientmethods,線性代數(shù)方程和極小化：對于對稱正定矩陣A，求解共軛:,等價(jià)于找到,使F極小化：,29,5.3.6Conjugategradientmethods(cont),最速下降法：收斂慢，搜索方向可能重復(fù)共軛梯度法：新的搜索方向要求和過去所有的搜索方向共軛n*n矩陣，n次搜索就可以收斂CG的收斂速度依賴于A的條件數(shù)CFD問題的條件數(shù)Ni*2改進(jìn)（其實(shí)對所有方法都有效):預(yù)處理,30,M=C-1,C為pre-conditioningmatrix.ThechoiceofMisincompletecholeskyLU,對稱正定矩陣方程的Conjugategradientmethod,(GolubandvanLoan,Matrixcomputation,1990),31,非對稱矩陣方程的Bi-conjugategradientmethod,CG方法只適用于對稱系統(tǒng)(如Poisson方程)把非對稱轉(zhuǎn)化為對稱：,第一個(gè)方程：原始方程第二個(gè)方程：轉(zhuǎn)置方程，與解無關(guān)。WhenpreconditionedCGmethodisappliedtoabovesystem,thefollowingbi-conjugategradientmethodresults:,32,適用于非對稱矩陣的Bi-conjugategradient算法如下:,2倍于CG的計(jì)算量，相同的收斂速度，魯棒性好,33,其他解法,CGSTAB(穩(wěn)定化的CG)GMRES(SaadandShultz,1986),34,5.3.8Multigridmethods,大多數(shù)迭代法在細(xì)網(wǎng)格上可以很快消除誤差的高頻分量，但低頻分量相當(dāng)頑固?？梢栽诖志W(wǎng)格上消除這些低頻分量。,35,典型V循環(huán)式多重網(wǎng)格法的粗網(wǎng)格、限制和插值算子,36,兩級線性多重網(wǎng)格法步驟,多級多重網(wǎng)格法：繼續(xù)向更粗的網(wǎng)格限制，直到無更粗的網(wǎng)格為止。在最粗網(wǎng)格上精確求解修正方程。,37,公式描述:線性方程,38,公式描述:非線性方程,39,限制和插值算子:,對于eq(5.63)1/2*eq(i-1)+*eq(i+1)+eq(i)resultsin:,40,Comparisonofcountforconvergence,On2DPoissonequation,k*kgrid,n=k2,unknownMethodCostGaussianeliminationO(n3)GSO(n2logn)CGO(n1.5)FFT/CyclicreductionO(nlogn)MultigridO(n),optimal,41,選擇solver,MG+SIPorMG+GSICCGSIPADIGSGMRES+MG沒有MG時(shí)，ICCGSIPADIGS,42,5.4其他迭代法coupledequations(systemofnonlinearequations),Simultaneousapproach:Allequationsareconsideredpartofasinglesystem.Sequentialapproach:Eachequationissolvedforitsdominantvariable,treatingtheotherasknown,andoneiteratesthroughtheequationsuntilthesolutionofthecoupledsystemisobtained.Iterationsperformedoneachequationarecalledinneriteration.Inordertoobtainasolutionwhichsatisfyallequations,thecoefficientmatricesandsourcevectormustbeupdatedaftereachcycleadtheprocessrepeated.Thecyclearecalledouteriteration.,43,Sequentialsolution:Under-Relaxation,Onthenthiterationtheequationforgenericvariableis,Patankar1980對SIMPLE采用,穩(wěn)定求解，但可能降低收斂率時(shí)間相關(guān)法就是一種松馳法。,44,5.4.2延遲修正辦法deferred-correctionappr