线性代数方程组解法.ppt

1、第三章 线性方程组的数值解法,讨论线性方程组解法的必要性,工程实际中的许多问题都归结为解线性方程组,我们知道线 性方程组 a11x1+ a12x2+ +a1nxn=b1 a21x1+ a22x2+ +a2nxn=b2 an1x1+ an2x2+ +annxn=b2 即 Ax = B 若|A| 0, 根据克莱姆(Gramer)法则, 方程组有唯一解 Xi=Di/D ( i=1, 2 , , n ) 然而,对于较高阶的情况, 用这种方法求解是不现实的。一 个 n 阶行列式有 n! 项, 每一项又是 n 个数的乘积。就算不计舍 入误差对计算结果的影响 , 对较大的 n , 其运算量之大 不考 虑加减

2、，仅乘除次数就需 (n+1) n! (n-1) +n , 也是计算机在一般 情况下难以容许的。因此 , 我们要讨论线性方程组的另外两种 解法: 直接法和迭代法。,解线性方程组的直接法和迭代法,一、直接法 经过有限步运算就能求得精确解的方法。 包括： 1. 顺序高斯消去法 2. 选主元高斯消去法 3. 高斯约当消去法 4. 矩阵三角分解法 二、迭代法 用某种极限过程去逐步逼近精确解的方法。 包括： 1. 雅可比迭代法 2. 赛得尔迭代法 3. 松弛迭代法 下面我们将介绍解线性方程组的直接法。,第一节 顺序高斯消去法,一、顺序高斯消去法的基本思想,顺序高斯消去法分为消元和回代两个过程。 首先应用矩

3、阵的初等变换将系数矩阵A按自然顺序化为上三角矩阵，与此同时将方程的右端向量B增补作为A的第n+1列，构成增广矩阵，同时参加变换。然后应用回代过程计算方程的解。,二、顺序高斯消去法举例,例 2x1 + 6x2 - 4x3 = 4 (1) x1 + 4x2 - 5x3 = 3 (2) 6x1 - x2 +18x3 = 2 (3) 解 a. 消元过程 第一次消元： (1)(-1/2)+(2) 、(1)(-6/2)+(3) 得 2x1 + 6x2 - 4x3 = 4 (1) x2 - 3x3 = 1 (2) -19x2 + 30 x3 = -10 (3) 第二次消元： (2) (-(-19)/1)+(

4、3) 得 2x1 + 6x2 - 4x3 = 4 (1) x2 - 3x3 = 1 (2) - 27x3 = 9 (3) b. 回代过程 x3 = 9/(-27) = -1/3， x2 = 1 + 3x3 = 1-1= 0， x1 = (4 + 4x3 + 6x2 )/2= (4+4(-1/3)+60)/2 = 4/3,三、一般线性方程组的求解过程(第一次消元过程) 第一次消元过程: 推出: 第一次消元即: ( i , j = 2, 3, , n ),三、一般线性方程组的求解过程(第k次消元及回代过程) 第k次消元过程: (i, j=k+1, , n) 回代过程: （i =n-1,2,1）,四

5、、顺序高斯消去法计算量分析,用计算机作四则运算时，加减操作所花的机器时间比乘除操 作少得多, 所以我们仅统计乘除次数。 1. 消元过程(共需n-1次消元） 第k次消元时需除：n-k 第k次消元时需乘：(n-k)(n-k+1) 共需乘除次数： (n-1)+(n-1)n+(n-2)+(n-2)(n-1)+1+12 = n3/3+n2 /2-5n/6 2. 回代过程 需除：n 需乘：1+2+(n-1)= (n-1)n/2 共需乘除次数：n+ (n-1)n/2= n2/2+n/2 所以总共需乘除次数: n3/3+n2 /2-5n/6+n2/2+n/2 = n3/3+n2 -n/3 。 n3/3+n2

6、-n/3(n+1) n! (n-1)+n(克莱姆法则需的乘除次数),因此 顺序高斯消去法从计算量上考虑是可行的。,五、顺序高斯消去法计算机实现,根据一般线性方程组的求解过程知,消元过程实际 上是一个三重（层）循环，而回代过程实际上是一个 二重（层）循环。据此，我们便可编出求解线性方程 组的程序。,第二节 选主元高斯消去法,前面介绍的顺序高斯消去法,也叫顺序选主元法。 当出现主元素 akk(k) = 0 时, 消元过程将无法继续进行， 或者即使akk(k) 0时，但如果绝对值很小，用它作除 数也会导致其它元素的数量级急剧增大和舍入误差扩 大, 将严重影响计算结果的精度。为了克服这一缺陷， 下面介

7、绍选主元高斯消去法。选主元高斯消去法有列 主元高斯消去法和全主元高斯消去法两种。我们首先 介绍列主元高斯消去法。,一、列主元高斯消去法,列主元消去法的主要思想是：在第k次消元时，从k列的以下的各个元素中选出绝对值最大的元素，然后通过行交换将其交换到k行上，再做第k次消元（同顺序高斯消去法）；回代过程与顺序高斯消去法完全相同。,用列主元高斯消去法解线性方程组举例 例 0.01x1 + 2x2 - 0.5x3 = - 5 - x1 - 0.5x2 + 2x3 = 5 5x1 - 4x2 + 0.5x3 = 9 解 0.01 2 - 0.5 - 5 5 - 4 0.5 9 A,b = - 1 - 0

8、.5 2 5 (1) (3) -1 - 0.5 2 5 5 - 4 0.5 9 0.01 2 - 0.5 5 (2)+(1)*1/5 5 - 4 0.5 9 5 - 4 0.5 9 (3)-(1)*1/500 0 - 1.30 2.10 6.80 (2) (3) 0 2.01 0.501 - 5.02 0 2.01 0.501 - 5.02 0 - 1.30 2.10 6.80 5 -4 0.5 9 (3)+(2)*1.30/2.01 0 2.01 0.501 - 5.02 0 0 1.78 3.55 回代 x3 = 1.99 , x2 = - 2.00 , x1 = 0.001,列主元高斯消

9、去法的计算步骤（计算机实现） 1 . 消元过程 对 k = 1，2， ，n-1 作下列运算: (1) 按列选主元 确定 r , 使满足 若ark = 0 , 说明系数矩阵奇异，则停止计算(结束) ; (2) 行交换 若 rk , 则交换第 k 行和第 r 行 ; (3) 消元计算 对 i = k+1 , k+2 , , n , j= k+1 , k+2 , , n+1 计算 2 . 回代过程 若ann = 0 , 则系数矩阵为奇异，停止计算(结束) ; 否则计 算 ( k= n , n-1, , 1),二、全主元高斯消去法 全主元消去法与列主元消去法的不同之处，是在第k次消元时，从系数矩阵的右

10、下角(n-k+1)阶子矩阵： 中，选取绝对值最大的元素作为主元素，如果它位于第r行第s列，则通过交换k,r两行及交换k,s两列，使主元素位于 的位置，然后进行消元计算。由于作列的交换改变了方程中未知量的次序，因此回代过程要按未知量调换后的编号顺序求解。,全主元消去法解线性方程组举例 例 0.01x1 + 2x2 - 0.5x3 = - 5 - x1 - 0.5x2 + 2x3 = 5 5x1 - 4x2 + 0.5x3 = 9 解 0.01 2 - 0.5 - 5 5 - 4 0.5 9 A,b = - 1 - 0.5 2 5 (1) (3) -1 - 0.5 2 5 5 - 4 0.5 9

11、0.01 2 - 0.5 5 (2)+(1)*1/5 5 - 4 0.5 9 5 0.5 - 4 9 (3)-(1)*1/500 0 -1.30 2.10 6.80 交换(2)、(3)列 0 2.10 -1.30 6.80 0 2.01 - 0.501 -5.02 0 - 0.501 2.01 -5.02 5 0.5 - 4 9 (3)+(2)*0.501/2.10 0 2.10 -1.30 6.8 即 0 0 1.70 -3.40 回代得：x2 = - 2.00 , x3 = 2.00 , x1 = 0.00,全主元高斯消去法的计算步骤(计算机实现) 1. 记录未知量的初始顺序( ti =

12、i , i = 1 , 2 , , n ) 2. 消元过程 对k = 1, 2 , , n-1 作下列运算： （1）选主元 确定 r,s 使 若ars=0,说明系数矩阵奇异，结束。 （2）行交换和列交换 若rk , 则交换 r , k 两行 ；若 sk , 则交换 s, k 两列并交换 ts、tk 的值。 （3）消元计算 同列主元消去法。 3. 回代过程 若ann=0,则系数矩阵奇异,结束;否则 计算 4. 输出x1 , x2 , , xn ( k = n , n-1, , 1),第三节 高斯-约当消去法(无回代过程的主元素消去法),高斯约当法的思想是将方程组化为对角形Dx=B的形式，其中矩阵

13、D为对角形矩阵，即 其特点是每次消元时利用主元将其所在列的冗余元素全部消为0，即在第k次消元时，不仅把k列中(k,k)位置以下的元素消为0，而且同时把(k,k)位置上的元素也化为0，消去的行是从第1行到第n行，但主行不进行消去，这样经过n次消元后系数矩阵就成为对角阵，不需回代就可直接求出方程组的解。,列主元高斯-约当消去法求解线性方程组举例 例 求解方程组Ax=b,其中 解：增广矩阵为 1 2 3 1 3 4 6 3 A,b = 2 4 5 4 (1) (3) 2 4 5 4 3 4 6 3 1 2 3 1 1 4/3 2 1 (2)-(1)*2 1 4/3 2 1 1 4/3 2 1 (1)

14、*1/3 2 4 5 4 (3)-(2) 0 4/3 1 2 ( 2)*3/4 0 1 3/4 3/2 1 2 3 1 0 2/3 1 0 0 2/3 1 0 (1)-(2)*4/3 1 0 1 -1 1 0 1 -1 (1)-(3) 1 0 0 1 (3)-(2)*2/3 0 1 3/4 3/2 (3)*2 0 1 3/4 3/2 (2)-(3)*3/4 0 1 0 3 0 0 1/2 -1 0 0 1 -2 0 0 1 -2 于是求得方程Ax=b的解为： x1 = 1 , x2 = 3 , x3 = -2,列主元高斯-约当消去法求解m个线性方程组的计算步骤 (计算机实现),列主元高斯-约当

15、消去法通常用来求解逆矩阵或同时求解系 数矩阵相同的多个方程组，下面是列主元高斯-约当消去法求解 m个线性方程组的计算步骤： 1 . 消元过程 对 k = 1，2， ，n 作下列计算 (1) 按列选主元以及行交换（同列主元高斯消去法）。 (2) 消元计算 ) akj= akj/akk j = k , k+1, , n , n+1 , ,n+m ) aij= aij aikakj i = 1, 2, , n (ik) j= k+1 , k+2 , , n+m 2 . 输出矩阵的n+s列,就是第s个方程的解(s=1，2， , m)。,第四节 直接三角分解法(矩阵三角分解法),三角分解法的思想是将系数

16、矩阵分解为两个三角形矩阵之积，即A=LU。其中: L为一个下三角矩阵,U为一个上三角矩阵。然后将解方程组Ax=b的过程化为解Ly=b和Ux=y两个方程组的过程。,直接三角分解法求解线性方程组Ax=b的出发点,若|A| 0， A = LU 1 U11 U12 U13 U1n L = L21 1 U = U22 U23 U2n Ln1 Ln2 Ln3 Lnn-1 1 Unn 即 1 U11 U12 U13 U1n L21 1 U22 U23 U2n Ln1 Ln2 Ln3 Lnn-1 1 Unn a11 a12 a1n = a21 a22 a2n an1 an2 ann,直接三角分解法求解线性方程

17、组Ax=b的具体过程 1. 三角分解 对 k = 1, 2, , n 计算U和L的元素 2. 求y值 令 Ux = y , Ly = b y1 = b1,( i = 2, 3, , n ),求x值 根据 Ux = y xn = yn/unn (i=n-1,n-2,1),直接三角分解法求解线性方程组的例子 例: 求 的解 解: 1 2 -1 1 2 -1 1 -1 5 1 -3 6 4 1 2 4 7/3 8 1 0 0 1 2 -1 即 L = 1 1 0 U = 0 -3 6 4 7/3 1 , 0 0 -8 1 0 0 y1 3 3 由 1 1 0 y2 = 0 得 y = -3 4 7/

18、3 1 y3 2 -3 1 2 -1 x1 3 -1/8 再由 0 -3 6 x2 = -3 得 x = 7/4 0 0 8 x3 -3 3/8,直接三角分解法求解线性方程组的计算机实现,按直接三角分解法求解线性 方程组Ax=b的具体过程实现。,第五节 线性方程组的迭代解法,线性方程组迭代解法的基本思想是构造适当的矩阵序列或向量序列，使其逐步逼近所求问题的精确解，故又称矩阵迭代法。 适用情况：未知数n较多(即方程组较大）、系数矩阵稀疏。,一、简单迭代法,设方程组Ax=b的系数矩阵非奇异，把它化为等价的方程组 x=Bx+g 其中： b11 b12 b1n g1 x1 B = b21 b22 b2

19、n g = g2 x = x2 bn1 bn2 bnn , gn , xn 按 x=Bx+g 构造迭代公式 x(k+1)=Bx(k)+g , k=0, 1, 2, 其中： ( k = 0, 1, 2, ) 任取初始向量x(0),用 x(k+1)=Bx(k)+g 逐次计算近似解向量 x(1), x(2), , x(k), 这种求解方法称为简单迭代法。,简单迭代法的一些概念,x(k+1)=Bx(k)+g 称为简单迭代公式(或迭代格式); 其 中的B称为迭代矩阵。 如果x(k)的各分量存在极限 , i = 1, 2, , n 则记为： 这时，称简单迭代法 x(k+1)=Bx(k)+g 是收敛的，否则

20、就 是发散的。 实际计算中，一般用 来控制迭代结束。,二、雅可比迭代法(一种简单迭代法） 线性方程组的一般形式为 设从上式中分离出变量xi，将它改写为 由此可以建立迭代公式 该公式即为雅可比迭代法。,用雅可比迭代法求解线性方程组的例子 例1 求 10 x1 - x3 = 9 -2x1 + 10 x2 - x3 = 7 -x2 +5x3 = 4 精度要求为 =0.005，用5位有效数字计算。 解 将方程组写成等价的方程组 x1 = 0.1x3 + 0.9 x2 = 0.2x1 + 0.1x3 + 0.7 x3 = 0.2x2 + 0.8 构造雅可比迭代公式 k=0,1, 取初始向量x(0)=0=

21、0,0,0T进行迭代，计算结果如下表：,用雅可比迭代法求解线性方程组的例子(续） 由于 所以x(5)满足精度要求，即得： x1 = 0.99980 , x2 = 0.99964 , x3 = 0.99960,用雅可比迭代法求解线性方程组的例子(续),例2 求 -2x1 + 10 x2 - x3 = 15 （1） -x1 - 2x2 + 5x3 = 10 （2） 10 x1 - 2x2 - x3 = 3 （3） 精度要求为 =0.005。 解 将方程组写成等价的方程组 x1 = 5x2 - 0.5x3 - 7.5 x2 = -0.5x1 + 2.5x3 - 5 x3 = 10 x1 - 2x2

22、- 3 其雅可比迭代公式为 x1(k+1) = 5x2(k) - 0.5x3(k) - 7.5 x2(k+1) = -0.5x1(k) + 2.5x3(k) - 5 x3(k+1) = 10 x1(k) - 2x2(k) - 3 ( k = 0, 1, ）,用雅可比迭代法求解线性方程组的例子(续),取初始向量 x(0)=0=0,0,0T ，按 x1(k+1) = 5x2(k) - 0.5x3(k) - 7.5 x2(k+1) = -0.5x1(k) + 2.5x3(k) - 5 x3(k+1) = 10 x1(k) - 2x2(k) - 3 ( k = 0, 1, ） 计算，其结果如下表:,x

23、1(k),x2(k),其结果的绝对值越来越大，不可能逼近于任何常数，这个迭代格式是发散得的。该方程组的精确解为1，2，3。,雅可比迭代格式收敛性的判别方法,可以证明，只要满足下面三个条件的一个便可保 证雅可比迭代格式收敛。 (1) (2) (3) 当写出的迭代格式不收敛时，可适当调整方程组 中各方程的次序或根据线性代数知识将原方程组中的 方程加以重新组合(如将一个方程的若干倍加到另一个 方程上进行变换等)，再写出相应的迭代格式。如例2， 可将方程组中的方程(3)调整为(1)、方程(1)调整为(2)、 方程(2)调整为(3),便可写出收敛的迭代格式, 直到满足 收敛条件。,三、高斯-赛德尔迭代法

24、 雅可比迭代的思想是用前次迭代计算所得的近似解来计算下一个近似解。它没有充分利用已有的结果( 雅可比迭代法在求x2(k+1)时x1(k+1) 已经求了出来, 而它仍然用x1(k)来求x2(k+1) ; 在求x3(k+1)时x1(k+1) 、 x2(k+1)已经求了出来，而它仍然用x1(k) 、 x2(k)来求x3(k+1) ) 。 高斯-赛德尔迭代法是对雅可比迭代法的改进，它充分利用了已有的结果。其迭代公式为： 高斯-塞德尔迭代法由于每算出一个新近似值 , 立即用它代替 去进行下一个未知量 xi+1(k+1) 的计算。这样, 不仅提高了收敛速度（因新值xi(k+1) 比旧值 xi(k) 更准确 , 达到某一精度要求所需的计算量就会减少，这样计算速度就加快了 ）, 而且也节省了存储空间