线性方程组的解法.ppt

第二章线性方程组的解法,设有n元线性方程组,或记为,其中,(2.1),(2.2),设系行列式,则方程组(2.1)有唯一解。,解线性方程组的两类方法,直接法,如果不计运算过程的舍入误差，,经过有限,次运算后可得到方程组的精确解的方法。,迭代法,从解的某个近似值出发，,通过构造一个无穷序,列去逼近精确解的方法。,迭代法一般在有限步内得不到方程组的精确解。,Cramer法则,由Cramer(克莱姆)法则，方程(2.1)的解为,阵。,如果用按照某行(或某列)展开的方法计算,行列式，,那么用Cramer法则求解一个n元线性,方程组所需的乘法运算次数为,加,法运算次数为,当n较大时，,这个计算量,大得惊人。,2.1Gauss消去法,消元过程,写出方程组(2.1)的增广矩阵，,并记,2.1.1顺序Gauss消去法,若,则施行第一次消元：,原增广矩阵被变换成,将这一过程继续下去,步的计算过程为,第,原增广矩阵被变换成,若所有的,则经过,次消元得到：,(2.3),与原方程组(2.1)是同解方程组。,回代过程,回代过程就是由方程组(2.3)的最后一个方程解,然后通过逐步回代，,依次求出,出,具体算法为,例1,用顺序Gauss消去法解以下线性方程组,解,用增广矩阵表示法求解：,消元过程,回代过程,同解方程组为,乘除法次数,顺序Gauss消去法的运算量,消元过程,加减法次数,回代过程,乘除法次数,加减法次数,总运算量,乘除法次数,加减法次数,2.1.2列主元Gauss消去法,引例,考虑用顺序Gauss消去法求解以下方程组，,在运算中每次运算保留到小数点后四位。,消元后的同解方程组为,回代求解得,与准确解,相差很大。,改进：,对调方程,消元后的同解方程组为,回代求解得,与准确解,相差不大。,误差分析：,设准确解为,顺序Gauss消去法求得的解,为,改进后的Gauss消去法求得的解,为,顺序Gauss消去法的误差,则,改进后的Gauss消去法的误差,则,列主元Gauss消去法,若,1消元过程,对,选主元,则计算停止，,若,则换行，,消元,2回代过程,则计算停止，,若,对,否则,例2,2.2直接三角分解法,2.2.1Doolittle分解法与Cout分解法,其中L是下三角矩阵，,U是上三角矩阵，,这时方,程组就可化为两个容易求解的三角形方程组,(2.4),矩阵A分解成(2.4)的形式称为矩阵的三角分,解。,若L是单位下三角阵，,则称相应的分解为,Doolittle分解(也称为LU分解)。,若U是单位上,三角阵，,则称相应的分解为Crout分解。,定理1,定理2,Doolittle分解法,主子式都不为零。,则A有Doolittle分解,(2.5),由分解式(2.5)及矩阵的乘法知,Doolittle分解算法,对,对,Doolittle分解表上作业法,利用LU分解求解线性方程组的算法,先求解,即,所以,再求解,即,回代求解,例3,利用Doolittle分解求解以下方程组,解,回代求解x,2.2.3追赶法求解三对角线性方程组,设n元线性方程组Ax=b的系数矩阵A为非奇异,的三对角矩阵,这类方程组具有许多明显的应用背景，,这种方程组称为三对角线性方程组。,分方程数值解、三次样条函数等问题中，,在求微,都会遇,到这样的线性方程组。,唯一的LU分解，,则A有,并且A的LU分解有如下形式,其中,向前“追”的过程,往回“赶”的过程,(1),求解三对角线性方程组的追赶法,(1),表上作业的“追赶法”,例4,利用追赶法求解以下方程组,解,2.4解线性方程组的迭代法,直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)如前面我们介绍过的Gauss消去法和直接三角分解方法。,迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）,直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。,迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。,2.4.1迭代法概述,迭代法的一般形式,设n元线性方程组,(1),的系数矩阵,为n阶可逆方阵，,从而此方程组有唯一的非零解向量。构造形如,(2),的方程组，,其中G为n阶可逆方阵，,任取,作为(1)的初始近似解，,按递推公式,(3),产生向量序列,当k充分大时，,以,作为方程组,的近似解，,这种求解线,性方程组的方法称为迭代法。,递推公式(3)称为,迭代公式，其中G称为迭代矩阵。,迭代矩阵的产生方法,把系数矩阵A分解成两个矩阵N和P的差,其中N是n阶可逆方阵，,代入(1)式得,即可取,关于收敛性的概念,定义,如果,记为,如果对任意的初始向量,迭代公式,则称该迭代法是收敛的。,此时，,是方程组(2),解向量，,收敛定理1,向量x的充分必要条件是,其中,证明：,由收敛性的定义及范数等价性定理有，,收敛于x,对任意的,有,收敛定理2,定义2,若n阶方阵G的特征值为,则,对任意的向量d,迭代公式(3)收敛,的充分必要条件是,收敛定理3,若方阵G的某种范数,则,对于迭代公式(3)产生的序列,有,并且,(4),(5),对收敛定理3的几点说明,由(4)式知，,越小，,收敛的越快；,由(5)式知，,就会充分接近于,方程组的解,所以在实际计算中可用,作为迭代的终止条件。,此时，应构造其它的迭代方法求解。,设线性方程组,的系数矩阵满足,称迭代公式,所表示的迭代法为Jacobi迭代法(或简单迭代法)。,2.4.2Jacobi迭代法,记,其中,则Jacobi迭代法可表示为,(7),若取,(8),收敛条件,Jacobi迭代法收敛的充分必要条件,若,则Jacobi迭代收敛。,若n阶方阵A是主对角线按行(或按列)严格,占优阵，,则用Jacobi迭代法求解线性方程组,Ax=b必收敛。,说明,当n阶方阵A为主对角线按行严格占优阵，,即,满足条件,此时有,由收敛定理3知线性方程,组Ax=b有唯一解，,并且Jacobi迭代法收敛。,当n阶方阵A为主对角线按列严格占优阵，,即,满足条件,可用反证法,得到,从而说明Jacobi法收敛。,例1,用Jacobi迭代法求解,解：,此方程组的系数矩阵是主对角线按行严格占,优阵，,常数项,迭代矩阵,Jacobi迭代公式为,所以用Jacobi迭代法求解必收敛。,计算结果,由于,绝对误,差限为,Jacobi迭代法的计算过程：,1.,输入,维数n,误差,初,始值,最大迭代次数N；,2.,置k=1；,3.,对,4.,若,输出x，停机；否则转5。,5.,若,置,转3；,否则，输出失败信息，停机。,2.4.3Gauss-Seidel迭代法代法,在Jacobi迭代公式,若把迭代公式改写成,(9),便得到所谓的Gauss-Seidel迭代公式。,它只需用,n个单元储存近似解分量。,而且通常情况下，,得到的近似解可能比老近似解更接近精确解，,新,因此，可望这种迭代会更有效。,矩阵表示,记,其中,则Gauss-Seidel迭代法可表示为,其中，,为Gauss-Seidel迭代法的,迭代矩阵，,是其右端常数项。,收敛条件,Gauss-Seidel迭代法收敛的充分必要条件,若,则Gauss-Seidel迭代收敛。,若n阶方阵A是主对角线按行(或按列)严格,占优阵，,则用Gauss-Seidel迭代法求解线性方,程组Ax=b必收敛。,例2,用Gauss-Seidel迭代法求解,解：,此方程组的系数矩阵是主对角线按行严格占,优阵，