长沙理工大学，数学与统计学院，湖南 长沙

收稿日期：2022年2月28日；录用日期：2022年3月23日；发布日期：2022年3月30日

摘要

本文基于Toeplitz矩阵有循环与反循环分裂(CSCS)的事实，提出求解Hermitian正定Toeplitz线性方程组的外推CSCS方法，并给出其最优双参数 $\alpha ,\beta$，以及最优外推参数 $\omega$ 的选取策略。并通过数值实验验证我们方法的有效性。

关键词

外推法，Toeplitz矩阵，循环与反循环分裂，双参数，Hermitian正定矩阵

Extrapolated Circulant and Skew Circulant Splitting Method for Hermitian Positive Definite Toeplitz Systems

Maoli Fu, Zhongyun Liu

School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha Hunan

Received: Feb. 28^th, 2022; accepted: Mar. 23^rd, 2022; published: Mar. 30^th, 2022

ABSTRACT

Based on the fact that a Toeplitz matrix admits a circulant and skew circulant splitting (CSCS), we propose the extrapolated CSCS method to solve Hermitian definite Toeplitz systems and discuss the strategy to select the optimal two parameters $\alpha ,\beta$, and the extrapolated parameter $\omega$. The effectiveness of our method is verified by numerical experiments.

Keywords:Extrapolated Method, Toeplitz Matrices, Circulant and Skew Circulant Splitting, Two Parameters, Hermitian Definite Matrices

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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)$ 达到最小，那么需要 $\widehat{\alpha },\widehat{\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. 例子4.1的数值结果

表2. 例子4.2的数值结果

表3. 例子4.3的数值结果

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

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

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

图1. 当n = 1024时，例4.1~4.3中三种迭代方法的迭代步数与相对残差变化图

5. 结束语

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

文章引用

傅毛里,刘仲云. Hermitian正定Toeplitz线性方程组的外推CSCS方法
Extrapolated Circulant and Skew Circulant Splitting Method for Hermitian Positive Definite Toeplitz Systems[J]. 应用数学进展, 2022, 11(03): 1484-1492. https://doi.org/10.12677/AAM.2022.113162

参考文献