当前位置:
文档之家› 数值分析——线性方程组直接解法
数值分析——线性方程组直接解法
b
b2
an1
an2
ann
xn
bn
2020/8/22
第五章 线性方程组的直接解法
2
若系数矩阵A非奇异,即 det (A)≠0 ,则方程组有
惟一解 x =( x1, x2, …, xn )T .
根据 Gramer(克莱姆)法则,求解方程组(7.1)时, 要计算大量的行列式,所需乘法次数大约为
Gauss消去法由消元和回代两个过程组成,先讨论 一个具体的线性方程组的求解。
2020/8/22
第五章 线性方程组的直接解法
5
一、顺序Gauss消 例去7.1法. 用Gauss消去法解方程组 用增广矩阵进行进算
2 x1 4 x2 2 x3 2
x1
2 x2
3 x3
3
3 x1 2 x2 5 x3 1
a(1) 1n
a(2) 2n
a(3) 3n
b1(1) b2( 2 )
b3( 3 )
0
0
a(3) n3
a(3) nn
bn(3)
其中
a(3) ij
a(2) ij
l
i
a(2)
2 2j
,
i, j 3,4,, n
b(3) i
b(2) i
li
b(2)
2020/8/22
第五章 线性方程组的直接解法
4
§1 Gauss消去 法
Gauss(高斯)消去法是一种规则化的加减消元法
基 本思 想
通过逐次消元计算把需求解的线性方程组转化成 上三角形方程组,也就是把线性方程组的系数矩阵转 化为上三角矩阵,从而使一般线性方程组的求解转化 为等价(同解)的上三角形方程组的求解。
an(11)
a (1) n2
a (1) n3
顺序Gauss消去法的消元过程可表述如下:
a (1) 1n
a (1) 2n
a (1) 3n
a (1) nn
b1(1) b2(1)
b3(1)
bn(1)
第一步,设 a11(1)≠ 0 ,将第一列a11(1)以下各元素消成零
即依次用
li1
a (1) i1
x 2 3 23020/8/22 x2 1 6
x 2 3 x 1 第五章 线性方程组的直接解法
3
2
3,
x2 1/ 6,
x1 2 / 3 6
这样,对于方程组
a11 x1 a12 x2 a1n xn b1 a21x1a22 x2 a2n xn b2 an1 x1 an2 x2 ann xn bn
第五章 线性方程组的直接解法
§1 Gauss消去法 1.1 顺序Gauss消去法 1.2 列主元Gauss消去法
§2 直接三角分解方法 2.1 Gauss消去法的矩阵运算 2.2 Doolittle分解法 2.3 平方根法 2.4 追赶法
在科学计算中,经常需要求解含有n个未知量
的n个方程构成的线性方程组
即依次用
li2
a(2) i2
a(2) 22
(i=3,4,…,n)
乘以矩阵[A(2),b(2)]的第二行再加到第i行,得到矩阵
2020/8/22
第五章 线性方程组的直接解法
9
a01(11)
A(2) , b(2) 0
a(1) 12
a(2) 22 0
a(1) 13
a(2) 23
a(3) 33
a(2) 3n
b1(1) b2( 2 )
b3( 2 )
0
a(2) n2
a(2) n3
a(2) nn
bn(2)
其中
a(2) ij
a (1) ij
l
i
a (1)
1 1j
,
i,
j
2,3,, n
b(2) i
b(1) i
l
i
b(1)
11
,
i
2,3,, n
第二步,设 a22(2)≠ 0 ,将第二列a22(2)以下各元素消成零,
a (1) 1n
a (1) 2n
a (1) 3n
a (1) nn
b1(1) b2(1)
b3(1)
bn(1) 7
aa12((1111))
A, b A(1) , b(1) a3(11)
a (1) 12
a (1) 22
a (1) 32
a (1) 13
a (1) 23
a (1) 33
a (1) 11
(i=2,3,…,n)
乘以矩阵[A(1),b(1)]的第一行再加到第i 行,得到矩阵
2020/8/22
第五章 线性方程组的直接解法
8
a01(11)
A(2) , b(2) 0ห้องสมุดไป่ตู้
a(1) 12
a(2) 22
a(2) 32
a(1) 13
a(2) 23
a(2) 33
a(1) 1n
a(2) 2n
(7.1)
或者
Ax=b
我们用增广矩阵表示,并给出gauss消去法的具体算法
aa12((1111))
A, b A(1) , b(1) a3(11)
a (1) 12
a (1) 22
a (1) 32
a (1) 13
a (1) 23
a (1) 33
2020/8/22
第五章a线n(11性) 方程a组n(的12)直接a解n法(13)
a11 x1 a12 x2 a1n xn b1 a21x1a22 x2 a2n xn b2 an1 x1 an2 x2 ann xn bn
(7.1)
方程组还可以用矩阵形式表示为: Ax=b
a11 a12 a1n
x1
b1
A
a21
a22
a2n
,
x
x2
,
N=(n2-1)n!
当 n 较大时,这个计算量是惊人的。例 如,当 n= 20
时,约需乘法次数为 N=9.7×1020
如果用每秒一亿次的计算机来计算,需要三十万年时 间。可见Gramer法则不是一种实用的方法。
因此,必须构造出适合于计算机使用的线性方程组的求 解方法。
2020/8/22
第五章 线性方程组的直接解法
2 x1 4 x2 2 x3 2
4x2 2x3 2
8x2 8x3 4
2 4 2 2
A, b
1
2 3 3
3 2 5 1
2 4 2 2 0 4 2 2 0 8 8 1
2 x1 4 x2 2 x3 2
4x2 2x3 2
12 x3 8
2 4 2 2 0 4 2 2 0 0 12 8
3
求解线性方程组的数值方法可分为两大类:直接 方法和迭代方法。本章讨论直接方法,迭代方法将在 下一章中讨论。
直接方法的特点是,如果不考虑计算过程中的舍 入误差,运用此类方法经过有限次算术运算就能求出 线性方程组的精确解。
需要指出,由于实际计算中舍入误差的存在,用 直接方法一般也只能求得方程组的近似值。本章我们 将给出直接解法的若干算法。