分析02-线性方程组直接解法(2)

W

关于线性方程组的数值解法

其中：

( ( (k aijk 1) aijk ) lik akj ) ( k 1) ( bi( k ) lik bk k ) bi (i, j k 1, , n)

(1 (1 (1 a11) x1 a12) x2 a13) x3 a1(1) xn b1(1) n ( 2) ( 2) ( 2) ( 2) a22 x2 a23 x3 a2 n xn b2 ( 3) ( 3) ( 3) a33 x3 a2 n xn b3 (2 - 6)(d) (n) (n) ann xn bn 第二章 线性方程组直接解法 2-14

W

Gauss消元法的消元过程3(n阶)照此消元下去，完成n 1次 消元后，可将原方程组化成 同解的上三角形方程组如下：

Y

关于线性方程组的数值解法

回代过程：逐步回代求得原方程组的解(n xn bn( n ) / ann ) n (2 - 7) (k ) (k ) (k ) xk (bk akl xl ) / akk k n 1, n 2, ,2,1 l k 1

由以上讨论可知 消元过程能进行到底的 , 条件是：(k (k akk ) 0 (k 1,2, , n 1) (称akk )为主元素),

而只有所有主元素 , a , , a 均不为零, 才能 a(1) 11 ( 2) 22 (n) nn

使用Gauss消去法求解线性方程组 Ax b. :第二章 线性方程组直接解法 2-15

W

Gauss消元法的回代过程(n阶)

Y

关于线性方程组的数值解法

( ( aijk 1) aijk ) lik akj x b( n) / a ( n) n n nn Gauss消元法的计算量 ( k 1) (k ) (k ) n (2 bi lik bk bi (k ) (k ) (k ) 由于在计算机中作乘除运算量所需时间远大于作加减 - 7) xk (bk akl xl ) / akk k n 1, n 2, ,2,1 (i, j k 1, , n) l k 1 运算所需时间，故只考虑作乘除运算量。

由消元法步骤知，第k次消元需作n k次除法，作 (n k)(n k + 1)次乘法，故消元过程中乘除法运算量

为：n 2 n 乘法次数 : (n k )(n k 1) (n 1) 除法次数 : (n k ) (n 1) 3 2 k 1 k 1回代过程中: 求xk 需1次除法和n k次乘法，因此回代过程 运算量为： 除法：n次； n 乘法： (n k ) (n 1) 2 k 1n

n 2 n n n3 n 2 N ( n 1) ( n 1) n ( n 1) n 3 2 2 3 3 2-16 第二章 线性方程组直接解法

W

Y

n 1

n 1

所以Gauss 消去法的 乘除法总运算量为：

关于线性方程组的数值解法

Gauss 消元法的乘 n 2 n n3 Gauss法与Cramer法则的计算量比较 n N (n 1) (n 1) n2 除法总运算量为： 3 2 3 3 与我们曾经介绍的Cramer法则的乘除法总运算量 (n2 1)n!+n 相比，由下表可知：当阶数越高时，Gauss消 元法所需乘除法次数比Cramer法则要少得多：方程组阶数Gauss消元法运算量Cramer法则运算量Y

Gauss 消元法的优缺点： Gauss消元法简单易行。 但其计算过程中，要求akk(k)(称为主元素)均不为零， 因而适用范围小，只适用于从1到n 1阶顺序主子式均不 为零的矩阵A,计算实践还表明，Gauss消元法的数值稳 定性差，当出现小主元素时，会严重影响计算结果的精度， 2-17 第二章 线性方程组直接解法 甚至导出错误的结果。

W

3

10

20

50

1751

430359251210

30609.7×1020

441507.6×1067

关于线性方程组的数值解法

2.1 引入主元素的必要性 对线性方程组AX = b,若其系数行列式 det(A) 0,则该方程组有唯一 解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元 素等于零，就不能用Gauss消元法求解该方程组， 即使所有主元素不等于零，但 某一主元素的绝对 值很小时，Gauss消元法也是不适用的。如下例： 0.50x1 1.1x2 3.1x3 6.0 例2 求解方程组： .0 x1 4.5 x2 0.36x3 0.020 (2 - 8) 2 5.0 x 0.96x 6.5 x 0.96 1 2 3 第二章 线性方程组直接解法

上式中所有系数均有 位有效数字。 2

W

§2 主元素法

Y

2-18

关于线性方程组的数值解法

解：为减小误差，计算过程中保留3位有效数字。 按Gauss消元法步骤：

第一次消元后得同解方程组： 第二次消元后得同解方程组 0.50x1 1.1x 2 3.1x3 6.0 0.50x1 1.1x 2 3.1x3 6.0 0.100x 2 12.0 x3 24.0 0.100x 2 12.0 x3 24.0 1220x3 2460 10.0 x 2 24.5 x3 59.0

回代得解，x3 = 2.02,x2 = 2.40,x1 = 5.80。 容易验证，方程组(3-8)的准确解为： x1 = 2.60, x2 = 1.00,x3 = 2.0。显然两种结果相差很大。第二章 线性方程组直接解法 2-19

W

例2(续1)

Y