五代数方程求解市公开课一等奖百校联赛特等奖课件.pptx

(五五)代数方程求解代数方程求解5.1 代数方程系统5.2 直接法5.3 主要迭代法5.4 其它迭代方法1第1页5.1 代数方程系统有限差分(体积)离散格式提供一个网格点(单元）代数方程,以线性代数方程为例：P点和周围邻居点组成计算模板(比差分基架还大）计算模板(计算分子;解元SE)2第2页5.1 代数方程系统:计算模板2D 2阶模板2D 3阶模板3D 2阶模板3第3页5.1 代数方程系统:整体方程系统流场中每一点都有一个方程(小组),整个计算域就有一个大型稀疏方程系统4第4页5.1 代数方程系统:系数矩阵存放只存放非零对角元素2维5点格式：5 Ni*Nj3维7点格式：7 Ni*Nj*NkAl,l-Nj=WAl,l-1=SAl,l=PAl,l+1=NAl,l+Nj=E 5第5页5.2 直接法5.2.1 Gauss elimination5.2.2 LU decomposition5.2.3 Tridiagonal system5.2.4 Cyclic reduction6第6页5.2.1 Gauss EliminationBy backward substitution,we havefromRequire O(n3/3)arithmetic operationBackward substitution O(n2/2)Pivoting Rarely used in CFDforward elimination7第7页5.2.2 LU decompositionwhereletthenRequire O(2n2)arithmetic operationBasis of other iterative methods8第8页5.2.3 Tridiagonal system(TDMA)*Gives upper bi-diagonal matrix.By backward substitution,we getelimination:*9第9页5.2.3 Tridiagonal system:块三对角方程组10第10页5.2.3 Tridiagonal system(cont)计算量 O(n)周期三对角方程组三对角方程组并行化解法cyclic reduction,recursive doubling,SPP 五对角方程组（类似三对角）11第11页5.3 迭代法5.3.1 基本概念5.3.2 收敛速度5.3.3 一些基本方法5.3.4 不完全LU 分解方法5.3.5 ADI 和其它分裂方法5.3.6 Conjugate gradient methods5.3.7 Bi-conjugate gradients,CGSTAB,GMRES5.3.8 Multigrid methods12第12页迭代误差迭代解收敛：Matrix A is sparse 设n次迭代近似解为 ,不满足上述方程，带入上述方程后有残量 ：5.3.1 基本概念基本概念实际计算中:13第13页5.3.2 收敛性Consider an iterative scheme for a linear system上两式相减或M称为迭代矩阵14第14页设特征向量完备，则is the largest eigenvalue迭代次数：5.3.2 收敛性（续）趋于零充要条件：15第15页5.3.2 收敛性：收敛速度16第16页Jacobi method:Gauss-Seidel Method:Successive Over-relaxation(SOR if w1):Useful for solving linear systems occurring in certain PDEsFor positive definite matrix,the SOR converges for Converge slow2 times as fast as Jacobi5.3.3 一些基本迭代方法17第17页GS 和SOR普通形式18第18页GS迭代法应用：LU-SGS奇次迭代步从左下角开始，偶次迭代步就从右上角开始19第19页GS迭代法应用：线-SGS20第20页GS迭代法应用：并行Red-black21第21页5.3.4 不完全LU 分解方法(ILU)在PDE中应用：SIP方法LU method是通用方法，但没有利用原矩阵稀疏性质；ILU:非准确分解，i.e.M=LU=A+N;在ILU中,假如迭代矩阵M尽可能靠近原矩阵A，则收敛快.ILU method for CFD is Strongly Implicit Procedure (SIP)，by Stone.N 含有 两个对角线非零元素，而在 A却为零.M中元素由矩阵相乘得出：M=LU专用2D五点格式：LM=A+NU22第22页Standard ILU:收敛慢！23第23页Stone(1968):SIPN在7条对角线都能够有元素N和向量相结果尽可能靠近零N*:要求：24第24页SIP:(cont)带入(5.39)，并等于（5.38)，能够得到N全部元素，并令M=A+N,可得到SIPLU.(5.40)仅对PDE点离散格式有效。SIP求解用更新变量：SIP求解由L-sweep和U-sweep组成 收敛所用迭代次数少,但计算L和U工作量大，总体效率较高3D 七对角线和2D 九对角线(九点格式）程序见Peric书附件。25第25页5.3.5 ADI 和其它分裂方法 主要解对多维抛物型方程，也能够解拟时间抛物型方程-椭圆形方程Crank-Nicholson Discretizationwhere2D抛物型方程26第26页改写成The last term is proportion to and can be neglected.只需求解两个坐标坐标方向三对角线方程。2D无条件稳定。3D有条件稳定。特殊形式能够无条件稳定。增量形式ADI称为 approximate factorization (AF)。优点:收敛性快,计算量不大，缺点：中间变量边界条件不知道。27第27页5.3.6 Conjugate gradient methods 线性代数方程和极小化：对于对称正定矩阵A，求解共轭:等价于找到 ,使F极小化：28第28页5.3.6 Conjugate gradient methods(cont)最速下降法：收敛慢，搜索方向可能重复共轭梯度法：新搜索方向要求和过去全部搜索方向共轭 n*n矩阵，n次搜索就能够收敛 CG收敛速度依赖于A条件数 CFD问题条件数 Ni*2 改进（其实对全部方法都有效):预处理29第29页M=C-1,C为pre-conditioning matrix.The choice of M is incomplete cholesky LU对称正定矩阵方程 Conjugate gradient method(Golub and van Loan,Matrix computation,1990)30第30页非对称矩阵方程 Bi-conjugate gradient methodCG 方法只适合用于对称系统(如Poisson方程)把非对称转化为对称：第一个方程：原始方程第二个方程：转置方程，与解无关。When preconditioned CG method is applied to above system,the following bi-conjugate gradient method results:31第31页适合用于非对称 矩阵Bi-conjugate gradient 算法以下:2倍于CG计算量，相同收敛速度，鲁棒性好32第32页其它解法CGSTAB(稳定化CG)GMRES (Saad and Shultz,1986)33第33页5.3.8 Multigrid methods大多数迭代法在细网格上能够很快消除误差高频分量，但低频分量相当顽固。能够在粗网格上消除这些低频分量。34第34页经典V循环式多重网格法粗网格、限制和插值算子35第35页两级线性多重网格法步骤多级多重网格法：继续向更粗网格限制，直到无更粗网格为止。在最粗网格上准确求解修正方程。36第36页公式描述:线性方程37第37页公式描述:非线性方程38第38页限制和插值算子:对于eq(5.63)1/2*eq(i-1)+*eq(i+1)+eq(i)results in:39第39页Comparison of count for convergenceOn 2D Poisson equation,k*k grid,n=k2,unknownMethod Method CostCostGaussian elimination O(n3)GS O(n2logn)CG O(n1.5)FFT/Cyclic reduction O(nlogn)Multigrid O(n)optimal 40第40页选择solverMG+SIP or MG+GS ICCG SIP ADI GSGMRES+MG 没有MG时，ICCGSIP ADI GS41第41页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 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.42第42页Sequential solution:Under-RelaxationOn the nth iteration the equation for generic variable is Patankar 1980对SIMPLE采取,稳定求解，但可能降低收敛率时间相关法就是一个松驰法。43第43页5.4.2延迟修正方法deferred-correction approaches对于高阶差分离散，假如左端项用高阶差分,则计算复杂假如左端项只保留相邻点项，远邻点移到右端，则计算可能发散为克服上述困难，可用延迟修正:高阶差分移到右端，同时在左右两端加仅包括相邻点低阶差分：用途：能够处理隐式高阶差分、交叉导数项、非正交相等。但不能处理高阶导数项。44第44页第5次课阅读提醒傅计算流体力学第5章全部。Peric书Chapter 5 全部。45第45页第五次课后作业实践Peric书附代数方程求解程序（待详细 化）46第46页