理学计算物理课件.ppt
1,5 Linear equations,5.1 Gauss elimination 5.2 Pivoting5.3 LU factorisation 5.4 The determinant and Inverse of a matrix5.5 Banded matrices and Tridiagonal matrices5.6 Other approaches to solving linear systems,2,In this chapter we deal with basic matrix operations,such as the solution of linear equations,calculate the inverse of a matrix,its determinant etc.,3,5.1 Gauss elimination,4,例1 用高斯消元法求解方程组,5,=,-,-,=,-,+,=,+,+,12,6,0,3,1,14,2,8,2,3,2,1,3,2,1,3,2,1,x,x,x,x,x,x,x,x,x,0,0,1,6,matrix operations,7,8,9,10,x1=x2=x3=1.,11,5.2 Pivoting,主元交换法,列主元交换法,行主元交换法,12,5.2.1 Partial pivoting,部分主元交换法,13,行主元交换法,14,例如.求解方程组,15,用高斯顺序消去法求解,16,用主元交换法求解,17,5.2.2 Full pivoting,全主元交换法,18,19,而交换列时解的次序发生改变,20,；,；,；,，,对,；,；,中选绝对值最大者,从,选主元,、第一步消元,j,t,i,l,a,then,a,if,do,n,j,n,i,t,l,a,n,j,i,a,ij,ij,ij,=,=,=,=,=,=,=,=,=,|,|,max,|,|,max,.,1,.,1,;,1,1,|,|,max,.,),.,2,1,(,),1,1,11,21,顺序消元；,；,做,，,，,，,初值,踪数组,因此设跟,而交换列时解的次序发生改变,),3,),(,),1,(,),Z(,.,2,),Z(2,1,),Z(1,),(,t,Z,Z,n,n,i,Z,=,=,=,22,高斯若当(Gauss-Jordan)消元法,23,5.3 LU factorisation,A=LU,24,25,26,27,Doolittle分解,若矩阵A有分解：A=LU，其中L为单位下三角阵，U为上三角阵，则称该分解为Doolittle分解，可以证明，当A的各阶顺序主子式均不为零时，Doolittle分解可以实现并且唯一。,28,A的各阶顺序主子式均不为零，即,29,Doolittle分解,30,Doolittle分解,31,Doolittle分解,32,将矩阵A进行LU分解,33,34,Y1=12Y2=7Y3=-2,x3=2,x2=1,x1=3,35,将矩阵A进行LU分解,36,37,Doolittle分解,38,Ax=w,Ax=BCx=w,By=w,y=Cx,This equation can be calculated in two steps,39,For our four-dimentional example this takes the form,By=w,y=Cx,40,forward substitution,Back substitution,41,例题,42,43,例题,44,所以方程组的解为,。,45,5.4 The determinant and Inverse of a matrix,矩阵的行列式和逆矩阵,46,定义矩阵A的行列式,.,1 The determinant of a matrix,=,The basic definition of the determinant of A is,47,1 The determinant of a matrix,48,The basic definition of the determinant of A is,A=LU,49,50,For the sake of simplicity,let us look at a(4x4)matrix A and a corresponding identity matrix I,The inverse of a matrix is defined by,2 The Inverse of a matrix,51,The inverse is slightly more difficult to obtain from the LU decomposition.It is formally defined as,If we call D for the inverse of B,we can determine the matrix elements of D through the equation,A=BC,2.1 LU decomposition,52,53,which gives the following general algorithm,which is valid for ij.The diagonal is 1 and the upper matrix elements are zero.We solve thisequation column by column(increasing order of j).,54,In a similar way we can define an equationwhich gives us the inverse of the matrix C,labelled E in the equation below.,with the following general equation,55,56,A calculation of the inverse of a matrix could then be implemented in the following way:,Set up the matrix to be inverted.Call the LU decomposition function.Check whether the determinant is zero or not.Then solve column by column eqs.,57,定理 设,A为非奇异矩阵，方程组,的增广矩阵为,，如果对C,应用高斯-若当方法化为,，则,2.2高斯-若当方法,58,例2 用高斯若当消元法求,的逆矩阵,.,59,60,5.5 Banded matrices and Tridiagonal matrices,In Banded matrices,the only non-zero elements fall within some distance of the leading diagonal.LU Factorisation may readily be modified to account for banded structure.For example,if elements outside the range ai,ib to ai,i+b are all zero,then the summations in the LU Factorisation algorithm need be performed only from k=i or k=i+1 to k=i+b.Moreover,the factorisation loop FOR q=i+1 TO n can terminate at i+b instead of n.,61,Tridiagonal matrices,62,63,=,-,-,-,n,n,n,n,n,b,a,c,b,a,c,b,a,c,b,A,1,1,1,2,2,2,1,1,O,O,O,64,65,三对角方程组的追赶法,66,例 用追赶法解三对角线方程组,67,u1=1/2,game1=0game2=-1/(2-0)=-1/2u2=(0+1/2)/(2-1/2)=1/3game3=-1/(2-1/2)=-2/3u3=1/3/(2-2/3)=1/4Game4=-1/(2-2/3)=3/4u4=(1+1/4)/(2+3/4)=5/11u3=1/4-15/44=-1/11u2=1/3-2/33=3/11u1=1/2+3/22=7/11,68,Finally,an important property of hermitian and symmetric matrices is that they have realeigenvalues.,69,Real orthogonal matrices is,70,矩阵特征值和特征向量的数值解法,幂法,逆幂法,古典Jacobi法,Jacobi法的改进,QR算法,71,QR算法是目前求一般矩阵全部特征值和特征向量行之有效的一种方法，它适合于对称矩阵，也适合于非对称矩阵。QR算法最早在1961年由J.G.Francis提出的，后来经一系列数学家进行深入讨论,并作出了做有成效的改进与发展。,QR算法,72,矩阵的QR分解,定理:设矩阵A非奇异，则一定存在正交矩阵Q，上三角矩阵R，使,且当要求R的主对角元素均为正数时，则上述分解式是唯一的。,QR算法是对A进行一系列的正交相似变换，达到求出矩阵A的全部特征值和相应的特征向量。,73,5.6 Other approaches to solving linear systems,Iteration,74,1.The Jacobi Iteration,75,其中,为初始向量.,76,前三次叠代的结果，要求取,77,78,79,80,81,82,用Jacobi 迭代法求解方程组,前三次叠代的结果，要求取,83,2.The Gauss-Seidel Iteration,In the Jacobi Iteration,84,In the Gauss-Seidel Iteration,85,高斯赛得尔（Gauss-Seidel）迭代法,（i=1,2,n）,86,87,用高斯赛得尔（Gauss-Seidel）迭代法求解方程组,前三次叠代的结果，要求取,88,89,90,Gauss-Seidel Iteration,Jacobi Iteration,91,从此例看出,高斯塞德尔迭代法比雅可比迭代法收敛快(达到同样的精度所需迭代次数少),但这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯塞德尔迭代法却是发散的.,92,迭代收敛的充分条件,下面介绍迭代格式的矩阵表示：,其中,为初始向量.,93,定义1：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素的绝对值，即,则称矩阵A按行严格对角占优，类似地，也有按列严格对角占优。,94,定理：若线性方程组AX=b的系数矩阵A按行严格对角占优，则雅克比迭代法和高斯赛得尔迭代法对任意给定初值均收敛。,如果矩阵A严格对角占优，那么高斯赛得尔迭代法的收敛速度快于雅克比迭代法的收敛速度。,95,用 Gauss-Seidel 迭代法求解时方程组,前三次叠代的结果，要求取,96,3.Successive Over Relaxation(SOR)超松驰法,使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。超松驰迭代法是一种线性加速方法。,超松驰迭代法是高斯塞德尔方法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一，它具有计算公式简单，程序设计容易,占用计算机内存较少等优点,但需要较好的加速因子(即最佳松驰因子).,97,超松驰迭代法是一种线性加速方法。这种方法将前一步的结果,与高斯赛得尔方法的迭代值,适当进行线性组合，以构成一个收敛速度较快的近似解序列。改进后的迭代方案是：,98,In the Gauss-Seidel Iteration,In the Successive Over Relaxation,其中系数,要保证迭代格式收敛必须要求,称松驰因子。可以证明，,99,当,=1时，即为高斯赛得尔迭代法，为使,松驰因子的选取对迭代格式的收敛速度影响极大。实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子。,收敛速度加快，通常取,1，即为超松驰法。,要保证迭代格式收敛必须要求,100,=1.046,101,102,
