写在前面

• 1 SOR简介
• 2 SOR算法推导
• 3 SOR算法收敛性
• 4 实例分析
• 5 代码实现
• 6 参考文献与链接

迭代法收敛定理

定理1(充要条件)：
矩阵$\mathbf{M}$M的谱半径
$\rho \left( \mathbf{M} \right) =\mathop {\max} \limits_i\left\{ \lambda _i\left| i=1,2,\cdots n \right. \right\} <1\left( \lVert \mathbf{M} \rVert _2<1 \right) \,\, \tag{1}$ρ(M)=imax​{λi​∣i=1,2,⋯n}<1(∥M∥2​<1)(1)

定理2(充分条件)：
矩阵$\mathbf{M}$M的某个算子范数
$\lVert \mathbf{M} \rVert <1 \tag{2}$∥M∥<1(2)

1 SOR简介

SOR是Successive Over Relaxation（逐次超松弛）的缩写。该方法是求解大型稀疏矩阵方程组的有效方法之一，也可看作为Gauss-Seidel迭代法的加速，Gauss-Seidel是SOR迭代的一种特殊形式。

2 SOR算法推导

将方程组$\mathbf{AX}=b$AX=b写成
$a_{i 1} x_{1}+a_{i 2} x_{2}+\cdots+a_{i, i-1} x_{i-1}+a_{i i} x_{i} \cdots+a_{i n} x_{n}=b_{i}, \quad(i=1,2, \cdots, n)\tag{2.1}$ai1​x1​+ai2​x2​+⋯+ai,i−1​xi−1​+aii​xi​⋯+ain​xn​=bi​,(i=1,2,⋯,n)(2.1)
则
$\begin{aligned} &\Rightarrow a_{i i} x_{i}=b_{i}-\left(a_{i 1} x_{1}+a_{i 2} x_{2}+\cdots+a_{i, i-1} x_{i-1}\right)-\left(a_{i, i+1} x_{i+1}+\cdots+a_{i n} x_{n}\right)\\ &\Rightarrow a_{i i} x_{i}=a_{i i} x_{i}+\left(b_{i}-a_{i 1} x_{1}-a_{i 2} x_{2}-\cdots-a_{i, i-1} x_{i-1}-a_{i i} x_{i}-a_{i, i+1} x_{i+1}-\cdots-a_{i n} x_{n}\right)\\ &\Rightarrow x_{i}=x_{i}+\frac{1}{a_{i i}}\left(b_{i}-a_{i 1} x_{1}-a_{i 2} x_{2}-\cdots-a_{i, i-1} x_{i-1}-a_{i t} x_{i}-a_{i, i+1} x_{i+1}-\cdots-a_{i n} x_{n}\right) \end{aligned}$​⇒aii​xi​=bi​−(ai1​x1​+ai2​x2​+⋯+ai,i−1​xi−1​)−(ai,i+1​xi+1​+⋯+ain​xn​)⇒aii​xi​=aii​xi​+(bi​−ai1​x1​−ai2​x2​−⋯−ai,i−1​xi−1​−aii​xi​−ai,i+1​xi+1​−⋯−ain​xn​)⇒xi​=xi​+aii​1​(bi​−ai1​x1​−ai2​x2​−⋯−ai,i−1​xi−1​−ait​xi​−ai,i+1​xi+1​−⋯−ain​xn​)​
于是Gauss-Seidel迭代法可写成（$a_{i,i}\ne 0$ai,i​​=0）
$\begin{array}{c} x_{i}^{(k+1)}=x_{i}^{(k)}+\frac{1}{a_{i i}}\left(b_{i}-a_{i 1} x_{1}^{(k+1)}-\cdots-a_{i, i-1} x_{i-1}^{(k+1)}-a_{i n} x_{i}^{(k)}-\cdots-a_{i n} x_{n}^{(k)}\right) \\ =x_{i}^{(k)}+\frac{1}{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) \\ r_{i}^{(k)}=\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), \quad i=1,2, \cdots, n \end{array}\tag{2.2}$xi(k+1)​=xi(k)​+aii​1​(bi​−ai1​x1(k+1)​−⋯−ai,i−1​xi−1(k+1)​−ain​xi(k)​−⋯−ain​xn(k)​)=xi(k)​+aii​1​(bi​−∑j=1i−1​aij​xj(k+1)​−∑j=in​aij​xj(k)​)ri(k)​=(bi​−∑j=1i−1​aij​xj(k+1)​−∑j=in​aij​xj(k)​),i=1,2,⋯,n​(2.2)
记
$r_{i}^{(k)}=\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), \quad i=1,2, \cdots, n$ri(k)​=(bi​−j=1∑i−1​aij​xj(k+1)​−j=i∑n​aij​xj(k)​),i=1,2,⋯,n
则(2.2)式可写成
$x_{i}^{(k+1)}=x_{i}^{(k)}+\frac{1}{a_{i i}} r_{i}^{(k)}\tag{2.3}$xi(k+1)​=xi(k)​+aii​1​ri(k)​(2.3)
由(2.3)式可看出，Gauss-Seidel迭代法的第$k+1$k+1步的基础上每个分量上加上$\frac{1}{a_{i i}} r_{i}^{(k)}$aii​1​ri(k)​。为了获得更快的收敛效果，在修正项的前面乘以一个参数$\omega$ω，于是得到逐次超松弛算法
$x_{i}^{(k+1)}=x_{i}^{(k)}+\frac{\omega}{a_{i i}} r_{i}^{(k)}, \quad i=1,2, \cdots, n\tag{2.4}$xi(k+1)​=xi(k)​+aii​ω​ri(k)​,i=1,2,⋯,n(2.4)
即
$x_{i}^{(k+1)}=(1-\omega) 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+1}^{n} a_{i j} x_{j}^{(k)}\right), \quad i=1,2, \cdots, n\tag{2.5}$xi(k+1)​=(1−ω)xi(k)​+aii​ω​(bi​−j=1∑i−1​aij​xj(k+1)​−j=i+1∑n​aij​xj(k)​),i=1,2,⋯,n(2.5)
其矩阵形式为
$\mathbf{X}^{(k+1)}=(1-\omega) \mathbf{X}^{(k)}+\omega \mathbf{D}^{-1}\left(b+\mathbf{L} \mathbf{X}^{(k)}+\mathbf{U} \mathbf{X}^{(k)}\right)\tag{2.6}$X(k+1)=(1−ω)X(k)+ωD−1(b+LX(k)+UX(k))(2.6)
其中，$\mathbf{A=D-L-U}$A=D−L−U
$\mathbf{D}=\left( \begin{matrix} a_{11}& & & \\ & a_{22}& & \\ & & \ddots& \\ & & & a_{nn}\\ \end{matrix} \right), \mathbf{L}=\left( \begin{matrix} 0& & & \\ a_{21}& 0& & \\ \vdots& \ddots& \ddots& \\ a_{n1}& a_{n2}& \cdots& 0\\ \end{matrix} \right) , \mathbf{U}=\left( \begin{matrix} 0& a_{12}& \cdots& a_{1n}\\ & 0& \ddots& a_{2n}\\ & & \ddots& \vdots\\ & & & 0\\ \end{matrix} \right)$D=⎝⎜⎜⎛​a11​​a22​​⋱​ann​​⎠⎟⎟⎞​,L=⎝⎜⎜⎜⎛​0a21​⋮an1​​0⋱an2​​⋱⋯​0​⎠⎟⎟⎟⎞​,U=⎝⎜⎜⎜⎛​0​a12​0​⋯⋱⋱​a1n​a2n​⋮0​⎠⎟⎟⎟⎞​

3 SOR算法收敛性

由(2.6)式有
$\mathbf{DX}^{\left( k+1 \right)}=\left( 1-\omega \right) \mathbf{DX}^{\left( k \right)}+\omega \left( b+\mathbf{LX}^{\left( k+1 \right)}+\mathbf{UX}^{\left( k \right)} \right)$DX(k+1)=(1−ω)DX(k)+ω(b+LX(k+1)+UX(k))
即
$\mathbf{D} \mathbf{X}^{(k+1)}-\omega \mathbf{L} \mathbf{X}^{(k+1)}=(1-\omega) \mathbf{D} \mathbf{X}^{(k)}+\omega \mathbf{U} \mathbf{X}^{(k)}+\omega b$DX(k+1)−ωLX(k+1)=(1−ω)DX(k)+ωUX(k)+ωb
于是有
$\begin{array}{l} (\mathbf{D}-\omega \mathbf{L}) \mathbf{X}^{(k+1)}=[(1-\omega) \mathbf{D}+\omega \mathbf{U}] \mathbf{X}^{(k)}+\omega b \\ \Rightarrow \mathbf{X}^{(k+1)}=(\mathbf{D}-\omega \mathbf{L})^{-1}[(1-\omega) \mathbf{D}+\omega \mathbf{U}] \mathbf{X}^{(k)}+\omega(\mathbf{D}-\omega \mathbf{L})^{-1} b \end{array}$(D−ωL)X(k+1)=[(1−ω)D+ωU]X(k)+ωb⇒X(k+1)=(D−ωL)−1[(1−ω)D+ωU]X(k)+ω(D−ωL)−1b​
记
$\left\{\begin{array}{c} \mathbf{B}_{\omega}=(\mathbf{D}-\omega \mathbf{L})^{-1}[(1-\omega) \mathbf{D}+\omega \mathbf{U}] \\ \mathbf{F}_{\omega}=\omega(\mathbf{D}-\omega \mathbf{L})^{-1} b \end{array}\right. \tag{3.1}${Bω​=(D−ωL)−1[(1−ω)D+ωU]Fω​=ω(D−ωL)−1b​(3.1)
则有
$\mathbf{X}^{(k+1)}=\mathbf{B_{\omega}} \mathbf(X)^{(k)}+\mathbf{F_{\omega}} \tag{3.2}$X(k+1)=Bω​(X)(k)+Fω​(3.2)
其中，$\mathbf{B_{ \omega}}$Bω​为SOR迭代矩阵。
由收敛定理的定理1和定理2可知，SOR收敛的充要条件是$\rho{(\mathbf{B_{\omega}})}<1$ρ(Bω​)<1或者$\lVert \mathbf{B}_{\omega} \rVert _2 <1$∥Bω​∥2​<1，可以看出SOR迭代法收敛与否或收敛的快慢都与松弛因子$\omega$ω有关，因此SOR迭代算法存在如下定理.
定理3: SOR迭代法收敛的充要条件是松弛因子$0<\omega<2$0<ω<2 .
证：由于SOR收敛，则$\rho{(\mathbf{B_{\omega}})}<1$ρ(Bω​)<1。记$\mathbf{B_{\omega}}$Bω​的特征值为$\lambda _1,\lambda _2,\cdots ,\lambda _n$λ1​,λ2​,⋯,λn​,而$n$n阶矩阵的$n$n个特征值之积等于其行列式之值，即
$\left|\operatorname{det} \mathbf{B}_{\omega}\right|=\left|\lambda_{1} \lambda_{2} \cdots \lambda_{n}\right|$∣detBω​∣=∣λ1​λ2​⋯λn​∣
而
$\left|\lambda_{i}\right| \leq\left|\rho\left(\mathbf{B}_{\omega}\right)\right|$∣λi​∣≤∣ρ(Bω​)∣
故
$\left|\operatorname{det} \mathbf{B}_{\omega}\right|=\left|\lambda_{1} \lambda_{2} \cdots \lambda_{n}\right| \leq\left[\rho\left(\mathbf{B}_{\omega}\right)\right]^{n}<1$∣detBω​∣=∣λ1​λ2​⋯λn​∣≤[ρ(Bω​)]n<1
另一方面，由
$\mathbf{B}_{\omega}=(\mathbf{D}-\omega \mathbf{L})^{-1}[(1-\omega) \mathbf{D}+\omega \mathbf{U}]$Bω​=(D−ωL)−1[(1−ω)D+ωU]
有
$\left|\operatorname{det} \mathbf{B}_{\omega}\right|=\left|\operatorname{det}(\mathbf{D}-\omega \mathbf{L})^{-1}\right| \cdot | \operatorname{det}[(1-\omega) \mathbf{D}+\omega \mathbf{U}]$∣detBω​∣=∣∣​det(D−ωL)−1∣∣​⋅∣det[(1−ω)D+ωU]
即
$\left|\operatorname{det} \mathbf{B}_{\omega}\right|=\frac{|\operatorname{det}[(1-\omega) \mathbf{D}+\omega \mathbf{U}]|}{|\operatorname{det}(\mathbf{D}-\omega \mathbf{L})|}=|1-\omega|^{n}$∣detBω​∣=∣det(D−ωL)∣∣det[(1−ω)D+ωU]∣​=∣1−ω∣n
因此有$|1-\omega|^{n}<1$∣1−ω∣n<1或者$|1-\omega|<1$∣1−ω∣<1,也即$0<\omega<2$0<ω<2.　　　　　　　　　　　$\square$□

定理4：如果矩阵$\mathbf{A}$A是对称正定的，则SOR法对于$0<\omega<2$0<ω<2是收敛的。

4 实例分析

用逐次超松弛（SOR）迭代法求解方程组$\mathbf{AX}=b$AX=b，其中矩阵$\mathbf{A}$A为
$\mathbf{A}=\left[\begin{array}{ccccccc} 12 & -2 & 1 & & & & \\ -2 & 12 & -2 & 1 & & & \\ 1 & -2 & 12 & -2 & 1 & & \\ & \ddots & \ddots & \ddots & \ddots & \ddots & \\ & & 1 & -2 & 12 & -2 & 1 \\ & & & 1 & -2 & 12 & -2 \\ & & & & 1 & -2 & 12 \end{array}\right]\left[\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ \vdots \\ x_{18} \\ x_{19} \\ x_{20} \end{array}\right]=\left[\begin{array}{c} 5 \\ 5 \\ 5 \\ \vdots \\ 5 \\ 5 \\ 5 \end{array}\right]\tag{4.1}$A=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​12−21​−212−2⋱​1−212⋱1​1−2⋱−21​1⋱12−21​⋱−212−2​1−212​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​x1​x2​x3​⋮x18​x19​x20​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​555⋮555​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​(4.1)
利用Matlab2016a软件求解(4.1)式（具体程序见第五节），讨论不同的松弛因子$\omega$ω对迭代速度的影响。其中参数设置为：最大迭代值为500。

由于(4.1)式是一个对称正定阵，且本文规定松弛因子$0<\omega<2$0<ω<2，因此由定理4可知，式(4.1)一定收敛，也即有解。求解的结果如下表。

表1　不同$\omega$ω值对方程收敛速度的影响

w	迭代次数
0.3	120
0.6	50
0.9	25
1.2	30
1.5	50
1.8	150

图1 不同$\omega$ω值时的SOR迭代曲线值

由表1或图1可知，（1）当SOR迭代法松弛因子$\omega>1$ω>1时，$\omega$ω值越大，迭代的次数就越多，收敛速度就越慢，$\omega$ω越接近1时，迭代的次数越少，收敛速度越快；（2）当SOR迭代法松弛因子$\omega<1$ω<1时，$\omega$ω越小，迭代的次数就越多，收敛速度就越慢，$\omega$ω越接近1时，迭代的次数越少，收敛速度越快；（3）SOR迭代法松弛因子不在范围内时，系数矩阵的谱半径大于1，不收敛。

小结

1. 在SOR迭代算法中，松弛因子$\omega$ω越接近1时，迭代的次数越小，收敛速度越快，故$\omega$ω最优值应选择$\omega=1$ω=1。
2. 在SOR迭代算法中，松弛因子$\omega$ω距离1越远时，迭代次数越多，收敛速度越慢。
3. 在SOR迭代算法中，松弛因子应选择$0<\omega<2$0<ω<2，当$\omega$ω超过这个范围时，不满足收敛定理，即谱半径不小于1，此时方程无解。

5 代码实现

数据下载地址
提取码：wmy0

6 参考文献与链接

[1] 数值分析 曾繁慧
[2] 科学计算与应用软件讲义_迭代思想 胡行华
[3] https://mdnice.com/
[4] Markdown Nice插件下载
[5] Markdown三线表制作方法
为了能够敲公式，第一次使用Markdown写文章，有很多不足之处请谅解
Markdown真香，更多内容请关注公众号获取