《高斯消元法》课件2.ppt

《《高斯消元法》课件2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章解线性方程组的直接方法5.1高斯消去法5.2高斯主元素消去法5.4误差分析5.3矩阵的三角分解【本章重点】1．Gauss消去法和列主元消去法及其实现条件。2．矩阵的三角分解，含LU分解和LLT分解及三对角方程组的追赶法。3．向量和矩阵范数的定义及性质。4．矩阵条件数及病态矩阵定义和解方程组直接法的误差估计。在自然科学和工程技术中许多问题的解决转化为解线性方程组，而这些方程组的系数矩阵大致分为两种，一种是低阶稠密矩阵，一种是高阶稀疏矩阵。引言解线性方程组的数值解也有两种：直接法，就是经过有限步算术运算，可以求得线性方程组的解，但实际计算时有舍入误差的存在和影响，所以求得的结果也只

2、能是近似解对低阶稠密矩阵和部分大型稀疏矩阵有效。迭代法，就是用某种极限过程去逐步逼近精确解，是解决大型稀疏矩阵的重要方法。从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。高斯消去法是一个古老的求解线性方程组的方法，但由于它的改进、变形得到的选主元素消去法、三角分解法仍是在计算机上求解系数矩阵为中、低阶稠密矩阵的线性方程组常用的有效方法，所以本节介绍这一方法。§1高斯消去法用高斯消去法求解n阶线性方程组Ax=b的基本思想是在逐步消元的过程中，把方程组的系数矩阵化为上三角矩阵，从而将原方程组约化为容易求解的等价三角方程组，然后进行回代求解。一、高斯消去法例1用消去

3、法求解方程组11164-152-21111164-150-4-1-1111164-1500-2-6还原为方程组（消元过程）（回代过程）x3=3，x2=2，x1=1设有方程组改写成矩阵形式：简记为：一般线性方程组的高斯消去法将原方程组记为其中则第一步（k=1)，若a11不等于0，则可以计算乘数用-mi1乘方程组的第一个方程加到第i个方程，则原方程组同解方程组为：其中简记为第二步，设经过k-1次消元后的同解方程组为设计算乘数用-mik乘上面的线性方程组的第k个方程加到第i个方程，可以消去xk元,得到同解方程组其中重复上述过程，可以将方程组化为等价的简单方程组其中为上梯形阵。当m=n时，与

4、原方程组等价的方程组为即（消元过程）由上述方程组很快可以求出：（回代过程）乘除运算量乘除运算量：由于计算机中做乘除运算的时间远远超过做加减运算时间，故估计运算量时，往往只估计乘除的次数。第k步：消去第k列设，计算计算(i=k+1,…,n)回代求解：(i=k+1,…,n)n–k次(n–k)2次n–k次n(n+1)/2次高斯消去法总的乘除运算量为：定理1设Ax=b,其中A∈Rn×n(1)如果则可通过高斯消去法，将方程组化为等价三角形方程组，计算公式为：(a)消元计算(k=1,2,…,n)(b)回代计算(2)如果系数矩阵A为非奇异矩阵则可通过高斯消去法与初等行变换方法，将方程组约化为三角形

5、方程组。定理2约化的主元素的充要条件是矩阵A的顺序主子式即证明略推论如果矩阵A的顺序主子式则functionx=gauss(A,b)n=length(b);x=zeros(n,1);fori=1:n-1%消元过程fork=i+1:nforj=i+1:nA(k,j)=A(k,j)+A(i,j)*(-A(k,i)/A(i,i));endb(k)=b(k)+b(i)*(-A(k,i)/A(i,i));A(k,i)=0;endenddisp(A)disp(b)pausex(n)=b(n)/A(n,n);fori=n-1:-1:1%回代过程sum=0;forj=i+1:nsum=sum+A(i

6、,j)*x(j);endx(i)=(b(i)-sum)/A(i,i);end程序设计A=[111;04-1;2-21];b=[651]';x=gauss(A,b)程序执行消元后的A11104-100-2消元后的b65-6x=123二、矩阵的三角分解由上面消去法的分析知，若方程组的系数矩阵A的顺序主子式不等于0，高斯消元的过程是作一系列初等行变换，等价于矩阵A左乘一个初等矩阵。一般第k步消元，A(k)化为A(k+1),b(k)化为b(k+1),相当于所以第一次消元可表示为：其中：重复以上过程，最后得到令为单位下三角矩阵。定理2（矩阵的LU分解）设A为一个n阶矩阵，若其顺序主子式Di≠0

7、(i=1,2,…,n)。则A可分解为一个单位下三角形矩阵L和一个上三角形矩阵U的乘积，且这种分解是唯一的。证明：存在性由定理1可得；唯一性：设有两种分解，即A=LU=L1U1所以由L可逆，U1可逆，知L-1L1=UU1-1左边为单位下三角形矩阵，右边为上三角形矩阵，所以均为单位矩阵，即有L=L1,U=U1分解唯一。Ax=bLUx=b记Ux=y,Ly=b由Ly=b求出y,再由Ux=y求出x注意：LU分解的作用是将一个较复杂的矩阵化为两个简单的矩阵。A=[11