五代数方程的求解-LSEC

五代数方程的求解-LSEC第一页，编辑于星期六：十一点六分。5.1代数方程系统有限差分(体积)离散格式提供一个网格点(单元）的代数方程,以线性代数方程为例：P点和周围邻居点构成计算模板(比差分基架还大）计算模板(计算分子;解元SE)第二页，编辑于星期六：十一点六分。25.1代数方程系统:计算模板2D2阶模板2D3阶模板3D2阶模板第三页，编辑于星期六：十一点六分。35.1代数方程系统:整体方程系统流场中每一点都有一个方程(小组),整个计算域就有一个大型稀疏方程系统第四页，编辑于星期六：十一点六分。45.1代数方程系统:系数矩阵的存储只存储非零的对角元素2维5点格式：5Ni*Nj3维7点格式：7Ni*Nj*NkAl,l-Nj=WAl,l-1=SAl,l=PAl,l+1=NAl,l+Nj=E

第五页，编辑于星期六：十一点六分。55.2直接法5.2.1Gausselimination5.2.2LUdecomposition5.2.3Tridiagonalsystem5.2.4Cyclicreduction第六页，编辑于星期六：十一点六分。65.2.1GaussEliminationBybackwardsubstitution,wehavefromRequireO(n3/3)arithmeticoperationBackwardsubstitutionO(n2/2)PivotingRarelyusedinCFDforwardelimination第七页，编辑于星期六：十一点六分。75.2.2LUdecompositionwhereletthenRequireO(2n2)arithmeticoperationBasisofotheriterativemethods第八页，编辑于星期六：十一点六分。85.2.3Tridiagonalsystem(TDMA)

*Givesupperbi-diagonalmatrix.Bybackwardsubstitution,wegetelimination:***第九页，编辑于星期六：十一点六分。95.2.3Tridiagonalsystem:块三对角方程组第十页，编辑于星期六：十一点六分。105.2.3Tridiagonalsystem(cont)计算量O(n)周期三对角方程组三对角方程组的并行化解法cyclicreduction,recursivedoubling,SPP…五对角方程组（类似三对角）第十一页，编辑于星期六：十一点六分。115.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第十二页，编辑于星期六：十一点六分。12迭代误差迭代解的收敛：MatrixAissparse设n次迭代的近似解为,不满足上述方程，带入上述方程后有残量：5.3.1基本概念实际计算中:第十三页，编辑于星期六：十一点六分。135.3.2收敛性Consideraniterativeschemeforalinearsystem上两式相减或M称为迭代矩阵第十四页，编辑于星期六：十一点六分。14设特征向量完备，则isthelargesteigenvalue迭代次数：5.3.2收敛性（续）趋于零的充要条件：第十五页，编辑于星期六：十一点六分。155.3.2收敛性：收敛速度第十六页，编辑于星期六：十一点六分。16Jacobimethod:Gauss-SeidelMethod:SuccessiveOver-relaxation(SORifw>1):UsefulforsolvinglinearsystemsoccurringincertainPDE’sForpositivedefinitematrix,theSORconvergesforConvergeslow2timesasfastasJacobi5.3.3一些基本迭代方法第十七页，编辑于星期六：十一点六分。17GS和SOR的一般形式第十八页，编辑于星期六：十一点六分。18GS迭代法的应用：LU-SGS奇次迭代步从左下角开始，偶次迭代步就从右上角开始第十九页，编辑于星期六：十一点六分。19GS迭代法的应用：线-SGS第二十页，编辑于星期六：十一点六分。20GS迭代法的应用：并行的Red-black第二十一页，编辑于星期六：十一点六分。215.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五点格式：LM=A+NU第二十二页，编辑于星期六：十一点六分。22StandardILU:收敛慢！第二十三页，编辑于星期六：十一点六分。23Stone(1968):SIPN在7条对角线都可以有元素N和向量φ相的结果尽量接近零N*φ:要求：第二十四页，编辑于星期六：十一点六分。24SIP:(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书附件。第二十五页，编辑于星期六：十一点六分。255.3.5ADI和其他分裂方法主要解对多维抛物型方程，也可以解拟时间的抛物型方程->椭圆形方程Crank-NicholsonDiscretizationwhere2D抛物型方程第二十六页，编辑于星期六：十一点六分。26改写成Thelasttermisproportiontoandcanbeneglected.只需求解两个坐标坐标方向的三对角线方程。2D无条件稳定。3D有条件稳定。特殊形式可以无条件稳定。增量形式ADI称为approximatefactorization(AF)。优点:收敛性快,计算量不大，缺点：中间变量的边界条件不知道。第二十七页，编辑于星期六：十一点六分。275.3.6Conjugategradientmethods

线性代数方程和极小化：对于对称正定矩阵A，求解共轭:等价于找到,使F极小化：

第二十八页，编辑于星期六：十一点六分。285.3.6Conjugategradientmethods(cont)

最速下降法：收敛慢，搜索方向可能重复共轭梯度法：新的搜索方向要求和过去所有的搜索方向共轭n*n矩阵，n次搜索就可以收敛

CG的收敛速度依赖于A的条件数CFD问题的条件数~Ni**2

改进（其实对所有方法都有效):预处理第二十九页，编辑于星期六：十一点六分。29M=C-1,

C为pre-conditioningmatrix.ThechoiceofMisincompletecholeskyLU对称正定矩阵方程的Conjugategradientmethod(GolubandvanLoan,Matrixcomputation,1990)第三十页，编辑于星期六：十一点六分。30非对称矩阵方程的Bi-conjugategradientmethodCG方法只适用于对称系统(如Poisson方程)把非对称转化为对称：第一个方程：原始方程第二个方程：转置方程，与解无关。WhenpreconditionedCGmethodisappliedtoabovesystem,thefollowingbi-conjugategradientmethodresults:第三十一页，编辑于星期六：十一点六分。31适用于非对称矩阵的Bi-conjugategradient算法如下:2倍于CG的计算量，相同的收敛速度，鲁棒性好第三十二页，编辑于星期六：十一点六分。32其他解法CGSTAB(稳定化的CG)√GMRES(SaadandShultz,1986)第三十三页，编辑于星期六：十一点六分。335.3.8Multigridmethods大多数迭代法在细网格上可以很快消除误差的高频分量，但低频分量相当顽固。可以在粗网格上消除这些低频分量。第三十四页，编辑于星期六：十一点六分。34典型V循环式多重网格法的粗网格、限制和插值算子第三十五页，编辑于星期六：十一点六分。35两级线性多重网格法步骤多级多重网格法：继续向更粗的网格限制，直到无更粗的网格为止。在最粗网格上精确求解修正方程。第三十六页，编辑于星期六：十一点六分。36公式描述:线性方程第三十七页，编辑于星期六：十一点六分。37公式描述:非线性方程第三十八页，编辑于星期六：十一点六分。38限制和插值算子:对于eq(5.63)1/2*eq(i-1)+½*eq(i+1)+eq(i)resultsin:第三十九页，编辑于星期六：十一点六分。39ComparisonofcountforconvergenceOn2DPoissonequation,k*kgrid,n=k2,unknownMethod

CostGaussianeliminationO(n3)GSO(n2logn)CGO(n1.5)FFT/CyclicreductionO(nlogn)MultigridO(n)optimal第四十页，编辑于星期六：十一点六分。40选择solverMG+SIPorMG+GS>ICCG>SIP>ADI>GSGMRES+MG没有MG时，ICCG>SIP>ADI>GS第四十一页，编辑于星期六：十一点六分。415.4其他迭代法

coupledequations(systemofnonlinearequations)Simultaneousapproach:Allequationsareconsideredpartofasinglesystem.Sequentialapproach:Eachequationissolvedforitsdominantvariable,treatingtheotherasknown,andoneiteratesthroughtheequationsuntilthesolutionofthecoupledsystemisobtained.Iterationsperformedoneachequationarecalledinneriteration.

Inordertoobtainasolutionwhichsatisfyallequations,thecoefficientmatricesandsourcevectormustbeupdatedaftereachcycleadtheprocess