代数方程的求解.课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,(,五,),代数方程的求解,5.1 代数方程系统,5.2 直接法,5.3 主要迭代法,5.4 其他迭代方法,1,5.1 代数方程系统,有限差分,(,体积,),离散格式提供一个网格点,(,单元）的代数方程,以线性代数方程为例：,P,点和周围邻居点构成计算模板,(,比差分基架还大）,计算模板,(,计算分子,;,解元,SE),2,5.1 代数方程系统:计算模板,2D 2,阶模板,2D 3,阶模板,3D 2,阶模板,3,5.1,代数方程系统,:,整体方程系统,流场中每一点都有一个方程,(,小组,),整个计算域就有一个大型稀疏方程系统,4,5.1,代数方程系统,:,系数矩阵的存储,只存储非零的对角元素,2,维,5,点格式：,5 Ni*Nj,3,维,7,点格式：,7 Ni*Nj*Nk,Al,l-Nj=W,Al,l-1=S,Al,l=P,Al,l+1=N,Al,l+Nj=E,5,5.2 直接法,5.2.1 Gauss elimination,5.2.2 LU decomposition,5.2.3 Tridiagonal system,5.2.4 Cyclic reduction,6,5.2.1 Gauss Elimination,By backward substitution,we have,from,Require,O,(n,3,/3)arithmetic operation,Backward substitution O(n,2,/2),Pivoting,Rarely used in CFD,forward elimination,7,5.2.2 LU decomposition,where,let,then,Require,O,(2n,2,)arithmetic operation,Basis of other iterative methods,8,5.2.3 Tridiagonal system(TDMA),*,Gives upper bi-diagonal matrix.By backward substitution,we get,elimination:,*,*,*,9,5.2.3 Tridiagonal system:,块三对角方程组,10,5.2.3 Tridiagonal system(cont),计算量,O(n),周期三对角方程组,三对角方程组的并行化解法,cyclic reduction,recursive doubling,SPP,五对角方程组（类似三对角）,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 methods,5.3.7 Bi-conjugate gradients,CGSTAB,GMRES,5.3.8 Multigrid methods,12,迭代误差,迭代解的收敛：,Matrix A is sparse,设n次迭代的近似解为 ,不满足上述方程，带入上述方程后有残量 ：,5.3.1,基本概念,实际计算中,:,13,5.3.2,收敛性,Consider an iterative scheme for a linear system,上两式相减,或,M,称为迭代矩阵,14,设特征向量完备，则,is the largest eigenvalue,迭代次数：,5.3.2,收敛性（续）,趋于零的充要条件：,15,5.3.2,收敛性：收敛速度,16,Jacobi method,:,Gauss-Seidel Method,:,Successive Over-relaxation(SOR if w1):,Useful for solving linear systems occurring in certain PDEs,For positive definite matrix,the SOR converges for,Converge slow,2 times as fast as Jacobi,5.3.3,一些基本迭代方法,17,GS 和SOR的一般形式,18,GS迭代法的应用：LU-SGS,奇次迭代步从左下角开始，偶次迭代步就从右上角开始,19,GS迭代法的应用：线-SGS,20,GS,迭代法的应用：并行的,Red-black,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,五点格式：,L,M=A+N,U,22,Standard ILU:,收敛慢！,23,Stone(1968):SIP,N,在,7,条对角线都可以有元素,N,和向量,相的结果尽量接近零,N*,:,要求：,24,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,书附件。,25,5.3.5 ADI,和其他分裂方法,主要解对多维抛物型方程，也可以解拟时间的抛物型方程,-,椭圆形方程,Crank-Nicholson Discretization,where,2D,抛物型方程,26,改写成,The last term is proportion to and can be neglected.,只需求解两个坐标坐标方向的三对角线方程。,2D,无条件稳定。,3D,有条件稳定。特殊形式可以无条件稳定。,增量形式,ADI,称为,approximate factorization (AF),。,优点,:,收敛性快,计算量不大，缺点：中间变量的边界条件不知道。,27,5.3.6 Conjugate gradient methods,线性代数方程和极小化：,对于对称正定矩阵,A,，求解,共轭,:,等价于找到,使,F,极小,化,：,28,5.3.6 Conjugate gradient methods(cont),最速下降法：收敛慢，搜索方向可能重复,共轭梯度法：新的搜索方向要求和过去所有的搜索方向共轭,n*n,矩阵，,n,次搜索就可以收敛,CG,的收敛速度依赖于,A,的条件数,CFD,问题的条件数,Ni*2,改进（其实对所有方法都有效,):,预处理,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,非对称矩阵方程的,Bi-conjugate gradient method,CG,方法只适用于对称系统,(,如,Poisson,方程,),把非对称转化为对称：,第一个方程：原始方程,第二个方程：转置方程，与解无关。,When preconditioned CG method is applied to above system,the following bi-conjugate gradient method results:,31,适用于非对称 矩阵的,Bi-conjugate gradient,算法如下,:,2,倍于,CG,的计算量，相同的收敛速度，鲁棒性好,32,其他解法,CGSTAB(,稳定化的,CG),GMRES (Saad and Shultz,1986),33,5.3.8 Multigrid methods,大多数迭代法在细网格上可以很快消除误差的高频分量，但低频分量相当顽固。可以在粗网格上消除这些低频分量。,34,典型,V,循环式多重网格法的粗网格、限制和插值算子,35,两级线性多重网格法步骤,多级多重网格法：继续向更粗的网格限制，直到无更粗的网格为止。在最粗网格上精确求解修正方程。,36,公式描述:线性方程,37,公式描述:非线性方程,38,限制和插值算子:,对于,eq(5.63),1/2*eq(i-1)+,*eq(i+1),+eq(i)results in:,39,Comparison of count for convergence,On 2D Poisson equation,k*k grid,n=k,2,unknown,Method,Cost,Gaussian elimination O(n,3,),GS O(n,2,logn),CG O(n,1.5,),FFT/Cyclic reduction O(nlogn),Multigrid O(n),optimal,40,选择solver,MG+SIP or MG+GS ICCG SIP ADI GS,GMRES+MG,没有MG时，ICCGSIP ADI GS,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,Sequential solution:Under-Relaxation,On the nth iteration the equation for generic variable is,Patankar 1980,对,SIMPLE,采用,稳定求解，但可能降低收敛率,时间相关法就是一种松驰法。,43,延迟修正办法,deferred-correction approaches,对于高阶差分离散，如果左端项用高阶差分,则计算复杂,如果左端项只保留相邻点的项，远邻点移到右端，则计算可能发散,为克服上述困难，可用,延迟修正,:,高,阶差分移到右端，同时在左右两端加仅涉及相邻点的低阶差分：,用途：可以处理隐式高阶差分、交叉导数项、非正交相等。但不能处理高阶导数项。,44,第5次课阅读提示,傅,计算流