研究生数值分析(7)线性方程组的解法

数值分析线性方程组的解法主讲老师: 雷鸣

第2章 线性方程组的解法 求解线性代数方程组的问题在科学研究与工程

计算中经常遇到。下面我们就从n阶线性代数方程组的解法开始讨论这一问题。 设n阶线性代数方程组

a11 x1 a12 x2 a1n xn b1 a x a x a x b 21 1 22 2 2n n 2 an1 x1 an 2 x2 ann xn bn

(1)

(1)可写成矩阵形式AX b

(2)

其中A (aij )n n , X ( x1, x2 , , xn )T , b (b1, b2 , , bn )T

在线性代数中，若 D A 0

,(2)有唯

一解，可用克莱姆(Cramer)法则求解，即

xi Di / D

(i 1, 2, , n)

从计算效果看，克莱姆法则求解，需计算n+1 个 n 阶行列式，又每个 n 阶行列式为 n!项

之和，每项又是 n 个元素的乘积，计算中仅乘法就有 (n+1)n!(n-1) 次，当 n 较大时，计算量相

当惊人。比如：n=20,则

(n 1)n!(n 1) 4.6225 10

19

这个工作量在每秒作1010运算的计算机上计 算，需要大约162年，因此必须研究其它的数值 计算方法。 (在计算机上加、减运算远远快于乘、除运

算，因而常用乘、除法运算次数说明工作量)关于计算机上解线性代数方程组的方法一

般分为: “直接法”和“迭代法”两类。

(1)“直接法”就是指在没有舍入误差影 响的条件下经过有限步四则运算可求得准确解 的方法。

(2)“迭代法”就是先给一个解的初始近似值，然后按照一定法则逐步求出解的各

个更准确的近似值的方法，即用某种极限过程逐步逼近准确解的方法。

§1 Gauss消去法1)三角方程组及其解法 形如 a11 x1 a12 x2 a1n xn b1 a22 x2 a2 n xn b2 ann xn bn

(3)

的方程组是一个称为上三角线性方程组的线

性代数方程组。 当 aii 0(i 1, 2, n) 时有唯一解。

先由第n个方程解得

xn bn / ann

(4)

代入第n-1个方程，可得 xn 1 (bn 1 an 1,n xn ) / an 1,n 1 继续下去，假设已求得

xn , xn 1, , xk 1

代入第k个方程即得 xk 的计算式

bk xk

j k 1

a

n

kj

xj(k n 1, n 2, ,1) (5)

akk 上述求解过程称为回代过程。(求解三角线性 方程组(3)只需进行 1 2 n n(n 1) / 2次乘、除运算。)

1 顺序Gauss消去法 求解三角形线性方程组不但方法简单，而且计 算量又小。Gauss消去法就是基于这种思路设计的 一种解法。

高斯消去法在线性代数课程当中已经学习过，这 里再提及是想在此基础上对高斯消去法作些改进。

例1:用高斯消去法解线性方程组

x1 x2 x3 6 ① x1 3x2 2 x3 1 ② 2

x 2 x x 1 ③ 2 3 1解：先用方程①消去方程②③中的 x1即②-①,③-2①得

x1 x2 x3 6 2 x2 2 x3 5 4 x x 11 2 3

① ④ ⑤

再⑤+2④得同解三角方程组

x1 x2 x3 6 2 x2 2 x3 5 7 x3 11 回代求解得：

① ④ ⑥

x1 3, x2 2, x3 1可以看出,用高斯消去法解线性方程组可简单 分为消元和回代两个过程。

例1中消元过程表示为 1 1 1 6 1 1 1 6 1 1 1 6 第一次消元 第二次消元 [ A b] 1 3 2 1 0 2 3 5 0 2 3 5 即 r22 rr1 即r3 2r2 r3 1 2 2 1 1 0 4 1 11 0 0 7 21

其中 ri mrk 表示将第k行的m倍加到i行上去。 对一般线性代数方程组(2),若系数矩阵

A A [aij ]n n(1) (1)

右端向量

b b(1) (b1(1) , b2(1) , , bn(1) )T

则第一次消元为：当

a11(1) 0

时先算乘数(i 2,3, , n)

mi1 ai1(1) / a11(1)然后将[ A(1) b(1) ]

第一行的 mi1 倍加到第 i 行(i 2,3, , n)

(即 ri mi1r1)

,得

a11(1) a12 (1) a1n (1) (2) (2) a22 a2 n 0 (2) (2) an 2 ann 0

b (2) (2) [A b ] (2) bn b(1) 1 (2) 2

其中

aij

(2)

aij mi1a1 j(1)

(1)

(i, j 2,3, , n) (i 2,3, , n)

bi (2) bi (1) mi1b1(1)这样就得到与原方程组 同解的方程组

A(1) X b(1)

A(2) X b(2)

对 [ A(2) b(2) ]进行类似初等行变换可得

a11(1)

a12 (1) a22 (2)

a13(1) a23(2) a33(3) an 3(3)

a1n (1) a11(1)

a11(1) ann (3)

b1(1) (2) b2 (3) A(3) b(3) b3 bn (3)

其中mi 2 ai 2(2) / a22(2)aij (3) aij (2) mi 2a2 j (2)(i 3, 4, , n)

(i, j 3, 4, , n)(i 3, 4, , n)

bi (3) bi (2) mi 2b2(2)

这样，当 akk (k ) 0(k 1, 2, , n 1) 时，经n-1次消元，可得同解三角形方程组 A( n ) X b( n) ,即

a11(1) a12(1) a1n (1) x1 b1(1) (2) (2) (2) a22 a2 n x2 b2 (n) (n) ann xn bn

(6)