现代数值计算
第二章 线性方程组的数值解法
第二章 线性方程组的数值解法
§2.0 引 言 §2.1 Gauss消去法 §2.2 矩阵的三角分解 §2.3 QR分解和奇异值分解
汪远征
§2.0 引 言
汪远征
在自然科学和工程技术中很多问题的解决常常归结为解线性
代数方程组。
例如：电学中的网络问题
用最小二乘法求实验数据的曲线拟合问题
a(1) 11
0
a(1) 12
a(2) 22
a(1) 1n
a(2) 2n
素=00不, 则为a在n0(22,)第可1交列换中an(2n至行)
b(1) 1
b(2) 2
bn( 2
)
后再消元
[ A(2) | b(2) ]
a(2) ij
a (1) ij
a (1) i1
a (1) 11
a (1) 1j
迭代法具有需要计算机的存贮单元较少、程序设计简单、原
始系数矩阵在计算过程中始终不变等优点, 但存在收敛性及收
敛速度问题。
迭代法是解大型稀疏矩阵方程组(尤其是由微分方程离散后得
到的大型方程组)的重要方法。
第6章介绍迭代法解线性方程组。
§2.1 Gauss消去法
直接法的基础
汪远征
高斯(Gauss)消去法是解线性方程组最常用的方法之一
1. 消去过程 bi(k1)
bi( k )
a(k) ik
a(k) kk
bk( k )
(2) 第k次消元。
— —
减去第k行的
减去bk( k
)的
ai(kk ak( kk
aa)汪ki((kkkk远)) 倍征
倍
)
i k 1, k 2,..., n
a1(11) 0 [ A(k) | b22 an2
a1n
a2n
ann
为非奇异阵,
x1
x
x2
,
xn
b1
b
b2
bn
关于线性方程组的数值解法一般有两类：
直接法与迭代法。
§2.0 引 言
汪远征
1. 直接法
就是经过有限步算术运算, 可求得方程组精确解的方法(若计算
过程中没有舍入误差)。
a(1) n1
a(1) 12
a(1) 22
a(1) n2
a(1) 1n
a(1) 2n
a(1)
nn
b1(1 b2(1
) )
bn(1
)
a1(11)
0
0
a(1) 12
a(2) 22
a(2) n2
a(1) 1n
a(2) 2n
b(1) 1
b(2) 2
a(2) nn
b(2) n
[ A(2) | b(2) ]
它的基本思想是通过逐步消元（行的初等变换）, 把方程组化 为系数矩阵为三角形矩阵的同解方程组, 然后用回代法解此三 角形方程组（简单形式）得原方程组的解。
例如：
1 1 1 6 1 1 1 6
[ A | b] 1
3
2 1 0
2
3
5
2 2 1 1 0 4 1 11
1 1 1 6
0
2
b( k1) i
bi( k )
a(k) ik
a(k) kk
bk( k )
j k 1, k 2,..., n
— —
减去第k行的
减去bk(
k
)的
ai(kk ak( kk
a(k) ik
a(k) kk )
倍
)
倍
i k 1, k 2,..., n
注：为减少计算量,
令 lik
a(k) ik
a(k) kk
a(1) 1k
a(k) kk
a(k) nk
a(1) 1n
b1(1
)
a(k) kn
bk( k
)
a(k) nn
bn(k )
a(1) 11
a(1) 1k
a(1) 1 k 1
a a (k )
(k)
kk
k ,k1
0
a ( k1) k 1, k 1
0
a ( k1) n, k 1
a(1) 1n
3
5
0 0 7 21
§2.1 Gauss消去法 下面讨论一般的解n阶方程组的高斯消去法。
1. 消去过程
将原方程组记为 A(1)x =b(1) 其中A(1)=(aij(1))nn=(aij)nn , b(1)=b (1) 第一次消元。
汪远征
[ A(1)
|
b(1) ]
a(1) 11
a(1) 21
,
则
a( k 1) ij
a(k) ij
likak( kj )
b( k 1) i
b(k) i
likbk( k )
j k 1, k 2,..., n
i k 1, k 2,..., n
但实际计算中由于舍入误差的存在和影响, 这种方法也只能求
得线性方程组的近似解。
本章将阐述这类算法中最基本的高斯消去法及其某些变形。
这类方法是解低阶稠密矩阵方程组的有效方法, 近十几年来直
接法在求解具有较大型稀疏矩阵方程组方面取得了较大进展
。
§2.0 引 言
汪远征
2. 迭代法
就是用某种极限过程去逐步逼近线性方程组精确解的方法。
a(k)
kn
a ( k 1) k 1, n
a ( k 1) nn
b(1) 1
b(k) k
b( k 1 k 1
)
[ A(k1)
|
b(k1) ]
bn( k1)
§2.1 Gauss消去法
1. 消去过程
汪远征
(2) 第k次消元。
a( k1) ij
a(k) ij
a(k) ik
a(k) kk
a(k) kj
b(2) i
b(1) i
a (1) i1
a (1) 11
b(1) 1
j 2,3,..., n
—
减去第1行的
a (1) i1
a (1) 11
倍
—
减去b1(1)的
a (1) i1
a (1) 11
倍
i 2,3,..., n
ai(§jk12) .1ai(Gjk )auaaski((skkkk消)) ak(去kj ) 法j k 1, k 2,..., n
解非线性方程组问题
用差分法或者有限元方法解常微分方程
偏微分方程边值问题等
都导致求解线性代数方程组。
§2.0 引 言
汪远征
这些方程组的系数矩阵大致分为两种
一种是低阶稠密矩阵(例如, 阶数大约为≤150)
另一种是大型稀疏矩阵(即矩阵阶数高且零元素较多)
§2.0 引 言
汪远征
设有线性方程组Ax = b, 其中
§2.1 Gauss消去法
1. 消去过程
(1) 第一次消元。
[ A(1)
|
b(1) ]
a(1) 11
a(1) 21
a(1) 12
a(1) 22
a(1) n1
a(1) n2
其中
a(2) 2j
a (1) 2j
a (1) 21
a (1) 11
a (1) 1j
汪远征
j 2,3,...n
aaa注 少12n(((111nnn)))：有bbb若一12n(((111))) a个11(元1)