高斯消去法ppt课件.ppt

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

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

2、术运算，可以求得线性方程组的解，但实际计算时有舍入误差的存在和影响，所以求得的结果也只能是近似解对低阶稠密矩阵和部分大型稀疏矩阵有效。迭代法，就是用某种极限过程去逐步逼近精确解，是解决大型稀疏矩阵的重要方法。从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。7/28/2021数值分析高斯消去法是一个古老的求解线性方程组的方法，但由于它的改进、变形得到的选主元素消去法、三角分解法仍是在计算机上求解系数矩阵为中、低阶稠密矩阵的线性方程组常用的有效方法，所以本节介绍这一方法。§1高斯消去法用高斯消去法求解n阶线性方

3、程组Ax=b的基本思想是在逐步消元的过程中，把方程组的系数矩阵化为上三角矩阵，从而将原方程组约化为容易求解的等价三角方程组，然后进行回代求解。一、高斯消去法7/28/2021数值分析例1用消去法求解方程组11164-152-21111164-150-4-1-1111164-1500-2-6还原为方程组（消元过程）（回代过程）x3=3，x2=2，x1=1设有方程组改写成矩阵形式：简记为：一般线性方程组的高斯消去法7/28/2021数值分析将原方程组记为其中则第一步（k=1)，若a11不等于0，则可以计算乘数用-mi1乘方程组的第一个

4、方程加到第i个方程，则原方程组同解方程组为：其中简记为第二步，设经过k-1次消元后的同解方程组为设计算乘数用-mik乘上面的线性方程组的第k个方程加到第i个方程，可以消去xk元,得到同解方程组其中7/28/2021数值分析重复上述过程，可以将方程组化为等价的简单方程组其中为上梯形阵。当m=n时，与原方程组等价的方程组为即（消元过程）由上述方程组很快可以求出：（回代过程）乘除运算量乘除运算量：由于计算机中做乘除运算的时间远远超过做加减运算时间，故估计运算量时，往往只估计乘除的次数。第k步：消去第k列设，计算计算(i=k+1,…,n)

5、回代求解：(i=k+1,…,n)n–k次(n–k)2次n–k次n(n+1)/2次高斯消去法总的乘除运算量为：7/28/2021定理1设Ax=b,其中A∈Rn×n(1)如果则可通过高斯消去法，将方程组化为等价三角形方程组，计算公式为：(a)消元计算(k=1,2,…,n)(b)回代计算(2)如果系数矩阵A为非奇异矩阵则可通过高斯消去法与初等行变换方法，将方程组约化为三角形方程组。定理2约化的主元素的充要条件是矩阵A的顺序主子式即证明略推论如果矩阵A的顺序主子式则functionx=gauss(A,b)n=length(b);x=zer

6、os(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,j)*x(j);endx(i)=(b(i)-sum)/A(i,i);end程序设计A=[111;04-1;2-

7、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(i=1,2,…,n)。则A可分解为一个单位下三角形矩阵L

8、和一个上三角形矩阵U的乘积，且这种分解是唯一的。证明：存在性由定理1可得；唯一性：设有两种分解，即A=LU=L1U1所以由L可逆，U1可逆，知L-1L1=UU1-1左边为单位下三角形矩阵，右边为上三角形矩阵，所以均为单位矩阵，即有L=L1,U=U1