第五章 线性方程组的直接方法.ppt

5.1 引言 在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重要的。,第五章 方程组的数值解法,解线性方程组的直接法,简记为 Ax=b，其中,(6.1),常见的线性方程组是方程个数和未知量个数相同的n阶线性方程组，一般形式为,线性方程组的数值解法一般有两类：直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。迭代法:就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解),三、特殊矩阵,对角矩阵三对角矩阵上三角矩阵上海森伯(Hessenberg)阵对称矩阵埃尔米特矩阵对称正定矩阵正交矩阵酉矩阵初等置换阵置换阵,定理1 设ARnn,A非奇异?,定理2 若ARnn对称正定矩阵，则?,定理3 若ARnn对称矩阵，则对称正定矩阵=?,定理4(若当标准型),其中,对角化的条件：1）；2）.,5.2 高斯消去法,5.2.1 高斯消去法的基本思想先用一个简单实例来说明Gauss法的基本思想例5.1 解线性方程组,解:该方程组的求解过程实际上是将中学学过的消元法标准化,将一个方程乘或除以某个常数,然后将两个方程相加减,逐步减少方程中的未知数,最终使每个方程只含有一个未知数,从而得出所求的解。整个过程分为消元和回代两个部分。,（1）消元过程第1步:将方程乘上(-2)加到方程 上去,将方程 乘上 加到方程 上去,这样就消去了第2、3个方程的 项,于是就得到等价方程组,第2步：将方程 乘上 加到方程 上去，这样就消去了第3个方程的 项，于是就得到等价方程组,这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。,（2）回代过程回代过程是将上述三角形方程组自下而上求解，从而求得原方程组的解：,前述的消元过程相当于对原方程组,的增广矩阵进行下列变换(表示增广矩阵的第 行）,同样可得到与原方程组等价的方程组,由此看出,高斯消去法解方程组基本思想是设法消去方程组的系数矩阵A的主对角线下的元素,而将Ax=b化为等价的上三角形方程组,然后再通过回代过程便可获得方程组的解。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三角形矩阵,而以上三角形矩阵为系数的方程组的求解比较简单,可以从最后一个方程开始,依次向前代入求出未知变量 这种求解上三角方程组的方法称为回代,通过一个方程乘或除以某个常数,以及将两个方程相加减,逐步减少方程中的变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。,通常把按照先消元,后回代两个步骤求解线性方程组的方法称为高斯（Gauss）消去法。,5.2.2 高斯消去法算法构造 我们知道,线性方程组(6.1)用矩阵形式表示为,(6.3),解线性方程组（6.1）的高斯（Gauss）消去法的消元过程就是对(6.3)的增广矩阵进行行初等变换。将例6.1中解三阶线性方程组的消去法推广到一般的 阶线性方程组并记则高斯消去法的算法构造归纳为：,消元过程,斯消去法的消元过程由n-1步组成：第1步 设,把(6.3)中的第一列中元素 消为零,令,用 乘以第1个方程后加到第 个方程上去,消去第2n个方程的未知数,得到 即,其中,第k步（k=2,3,n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组,记为 其中,只要,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组,记为,或者写成,即,(6.7),（2）回代过程就是对上三角方程组（6.7）自下而上逐步回代解方程组计算，即,（3）高斯消去法的计算步骤：消元过程;设 计算,回代过程,(4)高斯消去法流程图，(5)Gauss消去法计算量,消元计算:aij(k+1)=aij(k)-mik akj(k)(i,j=k+1,k+2,n)第一 步计算乘数mik,mik=ai1/a11(i=2,3,n)需要n-1次除法运算,计算 aij(2）(i,j=2,3,n)需要(n-1)2次乘法运算及(n-1)2次加减法运 算,乘除法次数：MD=n(n-1)(2n-1)/6+n(n-1)/2=1/3 n(n2-1)加减法次数：AS=n(n-1)(2n-1)/6,算法.,乘除法运算工作量,消元过程乘除法次数：,回代过程乘除法次数：,总的乘除法运算次数：,非零判断次数最多为：,行交换的元素个数为：,5.2.3 高斯消去法的适用条件,定理1 方程组系数矩阵的顺序主子式全不 为零则高斯消去法能实现方程组的 求解。证明 上三角形方程组是从原方程组出发，通过逐次进行“一行乘一数加到另一行”而得出的，该变换不改变系数矩阵顺序主子式的值。,设方程组系数矩阵，其顺序主子式,（m=1,2,，n）,经变换得到的上三角形方程组的顺序主子式,所以能实现高斯消去法求解,（m=1,2,，n）,定义5.1 设矩阵 每一行对角元素的绝对值都大于同行其他元素绝对值之和,则称A为严格对角占优矩阵。,定理 1.1 若方程组 的系数矩阵A为严格对角占优，则用高斯消去法求解时，全不为零。,证:先考察消元过程的第1步,因A为严格对角占 优,故 故,又根据高斯消 去公式得 于是,再利用方程组的对角占优性,由上式可进一步得,又由,得,故有,当A为严格对角占优时,余下的子阵仍是对角占优的，从而又有。依次类推全不为零。定理证毕。,