吳越（安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601）

合流多項式Vandermonde矩陣的塊LU分解①

吳越
（安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601）

將給出多項式基下合流Vandermonde矩陣的塊LU分解，它是基于多項式基下合流Vandermonde矩陣所滿足的位移結(jié)構(gòu)方程這一特殊形式，利用這一特殊形式對多項式合流Vandermonde矩陣進(jìn)行Gauss消元法，從而降低算法的運算量.在降低運算量的基礎(chǔ)上，運用位移結(jié)構(gòu)矩陣Schur補的性質(zhì)來計算此類矩陣的LU分解.

位移結(jié)構(gòu)；合流Vandermonde矩陣；Schur補；LU分解

0　引言

近年來，在工程應(yīng)用及許多實際問題中，如數(shù)值分析、自動控制、數(shù)字信號處理等方面廣泛的涉及到矩陣的計算問題，Vandermonde矩陣作為科學(xué)計算中一類常見的矩陣已受到許多數(shù)學(xué)工作者的關(guān)注，尤其是對以Vandermonde矩陣為系數(shù)的線性系統(tǒng)及其對偶系統(tǒng)的研究取得了很多重要的成果.研究Vandermonde矩陣的LU分解有助于快速計算以Vandermonde矩陣為系數(shù)矩陣的線性方程組［1］.通常情況下，對于一個階矩陣，在采用Gauss消元法時所需的運算量為O（（dn）3），根據(jù)多項式基Q（x）=｛Q0（x），Q1（x），…，Qdn（x）｝下合流Vandermonde矩陣所滿足的位移結(jié)構(gòu)方程這一特殊形式，基于這種特殊形式對位移結(jié)構(gòu)矩陣進(jìn)行Gauss消元法時將運算量降低為O（（dn）2），并在O（（dn）2）運算量的基礎(chǔ)上，借助結(jié)構(gòu)矩陣的Schur補同樣滿足位移結(jié)構(gòu)方程這一性質(zhì)［2］來給出多項式基下合流Vandermonde矩陣的塊LU分解，因此在用這種方法來計算來計算矩陣的LU分解時將會隨著矩陣階數(shù)的增加，大大減少運算量.

1　預(yù)備知識

下面給出矩陣Schur補的定義，

對于n×n階矩陣將其分塊為

定義1［3］：上述分塊矩陣中，如果V11非奇異，則稱在V中的Schur補，則有：

定義2［3］：上述分塊矩陣中，如果V22非奇異，則在W中的Schur補，并記為：

本文中，記A為dr×dr復(fù)矩陣，記g為dr階復(fù)向量

假設(shè)A11是非奇異的，則矩陣A的Schur補 S（A）的定義如下：

本文將用Gauss消元法來解決帶重點的多項式Vandermonde方程組：

其對偶系統(tǒng)

本文的方法是基于（1）所定義的多項式Vandermonde矩陣所滿足的位移結(jié)構(gòu)方程，同樣地，結(jié)構(gòu)矩陣的Schur補也滿足位移結(jié)構(gòu)方程.通常情況下在解決（3），（4）方程組時，采用Gauss消元法要用到O（（dn）3）次算法.本文將會改善這種復(fù)雜程度，得到O（（dn）3），并在此基礎(chǔ)上對其進(jìn)行LU分解.

2　重點多項式Vandermonde矩陣的位移結(jié)構(gòu)方程

Vandermonde矩陣在矩陣應(yīng)用理論中是一種重要的矩陣，它與Toeplitz矩陣，Hankel矩陣以及Cauchy矩陣等之間都有重要聯(lián)系，而其中頗受關(guān)注的就是Vandermonde矩陣位移結(jié)構(gòu)性質(zhì).

引理3［4］：多項式基下的合流Vandermonde矩陣滿足如下方程：

顯然，該位移結(jié)構(gòu)方程是如下Sylvester型位移方程的一種特殊情況：

這里Ω1為下三角矩陣，A1為上三角形，且對角線上的元素都兩兩互不相同，R1為dn×dn階矩陣，對矩陣R1實行dn-1次 Gauss消元法有：

由于矩陣R1滿足位移結(jié)構(gòu)方程，因此可以減少Gauss消元法的運算量，只需要做O（（dn）2）次運算，可以簡化Guass消元法的一個重要原因就是位移結(jié)構(gòu)矩陣的Shur補同樣滿足位移結(jié)構(gòu)方程.

文獻(xiàn)［2］給出了滿足方程（7）中關(guān)于矩陣R1用Gauss消元法對其矩陣進(jìn)行三角分解的算法.

定義4： 如果A是一個dr×dr階矩陣是（r= 1，2，…，n），存在dr維行向量g以及dr維列向量h，使得如下方程成立：

則稱矩陣A是一個r-SCV（結(jié)構(gòu)合流Vandermonde矩陣）矩陣.

將矩陣VQ（x）作如下分塊這里矩陣V11和V22都是方陣，當(dāng)V11可逆時，則由schur補的定義可得：

則

引理5［7］：對于位移結(jié)構(gòu)方程：

DVQ-VQW=GB

若有如下分塊：

假設(shè)v11≠0，則V關(guān)于v11的schur補：V/v11=滿足方程，其中 G2=G21-其中= （w12，w13，…，w1dn）T，θ=（d21，d31，…，ddn1）T，設(shè)v11≠0，則V關(guān)于v11的Schur補，滿足方程：

顯然（5）式中WQ是一個上三角矩陣是塊對角矩陣，因此由上述引理可知矩陣W的schur補滿足同種類型的位移結(jié)構(gòu)方程.

3　合流Vandermonde矩陣的LU分解

針對合流多項式Vandermonde矩陣滿足上述位移方程這一特殊性質(zhì)，下面來計算矩陣W的LU分解，利用其元素的這種特殊性，對矩陣進(jìn)行計算時可以減少很多計算量.對于矩陣W的分解計算可以利用Gauss消去法來進(jìn)行.

定理6：矩陣W是一個dn×dn合流Vandermonde矩陣，其Schur補為Sk（W），k=0：n -1，其中S0（W）=W?［e1，v］n，Sk（W）?［g［k］，h［k］］，k=0：n-2，并且滿足如下遞推關(guān)系：

易得，該遞推公式可以在O（（dn）n）的運算量內(nèi)實現(xiàn)對合流Vandermonde矩陣W的塊LU分解，即W=LU.

［1］Oruc，H.LU factorization of the Vandermonde Matrix and Its Applications［J］.Applie-d mathematics letters，2007，20（9）：982-987.

［2］Gohberg I，Kailath T，Olshevsky V.Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure ［J］.Mathematics of Computation，1995，64（212）：1557-1576.

［3］顧敦和.矩陣LU分解的Schur補表示［J］.南京理工大學(xué)學(xué)報（自然科學(xué)版），984，3：014.

［4］Yang Z H，Hu Y J.Confluent Polynomial Vandermonde-like Matrices：Displacement Structures，Inversion Formulas and Fast Algorithm［J］.Linear algebra and its applications，2004，382：61-82.

The Block LU-factorization of Confluent Polynomial Vandermonde Matrix

WU Yue

（School of Mathematical Science，Anhui University，Hefei 230601，China）

A block LU-factorization for confluent Vandermonde matrices was given based on the displacement structure satisfied by confluent Vandermonde matrices and the fact that the Shcur complement of the structured matrix still satisfies the same displacement equation.

Displacement structure；Confluent Vandermonde；Schur complement；LU-factorization

O151.21

A

1008-1402（2015）06-0824-03

2015-10-08

安徽省自然科學(xué)基金項目（1208085MA02），安徽大學(xué)學(xué)術(shù)創(chuàng)新研究項目（yfc100010）.

吳越（1991-），女，山東臨沂人，碩士研究生，從事矩陣與算子理論、多項式與線性控制系統(tǒng)理論的研究.