大学数值计算方法(第3章解线性方程组的数值解法)3

a 11 Di xi , D det( A ), D i det D a n1

a 1i 1
b1 bn
a1i 1 a ni 1


a ni 1

a1 n a nn
第3章
线性方程组的数值解法
但Gram法则不能用于计算方程组的解，如n＝100，1033次/秒的计算机要算10120年
所以，Gauss消元法的可行条件为： a ( k ) 0 kk
《 计 算 方 法 与 实 习 》
因此，有些有解的问题，不能用Gauss消元求解
另外，如果某个 a kk
(k )
很小的话，会引入大的误差
第3章
线性方程组的数值解法
高斯主元素消元法是消去法的一种改进。它的基
本思想是在逐次消元时总是选绝对值最大的元素(称之 为主元)做除数,按消元法的步骤消元。
《 n次运算 ① 计 算 方 A diag ( a , a , , a ) x b i , i 1, , n 11 22 nn i 法 a ii 与 实② （n＋1）n/2次运算 习 i 1 》 l11
l 21 A l n1
l 22 ln 2 l nn
《 解线性方程组的方法可以分为2类： 计 ①直接法：准确，可靠，理论上得到的解是精确的,但由于计算中有舍入误差,故 算 得到的也是近似解. 方 法 ②迭代法：速度快，但有误差（雅可比迭代法、高斯—赛得尔迭代法） 与 实 习 》
第3章
线性方程组的数值解法
3.2 消元法
我们知道，下面有3种方程的解我们可以直接求出：
运算量： (n-2)*(1+n-1)=(n-2)n

第k步消元：
丛rk+1,rk+2, ,rn中消去xk项，条件akk(k)≠0，使得
A(k+1)x = b(k+1)A(k)x = b(k)
其中
第3章 线性代数方程组的数值解法Gauss消去法
(1 a11) (1 a12)

(k a kk )
( a11) n ( a 22 ) n


( a nn,1n)1 1

( a nn 1) 1n (n a nn)
b1(1) (1) b1 ( bnn11) (n) bn
(3.2.5)
由(3.2.4)式按倒序可方便的求出解向量x：
xn
( n) bn
( n) ann
( ( ( xn1 bnn11) ann,1n) xn ann,1n)1 1 1
ri(k)likrk(k) ri(k+1)，i= k+1,k+2, ,n
(3.2.2)
以矩阵[A(k)，b(k)]中的第k行乘以-lik加到i行，即 其中第i行 aij(k+1) = aij(k) likakj(k)，i, j= k+1,k+2,,n bi(k+1) = bi (k) likbk (k)，i= k+1,k+2,,n 当完成第k=n1步时， A(1)变为上三角阵A(n) ，Gauss消元过程
b1(1) ( 2) b2 ( bn2 )
第3章 线性代数方程组的数值解法Gauss消去法
具体方法：
-(r1(1)/a11(1))a21(1)加到第2行， -(r1(1)/a11(1))a31(1)加到第3行，，

其中biT为A的第i行的n维行向量.
上页 下页
矩阵的基本运算：
(1) 矩阵加法
C A B cij aij bij ( A, B, C R
(2) 矩阵与标量的乘法
mn
).
C A cij aij ( A, C Rmn ,是一个数).
(3) 矩阵与矩阵的乘法


(1) b1 (1) b2
(1) (1) (1) a12 a1 x b n 1 1 (1) (1) (1) a 22 a 2 n x 2 b2 . (1) ( 1 ) (1) am a mn 2 x n bm

(1) bm
上页
下页
将(2.1)记为A(1)x=b(1)，其中
(1) a11 (1) a 21 a (1) m1 (1) (1) a11 a12 a1 n (1) (1) a 22 a2 a21 n (1) (1) a am a 2 mn m1
解为
b1 b2 l 21 y1 y1 , y2 , l11 l 22
, yn
bn l1 j y j
j 1
n 1
l nn
计算量（乘除法的主要部分）都为 n2/2. 因此，我们将一般的线性方程组化成等价的三 角形方程组来求解.
上页 下页
首先举一个简单的例子来说明消去法的基本思想. 例1 用消去法解方程组
上页 下页
x1 x 2 (m维列向量). m x R x x m A a1 a2 an ,
其中aj为A的第j列的m维列向量. 同理

个顺序主子式
a a (1)
(1)
11
12
Dk
a(1) 21
a(1) 22
a(1) 1k
a(1) 2k
0
(k 1, 2,..., n 1).
a a (1)
(1)
k1
k2
a(1) kk
.
13
顺序Gauss消去法计算过程中的 akk(k) 称为主元素，在 第k步消元时要用它作除数,则可能会出现以下几种情况
.
是原方程组 Ax=b 的解向量。
27
对于
Ly =b
1
由
l21
1
l31
l32 1
y1 b1
y2
b2
y3
b3
ln1 ln2 lnn1 1 yn bn
.
解得
y1 yk
b1 bk
k 1 i 1
lki
yi
,
k 2,3,, n
28
对于 Ux =y
u11 u12 u1n x1 y1
2x3 6
⑤
x1 6 (x2 x3 ) 1
x2 x3 5 / 4 2
x3 (6) / (2) 3
用x3, x2的值求x1 把x3的值代入②求x2
.
8
从下向上逐步求解
对应的增广矩阵的变化
1 1 1 6 1 1 1 6
( A | b) 0
4
1 5 0
4
1
5
2 2 1 1 0 4 1 11
0.8334
5.910
12.10
0.0120 0.0100 0.1670 0.6781
3200
1200
4.200 981.0