概述
文章目录
- 6 解线性方程组迭代方法
- 6.1 Jacobi迭代法和Gauss-Seidel迭代法
- 6.1.1 Jacobi迭代法
- 6.1.2 Gauss-Seidel迭代法
- 6.1.3 上面两种迭代法的矩阵形式
- 6.2 迭代法的一般形式与收敛性
- 6.2.1 一般形式
- 6.2.2 收敛性
- 6.3 Jacobi和Gauss-Seidel的收敛性
- 6.4 逐次超松弛迭代法
6 解线性方程组迭代方法
迭代方法选取一个初始向量 x ( 0 ) x^{(0)} x(0)，然后按照迭代公式，依次计算 x ( 1 ) x^{(1)} x(1)， x ( 2 ) x^{(2)} x(2)，……，最终当 k k k足够大的情况下， x ( k ) x^{(k)} x(k)就是方程组的近似解。由于是迭代计算，本身求解结果就是不停迭代来不停接近真实解，而且在每次迭代计算过程中由于机器精度问题也会存在误差，所以迭代法难以获得精确解，是一种逐次近似的方法。
虽然不绝对精确，但是因为算法简单易于实现，所以适用于求解大型稀疏线性方程组。
6.1 Jacobi迭代法和Gauss-Seidel迭代法
通过一个简单方程组，理解两种迭代方法：
{
a
11
x
1
+
a
12
x
2
+
a
13
x
3
=
b
1
a
21
x
1
+
a
22
x
2
+
a
23
x
3
=
b
2
a
31
x
1
+
a
32
x
2
+
a
33
x
3
=
b
3
left{begin{array}{l}{a_{11} x_{1}+a_{12} x_{2}+a_{13} x_{3}=b_{1}} \ {a_{21} x_{1}+a_{22} x_{2}+a_{23} x_{3}=b_{2}} \ {a_{31} x_{1}+a_{32} x_{2}+a_{33} x_{3}=b_{3}}end{array}right.
⎩⎨⎧a11x1+a12x2+a13x3=b1a21x1+a22x2+a23x3=b2a31x1+a32x2+a33x3=b3
6.1.1 Jacobi迭代法
雅克比迭代法，就是这个方程组通过简单的移项等操作，可以得到等价的下面方程组：
{
x
1
=
1
a
11
(
b
1
−
a
12
x
2
−
a
13
x
3
)
x
2
=
1
a
22
(
b
2
−
a
21
x
1
−
a
23
x
3
)
x
3
=
1
a
33
(
b
3
−
a
31
x
1
−
a
32
x
2
)
left{begin{array}{l}{x_{1}=frac{1}{a_{11}}left(b_{1}-a_{12} x_{2}-a_{13} x_{3}right)} \ {x_{2}=frac{1}{a_{22}}left(b_{2}-a_{21} x_{1}-a_{23} x_{3}right)} \ {x_{3}=frac{1}{a_{33}}left(b_{3}-a_{31} x_{1}-a_{32} x_{2}right)}end{array}right.
⎩⎨⎧x1=a111(b1−a12x2−a13x3)x2=a221(b2−a21x1−a23x3)x3=a331(b3−a31x1−a32x2)
这样就可以形成迭代计算公式，因为
x
1
,
x
2
,
x
3
x_1,x_2,x_3
x1,x2,x3都可以根据其他值进行计算，得到下面：
{
x
1
(
k
+
1
)
=
1
a
11
(
b
1
−
a
12
x
2
(
k
)
−
a
13
x
3
(
k
)
)
x
2
(
k
+
1
)
=
1
a
22
(
b
2
−
a
21
x
1
(
k
)
−
a
23
x
3
(
k
)
)
x
3
(
k
+
1
)
=
1
a
33
(
b
3
−
a
31
x
1
(
k
)
−
a
32
x
2
(
k
)
)
left{begin{array}{l}{x_{1}^{(k+1)}=frac{1}{a_{11}}left(b_{1}-a_{12} x_{2}^{(k)}-a_{13} x_{3}^{(k)}right)} \ {x_{2}^{(k+1)}=frac{1}{a_{22}}left(b_{2}-a_{21} x_{1}^{(k)}-a_{23} x_{3}^{(k)}right)} \ {x_{3}^{(k+1)}=frac{1}{a_{33}}left(b_{3}-a_{31} x_{1}^{(k)}-a_{32} x_{2}^{(k)}right)}end{array}right.
⎩⎪⎪⎪⎨⎪⎪⎪⎧x1(k+1)=a111(b1−a12x2(k)−a13x3(k))x2(k+1)=a221(b2−a21x1(k)−a23x3(k))x3(k+1)=a331(b3−a31x1(k)−a32x2(k))
对于这个计算公式，先任意选定一个初始向量
x
(
0
)
=
(
x
1
(
0
)
,
x
2
(
0
)
,
x
3
(
0
)
)
x^{(0)}=(x_1^{(0)},x_2^{(0)},x_3^{(0)})
x(0)=(x1(0),x2(0),x3(0))，然后依次计算出
x
(
1
)
,
x
(
2
)
,
.
.
.
x^{(1)},x^{(2)},...
x(1),x(2),...如果这些迭代向量
{
x
(
k
)
}
{x^{(k)}}
{x(k)}收敛于向量
x
∗
x^*
x∗，那么向量
x
∗
x^*
x∗就是原方程组的解。而且，根据精度要求，可以取第k次迭代向量作为原方程组的近似解。
当方程组扩展到n元时，Jacobi迭代方法为：
x
i
(
k
+
1
)
=
1
a
i
i
(
b
i
−
∑
j
=
1
i
−
1
a
i
j
x
j
(
k
)
−
∑
j
=
i
+
1
n
a
i
j
x
j
(
k
)
)
i
=
1
,
2
,
⋯
 
,
n
,
k
=
0
,
1
,
⋯
begin{array}{c}{x_{i}^{(k+1)}=frac{1}{a_{i i}}left(b_{i}-sum_{j=1}^{i-1} a_{i j} x_{j}^{(k)}-sum_{j=i+1}^{n} a_{i j} x_{j}^{(k)}right)} \ {i=1,2, cdots, n, quad k=0,1, cdots}end{array}
xi(k+1)=aii1(bi−∑j=1i−1aijxj(k)−∑j=i+1naijxj(k))i=1,2,⋯,n,k=0,1,⋯
6.1.2 Gauss-Seidel迭代法
高斯-赛德尔迭代法，优化了雅克比迭代法。在雅克比迭代中，每次计算迭代向量都是根据前一次的结果进行计算，但实际上在计算
x
i
x_i
xi的时候，
x
j
,
j
∈
[
1
,
i
−
1
]
x_j,jin [1,i-1]
xj,j∈[1,i−1]都已经计算出来了。GS迭代法，就是利用上了当前迭代过程已经计算出的结果，有如下迭代公式：
{
x
1
(
k
+
1
)
=
1
a
11
(
b
1
−
a
12
x
2
(
k
)
−
a
13
x
3
(
k
)
)
x
2
(
k
+
1
)
=
1
a
22
(
b
2
−
a
21
x
1
(
k
+
1
)
−
a
23
x
3
(
k
)
)
x
3
(
k
+
1
)
=
1
a
33
(
b
3
−
a
31
x
1
(
k
+
1
)
−
a
32
x
2
(
k
+
1
)
)
left{begin{array}{l}{x_{1}^{(k+1)}=frac{1}{a_{11}}left(b_{1}-a_{12} x_{2}^{(k)}-a_{13} x_{3}^{(k)}right)} \ {x_{2}^{(k+1)}=frac{1}{a_{22}}left(b_{2}-a_{21} x_{1}^{(k+1)}-a_{23} x_{3}^{(k)}right)} \ {x_{3}^{(k+1)}=frac{1}{a_{33}}left(b_{3}-a_{31} x_{1}^{(k+1)}-a_{32} x_{2}^{(k+1)}right)}end{array}right.
⎩⎪⎪⎪⎨⎪⎪⎪⎧x1(k+1)=a111(b1−a12x2(k)−a13x3(k))x2(k+1)=a221(b2−a21x1(k+1)−a23x3(k))x3(k+1)=a331(b3−a31x1(k+1)−a32x2(k+1))
当方程组扩展到n元时，GS迭代方法为：
x
i
(
k
+
1
)
=
1
a
i
i
(
b
i
−
∑
j
=
1
i
−
1
a
i
j
x
j
(
k
+
1
)
−
∑
j
=
i
+
1
n
a
i
j
x
j
(
k
)
)
i
=
1
,
2
,
⋯
 
,
n
,
k
=
0
,
1
,
⋯
begin{array}{c}{x_{i}^{(k+1)}=frac{1}{a_{i i}}left(b_{i}-sum_{j=1}^{i-1} a_{i j} x_{j}^{(k+1)}-sum_{j=i+1}^{n} a_{i j} x_{j}^{(k)}right)} \ {i=1,2, cdots, n, quad k=0,1, cdots}end{array}
xi(k+1)=aii1(bi−∑j=1i−1aijxj(k+1)−∑j=i+1naijxj(k))i=1,2,⋯,n,k=0,1,⋯
6.1.3 上面两种迭代法的矩阵形式
设有线性方程组：
A
x
=
b
Ax=b
Ax=b
那么可以将系数矩阵A分解为：
A
=
D
−
L
−
U
A=D-L-U
A=D−L−U
其中D是A的对角线构成的对角矩阵，L和U分别是下三角矩阵和上三角矩阵，也就是公式（7）改为：
(
D
−
L
−
U
)
x
=
b
(D-L-U)x=b
(D−L−U)x=b
通过移项可以得到两种等价形式：
KaTeX parse error: Got function 'hskip' as argument to 'begin{array}' at position 1: ̲h̲s̲k̲i̲p̲1emrelax
通过第一种形式可以得到雅克比迭代矩阵形式：
x
(
k
+
1
)
=
D
−
1
(
L
+
U
)
x
(
k
)
+
D
−
1
b
,
k
=
0
,
1
,
⋯
x^{(k+1)}=D^{-1}(L+U) x^{(k)}+D^{-1} b, quad k=0,1, cdots
x(k+1)=D−1(L+U)x(k)+D−1b,k=0,1,⋯
通过第二种等价形式可以得到GS迭代矩阵形式：
x
(
k
+
1
)
=
(
D
−
L
)
−
1
U
x
(
k
)
+
(
D
−
L
)
−
1
b
,
k
=
0
,
1
,
⋯
x^{(k+1)}=(D-L)^{-1} U x^{(k)}+(D-L)^{-1} b, quad k=0,1, cdots
x(k+1)=(D−L)−1Ux(k)+(D−L)−1b,k=0,1,⋯
6.2 迭代法的一般形式与收敛性
6.2.1 一般形式
设有线性方程组：
A
x
=
b
Ax=b
Ax=b
其转化的等价形式:
x
=
M
x
+
g
x=Mx+g
x=Mx+g
可以建立迭代公式:
x
(
k
+
1
)
=
M
x
k
+
g
x^{(k+1)}=Mx^{k}+g
x(k+1)=Mxk+g
其中M成为迭代矩阵，g为某一个向量。如果迭代向量最终收敛到
x
∗
x^*
x∗，那么取极限就可以得到：
x
∗
=
M
x
∗
+
g
x^*=Mx^*+g
x∗=Mx∗+g
也就是说，
x
∗
x^*
x∗就是方程组的解。这就是迭代法的一般形式。
通过一般形式，可以知道雅克比和GS迭代法的一般式为：
- 雅克比： M = D − 1 ( L + U ) , g = D − 1 b M=D^{-1}(L+U),quad g=D^{-1}b M=D−1(L+U),g=D−1b
- GS: M = ( D − L ) − 1 U , g = ( D − L ) − 1 b M=(D-L)^{-1}U,quad g=(D-L)^{-1}b M=(D−L)−1U,g=(D−L)−1b
6.2.2 收敛性
通过一般形式可以知道:
e
(
k
+
1
)
=
M
e
(
k
)
,
k
=
0
,
1
,
⋯
e^{(k+1)}=M e^{(k)}, quad k=0,1, cdots
e(k+1)=Me(k),k=0,1,⋯
其中e为误差向量，
e
(
k
)
=
x
(
k
)
−
x
∗
e^{(k)}=x^{(k)}-x^*
e(k)=x(k)−x∗，递推可以得到：
e
(
t
)
=
M
k
e
(
0
)
,
k
=
0
,
1
,
⋯
e^{(t)}=M^{k} e^{(0)}, quad k=0,1, cdots
e(t)=Mke(0),k=0,1,⋯
所以误差趋近于0的条件是
M
k
→
0
M^kto0
Mk→0。
定理：对任意初始向量，迭代法收敛的充分必要条件是迭代矩阵M的谱半径 ρ ( M ) < 1 rho(M)<1 ρ(M)<1。
谱半径，就是矩阵特征值绝对值的最大值。
推论：对任意初始向量，迭代收敛的充分条件是 ∣ ∣ M ∣ ∣ < 1 ||M||<1 ∣∣M∣∣<1。
又来一个定理：设
∣
∣
M
∣
∣
<
1
||M||<1
∣∣M∣∣<1，那么有如下误差估计公式：
∥
x
(
k
)
−
x
∗
∥
⩽
∥
M
∥
1
−
∥
M
∥
∥
x
(
k
)
−
x
(
α
−
1
)
∥
left|x^{(k)}-x^{*}right| leqslant frac{|M|}{1-|M|}left|x^{(k)}-x^{(alpha-1)}right|
∥∥∥x(k)−x∗∥∥∥⩽1−∥M∥∥M∥∥∥∥x(k)−x(α−1)∥∥∥
∥ x ( k ) − x ∗ ∥ ⩽ ∥ M ∥ k 1 − ∥ M ∥ ∥ x ( 1 ) − x ( 0 ) ∥ left|x^{(k)}-x^{*}right| leqslant frac{|M|^{k}}{1-|M|}left|x^{(1)}-x^{(0)}right| ∥∥∥x(k)−x∗∥∥∥⩽1−∥M∥∥M∥k∥∥∥x(1)−x(0)∥∥∥
这样就可以根据迭代次数求得误差界限。按照下面的公式，可以根据误差界限，判断需要的迭代次数：
k
>
(
ln
ε
+
ln
1
−
∥
M
∥
∥
x
(
1
)
−
x
(
0
)
∥
)
/
ln
∥
M
∥
k>left(ln varepsilon +ln frac{1-|M|}{left|x^{(1)}-x^{(0)}right|}right) / ln |M|
k>(lnε+ln∥∥x(1)−x(0)∥∥1−∥M∥)/ln∥M∥
其中
ε
varepsilon
ε就是精度要求。
6.3 Jacobi和Gauss-Seidel的收敛性
迭代法一般形式的收敛性同样适用于这两种迭代方法，也就是谱半径小于1是充分必要条件，行列式小于1是充分条件。这里有提出了新的收敛判定方法。
定义：严格对角占优矩阵，就是对角线上的元素是其对应行的绝对值最大的元素，如下面：
KaTeX parse error: Got function 'hskip' as argument to 'begin{array}' at position 1: ̲h̲s̲k̲i̲p̲1emrelax
而且有：如果A是严格对角占优矩阵，则A是非奇异矩阵。
**定理：**如果A是严格对角占优矩阵，那么方程组 A x = b Ax=b Ax=b的雅克比和GS迭代法均收敛。
**定理：**如果A是对称正定矩阵，则方程组 A x = b Ax=b Ax=b的GS迭代法收敛。
6.4 逐次超松弛迭代法
逐次超松弛迭代法，简称SOR方法，是前面两种迭代法的改进，他是在每一次迭代结果添加一个修正量来得到更精确的迭代值，如果是雅克比迭代法进行优化，那么就有下面的计算公式：
x
i
(
k
+
1
)
=
x
i
(
k
)
+
1
a
i
i
(
b
i
−
∑
j
=
1
i
−
1
a
i
j
x
j
(
k
)
−
∑
j
=
i
n
a
i
j
x
j
(
k
)
)
i
=
1
,
2
,
⋯
 
,
n
,
k
=
0
,
1
,
⋯
begin{array}{c}{x_{i}^{(k+1)}=x_{i}^{(k)}+frac{1}{a_{ii}}left(b_{i}-sum_{j=1}^{i-1} a_{i j} x_{j}^{(k)}-sum_{j=i}^{n} a_{i j} x_{j}^{(k)}right)} \ {i=1,2, cdots, n, quad k=0,1, cdots}end{array}
xi(k+1)=xi(k)+aii1(bi−∑j=1i−1aijxj(k)−∑j=inaijxj(k))i=1,2,⋯,n,k=0,1,⋯
这时，如果考虑添加一个参数来控制修正量的大小（好比机器学习中的学习率）就能得到下面由GS方法优化得到的计算公式：
x
i
(
k
+
1
)
=
x
i
(
k
)
+
ω
a
i
i
(
b
i
−
∑
j
=
1
i
−
1
a
i
j
x
j
(
k
+
1
)
−
∑
j
=
i
n
a
i
j
x
j
(
k
)
)
i
=
1
,
2
,
⋯
 
,
n
,
k
=
0
,
1
,
⋯
begin{array}{c}{x_{i}^{(k+1)}=x_{i}^{(k)}+frac{omega}{a_{i i}}left(b_{i}-sum_{j=1}^{i-1} a_{i j} x_{j}^{(k+1)}-sum_{j=i}^{n} a_{i j} x_{j}^{(k)}right)} \ {i=1,2, cdots, n, quad k=0,1, cdots}end{array}
xi(k+1)=xi(k)+aiiω(bi−∑j=1i−1aijxj(k+1)−∑j=inaijxj(k))i=1,2,⋯,n,k=0,1,⋯
这个迭代方法就是SOR方法，其中的参数
ω
omega
ω叫做松弛因子，如果
ω
<
1
omega<1
ω<1，就叫做欠松弛迭代，如果
ω
>
1
omega>1
ω>1，就叫做超松弛迭代，如果
ω
=
1
omega=1
ω=1恰好就是GS迭代法的格式。根据上面计算公式可以得到矩阵格式：
x
(
k
+
1
)
=
x
(
k
)
+
ω
D
−
1
(
b
+
L
x
(
k
+
1
)
+
(
U
−
D
)
x
(
k
)
)
.
x^{(k+1)}=x^{(k)}+omega D^{-1}left(b+L x^{(k+1)}+(U-D) x^{(k)}right).
x(k+1)=x(k)+ωD−1(b+Lx(k+1)+(U−D)x(k)).
再进一步按照一般形式转化：
x
(
k
+
1
)
=
(
D
−
ω
L
)
−
1
[
(
1
−
ω
)
D
+
ω
U
]
x
(
k
)
+
ω
(
D
−
ω
L
)
−
1
b
k
=
0
,
1
,
⋯
begin{array}{c}{x^{(k+1)}=(D-omega L)^{-1}[(1-omega) D+omega U] x^{(k)}+omega(D-omega L)^{-1} b} \ {k=0,1, cdots}end{array}
x(k+1)=(D−ωL)−1[(1−ω)D+ωU]x(k)+ω(D−ωL)−1bk=0,1,⋯
可以得到SOR方法的迭代矩阵：
f
ω
=
(
D
−
ω
L
)
−
1
[
(
1
−
ω
)
D
+
ω
U
]
mathcal{f}_{omega}=(D-omega L)^{-1}[(1-omega) D+omega U]
fω=(D−ωL)−1[(1−ω)D+ωU]
定理：SOR方法的收敛的充分必要条件是
ρ
(
f
ω
)
<
1
rho(mathcal{f}_omega)<1
ρ(fω)<1，收敛的充分条件是
∣
∣
f
ω
∣
∣
<
1
||mathcal{f}_omega||<1
∣∣fω∣∣<1
定理:SOR方法收敛的必要条件是 0 < ω < 2 0<omega<2 0<ω<2
定理：如果系数矩阵A是对称正定矩阵，且 0 < ω < 2 0<omega<2 0<ω<2，则SOR方法收敛。
最后
以上就是潇洒店员为你收集整理的数值分析(6)-解线性方程组迭代方法6 解线性方程组迭代方法的全部内容，希望文章能够帮你解决数值分析(6)-解线性方程组迭代方法6 解线性方程组迭代方法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复