結(jié)構(gòu)方陣秩虧為k的可信性驗(yàn)證

李 喆，尹偉石，楊 華

(長春理工大學(xué)理學(xué)院，長春 130022)

結(jié)構(gòu)方陣秩虧為k的可信性驗(yàn)證

李 喆，尹偉石，楊 華

(長春理工大學(xué)理學(xué)院，長春 130022)

利用區(qū)間算法研究結(jié)構(gòu)矩陣秩虧為k的可信性驗(yàn)證.對具有特殊代數(shù)結(jié)構(gòu)的矩陣A(p)，給出了算法輸出具有相同代數(shù)結(jié)構(gòu)的區(qū)間矩陣A(p+W)，其每個位置的元素為矩陣A(p)相應(yīng)位置元素的很小區(qū)間攝動，使得區(qū)間矩陣A(p+W)中包含一個具有相同代數(shù)結(jié)構(gòu)且秩虧為k的矩陣A(p+^w).結(jié)果表明，結(jié)構(gòu)矩陣秩虧為k的可信性驗(yàn)證可以應(yīng)用到多項式因式分解的可信性計算中.

區(qū)間算法;結(jié)構(gòu)方陣;可信性驗(yàn)證;秩

1 預(yù)備知識

設(shè)?表示實(shí)數(shù)集合，? 表示實(shí)數(shù)區(qū)間.Om×n表示m×n零矩陣，In表示n×n單位矩陣.Mi，:和M:，i分別表示矩陣M的第i行和第i列.

命題1 設(shè)A∈?n×n，若對某個B，C∈?n×k，(n+k)×(n+k)矩陣

非奇異，則rank(A)=n-k當(dāng)且僅當(dāng)線性方程組

的解滿足F=Ok×k.

證明:必要性.若 rank(A)=n-k，設(shè) Nullspace(A)=span{b1，b2，…，bk}，則矩陣CT(b1b2… bk)非奇異，且存在唯一的矩陣B，使得CT(b1b2… bk)B=Ik.由于矩陣(1)非奇異，因此，線性方程組(2)的解為

充分性.若F=Ok×k，則AU=On×k，CTU=Ik，故向量U:，1，U:，2，…，U:，k∈NullSpace(A)，且U:，1，U:，2，…，U:，k線性無關(guān).若rank(A)＜n-k，不妨設(shè)Nullspace(A)=span{U:，1，U:，2，…，U:，k，a}，則必存在λ=(λ1，…，λk，λk+1)T∈?k+1，使得

這與矩陣(1)非奇異矛盾.故rank(A)=n-k.

命題2 設(shè)A∈?n×n且rank(A)=n-k.再設(shè)

證明:只需證明

的解為U*=On×k，F(xiàn)*=Ok×k.將方程組

左乘矩陣(b1b2… bk)T，有

由(b1b2… bk)TB非奇異可知F*=Ok×k，故CTU*=Ok×k.進(jìn)一步，由于AU*=On×k，故存在矩陣L，使得

由CT(a1a2… ak)非奇異可知L=Ok×k，即U*=On×k.證畢.

文獻(xiàn)［2］給出了系數(shù)陣為一般稠密矩陣的線性方程組求解的可信性驗(yàn)證方法，該算法已嵌入MATLAB中的INTLAB軟件包，并命名為Verifylss函數(shù).對于系數(shù)陣為區(qū)間矩陣的線性方程組，如果Verifylss函數(shù)輸出一個區(qū)間向量，則該區(qū)間向量包含該區(qū)間線性方程組的所有可能解.

定理1［3］輸入一區(qū)間矩陣A∈ ?n×n及區(qū)間右端列向量b∈ ?n，若Verifylss函數(shù)成功輸出區(qū)間向量X??n，則X滿足條件

Moore［4］給出了非線性方程組解存在性的充分條件.在此基礎(chǔ)上，Krawczyk［5］將牛頓迭代法應(yīng)用于區(qū)間計算，以此驗(yàn)證非線性方程組的解.Rump［6］改善了區(qū)間牛頓迭代法，使其能更好地適用于實(shí)際應(yīng)用.

定理2［6］設(shè)函數(shù)f:?n→?n，其中f=(f1，f2，…，fn)∈.給定初始近似解n，初始區(qū)間X∈?n，且0∈X.若存在區(qū)間矩陣M∈?n×n及實(shí)矩陣R∈?n×n滿足下列兩個條件:

定理3［7-8］設(shè)函數(shù)f:?m→?n構(gòu)成零維多項式系統(tǒng)，其中f=(f1，f2，…，fn)∈C1，m＜n.如果存在非空的Zariski開子集A?Cm×n，使得對每個A∈A，都為方程A·f(x)=0的根，則在概率為1的情況下，為f(x)=0的根.

注1 設(shè)f:?m→?n(m＜n)，A∈?m×n為隨機(jī)滿秩矩陣.可通過驗(yàn)證方程A·f(x)=0的根驗(yàn)證方程f(x)=0的根.若存在區(qū)間X使得其含有A·f(x)=0的根，則在概率1的情況下，X含有f(x)=0的根.在實(shí)際應(yīng)用中，采取計算f(X)做補(bǔ)充驗(yàn)證.若f(X)是一個非常小的包含0的區(qū)間，則在概率1的情況下，X含有f(x)=0的根［8］.

2 算 法

定義1 設(shè)A∈?n×n，給定數(shù)值秩容差ε∈?.若A的奇異值σ1(A)，σ2(A)，…，σn(A)滿足條件則稱A的數(shù)值秩為n-k.

問題1 給定具有某一特殊代數(shù)結(jié)構(gòu)的矩陣A(p)∈?n×n，其中p=(p1，p2，…，pl)T表示結(jié)構(gòu)矩陣的參數(shù).設(shè)矩陣A(p)的數(shù)值秩為n-r.如何確定參數(shù)擾動區(qū)間向量W=(W1，W2，…，Wl)T∈ ?l，使得必存在實(shí)擾動∈W1∈W2，…∈Wl滿足矩陣A(p+)秩虧為k，其中=，…，)T.

由命題1可得:

引理1 設(shè)A(p)∈?n×n為具有某一特殊代數(shù)結(jié)構(gòu)的矩陣，其中p∈?l.設(shè)非線性函數(shù)

本文假設(shè)k2≤l，即假設(shè)非線性方程組F(w)=0為欠定方程組.結(jié)構(gòu)矩陣奇異性的可信性驗(yàn)證依賴于初值=，…)的選取.先用文獻(xiàn)［9］的數(shù)值方法得到優(yōu)化的初值.設(shè)邊界矩陣(6)當(dāng)w=時非奇異，假設(shè)為F(w)=0的近似解，計算在w=附近F(w)=0的可信解.

求解線性方程組(7)，可計算F(w)=0的Jacobi矩陣JF()［10］.設(shè)JF()的數(shù)值秩為r，選取指標(biāo)集i1，i2，…，ir，使得數(shù)值列滿秩，其中表示由矩陣JF()的第i1，i2，…，ir列所構(gòu)成的矩陣.令

令Wit∈ ?且0∈Wit，1≤t≤r.設(shè) R為矩陣 H·JˉF(，…，)的近似逆矩陣.令=+，1≤t≤r.利用MATLAB中Verifylss函數(shù)求解線性方程組(5)，得到區(qū)間矩陣U，使得U?U(++，…).進(jìn)而，利用Verifylss函數(shù)，求解線性方程組(7)，得到區(qū)間矩陣J滿足條件

令R為矩陣JˉF(~w)的近似逆矩陣，若

根據(jù)上述理論，設(shè)計算法如下.

算法1

輸出:

步驟:

①令iter表示迭代次數(shù)，初始iter=1;初始區(qū)間向量∈?且0∈，1≤t≤r;令Wi=0，i≠it，1≤t≤r;選取隨機(jī)矩陣H∈，令R為區(qū)間矩陣H·JˉF(，…)近似逆矩陣;

②計算滿足條件(9)的區(qū)間矩陣J，如果條件(10)成立，轉(zhuǎn)步驟4);否則，令

令iter←iter+1，返回步驟②;

③如果iter=T，則區(qū)間牛頓迭代法不收斂，返回“失敗”，算法終止.

由引理1和定理3易證如下命題.

3 應(yīng)用實(shí)例

給定對稱矩陣

其中p=(0.98，2.01，2.99，4，6，9)T.令tol2=10-12.利用文獻(xiàn)［9］方法可得數(shù)值初值:

1)計算JF(~w)的數(shù)值秩為r=2，選取指標(biāo)值i1=1，i2=2.

2)令W1=［-10-12，10-12］，W2=［-10-12，10-12］，經(jīng)計算條件(10)成立.

3)計算‖F(xiàn)(~w+W)‖＜10-12，則在概率為1的情況下，

［1］ 李喆，周蕊.結(jié)構(gòu)方陣秩虧為1的可信性驗(yàn)證［J］.吉林大學(xué)學(xué)報:理學(xué)版，2013，51(6):1101-1103.(LI Zhe，ZHOU Rui.Certification of Square Structure Matrix with Rank Deficiency One［J］.Journal of Jilin University:Science Edition，2013，51(6):1101-1103.)

［2］ Rump S M.Kleine Fehlerschranken Bei Matrixproblemen［D］.Karlsruhe:University Karlsruhe，1980.

［3］ Rump S M.Verification Methods:Rigorous Results Using Floating-Point Arithmetic［J］.Acta Numerica，2010，19: 287-449.

［4］ Moore R E.A Test for Existence of Solutions to Nonlinear System［J］.SIAM J Numer Anal，1977，14(4):611-615.

［5］ Krawczyk R.Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken［J］.Computing，1969，4:187-201.

［6］ Rump S M.Solving Algebraic Problems with High Accuracy［C］//Proceeding of the Symposium on a New Approach to Scientific Computation.San Diego:Academic Press，1983:51-120.

［7］ Sommese A J，Wampler C WⅡ.The Numerical Solution of Systems of Polynomials Arising in Engineering and Science［M］.Singapore:World Scientific Publishing，2005.

［8］ YANG Zhengfeng，ZHI Lihong，ZHU Yijun.Verfied Error Bounds for Real Solutions of Positive-Dimensional Polynomial Systems［C］//ISSAC’13 Proceedings of the 38th International Symposium on International Symposium on Symbolic and Algebraic Computation.New York:ACM，2013:371-378.

［9］ Golub G H，Van Loan C F.Matrix Computations［M］.3rd ed.Baltimore:Johns Hopkins University Press，1996.

［10］ Spence A，Poulton C.Photonic Band Structure Calculations Using Nonlinear Eigenvalue Techniques［J］.J Comput Phy，2005，204(1):65-81.

(責(zé)任編輯:趙立芹)

Certification of the Square Structure Matrix with Rank Deficiency k

LI Zhe，YIN Weishi，YANG Hua
(College of Science，Changchun University of Science and Technology，Changchun 130022，China)

The authors mainly discussed the certification of the square structure matrix with rank deficiencyk. For a square structure matrix A(p)，we gave an algorithm which outputs an interval square matrix A(p+W) with the same algebraic structure such that A(p+W)contains a structure matrix A(p+^w)with rank deficiencyk，where each element of A(p+W)is a small interval perturbation of the corresponding element of A(p).

interval algorithm;square structure matrix;certification;rank

O241.3

A

1671-5489(2014)03-0465-05

10.13413/j.cnki.jdxblxb.2014.03.11

可信性驗(yàn)證也稱為自驗(yàn)證方法，其研究目標(biāo)是如何將浮點(diǎn)運(yùn)算進(jìn)行嚴(yán)格證明.對于給定的問題，利用可信性驗(yàn)證方法可以得出該問題的一個近似解及相應(yīng)的誤差界，使得在近似解的誤差界范圍內(nèi)必存在一個精確解.令φ:?l?n×n為參數(shù)p的線性矩陣函數(shù)，定義A(p)∶=φ(p)，則∶={A(p):p∈?l} 表示某類具有特殊代數(shù)結(jié)構(gòu)的矩陣.本文推廣文獻(xiàn)［1］結(jié)構(gòu)方陣秩虧為1的可信驗(yàn)證方法，給出了結(jié)構(gòu)方陣秩虧為k的可信性驗(yàn)證方法.矩陣秩虧為k的可信性驗(yàn)證是指對于給定的矩陣，計算該矩陣中每個位置元素相應(yīng)的區(qū)間擾動，以保證擾動后的區(qū)間矩陣中包含一秩虧為k的矩陣.結(jié)構(gòu)方陣秩虧為k的可信性驗(yàn)證是指對于給定的、具有特殊代數(shù)結(jié)構(gòu)的方陣A(p)，給出算法輸出具有相同代數(shù)結(jié)構(gòu)的區(qū)間方陣A(p+W)，其每個位置的元素為矩陣A(p)相應(yīng)位置元素的很小區(qū)間攝動，使得A(p+W)中包含一個具有相同代數(shù)結(jié)構(gòu)且秩虧為k的矩陣A(p+^w).結(jié)構(gòu)矩陣秩虧為k的可信性驗(yàn)證可應(yīng)用于多項式因式分解的可信性計算，而多項式因式分解的可信計算是符號與數(shù)值混合計算中的基本問題.本文利用邊界矩陣?yán)碚?，將?yàn)證結(jié)構(gòu)矩陣秩虧為k的問題轉(zhuǎn)化為計算一個由k×k個非線性方程構(gòu)成的非線性方程組可信解.

2013-09-09.

李 喆(1981—)，女，漢族，博士，講師，從事符號計算及符號數(shù)值混合計算的可信性計算研究，E-mail:zheli200809@ 163.com.通信作者:尹偉石(1980—)，男，漢族，博士，講師，從事數(shù)學(xué)物理反問題的研究，E-mail:yinweishi@foxmail.com.

國家自然科學(xué)基金(批準(zhǔn)號:11171133)和數(shù)學(xué)天元基金(批準(zhǔn)號:11326209).