1. 引言
本文考虑用迭代法求解线性方程组
(1.1)
其中
,
是Hermitian正定Toeplitz矩阵。
在信号处理和控制论 [1] [2] [3] 等许多应用中经常遇到这类Toeplitz线性方程组。关于这类线性方程组的解法,主要分为直接法和迭代法两大类 [4] [5] [6] [7]。由于直接法通常存在数值不稳定的缺点 [8],这使得迭代法更加受到人们的关注。
设系数矩阵
,若M非奇异,则可推导出如下求解线性方程组(1.1)的一个迭代序列
(1.2)
其中
为迭代矩阵。
对于非奇异线性方程组(1.1),迭代(1.2)收敛当且仅当
其中
是矩阵G的谱集,
是取最大元素。
对迭代(1.2),常用的加速技巧是外推法 [9],其迭代格式为
(1.3)
其中
,I是n阶单位矩阵。在(1.3)中可以看到,若
,则(1.3)就退化成了(1.2)的迭代方法。
对于任意Toeplitz矩阵
皆有以下分裂
(1.4)
其中
显然,
是一个Hermitian循环矩阵,
是一个Hermitian反循环矩阵,分裂(1.4)为
的一个CSCS。
基于CSCS(1.4),Ng提出了如下的CSCS [10]
(1.5)
其中
是一个给定的正常数。作者还证明了对于任意正定Toeplitz线性方程组CSCS迭代(1.5)都收敛。此外,作者还给出了CSCS迭代收缩因子的上界,它仅依赖于C和S的最大特征值与最小特征值。2012年Akhondi等人在CSCS迭代的基础上提出了双参数的加速版本,简称ACSCS [11] 迭代,其格式为
(1.6)
(1.6)可写成如下的单步迭代
(1.7)
其中
,
。
ACSCS迭代的计算主要是循环矩阵和反循环矩阵与向量的乘积,这可以使用快速Fourier变换 [12] (FFT)实现,其原理是循环矩阵利用Fourier矩阵进行对角化,反循环矩阵利用Fourier矩阵与一个对角矩阵的乘积实现对角化,
其中F是Fourier矩阵,
是对角矩阵,其主对角的元素为
,
为酉矩阵,则有
(1.8)
其中
和
都是对角矩阵,对角元分别为循环矩阵C和反循环矩阵S的特征值,并且循环矩阵与反循环矩阵的特征值只需一次FFT就可以精确算出来。
2. 预备知识
接下来给出文中用到的基本定义及引理。
定义2.1 [13] 若矩阵
满足
则称
为Toeplitz矩阵,若还满足
,则称
为Hermitian Toeplitz矩阵。
定义2.2 [14] 设
表示定义在区间
内所有以
为周期的连续实值函数,对所有
,若
为
的Fourier系数,则称
为Toeplitz矩阵
的生成函数。
定义2.3 [14] 若
是Toeplitz矩阵,且满足
,则称
为循环矩阵。
定义2.4 [14] 若
是Toeplitz矩阵,且满足
,则称
为反循环矩阵。
定义2.5 [14] 若
满足
则称
为Fourier矩阵。其中
为虚数单位,e为自然对数的底,
为圆周率。
引理2.1 [11] 设
是Hermitian正定Toeplitz矩阵,
为(1.4)所定义的矩阵,只要n足够大,则
和
的特征值均是正实的。
3. 外推CSCS迭代方法
为了进一步加速ACSCS迭代(1.7),我们提出了以下求解线性方程组(1.1)的迭代
(3.1)
我们称(3.1)为外推循环与反循环分裂迭代方法,简称EACSCS,其中
是给定的正常数。由(1.8)可知,循环矩阵和反循环矩阵与向量乘积可以利用快速Fourier变换实现,故EACSCS每次迭代的计算量为
。
迭代(3.1)可以理解为直接分裂迭代,主要是便于收敛性分析,但从实际计算效果来看,该迭代不如下面的基于残差校正的迭代 [15]
(3.2)
接下来我们分析迭代(3.1)的收敛性。在不引起歧义的情况下,我们将矩阵维数的下标省略。设T是一个Hermitian正定Toeplitz矩阵,由引理2.1可知C和S的特征值均是正实的,分别记为
,
。
下面我们讨论
的选取,为此先引入下面引理。
引理3.1 [16] 设T是一个Hermitian正定Toeplitz矩阵,R为(1.7)中所定义的迭代矩阵,则有
(3.3)
引理3.2设T是一个Hermitian正定Toeplitz矩阵,则有
(3.4)
(3.5)
证明 现在定义
可得
故
单调递减,
单调递增,所以
的最大值为
,
的最大值
,即(3.4)得证,同理可证得(3.5)。
定理3.2设T是一个Hermitian正定Toeplitz矩阵,若
取值为
(3.6)
(3.7)
则
达到最小,其值为
(3.8)
其中
,
,
,
,
,
。
证明 有引理3.2可知,存在
及
有(3.4),(3.4),为了求得
使得(3.3)中
达到最小,那么需要
让(3.4),(3.5),同时达到最小,即
(3.9)
利用
,则(3.9)可化简为
(3.10)
经过简单计算就可得出(3.6)和(3.7)。将
代入
得
虽然通过定理3.2可以找到
使得收缩上界达到最小,但不是谱半径
达到最小的参数,数值实验表明在
的附近可以搜索找到使
达到较小的数值最优
。
一旦
确定,接下来可以考虑外推参数的选取,关于外推参数的选取建议读者参阅文献 [9],文献中给出了外推法的上界最优参数,其选取方式如下
(3.11)
其中
为R的特征值实部最小值和最大值,
为R的特征值虚部最大值,
,
。
由(3.11)可知,选取最优外推参数
时,只与矩阵R的特征值的虚部最大值以及实部最小与最大值有关。我们在外推参数
的理论最优值附近进行搜索以此得到数值最优的
。
4. 数值实验
我们使用EACSCS迭代求解三个例子,并与CSCS迭代和ACSCS迭代作比较。测试矩阵的阶数
,迭代的初始向量
是零向量,方程(1.1)右端向量b是元素均为1的向量,迭代的停机准则为:
其中
是第k步迭代的残差向量。所有数值实验均在Matlab R2018b上进行测试。
以下测试例子均来自文献 [14]。
例子4.1进行Hermitian正定Toeplitz矩阵T的生成函数为
,其元素为
例子4.2进行Hermitian正定Toeplitz矩阵T的生成函数为
,
,其元素为
例子4.3进行Hermitian正定Toeplitz矩阵T的生成函数为
,
,其元素为
下表中只列出了数值最优参数
,其中计算
的过程中使用到了幂迭代,其迭代次数不超过3次。算法的迭代次数记为IT,算法的运行时间记为CPU (单位为秒)。
![](Images/Table_Tmp.jpg)
Table 1. Numerical results of example 4.1
表1. 例子4.1的数值结果
![](Images/Table_Tmp.jpg)
Table 2. Numerical results of example 4.2
表2. 例子4.2的数值结果
![](Images/Table_Tmp.jpg)
Table 3. Numerical results of example 4.3
表3. 例子4.3的数值结果
由表1~3可知,EACSCS方法的迭代次数和运算时间均比其它两种方法少,达到了较好的加速目的。
如上,我们绘制了EACSCS,ACSCS,CSCS的迭代步数与相对残差的变化图,并且标出了停机准则
线,分别用
和
曲线表示。
由图1可知,EACSCS迭代的相对残差下降速度明显快于其它两种方法,有较好的加速效果。
![](//html.hanspub.org/file/69-2622143x155_hanspub.png?20220331080816612)
![](//html.hanspub.org/file/69-2622143x156_hanspub.png?20220331080816612)
Figure 1. When n = 1024, the number of iteration steps and relative residual changes of the three iterative methods in Example 4.1~4.3
图1. 当n = 1024时,例4.1~4.3中三种迭代方法的迭代步数与相对残差变化图
5. 结束语
基于Toeplitz矩阵有CSCS的事实,本文提出了外推带双参数的CSCS方法,通过理论分析,我们给出了方法中最优外推参数
以及外推参数
的选取策略。利用数值实验,证明了我们的方法要明显优于ACSCS和CSCS。