代数方程的求解..ppt

1,(五)代数方程的求解,5.1代数方程系统5.2直接法5.3主要迭代法5.4其他迭代方法,2,5.1代数方程系统,有限差分(体积)离散格式提供一个网格点(单元）的代数方程,以线性代数方程为例：P点和周围邻居点构成计算模板(比差分基架还大）计算模板(计算分子;解元SE),3,5.1代数方程系统:计算模板,2D2阶模板,2D3阶模板,3D2阶模板,4,5.1代数方程系统:整体方程系统,流场中每一点都有一个方程(小组),整个计算域就有一个大型稀疏方程系统,5,5.1代数方程系统:系数矩阵的存储,只存储非零的对角元素2维5点格式：5Ni*Nj3维7点格式：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),计算量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,设n次迭代的近似解为,不满足上述方程，带入上述方程后有残量：,5.3.1基本概念,实际计算中:,14,5.3.2收敛性,Consideraniterativeschemeforalinearsystem,上两式相减,或,M称为迭代矩阵,15,设特征向量完备，则,isthelargesteigenvalue,迭代次数：,5.3.2收敛性（续）,趋于零的充要条件：,16,5.3.2收敛性：收敛速度,17,Jacobimethod:,Gauss-SeidelMethod:,SuccessiveOver-relaxation(SORifw1):UsefulforsolvinglinearsystemsoccurringincertainPDEs,Forpositivedefinitematrix,theSORconvergesfor,Convergeslow,2timesasfastasJacobi,5.3.3一些基本迭代方法,18,GS和SOR的一般形式,19,GS迭代法的应用：LU-SGS,奇次迭代步从左下角开始，偶次迭代步就从右上角开始,20,GS迭代法的应用：线-SGS,21,GS迭代法的应用：并行的Red-black,22,5.3.4不完全LU分解方法(ILU)在PDE中的应用：SIP方法,LUmethod是通用方法，但没有利用原矩阵的稀疏性质；ILU:非精确分解，i.e.M=LU=A+N;在ILU中,如果迭代矩阵M尽量接近原矩阵A，则收敛快.ILUmethodforCFDisStronglyImplicitProcedure(SIP)，byStone,.,N含有两个对角线的非零元素，而在A却为零.M中的元素由矩阵相乘得出：M=LU,专用的2D五点格式：,L,M=A+N,U,23,StandardILU:,收敛慢！,24,Stone(1968):SIP,N在7条对角线都可以有元素N和向量相的结果尽量接近零,N*:,要求：,25,SIP:(cont),带入(5.39)，并等于（5.38)，可以得到N的所有元素，并令M=A+N,可得到SIP的LU.(5.40)仅对PDE的点离散格式有效。SIP求解用更新变量：SIP求解由L-sweep和U-sweep组成收敛所用迭代次数少,但计算L和U的工作量大，总体效率较高3D七对角线和2D九对角线(九点格式）的程序见Peric书附件。,26,5.3.5ADI和其他分裂方法,主要解对多维抛物型方程，也可以解拟时间的抛物型方程-椭圆形方程,Crank-NicholsonDiscretization,where,2D抛物型方程,27,改写成,Thelasttermisproportiontoandcanbeneglected.,只需求解两个坐标坐标方向的三对角线方程。2D无条件稳定。3D有条件稳定。特殊形式可以无条件稳定。增量形式ADI称为approximatefactorization(AF)。优点:收敛性快,计算量不大，缺点：中间变量的边界条件不知道。,28,5.3.6Conjugategradientmethods,线性代数方程和极小化：对于对称正定矩阵A，求解共轭:,等价于找到,使F极小化：,29,5.3.6Conjugategradientmethods(cont),最速下降法：收敛慢，搜索方向可能重复共轭梯度法：新的搜索方向要求和过去所有的搜索方向共轭n*n矩阵，n次搜索就可以收敛CG的收敛速度依赖于A的条件数CFD问题的条件数Ni*2改进（其实对所有方法都有效):预处理,30,M=C-1,C为pre-conditioningmatrix.ThechoiceofMisincompletecholeskyLU,对称正定矩阵方程的Conjugategradientmethod,(GolubandvanLoan,Matrixcomputation,1990),31,非对称矩阵方程的Bi-conjugategradientmethod,CG方法只适用于对称系统(如Poisson方程)把非对称转化为对称：,第一个方程：原始方程第二个方程：转置方程，与解无关。WhenpreconditionedCGmethodisappliedtoabovesystem,thefollowingbi-conjugategradientmethodresults:,32,适用于非对称矩阵的Bi-conjugategradient算法如下:,2倍于CG的计算量，相同的收敛速度，鲁棒性好,33,其他解法,CGSTAB(稳定化的CG)GMRES(SaadandShultz,1986),34,5.3.8Multigridmethods,大多数迭代法在细网格上可以很快消除误差的高频分量，但低频分量相当顽固。可以在粗网格上消除这些低频分量。,35,典型V循环式多重网格法的粗网格、限制和插值算子,36,两级线性多重网格法步骤,多级多重网格法：继续向更粗的网格限制，直到无更粗的网格为止。在最粗网格上精确求解修正方程。,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时，ICCGSIPADIGS,42,5.4其他迭代法coupledequations(systemofnonlinearequations),Simultaneousapproach:Allequationsareconsideredpartofasinglesystem.Sequentialapproach:Eachequationissolvedforitsdominantvariable,treatingtheotherasknown,andoneiteratesthroughtheequationsuntilthesolutionofthecoupledsystemisobtained.Iterationsperformedoneachequationarecalledinneriteration.Inordertoobtainasolutionwhichsatisfyallequations,thecoefficientmatricesandsourcevectormustbeupdatedaftereachcycleadtheprocessrepeated.Thecyclearecalledouteriteration.,43,Sequentialsolution:Under-Relaxation,Onthenthiterationtheequationforgenericvariableis,Patankar1980对SIMPLE采用,稳定求解，但可能降低收敛率时间相关法就是一种松驰法。,44,5.4.2延迟修正办法deferred-correctionappr