史红芳

（太原师范学院数学系,山西晋中030619）

求解Toeplitz线性系统的快速CSCS分裂方法

史红芳

（太原师范学院数学系,山西晋中030619）

基于循环和反循环分裂迭代法（CSCS）,提出一种系数矩阵为Toeplitz矩阵线性系统的新的分裂迭代法,该方法在一定的条件下收敛于Toeplitz线性系统的唯一解.数值实验表明新方法是有效的和可行的.

Toeplitz矩阵；分裂；迭代方法；循环矩阵；反循环矩阵

0 引言

考虑如下大型稀疏线性系统

式中,A∈Cn×n是一个Toeplitz矩阵,且b,x∈Cn.

Toeplitz线性系统被广泛应用于诸多领域,尤其在信号处理和控制理论中,见文献［1］.

求解线性方程有直接法和迭代法.文献［2］中介绍了求解Toeplitz线性系统的一些直接法.如Zohar算法,Akaike算法,Bareiss变换法等.

在［3］中,借助于Toeplitz矩阵的特殊结构,Ng Michael K给出了一种基于循环和反循环的分裂迭代法（CSCS）.在该方法中,收敛因子的上界仅依赖于循环矩阵和反循环矩阵的谱.

在文献［4］的基础之上,一些学者对非Hermitian正定线性系统的分裂方式做了改进［5］,该方法明显优于原先的方法.

为了方便表达,这里给出一些简单的记号.通常情况下,用Cn×n表示n×n复矩阵的集合,Cn表示n维复向量空间.X＊代表矩阵或向量X的共轭转置.对于复数x,Re（x）和Im（x）分别表示x的实部和虚部.ρ（A）表示矩阵A的谱半径.circ（a0,a1,…,an－1）表示以a0,a1,…,an－1为第一行元素的循环矩阵,icirc（a0,a1,…,an－1）表示以a0,a1,…,an－1为第一行元素的反循环矩阵.

1 预备知识

定义1（［2］）一个n×n矩阵A称为是一个Toeplitz矩阵,如果其满足

ai,j＝ai－j,A的对角线上的元素相同且平行于主对角线的各对角线上的元素也彼此相等.两个n阶Toeplitz矩阵相加或数乘Toeplitz矩阵,其结果仍是Toeplitz矩阵.

定义2（［2］）形如

的n阶方阵称为r－循环矩阵.特别地,当r＝1时,称之为循环矩阵,

当r＝－1时,称之为斜循环矩阵（或反循环矩阵）.

循环矩阵可以被离散傅立叶矩阵

对角化,反循环矩阵可以被尺度傅里叶矩阵对角化［6］.

定理1C为形如（3）中r＝1时的循环矩阵,且

那么C的特征值为f（ωk）,k＝0,1,…,n－1,其中ωk为方程xn－1＝0,

0＜k＜n的解,并且满足

Toeplitz矩阵A的循环反循环分裂为A＝C＋S：

这里C是一个循环矩阵,S为反循环矩阵.

CSCS迭代法给定一个初始值x（0）,对于k＝0,1,2,…直到x（k）收敛,计算

这里α是一个正的常数.

理论分析表明,如果C和S都是正定的,那么CSCS迭代法收敛于线性系统（1）的唯一解.

本文其余部分安排如下.第二节介绍新的分裂迭代法,第三节讨论新算法的收敛性,最后,通过具体的数值例子证明它的有效性.

2 新的分裂迭代法

借助于线性系统（1）系数矩阵A∈Cn×n的特殊结构,在本节中我们介绍一种新的迭代算法.

3 收敛性分析

本节中,我们讨论迭代矩阵的谱半径性质,并分析前面章节中算法1的收敛性.

4 数值实验

在上一节中,我们在理论上证明了新算法的收敛性,本节通过具体的数值例子来证明该算法的收敛性,同时从谱半径ρ、迭代次数（IT）和运行时间（CPU,单位s）这三个维度上与原来的CSCS方法做对比.下面的测试中,在MATLAB上执行且从零向量开始,迭代取Toeplitz方程的右端项为一个随机的生成向量,迭代误差ε＝10－7,CSCS迭代的最优参数［3］如下：

这里γmin和γmax分别为矩阵C和S的特征值的实部的上界和下界,βmin和βmax分别为矩阵C和S的特征值虚部的绝对值的上界和下界.

例1 考虑线性系统（1）,矩阵A由以下生成函数给出：

aj＝（1＋｜j｜）－1,j≥0,aj＝i（1＋｜j｜）－1,j＜0.并设D＝d1＊diag（A）,这里取d1＝2.8.数值实验结果见表1.

表1 从ρ,IT和CPU这三个维度上比较算法1与CSCS方法

由表1,我们可以看出,与CSCS迭代方法相比,新的分裂迭代算法

1）在谱半径和迭代次数上没有原来的方法好,但是,随着矩阵维数的逐渐增大,这种差异逐渐减少.

2）在程序运行时间上占明显的优势,并且随着矩阵维数的逐渐增大,这种差异更大.

［1］CHAN R H,NG M K.Conjugate Gradient Methods for Toeplitz Systems［J］.Siam Review,1996,38（3）：427－482

［2］徐 仲,张凯院,陆 全.Toeplitz矩阵类的快速算法［M］.西安：西北工业大学出版社,1999：29－37

［3］NG MK.Circulant and Skew－circulant Splitting Methods for Toeplitz Systems［J］.Journal of Computational and Applied Mathematics,2003,159（1）：101－108

［4］BAI Z Z,GOLUB G H,Ng M K.Hermitian and Skew－Hermitian Splitting Methods for Non Positive Definite Linear Systems［J］.Siam J Matrix Anal Appl,2001,24（3）：603－626

［5］WANG C L,WEN R P,BAI Y H.A New Splitting and Preconditioner for Iteratively Solving Non－Hermitian Positive Definite Systems［J］.Comput.Math.Appl,2013,65：1047－1058

［6］P J.Davis.Circulant Matrices［M］.New York：Wiley,1979

［7］ZHANG F Z.Matrix Theory［M］.NewYork：Springer,2011：138－140

［8］Ng M K.Iterative Methods for Toeplitz Systems［M］.New York：Oxford University Press,2004

［9］夏长富.矩阵正定性的进一步推广［J］.数学研究与评论,1988,8（4）：499－504

［10］金小庆.Toeplitz系统预处理方法［M］.北京：高等教育出版社,2013：60－64

［11］徐成贤,徐宗本.矩阵分析［M］.西安：西北工业大学出版社,1991

Accelerated Circulant and Skew－Circulant Splitting Methods for Toeplitz Systems

SHI Hongfang
（Department of Mathematics,Taiyuan Normal University,Jinzhong 030619,China）

A new splitting iteration method based on CSCS for solving a linear system with coefficient matrix being Toeplitz matrix is proposed in this paper.The new method converges under reasonable conditions to the unique solution of the Toeplitz linear system.Numerical experiments are used to illustrate the effectiveness and feasibility of our new method.

Toeplitz matrix；splitting；iterative method；circulant matrix；skew－circulant matrix

1672－2027（2016）04－0004－05

O241

A

2016－05－27

史红芳（1990－）,女,山西大同人,硕士,主要从事计算数学研究.