求解Toeplitz線性系統(tǒng)的快速CSCS分裂方法

史紅芳

（太原師范學(xué)院數(shù)學(xué)系,山西晉中030619）

求解Toeplitz線性系統(tǒng)的快速CSCS分裂方法

史紅芳

（太原師范學(xué)院數(shù)學(xué)系,山西晉中030619）

基于循環(huán)和反循環(huán)分裂迭代法（CSCS）,提出一種系數(shù)矩陣為Toeplitz矩陣線性系統(tǒng)的新的分裂迭代法,該方法在一定的條件下收斂于Toeplitz線性系統(tǒng)的唯一解.數(shù)值實驗表明新方法是有效的和可行的.

Toeplitz矩陣；分裂；迭代方法；循環(huán)矩陣；反循環(huán)矩陣

0 引言

考慮如下大型稀疏線性系統(tǒng)

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

Toeplitz線性系統(tǒng)被廣泛應(yīng)用于諸多領(lǐng)域,尤其在信號處理和控制理論中,見文獻［1］.

求解線性方程有直接法和迭代法.文獻［2］中介紹了求解Toeplitz線性系統(tǒng)的一些直接法.如Zohar算法,Akaike算法,Bareiss變換法等.

在［3］中,借助于Toeplitz矩陣的特殊結(jié)構(gòu),Ng Michael K給出了一種基于循環(huán)和反循環(huán)的分裂迭代法（CSCS）.在該方法中,收斂因子的上界僅依賴于循環(huán)矩陣和反循環(huán)矩陣的譜.

在文獻［4］的基礎(chǔ)之上,一些學(xué)者對非Hermitian正定線性系統(tǒng)的分裂方式做了改進［5］,該方法明顯優(yōu)于原先的方法.

為了方便表達,這里給出一些簡單的記號.通常情況下,用Cn×n表示n×n復(fù)矩陣的集合,Cn表示n維復(fù)向量空間.X＊代表矩陣或向量X的共軛轉(zhuǎn)置.對于復(fù)數(shù)x,Re（x）和Im（x）分別表示x的實部和虛部.ρ（A）表示矩陣A的譜半徑.circ（a0,a1,…,an－1）表示以a0,a1,…,an－1為第一行元素的循環(huán)矩陣,icirc（a0,a1,…,an－1）表示以a0,a1,…,an－1為第一行元素的反循環(huán)矩陣.

1 預(yù)備知識

定義1（［2］）一個n×n矩陣A稱為是一個Toeplitz矩陣,如果其滿足

ai,j＝ai－j,A的對角線上的元素相同且平行于主對角線的各對角線上的元素也彼此相等.兩個n階Toeplitz矩陣相加或數(shù)乘Toeplitz矩陣,其結(jié)果仍是Toeplitz矩陣.

定義2（［2］）形如

的n階方陣稱為r－循環(huán)矩陣.特別地,當(dāng)r＝1時,稱之為循環(huán)矩陣,

當(dāng)r＝－1時,稱之為斜循環(huán)矩陣（或反循環(huán)矩陣）.

循環(huán)矩陣可以被離散傅立葉矩陣

對角化,反循環(huán)矩陣可以被尺度傅里葉矩陣對角化［6］.

定理1C為形如（3）中r＝1時的循環(huán)矩陣,且

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

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

Toeplitz矩陣A的循環(huán)反循環(huán)分裂為A＝C＋S：

這里C是一個循環(huán)矩陣,S為反循環(huán)矩陣.

CSCS迭代法給定一個初始值x（0）,對于k＝0,1,2,…直到x（k）收斂,計算

這里α是一個正的常數(shù).

理論分析表明,如果C和S都是正定的,那么CSCS迭代法收斂于線性系統(tǒng)（1）的唯一解.

本文其余部分安排如下.第二節(jié)介紹新的分裂迭代法,第三節(jié)討論新算法的收斂性,最后,通過具體的數(shù)值例子證明它的有效性.

2 新的分裂迭代法

借助于線性系統(tǒng)（1）系數(shù)矩陣A∈Cn×n的特殊結(jié)構(gòu),在本節(jié)中我們介紹一種新的迭代算法.

3 收斂性分析

本節(jié)中,我們討論迭代矩陣的譜半徑性質(zhì),并分析前面章節(jié)中算法1的收斂性.

4 數(shù)值實驗

在上一節(jié)中,我們在理論上證明了新算法的收斂性,本節(jié)通過具體的數(shù)值例子來證明該算法的收斂性,同時從譜半徑ρ、迭代次數(shù)（IT）和運行時間（CPU,單位s）這三個維度上與原來的CSCS方法做對比.下面的測試中,在MATLAB上執(zhí)行且從零向量開始,迭代取Toeplitz方程的右端項為一個隨機的生成向量,迭代誤差ε＝10－7,CSCS迭代的最優(yōu)參數(shù)［3］如下：

這里γmin和γmax分別為矩陣C和S的特征值的實部的上界和下界,βmin和βmax分別為矩陣C和S的特征值虛部的絕對值的上界和下界.

例1 考慮線性系統(tǒng)（1）,矩陣A由以下生成函數(shù)給出：

aj＝（1＋｜j｜）－1,j≥0,aj＝i（1＋｜j｜）－1,j＜0.并設(shè)D＝d1＊diag（A）,這里取d1＝2.8.數(shù)值實驗結(jié)果見表1.

表1 從ρ,IT和CPU這三個維度上比較算法1與CSCS方法

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

1）在譜半徑和迭代次數(shù)上沒有原來的方法好,但是,隨著矩陣維數(shù)的逐漸增大,這種差異逐漸減少.

2）在程序運行時間上占明顯的優(yōu)勢,并且隨著矩陣維數(shù)的逐漸增大,這種差異更大.

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

［2］徐 仲,張凱院,陸 全.Toeplitz矩陣類的快速算法［M］.西安：西北工業(yè)大學(xué)出版社,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］.數(shù)學(xué)研究與評論,1988,8（4）：499－504

［10］金小慶.Toeplitz系統(tǒng)預(yù)處理方法［M］.北京：高等教育出版社,2013：60－64

［11］徐成賢,徐宗本.矩陣分析［M］.西安：西北工業(yè)大學(xué)出版社,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－）,女,山西大同人,碩士,主要從事計算數(shù)學(xué)研究.