《计算方法》第三章 线性方程组解法

第三章线性方程组解法 (对线性代数方程组4x=b的近似解法) ●问题的提出: 求解线性方程组Ax=b,且A|≠0,其中 12 In 21 22 2n n2 b 对方程组Ar=b的解法主要用 cramer法则求 解。 ( Cramer法则:若detA≠0,则线性方程组的解 为x 其中

第三章 线性方程组解法 （对线性代数方程组 Ax = b 的近似解法） ⚫ 问题的提出： 求解线性方程组 Ax = b ，且 | A| 0 ,其中             = n n nn n n a a a a a a a a a A     1 2 2 1 2 2 2 1 1 1 2 1 ，             = xn x x x  2 1 ，             = bn b b b  2 1 对方程组 Ax = b 的解法主要用 Cramer 法则求 解。 （Cramer 法则：若 det 0 A  ，则线性方程组的解 为 1 2 , , , , 1 2 n x x x n    = = =    其中

△、(j=1,2,…,m)是以常数项向量b代换A中的第 列向量a;=(a1;a 后得到的n阶行 列式) 困难 当方程组的阶数M很大时, Cramer法则的计 算量很大,不便使用。 解决方法 1.直接解法:( Gauss消去法及其变形、矩 阵分解法等) 2.迭代解法:构造某种极限过程去逐步逼近 方程组的解(Jac0bi迭代法 Gauss- Seidel迭代法、逐次超松弛迭代法 等)。 注:如果没有特别提出,总是假定系数行列式的值 A|≠0 §1Guss消去法、矩阵分解法 ●GaSs逐步消去法: 例1、求解三阶线性代数方程组Ax=b的解。其 中

( 1,2, , ) j n j  = 是以常数项向量 b 代换 A 中的第 j 列向量 ( , , , ) 1 2 T a a a j j j nj a = 后得到的 n 阶行 列式） ⚫ 困难： 当方程组的阶数 n 很大时， Cramer 法则的计 算量很大，不便使用。 ⚫ 解决方法： 1. 直接解法：（ Gauss 消去法及其变形、矩 阵分解法等） 2. 迭代解法：构造某种极限过程去逐步逼近 方 程 组 的 解 （ Jacobi 迭 代 法 、 Gauss − Seidel 迭代法、逐次超松弛迭代法 等）。 注：如果没有特别提出，总是假定系数行列式的值 | A| 0 。 §1 Gauss 消去法、矩阵分解法 ⚫ Gauss 逐步消去法： 例 1、求解三阶线性代数方程组 Ax = b 的解。其 中

A=45-1x=x2|·b=11 解:对线性方程组的求解,主要是讨论其增广矩阵 IA|b,即: 5-1 r2-2n1 r3-0.51 241200 3-3 2.50.5 3.5 211 r2+ 03-3 3 等价的线性方程组为:

          − = − 1 2 1 4 5 1 2 1 1 A ,           = 3 2 1 x x x x ,           = 0 11 7 b 解：对线性方程组的求解，主要是讨论其增广矩阵 [A| b] ，即：           − − − ⎯⎯⎯→ −           − = − − − 3.5 3 7 0 2.5 0.5 0 3 3 2 1 1 0 11 7 1 2 1 4 5 1 2 1 1 3 1 2 1 0.5 2 r r r r A           − − − ⎯⎯⎯→ − + 6 3 7 0 0 2 0 3 3 2 1 1 3 2 6 5 r r 等价的线性方程组为：

2x,+x,+x,=7 3x2-3x3=-3 2x,=-6 由第三个方程当中解出x3=3,代入第二 个方程可得x2=2,将上述两个值代入第一个方 程中解得:x1=1 经过上述解题过程当中的消元和回代过程的解 题方法,称之为GS逐步消元法。其中an称为 主元素。只要i≠0,(=1,2,…,n),GaSs 逐步消元法就可以做下去。 由上述解题过程可得,对于一般的线性方程组, 解题步骤主要有如下几步: ①判断1=0?若a1≠0则做r1-r1 (=2,3),将a1,i=2,3化为0; ②判断2=0?若2≠0,重复上述步骤, 直至将最后一个方程化为:a3x3=b3,则可解

     − = − − = − + + = 2 6 3 3 3 2 7 3 2 3 1 2 3 x x x x x x 由第三个方程当中解出 x3 = 3 ，代入第二 个方程可得 x2 = 2 ，将上述两个值代入第一个方 程中解得： x1 = 1 。 经过上述解题过程当中的消元和回代过程的解 题方法，称之为 Gauss 逐步消元法。其中 aii 称为 主元素。只要 aii  0 ， (i = 1,2,  ,n) ， Gauss 逐步消元法就可以做下去。 由上述解题过程可得，对于一般的线性方程组， 解题步骤主要有如下几步： ①判断 a11 = 0 ？ 若 a11  0 则 做 1 11 1 r a a r i i − (i = 2,3) ，将 ai1 ,i = 2,3 化为 0； ②判断 a22 = 0 ？若 a22  0 ，重复上述步骤， 直至将最后一个方程化为： a33 x3 = b3 ，则可解

出x ⑧将x3回代于第二个方程解出x2,再回代到第 个方程中解出x1° 特点:在顺序的消元过程,存在一些重复的步骤(可 利用计算机的长处) 下面来看n阶线性代数方程组4x=b的 Gas逐步消去法: 设an≠0(i=1,2,…,m)。一般情况下的 Gas逐步消去法过程为,对方程组4x=b, 即: 1x1+a12x2+…+m1nxn=a1n+1 21x1+a22x2+…+a2nXn=a2n+1 n1+an2x2+…+ a x=m H+1 进行消元,对其增广矩阵[A|b,首先消去第 列除m1之外的所有元素,做n

出 x3 ； ③将 x3 回代于第二个方程解出 x2 ，再回代到第 一个方程中解出 1 x 。 特点：在顺序的消元过程，存在一些重复的步骤（可 利用计算机的长处）。 下面来看 n 阶线性代数方程组 Ax = b 的 Gauss 逐步消去法： 设 a 0(i 1,2, ,n) ii  =  。 一 般 情 况 下 的 Gauss 逐步消去法过程为，对方程组 Ax = b ， 即：        + + + = + + + = + + + = + + + 1 1 2 2 1 2 1 1 2 2 2 2 2 1 1 1 1 1 2 2 1 1 1 n n nn n nn n n n n n n a x a x a x a a x a x a x a a x a x a x a     进行消元，对其增广矩阵 [A | b] ，首先消去第一 列 除 a11 之 外 的 所 有 元 素 ， 做 1 11 1 r a a r i i −

(=2,3,…,n) 1 12 (0) A= 22 2n+1 (0) (0) 2 m+1 21/a1,×r1 (0) (0) 12 In n十 r3-a31/ au xr0 (1) (1) 2n+1 a,/axr 0 (1) (1) 2 m+1 然后对第二列也作同样的处理,即:自第二个方程 起,消去a(j=3,4,…,m)的所有元素,做 q,(l2(i=3,4,…,m)得 2 7-an/a2×[a1 (0) 2 r4-a42/a2×20 (1) 2 rn-an2/a2×X00 其第k-1步的结果为

(i = 2,3,  ,n)               = + + + (0) 1 (0) 2 1 (0) 1 1 (0) (0) 2 (0) 1 (0) 2 (0) 22 (0) 21 (0) 1 (0) 12 (0) 11 nn n n n n nn n n a a a a a a a a a a a a A                       −  − − − − − − − → −  −  + + + (1) 1 (1) 2 1 (0) 1 1 (1) (1) 2 (1) 2 (1) 2 2 (0) 1 (0) 1 2 (0) 1 1 1 1 1 1 3 3 1 1 1 1 2 2 1 1 1 1 0 0 nn n n n nn n n n n a a a a a a a a a a r a a r r a a r r a a r         然后对第二列也作同样的处理，即：自第二个方程 起，消去 ( 3,4, , ) (1) a j 2 j =  n 的所有元素，做 (1) 2 22 (1) 2 r a a r i i − (i = 3,4,  ,n) 得：               −  − − − − − − − → −  −  + + + (2) 1 (1) 2 1 (0) 1 1 (2) (1) 2 (1) 2 2 (0) 1 (0) 1 2 (0) 1 1 2 2 2 2 4 4 2 2 2 2 3 3 2 2 2 2 0 0 0 nn n n nn n n n n a a a a a a a a a r a a r r a a r r a a r         其第 k − 1 步的结果为：

lk In In+1 (k-1) (k-1) (k-1) 第/步消元过程:以第个方程为基础,后面的 第/+1个方程,第/+2个方程,直至第n个方 程,作如下的计算: ikk (i=k+1,k+2,…,n), (0) an0anm1其中: k-1) k+1k+1 k+ln k+1n+1 (k) (k-1) i (k-1) k (k) (k-1) L.a(k-1)上述过程经过 ik kj

                − + − − − + − − + ( 1) 1 ( 1) ( 1) ( 1) 1 ( 1) ( 1) (0) 1 1 (0) 1 (0) 1 (0) 1 1 k nn k nn k nk k k n k k n k k k k n n a a a a a a a a a a            第 k 步消元过程：以第 k 个方程为基础，后面的 第 k + 1 个方程，第 k + 2 个方程，直至第 n 个方 程，作如下的计算： r l r (i k 1,k 2, ,n) i − ik k = + +  ， 其中: ( 1) ( 1) − − = k kk k ik ik a a l , ( ) ( −1) ( −1) = − k ik kj k ij k aij a l a , 上 述 过 程 经 过                   + + + + + + + − + − − + − + ( ) 1 ( ) ( ) 1 ( ) ( ) 1 1 ( ) 1 ( ) 1 1 ( 1) 1 ( 1) ( 1) 1 ( 1) (0) 1 1 (0) 1 (0) 1 (0) 1 1 0 0 k nn k nn k k n k ij k k n k k n k k k k k n k k n k k k k k k k n n a a a a a a a a a a a a a a a              

n-1步之后,得 (0) (0) 11 12 In 1n+1 2 n n+ (n-1) (n- +1 上面的所有过程就是消元过程。下面的过程即为回 代过程: 由第n个方程,可以解得: nn+1 n nn 将其值代入到第n-1个方程,可以解得: (n-2) (n-2) n-1,n+1 n-1,n n n-2) (n-2).U +1 n-1,n+1 n-ln (n-1) nn 逐步回代,到第k个方程可求出x,即 (k-1 ∑qx)/a j=k+1 直至第一个方程,可以得到:

n −1 步之后，得             − + − + + ( 1) 1 ( 1) (1) 2 1 (1) 2 (1) 2 2 (0) 1 1 (0) 1 (0) 1 2 (0) 1 1 n nn n nn n n n n a a a a a a a a a      上面的所有过程就是消元过程。下面的过程即为回 代过程： 由第 n 个方程，可以解得： ( 1) ( 1) 1 − − + = n nn n nn n a a x ， 将其值代入到第 n − 1 个方程，可以解得： ( 1) , ( 1) 1 ( 2) 1, ( 2) 1, 1 ( 2) 1, ( 2) 1 1, 1 − − − + − − − + − − − − − + = −  = −  n n n n n nn n n n n n n n n n n n n n a a a a x a a x 逐步回代，到第 k 个方程可求出 xk ，即： ( 1) 1 ( 1) ( 1) 1 ( )/ − = + − − = + −  k k k n j k j k k j k k k n x a a x a 直至第一个方程，可以得到：

1n+1 ∑ 1j)/aco Gas逐步消去法的工作量的大小:运算数 量级大约为n3/3 其实质:对增广矩阵作初等行变换 其缺点:任一a kk 0(k=1,2,…,n), 就无法做下去 任一k绝对值很小时,也不行(误差大) Gas主元素消去法(GaSs逐步消去 法的改进) 列主元消去法 基本思想: Gauss逐步消去法时,消去第k列 时,取U1为: max(akk,a+k,…,amk对应的那个元 素。判断i=k?,若≠k,则r>r,即交 换第k个方程与第个方程。再判断>E? (其中E是用来控制a的大小的量),若i>E

(0) 11 2 (0) 1 (0) 1 1 1 x (a a x )/ a n j n  j j = = + − Gauss 逐步消去法的工作量的大小：运算数 量级大约为 / 3 3 n 其实质：对增广矩阵作初等行变换 其缺点：任一 a 0 (k 1,2, ,n) kk = =  ， 就无法做下去 任一 akk 绝对值很小时，也不行（误差大） ⚫ Gauss 主元素消去法（ Gauss 逐步消去 法的改进） 1.列主元消去法: 基本思想： Gauss 逐步消去法时，消去第 k 列 时，取 aik 为: max{ , , , } akk ak+1,k  ank 对应的那个元 素。判断 i = k? ，若 i  k ， 则 i k r  r ，即交 换第 k 个方程与第 i 个方程。再判断   aik ？， （其中  是用来控制 ik a 的大小的量），若   aik

消元可继续;否则,消元不能继续。 与GaSs逐步消去法相比,增加了一个选主元 和换行的步骤,其它过程均没有变化。 2.全主元消去法: 基本思路:在列主元消去法中,找的是各列元素 的绝对值的最大值。在全主元消去法中,找的是每 步中的子行列式中的各元素的绝对值的最大值。 考虑到找的是整个子行列式的最大值,故有可能要 交换行和列的值,对应的未知量的次序有改变,所 以消元过程结束后,要对未知量的顺序进行还原。 在一些特殊情况下,选主元与不选主元效果 样,为了节省机时就可以不选主元。如:在实际工 作中常见系数行列式中元素满足: an∑|an1(=12,…,m) J≠ 这样的矩阵我们称其为按行严格对角占优矩 阵,简称严格对角占优矩阵。 即对角线上每一元素的绝对值均大于同行各 元素绝对值之和。例如:

消元可继续；否则，消元不能继续。 与 Gauss 逐步消去法相比，增加了一个选主元 和换行的步骤，其它过程均没有变化。 2.全主元消去法: 基本思路：在列主元消去法中，找的是各列元素 的绝对值的最大值。在全主元消去法中，找的是每 一步中的子行列式中的各元素的绝对值的最大值。 考虑到找的是整个子行列式的最大值，故有可能要 交换行和列的值，对应的未知量的次序有改变，所 以消元过程结束后，要对未知量的顺序进行还原。 在一些特殊情况下，选主元与不选主元效果一 样，为了节省机时就可以不选主元。如：在实际工 作中常见系数行列式中元素满足： | | | | ( 1,2, , ) 1 a a i n n j i j ii   ij =   = 这样的矩阵我们称其为按行严格对角占优矩 阵，简称严格对角占优矩阵。 即对角线上每一元素的绝对值均大于同行各 元素绝对值之和。例如：