数值分析-线性方程组的直接解法课件

1、线性方程组的直接解法刘 斌线性方程组的直接解法刘 斌线性方程组的直接解法1 Gauss消去法 1.1 顺序Gauss消去法 1.2 列主元Gauss消去法 2 直接三角分解方法 2.1 Gauss消去法的矩阵运算 2.2 Doolittle分解法 2.3 平方根法 2.4 追赶法 线性方程组的直接解法1 Gauss消去法 引入 在科学计算中，经常需要求解含有n个未知量 的n个方程构成的线性方程组方程组还可以用矩阵形式表示为: Ax=b (1)引入 在科学计算中，经常需要求解含有n个未知量 引入 根据 Gramer（克莱姆）法则，求解方程组（1）时，要计算大量的行列式，所需乘法次数大约为 当 n

2、 较大时,这个计算量是惊人的。例 如，当 n= 20 时，约需乘法次数为 N=9.71020 若系数矩阵A非奇异，即 det (A)0，则方程组有惟一解 x =( x1, x2, , xn )T . 如果用每秒一亿次的计算机来计算，需要三十万年时间。可见Gramer法则不是一种实用的方法。 因此，必须构造出适合于计算机使用的线性方程组的求解方法。N=(n2-1)n!引入 根据 Gramer（克莱姆）法则，求解方程组（1）引入 直接方法的特点是，如果不考虑计算过程中的舍入误差，运用此类方法经过有限次算术运算就能求出线性方程组的精确解。 求解线性方程组的数值方法可分为两大类：直接方法和迭代方法。本

3、章讨论直接方法，迭代方法将在下一章中讨论。 需要指出，由于实际计算中舍入误差的存在，用直接方法一般也只能求得方程组的近似值。引入 直接方法的特点是，如果不考虑计算过程中的舍 1 Gauss消去法 Gauss（高斯）消去法是一种规则化的加减消元法 基 本 思 想 通过逐次消元计算把需求解的线性方程组转化成上三角形方程组，也就是把线性方程组的系数矩阵转化为上三角矩阵，从而使一般线性方程组的求解转化为等价（同解）的上三角形方程组的求解。 Gauss消去法由消元和回代两个过程组成，先讨论一个具体的线性方程组的求解。 1 Gauss消去法 Gauss（高斯）消去法是一、顺序Gauss消去法例1. 用Ga

4、uss消去法解方程组用增广矩阵进行进算一、顺序Gauss消去法例1. 用Gauss消去法解方程组用一、顺序Gauss消去法或者 Ax=b 我们用增广矩阵表示，并给出gauss消去法的具体算法一、顺序Gauss消去法或者 Ax=一、顺序Gauss消去法第一步，设 a11(1) 0 ，将第一列a11(1)以下各元素消成零乘以矩阵A（1），b（1）的第一行再加到第i 行，得到矩阵 (i2，3，n)即依次用一、顺序Gauss消去法第一步，设 a11(1) 0 一、顺序Gauss消去法其中 第二步，设 a22(2) 0 ，将第二列a22(2)以下各元素消成零，（i3，4，n） 即依次用乘以矩阵A（2），

5、b（2）的第二行再加到第i行，得到矩阵一、顺序Gauss消去法其中 第二步，设 a22(2) 0一、顺序Gauss消去法其中 如此继续消元下去第n1步结束后，得到矩阵一、顺序Gauss消去法其中 如此继续消元下去第n1步结束一、顺序Gauss消去法增广矩阵A（n），b（n）对应如下上三角形方程组 这是与原线性方程组（1）等价的方程组.一、顺序Gauss消去法增广矩阵A（n），b（n）对应如一、顺序Gauss消去法对于等价方程组进行回代求解，可以得到：一、顺序Gauss消去法对于等价方程组进行回代求解，可以得到算法 Gauss(A,a,b,n,x) 1. 消元 For k=1,2, , n-1

6、1.1 if akk=0 , stop; 1.2 For i=k+1,k+2, , n 1.2.1 l ik=aik /akk = aik 1.2.2 For j=k+1，k+2, ,n ai j -aik ak j =aij 1.2.3 bi -aik bk= bi 2. 回代2.1 bn / an=xn;2.2 For i=n-1,n-2, , 2,1 2.2.1 bk = S 2.2.2 For j=k+1，k+2, ,n S akj xj =S 2.2.3 S/ akk = xk a1 1 a1 2 a13 a1 n b1a2 1 a2 2 a23 a2 n b2a3 1 a3 2 a

7、33 a3 n b3an 1 an 2 an3 an n bnl21 l31 l41 .l n1 a22 a23 . a2n b2 l32 l42 .l n2 . a33 . a 3n b3l43 .l n3 a1 1 a1 2 a13 . a1 n b1a 4n b4. . .ann bn 算法 Gauss(A,a,b,n,x) 1. 消元 For 一、顺序Gauss消去法用Gauss消去法解方程组，应注意：1. 适用条件： 原方程组系数矩阵的各阶顺序主子 式不等于零。2 . 运算量小：共有乘除法次数为而Gramer 法则的乘除法次数为: (n2 -1) n！当 n=20 时一、顺序Gaus

8、s消去法用Gauss消去法解方程组，应注意：二 列主元Gauss消去法 顺序Gauss消去法计算过程中的 akk(k) 称为主元素，在第k步消元时要用它作除数,则可能会出现以下几种情况若出现 akk(k) 0，消元过程就不能进行下去。 akk(k) 0 ，消去过程能够进行，但若|akk(k)| 过小，也会造成舍入误差积累很大导致计算解的精度下降。 例2 在四位十进制的限制下，试用顺序Gauss消去法求解如下方程组二 列主元Gauss消去法 顺序Gauss消去二 列主元Gauss消去法此方程组具有四位有效数字的精确解为x117.46，x245.76，x35.546 解 用顺序Gauss消去法求解

9、，消元过程如下二 列主元Gauss消去法此方程组具有四位有效数字的精确解二 列主元Gauss消去法经回代求解得 x35.546，x2100.0，x1104.0和此方程组的精确解相比x35.546 ，x245.76， x117.46有较大的误差。 对于此例，由于顺序Gauss消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生较大的舍入误差，最终导致计算解 x1104.0 和 x2100.0 已完全失真。 为避免这种现象发生，可以对原方程组作等价变换，再利用顺序Gauss消去法求解。二 列主元Gauss消去法经回代求解得和此方程组的精确解相写出原方程组的增广

10、矩阵：针对第一列找出绝对值最大的元素，进行等价变换：写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行求得方程的解为：x35.546，x245.76，x117.46精确解为： x35.546 ，x245.76， x117.46 由此可见，第二种Gauss消去法的精度明显高于顺序Gauss消去法，我们称它为列主元Gauss消去法。 列主元Gauss消去法与顺序Gauss消去法的不同之处在于： 后者是按自然顺序取主元素进行消元 前者在每步消元之前先选取主元素然后再进行消元 求得方程的解为：x35.546，x245.76，x1下面将列主元Gauss消去法的计算步骤叙述如下： 给定线性方程组

11、 Axb, 记A（1）, b（1） A,b，列主元Gauss消去法的具体过程如下： 1. 首先在增广矩阵A（1）,b（1）第一列的n个元素中选取绝对值最大的一个作为主元素，并把此主元素所在的行与第一行交换，即 2. 其次进行第一步消元得到增广矩阵A（2）,b（2），在矩阵A（2）,b（2） 第二列的后 n1个元素中选取绝对值最大的一个作为主元素，并把此主元素所在的行与第二行交换，即下面将列主元Gauss消去法的计算步骤叙述如下： 3. 再进行第二步消元得到增广矩阵A（3），b（3）。按此方法继续进行下去，经过n1步选主元和消元运算，得到增广矩阵A（n），b（n），它对应的方程组A（n）xb（n

12、）是一个与原方程组等价的上三角形方程组，可进行回代求解。 容易证明，只要det（A）0，列主元Gauss消去法就可以顺利完成，即不会出现主元素为零或者绝对值太小的情形出现。 下面给出列主元Gauss消去法的计算流程： 3. 再进行第二步消元得到增广矩阵A（3），列主元Gauss消去算法 用列主元Gauss消去法求解线性方程组Axb 输入 A（aij），b（b1，bn）T，维数n输出 方程组解x1，xn，或方程组无解信息1： 对于k1，2，n1，循环执行步2到步52： 按列选主元素 aik ，即确定下标 I 使3： 若aik0，输出 no unique solution，停机4： 若ik，换行列主元Gauss消去算法 用列主元Gauss消去法求解线性方5：消元计算，对于ik1，n，计算 6：若 ann 0 输出 no unigue solution，停机7：回代求解 8：输出 x1，x2，xn5：消元计算，对于ik1，n，计算 6：若 ann 二 列主元Gauss消去法 由于这两种方法的精度差不多，且全主元Gaus