第6.2 线性方程组的迭代法
第六章 线性方程组的迭代法
一、教学目标及基本要求
通过对本节的学习,使学生掌握线性方程组的数值解法。
二、教学内容及学时分配
本节主要介绍线性方程组的数值解法,迭代公式的建立,迭代收敛性。
三、教学重点难点
1.教学重点:迭代公式的建立、迭代收敛性。 2. 教学难点:迭代收敛性。
四、教学中应注意的问题
多媒体课堂教学为主。适当提问,加深学生对概念的理解。
6.2 解线性方程组的迭代法
重要性:解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用。如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题。在实际问题中产生的线性方程组的类型有很多,如按系数矩阵含零元素多少分类,有稠密和稀疏(零元素占80%以上) 线性方程组之分;如按阶数的高低分类,有高阶(阶数在1000阶以上) 中阶、(500~1000阶) 和低阶(500阶以下) 线性方程组之分;如按系数矩阵的形状和性质分类,有对称正定、三对角、对角占优线性方程组之分。因为数值解法必须考虑方法的计算时间和空间效率以及算法的数值稳定性。因此,不同类型的线性方程组,其数值解法也不相同。但是,基本的方法可以归结为两大类,即直接法和迭代法。
分类:线性方程组的解法可分为直接法和迭代法两种方法。
(a) 直接法:对于给定的方程组,在没有舍入误差的假设下,能在预定的运算次数内求得精确解。最基本的直接法是Gauss 消去法,重要的直接法全都受到Gauss 消去法的启发。计算代价高。但实际计算中由于舍入误差的存在和影响,这种方法也只能求得线性方程组的近似解,如何避免舍入误差的增长是设计直接法时必须考虑的问题。
(b) 迭代法:基于一定的递推格式,产生逼近方程组精确解的近似序列。收敛性是其为迭代法的前提,此外,存在收敛速度与误差估计问题。迭代法要求方程组系数矩阵具有某种特殊形式(如对角占优阵),是解高阶稀疏矩阵方程组的重要方法。
迭代法的基本思想是用逐次逼近的方法求线性方程组的解。
设有方程组Ax =b (1)
将其转化为等价的便于迭代的形式x =Bx +f (2)
(这种转化总能实现,如令B =I -A , f =b )并由此构造迭代公式
x (k +1) =Bx (k ) +f (3)
其中,B 称为迭代矩阵f 称为迭代向量。对任意的初始向量x 量序列x (k ) 若lim x
k →∞
(0)
,由(3)式可求得向
{}
(k )
=x *,则x (k ) 就是方程组Ax =b 的解。此时称迭代公式(3)是
{}
收敛的,否则称为发散的。构造的迭代法是否收敛,取决于迭代矩阵 B 的性质。
§5.1.1雅可比迭代公式
⎧10x 1-x 2-2x 3=7. 2
⎪
例1 求解方程组⎨-x 1+10x 2-2x 3=8. 3
⎪-x -x +5x =4. 2
23⎩1
k +1k k
⎧x 1=0. 1x 2+0. 2x 3+0. 72⎧x 1=0. 1x 2+0. 2x 3+0. 72
⎪k +1⎪k k
x =0. 1x +0. 2x +0. 83⇒x =0. 1x +0. 2x ⎨2⎨13213+0. 83 ⎪x =0. 2x +0. 2x +0. 84⎪k +1k k
x =0. 2x +0. 2x +0. 8412⎩3312⎩
设取迭代初值x 精确解x
(0)
(0)
(0) (0)
=x 1(0) , x 2, , x n
()
T
=(0, 0, 0) T ,随着迭代次数增加,越来越接近
(0) (0)
=x 1(0) , x 2, , x n
()
T
=(1. 1, 1. 2, 1. 3) T
设有方程组
∑a
j =1
n
ij
x j =b i (1)
矩阵形式为Ax =b ,设系数矩阵A 为非奇异且a ii ≠0(i =1, 2, , n ) ,从(1)式的第i 个方程中解出x i ,得其等价形式
1x i =
a ii
n ⎛⎫ b i -∑a ij x j ⎪ ⎪
j =1, j ≠i ⎝⎭
(0)
(i =1, 2, n ) (2)
取初始向量x
(0) (0) =x 1(0) , x 2, , x n ,对(2)式应用迭代法,可建立相应的迭代公式
()
T
x
(k +1)
i
1=a ii
⎛ - ⎝
j =1, j ≠i (k +1)
∑a
n
ij
x
(k ) j
⎫+b i ⎪⎪ (3)
⎭
记为矩阵形式x
=Bx (k ) +f (4)
⎫⎪⎪⎪
⎪a nn ⎪⎭
⎛a 11
若将系数矩阵A 分解为A=D -L -U ,其中D =
⎝
a 22
⎛0 a 21
-L = a 31
a ⎝n 1
0a 32
a n 2 a nn -1
⎫⎛0a 12⎪
0⎪
⎪-U = ⎪
⎪
0⎪⎝⎭
a 13 a 23
a 1n ⎫
⎪
a 2n ⎪
⎪ ⎪
a n -1n ⎪
0⎪⎭
则方程组Ax =b 变为(D -L -U ) x =b ⇒Dx =(L +U ) x +b
x =D -1(L +U )x +D -1b =D -1(D -A ) x +D -1b =I-D -1A x +D -1b
(3),(4)分别称为雅克比迭代法的分量形式和矩阵形式,分量形式用于编程,矩阵形式用
于讨论迭代法的收敛性。 流程图P158 §6。1。2高斯—赛德尔(Gauss-Seidel )迭代法
雅克比(Jacobi)迭代法的优点是公式简单,迭代矩阵容易计算。在每一步迭代时,用x 的全部分量代入求出x 量x
(k )
(k +1)
(k )
()
的全部分量,因此称为同步迭代法,计算时需保留两个近似解向
和x
(k +1)
。
但在雅克比迭代过程中,对已经计算出的信息未能充分利用,即在计算第i 个分量x i (k +1)
(k +1) k +1) 时,已经计算出的最新分量x 1, x i (-1没有被利用。从直观上看在收敛的前提下,这些(k ) (k ) (k +1) k +1) 新的分量x 1, x i (-1应比旧分量x 1, x i -1更好,更精确一些。因此,如果每计算出一
个新的分量便立即用它取代对应的旧分量进行迭代,可能收敛更快,并且只需要存储一个近似解向量即可。
(k ) (k ) (k )
考察例1,设已得到近似值x 1, x 2, x 3
()
T
,则
⎧x 1=0. 1x 2+0. 2x 3+0. 72⎪
⎨x 2=0. 1x 1+0. 2x 3+0. 83 ⎪x =0. 2x +0. 2x +0. 84
12⎩3
k k
x 1k +1=0. 1x 2+0. 2x 3+0. 72
新值x 1
k +1
常比老值x 1精确,后面得计算用x 1
k k +1
代替x 1
k
k +1k x 2=0. 1x 1k +1+0. 2x 3+0. 83
再用x 2代替x 2
k +1k
k +1k x 3=0. 2x 1k +1+0. 2x 2+0. 84
由此得
k k ⎧x 1k +1=0. 1x 2+0. 2x 3+0. 72⎪k +1
k +1k
⎨x 2=0. 1x 1+0. 2x 3+0. 83 ⎪k +1k +1k +1x =0. 2x +0. 2x +0. 8412⎩3
据此思想可构造高斯—赛德尔(Gauss-Seidel )迭代法,其迭代公式为
x
(k+1) i
1=a ii
n ⎛i -1⎫(k+1)
-∑a ij x j -∑a ij x (k)⎪+b j i ⎪
j =i +1⎝j =1⎭
矩阵形式为X (k +1) =BX (k ) +f 仍将系数矩阵A 分解为A=D -L -U
则方程组Ax =b 变为(D -L -U ) x =b ⇒Dx =Lx +Ux +b 将最新分量代替旧分量,得
D X(k +1) =L X(k +1) +U X(k ) +b
(D -L )X(k +1) =U X(k ) +b
x (k +1) =(D -L ) -1Ux (k ) +(D -L ) -1b
B=(D -L )U f =(D -L ) -1b
-1
在多数情况下用高斯—赛德尔迭代法比雅克比迭代法收敛快。但也有相反的情况,即高
斯—赛德尔迭代法比雅克比迭代法收敛慢,甚至还有雅克比迭代法收敛,高斯—赛德尔迭代法发散的情形。 §6.1.3高斯—赛德尔(Gauss-Seidel )迭代法
超松弛迭代法是高斯—赛德尔迭代法的一种改进,是解大型稀疏矩阵方程组的有效方法之一。将前一步得结果x i k 与高斯—赛德尔迭代值~x i k +1加权平均,得到更好得近似值x i k +1。
~迭代x
加速x i
(k+1) i
1=a ii
⎛i -1
+1)
-∑a ij x (k-j ⎝j =1
j =i +1
∑a
n
ij
x
(k)j
⎫+b i ⎪⎪
⎭
k +1
=ω~x i k +1+(1-ω) x i k
合并后x
k +1i
=
-∑a ij x a ii ⎝j =1
ω⎛
i -1
(k+1) j
⎫k
-∑a ij x +b i ⎪+(1-ω) x i ⎪
j =i +1⎭
n
(k)
j
系数ω称为松驰因子。
当ω=1时, 为高斯-赛德尔迭代法.
当0
当某些方程组用高斯—赛德尔迭代法不收敛时,可以用低松弛方法获得收敛。
当ω>1时, 称为超松驰方法。可以用来加速收敛速度。
小结:通过这节课的学习,我们主要学习了线性方程组的解法可分为直接法和迭
代法两种方法。要求大家掌握雅克比迭代及高斯—赛德尔迭代法,并了解其各自优缺点。 作业:课后习题7-9.