DOI:10.12677/AAM.2022.113162,PDF,HTML,XML,被引量下载: 341浏览: 807
作者:傅毛里,刘仲云：长沙理工大学，数学与统计学院，湖南 长沙
关键词:外推法；Toeplitz矩阵；循环与反循环分裂；双参数；Hermitian正定矩阵；Extrapolated Method；Toeplitz Matrices；Circulant and Skew Circulant Splitting；Two Parameters；Hermitian Definite Matrices

文章引用：傅毛里, 刘仲云. Hermitian正定Toeplitz线性方程组的外推CSCS方法[J]. 应用数学进展, 2022, 11(3): 1484-1492. https://doi.org/10.12677/AAM.2022.113162

1. 引言

本文考虑用迭代法求解线性方程组

$T\text{x}=\text{b},$(1.1)

其中 $\text{x},\text{b}\in {ℂ}^n$， $T\in {ℂ}^n$是Hermitian正定Toeplitz矩阵。

在信号处理和控制论 [1] [2] [3] 等许多应用中经常遇到这类Toeplitz线性方程组。关于这类线性方程组的解法，主要分为直接法和迭代法两大类 [4] [5] [6] [7]。由于直接法通常存在数值不稳定的缺点 [8]，这使得迭代法更加受到人们的关注。

设系数矩阵 $T=M-N$，若M非奇异，则可推导出如下求解线性方程组(1.1)的一个迭代序列

${\text{x}}^{\left(k+1\right)}=G{\text{x}}^{\left(k\right)}+M^{-1}\text{b,}k=0,1,\cdots ,$(1.2)

其中 $G=M^{-1}N$为迭代矩阵。

对于非奇异线性方程组(1.1)，迭代(1.2)收敛当且仅当

$\rho \left(G\right)\equiv \max \left\{\left|\mu \right||\mu \in \sigma \left(G\right)\right\}<1\text{,}$

其中 $\sigma \left(G\right)$是矩阵G的谱集， $\max \{\cdot \}$是取最大元素。

对迭代(1.2)，常用的加速技巧是外推法 [9]，其迭代格式为

${\text{x}}^{\left(k+1\right)}=G_{\omega }{\text{x}}^{\left(k\right)}+\omega M^{-1}\text{b},$(1.3)

其中 $G_{\omega }=\left(1+\omega \right)I+\omega M^{-1}N$，I是n阶单位矩阵。在(1.3)中可以看到，若 $\omega =1$，则(1.3)就退化成了(1.2)的迭代方法。

对于任意Toeplitz矩阵 $T_n$皆有以下分裂

$T_n=C_n+S_n,$(1.4)

其中

$C_n=\frac{1}{2}\left[\begin{array}{ccccc}{t}_0& t_{-1}+t_{n-1}& \cdots & t_{2-n}+t_2& t_{1-n}+t_1\\ t_1+t_{1-n}& t_0& \cdots & t_{3-n}+t_3& t_{2-n}+t_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ t_{n-2}+t_{-2}& t_{n-3}+t_{-3}& \cdots & t_0& t_{-1}+t_{n-1}\\ t_{n-1}+t_{-1}& t_{n-2}+t_{-2}& \cdots & t_1+t_{1-n}& t_0\end{array}\right],$

$S_n=\frac{1}{2}\left[\begin{array}{ccccc}{t}_0& t_{-1}-t_{n-1}& \cdots & t_{2-n}-t_2& t_{1-n}-t_1\\ t_1-t_{1-n}& t_0& \cdots & t_{3-n}-t_3& t_{2-n}-t_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ t_{n-2}-t_{-2}& t_{n-3}-t_{-3}& \cdots & t_0& t_{-1}-t_{n-1}\\ t_{n-1}-t_{-1}& t_{n-2}-t_{-2}& \cdots & t_1-t_{1-n}& t_0\end{array}\right],$

显然， $C_n$是一个Hermitian循环矩阵， $S_n$是一个Hermitian反循环矩阵，分裂(1.4)为 $T_n$的一个CSCS。

基于CSCS(1.4)，Ng提出了如下的CSCS [10]

$\{\begin{array}{l}\left(\alpha I+C\right){\text{x}}^{\left(k+1/2\right)}=\left(\alpha I-S\right){\text{x}}^{\left(k\right)}+\text{b},\\ \left(\alpha I+S\right){\text{x}}^{\left(k+1\right)}=\left(\alpha I-C\right){\text{x}}^{\left(k\text{+}1/2\right)}+\text{b,}\end{array}$(1.5)

其中 $\alpha$是一个给定的正常数。作者还证明了对于任意正定Toeplitz线性方程组CSCS迭代(1.5)都收敛。此外，作者还给出了CSCS迭代收缩因子的上界，它仅依赖于C和S的最大特征值与最小特征值。2012年Akhondi等人在CSCS迭代的基础上提出了双参数的加速版本，简称ACSCS [11] 迭代，其格式为

$\{\begin{array}{l}\left(\alpha I+C\right){\text{x}}^{\left(k+1/2\right)}=\left(\alpha I-S\right){\text{x}}^{\left(k\right)}+\text{b,}\\ \left(\beta I+S\right){\text{x}}^{\left(k+1\right)}=\left(\beta I-C\right){\text{x}}^{\left(k+1/2\right)}+\text{b}\text{.}\end{array}$(1.6)

(1.6)可写成如下的单步迭代

${\text{x}}^{\left(k+1\right)}=R{\text{x}}^{\left(k\right)}+\tilde{b},$(1.7)

其中 $R={\left(\beta I+S\right)}^{-1}\left(\beta I-C\right){\left(\alpha I+C\right)}^{-1}\left(\alpha I-S\right)$， $\tilde{b}={\left(\beta I+S\right)}^{-1}\text{b}+{\left(\beta I+S\right)}^{-1}\left(\beta I-C\right){\left(\alpha I+C\right)}^{-1}\text{b}$。

ACSCS迭代的计算主要是循环矩阵和反循环矩阵与向量的乘积，这可以使用快速Fourier变换 [12] (FFT)实现，其原理是循环矩阵利用Fourier矩阵进行对角化，反循环矩阵利用Fourier矩阵与一个对角矩阵的乘积实现对角化，

$\tilde{F}=F\times \Omega ,$

其中F是Fourier矩阵， $\Omega$是对角矩阵，其主对角的元素为 $\left(1,{\text{e}}^{-\pi i/n},\cdots ,{\text{e}}^{-\left(n-2\right)\pi i/n},{\text{e}}^{-\left(n-1\right)\pi i/n}\right)$， $\tilde{F}$为酉矩阵，则有

$C=F^{*}{\Lambda }_{1}F,S={\tilde{F}}^{*}{\Lambda }_2\tilde{F},$(1.8)

其中 ${\Lambda }_1$和 ${\Lambda }_2$都是对角矩阵，对角元分别为循环矩阵C和反循环矩阵S的特征值，并且循环矩阵与反循环矩阵的特征值只需一次FFT就可以精确算出来。

2. 预备知识

接下来给出文中用到的基本定义及引理。

定义2.1 [13] 若矩阵 $T_n\in {ℂ}^{n\times n}$满足

$S_n=\frac{1}{2}\left[\begin{array}{ccccc}{t}_0& t_{-1}& \cdots & t_{2-n}& t_{1-n}\\ t_1& t_0& \cdots & t_{3-n}& t_{2-n}\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ t_{n-2}& t_{n-3}& \cdots & t_0& t_{-1}\\ t_{n-1}& t_{n-2}& \cdots & t_1& t_0\end{array}\right],$

则称 $T_n$为Toeplitz矩阵，若还满足 $t_k={\bar{t}}_{-k}\left(k=1,2,\cdots ,n-1\right)$，则称 $T_n$为Hermitian Toeplitz矩阵。

定义2.2 [14] 设 $C_{2\pi }$表示定义在区间 $\left[-\pi ,\pi \right]$内所有以 $2\pi$为周期的连续实值函数，对所有 $f\left(x\right)\in C_{2\pi }$，若

$t_k=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }f\left(x\right){\text{e}}^{-ikx}\text{d}x}\left(k=0,\pm 1,\pm 2,\cdots \right)$

为 $f\left(x\right)$的Fourier系数，则称 $f\left(x\right)$为Toeplitz矩阵 $T_n$的生成函数。

定义2.3 [14] 若 $C_n\in {ℂ}^{n\times n}$是Toeplitz矩阵，且满足 $c_{-k}=c_{n-k}\left(k=1,2,\cdots ,n-1\right)$，则称 $C_n$为循环矩阵。

定义2.4 [14] 若 $S_n\in {ℂ}^{n\times n}$是Toeplitz矩阵，且满足 $s_{-k}=-s_{n-k}\left(k=1,2,\cdots ,n-1\right)$，则称 $S_n$为反循环矩阵。

定义2.5 [14] 若 $F_n\in {ℂ}^{n\times n}$满足

${\left(F_n\right)}_{j,k}=\frac{1}{\sqrt{n}}{\text{e}}^{\frac{2\pi ijk}{n}},$

则称 $F_n$为Fourier矩阵。其中 $i=\sqrt{-1}$为虚数单位，e为自然对数的底， $\pi$为圆周率。

引理2.1 [11] 设 $T_n$是Hermitian正定Toeplitz矩阵， $C_n,S_n$为(1.4)所定义的矩阵，只要n足够大，则 $C_n$和 $S_n$的特征值均是正实的。

3. 外推CSCS迭代方法

为了进一步加速ACSCS迭代(1.7)，我们提出了以下求解线性方程组(1.1)的迭代

$\{\begin{array}{l}{\tilde{x}}^{\left(k+1\right)}=R{\text{x}}^{\left(k\right)}+\tilde{b},\hfill \\ {\text{x}}^{\left(k+1\right)}=\omega {\tilde{x}}^{\left(k+1\right)}+\left(\text{1}-\omega \right){\text{x}}^{\left(k\right)},\hfill \end{array}$(3.1)

我们称(3.1)为外推循环与反循环分裂迭代方法，简称EACSCS，其中 $\alpha ,\beta ,\omega$是给定的正常数。由(1.8)可知，循环矩阵和反循环矩阵与向量乘积可以利用快速Fourier变换实现，故EACSCS每次迭代的计算量为 $O\left(n\log n\right)$。

迭代(3.1)可以理解为直接分裂迭代，主要是便于收敛性分析，但从实际计算效果来看，该迭代不如下面的基于残差校正的迭代 [15]

$\{\begin{array}{l}{\text{x}}^{\left(k+1/2\right)}={\text{x}}^{\left(k\right)}+{\left(\alpha I+S\right)}^{-1}\left(\text{b}-T{\text{x}}^{\left(k\right)}\right)\text{,}\hfill \\ \begin{array}{l}{\tilde{x}}^{\left(k+1\right)}={\text{x}}^{\left(k+1/2\right)}+{\left(\beta I+S\right)}^{-1}\left(\text{b}-T{\text{x}}^{\left(k+1/2\right)}\right),\\ {\text{x}}^{\left(k+1\right)}=\omega {\tilde{x}}^{\left(k+1\right)}+\left(\text{1}-\omega \right){\text{x}}^{\left(k\right)}\end{array}\hfill \end{array}$(3.2)

接下来我们分析迭代(3.1)的收敛性。在不引起歧义的情况下，我们将矩阵维数的下标省略。设T是一个Hermitian正定Toeplitz矩阵，由引理2.1可知C和S的特征值均是正实的，分别记为 $0<{\lambda }_1<{\lambda }_2<\cdots <{\lambda }_n$， $0<{\mu }_1<{\mu }_2<\cdots <{\mu }_n$。

下面我们讨论 $\alpha ,\beta$的选取，为此先引入下面引理。

引理3.1 [16] 设T是一个Hermitian正定Toeplitz矩阵，R为(1.7)中所定义的迭代矩阵，则有

$\rho \left(R\right)\le {\max }_{1\le j\le n}\left|\frac{\alpha -{\mu }_j}{\beta +{\mu }_j}\right|{\max }_{1\le j\le n}\left|\frac{\beta -{\lambda }_j}{\alpha +{\lambda }_j}\right|=\varphi \left(\alpha ,\beta \right)$(3.3)

引理3.2设T是一个Hermitian正定Toeplitz矩阵，则有

${\max }_{1\le j\le n}\left|\frac{\alpha -{\mu }_j}{\beta +{\mu }_j}\right|=\{\begin{array}{lll}\frac{{\mu }_n-\alpha }{\beta +{\mu }_n},\hfill & \alpha \le \hat{\alpha },\hfill & \hfill \\ \frac{\alpha -{\mu }_1}{\beta +{\mu }_1},\hfill & \alpha >\hat{\alpha },\hfill & \hfill \end{array}{\mu }_1\le \hat{\alpha }\le {\mu }_n,$(3.4)

${\max }_{1\le j\le n}\left|\frac{\beta -{\lambda }_j}{\alpha +{\lambda }_j}\right|=\{\begin{array}{lll}\frac{{\lambda }_n-\beta }{\alpha +{\lambda }_n},\hfill & \beta \le \hat{\beta },\hfill & \hfill \\ \frac{\beta -{\lambda }_1}{\alpha +{\lambda }_1},\hfill & \beta >\hat{\beta }.\hfill & \hfill \end{array}{\lambda }_1\le \hat{\beta }\le {\lambda }_n,$(3.5)

证明 现在定义

$f_1\left(\mu \right)=\frac{\alpha -\mu }{\beta +\mu },\mu \in \left[{\mu }_1,\alpha \right],f_2\left(\mu \right)=\frac{\mu -\alpha }{\beta +\mu },\mu \in \left[\alpha ,{\mu }_n\right],$

可得

${f^{\prime }}_1\left(\mu \right)=\frac{-\beta -\alpha }{{\left(\beta +\mu \right)}^2}<0,{f^{\prime }}_2\left(\mu \right)=\frac{\beta +\alpha }{{\left(\beta +\mu \right)}^2}>0,$

故 $f_1\left(\mu \right)$单调递减， $f_2\left(\mu \right)$单调递增，所以 $f_1\left(\mu \right)$的最大值为 $f_1\left({\mu }_1\right)$， $f_2\left(\mu \right)$的最大值 $f_2\left({\mu }_n\right)$，即(3.4)得证，同理可证得(3.5)。

定理3.2设T是一个Hermitian正定Toeplitz矩阵，若 $\alpha ,\beta$取值为

$\hat{\alpha }=\frac{{\hat{\mu }}_p-{\hat{\lambda }}_p+\sqrt{\Delta }}{{\hat{\mu }}_s+{\hat{\lambda }}_s},$(3.6)

$\hat{\beta }=\frac{{\hat{\lambda }}_p-{\hat{\mu }}_p+\sqrt{\Delta }}{{\hat{\mu }}_s+{\hat{\lambda }}_s},$(3.7)

则 $\varphi \left(\alpha ,\beta \right)$达到最小，其值为

$\varphi \left(\hat{\alpha },\hat{\beta }\right)=\frac{\sqrt{\theta }-1}{\sqrt{\theta }+1},$(3.8)

其中 ${\hat{\mu }}_p={\mu }_1{\mu }_n$， ${\hat{\lambda }}_p={\lambda }_1{\lambda }_n$， ${\hat{\mu }}_s={\mu }_1+{\mu }_n$， ${\hat{\lambda }}_s={\lambda }_1+{\lambda }_n$， $\Delta ={\left({\hat{\mu }}_p-{\hat{\lambda }}_p\right)}^2+\left({\hat{\mu }}_s+{\hat{\lambda }}_s\right)\left({\hat{\mu }}_s{\hat{\lambda }}_p-{\hat{\lambda }}_s{\hat{\mu }}_p\right)$， $\theta =\left({\lambda }_n+{\mu }_1\right)\left({\lambda }_1+{\mu }_n\right)/\left[\left({\lambda }_n+{\mu }_n\right)\left({\lambda }_1+{\mu }_1\right)\right]$。

证明 有引理3.2可知，存在 $\hat{\alpha }\in \left[{\mu }_1,{\mu }_n\right]$及 $\hat{\beta }\in \left[{\lambda }_1,{\lambda }_n\right]$有(3.4)，(3.4)，为了求得 $\hat{\alpha },\hat{\beta }$使得(3.3)中 $\varphi \left(\alpha ,\beta \right)$达到最小，那么需要 $\hat{\alpha },\hat{\beta }$让(3.4)，(3.5)，同时达到最小，即

$\{\begin{array}{l}\frac{{\mu }_n-\alpha }{\beta +{\mu }_n}=\frac{\alpha -{\mu }_1}{\beta +{\mu }_1},\hfill \\ \frac{{\lambda }_n-\beta }{\alpha +{\lambda }_n}=\frac{\beta -{\lambda }_1}{\alpha +{\lambda }_1},\hfill \end{array}$(3.9)

利用 ${\hat{\mu }}_p,{\hat{\lambda }}_p,{\hat{\mu }}_s,{\hat{\lambda }}_s$，则(3.9)可化简为

$\{\begin{array}{l}2\left(\alpha \beta -{\hat{\mu }}_p\right)+(\alpha -\beta ){\hat{\mu }}_s=0,\hfill \\ 2\left(\alpha \beta -{\hat{\lambda }}_p\right)-(\alpha -\beta ){\hat{\lambda }}_s=0.\hfill \end{array}$(3.10)

经过简单计算就可得出(3.6)和(3.7)。将 $\hat{\alpha },\hat{\beta }$代入 $\varphi \left(\alpha ,\beta \right)$得

$\begin{array}{c}\varphi \left(\hat{\alpha },\hat{\beta }\right)=\frac{{\mu }_n-\hat{\alpha }}{\hat{\beta }+{\mu }_n}\times \frac{{\lambda }_n-\hat{\beta }}{\hat{\alpha }+{\lambda }_n}\\ =\frac{{\mu }_n\left({\hat{\mu }}_s+{\hat{\lambda }}_s\right)-{\hat{\mu }}_p+{\hat{\lambda }}_p-\sqrt{\Delta }}{{\mu }_n\left({\hat{\mu }}_s+{\hat{\lambda }}_s\right)-{\hat{\mu }}_p+{\hat{\lambda }}_p+\sqrt{\Delta }}\times \frac{{\lambda }_n\left({\hat{\mu }}_s+{\hat{\lambda }}_s\right)-{\hat{\lambda }}_p+{\hat{\mu }}_p-\sqrt{\Delta }}{{\lambda }_n\left({\hat{\mu }}_s+{\hat{\lambda }}_s\right)-{\hat{\lambda }}_p+{\hat{\mu }}_p+\sqrt{\Delta }}\\ =\frac{\left({\lambda }_n+{\mu }_n\right)\left({\lambda }_1+{\mu }_n\right)-\sqrt{\Delta }}{\left({\lambda }_n+{\mu }_n\right)\left({\lambda }_1+{\mu }_n\right)+\sqrt{\Delta }}\times \frac{\left({\lambda }_n+{\mu }_n\right)\left({\lambda }_n+{\mu }_1\right)-\sqrt{\Delta }}{\left({\lambda }_n+{\mu }_n\right)\left({\lambda }_n+{\mu }_1\right)+\sqrt{\Delta }}\\ =\frac{\left({\lambda }_n+{\mu }_1\right)\left({\lambda }_1+{\mu }_n\right)-\sqrt{\Delta }}{\left({\lambda }_n+{\mu }_1\right)\left({\lambda }_1+{\mu }_n\right)+\sqrt{\Delta }}\\ =\frac{\sqrt{\left({\lambda }_n+{\mu }_1\right)\left({\lambda }_1+{\mu }_n\right)/\left[\left({\lambda }_n+{\mu }_n\right)\left({\lambda }_1+{\mu }_1\right)\right]}-1}{\sqrt{\left({\lambda }_n+{\mu }_1\right)\left({\lambda }_1+{\mu }_n\right)/\left[\left({\lambda }_n+{\mu }_n\right)\left({\lambda }_1+{\mu }_1\right)\right]}+1}.\end{array}$

虽然通过定理3.2可以找到 $\hat{\alpha },\hat{\beta }$使得收缩上界达到最小，但不是谱半径 $\rho \left(R\right)$达到最小的参数，数值实验表明在 $\hat{\alpha },\hat{\beta }$的附近可以搜索找到使 $\rho \left(R\right)$达到较小的数值最优 ${\alpha }^{\text{*}},{\beta }^{\text{*}}$。

一旦 ${\alpha }^{\text{*}},{\beta }^{\text{*}}$确定，接下来可以考虑外推参数的选取，关于外推参数的选取建议读者参阅文献 [9]，文献中给出了外推法的上界最优参数，其选取方式如下

$\hat{\omega }=\{\begin{array}{ll}\frac{1-{\eta }_n}{{\left(1-{\eta }_n\right)}^2+{\tau }_n^2},\hfill & {\delta }_1\le {\delta }_2,\hfill \\ \frac{2}{2-\left({\eta }_1+{\eta }_n\right)},\hfill & {\delta }_1>{\delta }_2,\hfill \end{array}$(3.11)

其中 ${\eta }_1,{\eta }_2\in ℝ$为R的特征值实部最小值和最大值， ${\tau }_n\in ℝ$为R的特征值虚部最大值， ${\delta }_1=\left({\eta }_n-{\eta }_1\right)\left(1-{\eta }_n\right)$， ${\delta }_1=2{\tau }_n^2$。

由(3.11)可知，选取最优外推参数 $\omega$时，只与矩阵R的特征值的虚部最大值以及实部最小与最大值有关。我们在外推参数 $\omega$的理论最优值附近进行搜索以此得到数值最优的 ${\omega }^{\text{*}}$。

4. 数值实验

我们使用EACSCS迭代求解三个例子，并与CSCS迭代和ACSCS迭代作比较。测试矩阵的阶数 $n=64,128,256,512,1024$，迭代的初始向量 ${\text{x}}^{\left(0\right)}$是零向量，方程(1.1)右端向量b是元素均为1的向量，迭代的停机准则为：

$\epsilon =\frac{{\Vert {\text{r}}^{\left(k\right)}\Vert }_2}{{\Vert {\text{r}}^{\left(0\right)}\Vert }_2}\le {10}^{-7},$

其中 ${\text{r}}^{\left(k\right)}=\text{b}-T{\text{x}}^{\left(k\right)}$是第k步迭代的残差向量。所有数值实验均在Matlab R2018b上进行测试。

以下测试例子均来自文献 [14]。

例子4.1进行Hermitian正定Toeplitz矩阵T的生成函数为 $f\left(x\right)=x^4+1,x\in \left[-\pi ,\pi \right]$，其元素为

$t_k=\{\begin{array}{ll}\frac{4{\pi }^2{\left(-1\right)}^k}{k^2}-\frac{24{\left(-1\right)}^k}{k^2},\hfill & k\ne 0,\hfill \\ \frac{{\pi }^4}{5}+1,\hfill & k=0.\hfill \end{array}$

例子4.2进行Hermitian正定Toeplitz矩阵T的生成函数为 $f\left(x\right)={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\left[{\text{e}}^{ik\left(\log k+x\right)}/k+{\text{e}}^{-ik\left(\log k+x\right)}/k\right]}+4.2$， $x\in \left[-\pi ,\pi \right]$，其元素为

$t_k=\{\begin{array}{ll}\frac{{\text{e}}^{\sqrt{-1}\log k}}{k},\hfill & k>0,\hfill \\ 4.2,\hfill & k=0,\hfill \\ {\bar{t}}_{-k},\hfill & k<0.\hfill \end{array}$

例子4.3进行Hermitian正定Toeplitz矩阵T的生成函数为 $f\left(x\right)=2{\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\left[\left(\sin \left(kx\right)+\cos \left(kx\right)\right)/{\left(1+k\right)}^{1.1}\right]}$， $x\in \left[-\pi ,\pi \right]$，其元素为

$t_k=\{\begin{array}{ll}\frac{1+\sqrt{-1}}{{\left(1+k\right)}^{1.1}},\hfill & k>0,\hfill \\ 2,\hfill & k=0,\hfill \\ {\bar{t}}_{-k},\hfill & k<0.\hfill \end{array}$

下表中只列出了数值最优参数 ${\alpha }^{\text{*}},{\beta }^{\text{*}},{\omega }^{\text{*}}$，其中计算 ${\omega }^{\text{*}}$的过程中使用到了幂迭代，其迭代次数不超过3次。算法的迭代次数记为IT，算法的运行时间记为CPU (单位为秒)。

由表1~3可知，EACSCS方法的迭代次数和运算时间均比其它两种方法少，达到了较好的加速目的。

如上，我们绘制了EACSCS，ACSCS，CSCS的迭代步数与相对残差的变化图，并且标出了停机准则 $\epsilon$线，分别用 $\Delta \Delta \Delta ，\circ \circ \circ ，\ast \ast \ast$和 $---$曲线表示。

由图1可知，EACSCS迭代的相对残差下降速度明显快于其它两种方法，有较好的加速效果。

5. 结束语

基于Toeplitz矩阵有CSCS的事实，本文提出了外推带双参数的CSCS方法，通过理论分析，我们给出了方法中最优外推参数 $\alpha ,\beta$以及外推参数 $\omega$的选取策略。利用数值实验，证明了我们的方法要明显优于ACSCS和CSCS。

参考文献

[1]	Chui, C. and Chan, A. (1982) Application of Approximation Theory Methods to Recursive Digital Filter Design. IEEE Transactions on Acoustics Speech & Signal Processing, 30, 18-24. https://doi.org/10.1109/TASSP.1982.1163842
[2]	Gilliam, D., Martin, C. and Lund, J. (1987) Analytic and Numerical Aspects of the Observation of the Heat Equation. 26th IEEE Conference on Decision & Control, Los Angeles, 9-11 December 1987, 975-976. https://doi.org/10.1109/CDC.1987.272541
[3]	King, R., Ahmadi, M., Gorgui, R., et al. (1989) Digital Filtering in One and Two Dimensions. Plenum Press, New York. https://doi.org/10.1007/978-1-4899-0918-3
[4]	Axelsson, O. (2003) Iterative Solution Methods. Cambridge University Press, New York.
[5]	Cao, Z.H. (1995) Convergence of Two-Stage Iterative Methods for the Solution of Linear Systems. Mathematica Numerica Sinica, 17, 98-109.
[6]	Ruggiero, V. and Galligani, E. (1990) An Iterative Method for Large Sparse Linear Systems on a Vector Computer. Computers& Mathematics with Applications, 20, 25-28. https://doi.org/10.1016/0898-1221(90)90065-R
[7]	Saad, Y. (2003) Iterative Methods for Sparse Linear Systems. 2nd Edition, SIAM, Philadelphia. https://doi.org/10.1137/1.9780898718003
[8]	Golub, G.H. and Loan, A. (2013) Matrix Computations. 4th Edition, Johns Hopkins University Press, Baltimore.
[9]	Yeyios, A. (1984) On the Optimization of an Extrapolation Method. Linear Algebra and Its Applications, 57, 191-203. https://doi.org/10.1016/0024-3795(84)90187-3
[10]	Ng, M.K. (2003) Circulant and Skew-Circulant Splitting Methods for Toeplitz Systems. Journal of Computational and Applied Mathematics, 159, 101-108. https://doi.org/10.1016/S0377-0427(03)00562-4
[11]	Akhondi, N. and Toutounian, F. (2012) Accelerated Circulant and Skew Circulant Splitting Methods for Hermitian Positive Definite Toeplitz Systems. Advances in Numerical Analysis, 2012, Article ID: 973407. https://doi.org/10.1155/2012/973407
[12]	Chan, R. and Ng, M.K. (1996) Conjugate Gradient Methods for Toeplitz Systems. SIAM Review, 38, 427-482. https://doi.org/10.1137/S0036144594276474
[13]	Horn, R.A. and Johnson, C.R. (2013) Matrix Analysis. 2nd Edition, Cambridge University Press, New York.
[14]	Chan, R. and Jin, X. (2007) An Introduction to Iterative Toeplitz Solvers. SIAM, Philadelphia. https://doi.org/10.1137/1.9780898718850
[15]	Bai, Z.Z. and Rozloznik, M. (2015) On the Numerical Behavior of Matrix Splitting Iteration Methods for Solving Linear Systems. SIAM Journal on Numerical Analysis, 53, 1716-1737. https://doi.org/10.1137/140987936
[16]	Liu, Z.Y., Zhou, Y. and Zhang, Y. (2020) On Inexact Alternating Direction Implicit Iteration for Continuous Sylvester Equations. Numerical Linear Algebra with Applications, 27, e2320. https://doi.org/10.1002/nla.2320