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

李 喆，尹偉石，楊 華

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

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

李 喆，尹偉石，楊 華

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

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

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

1 預(yù)備知識(shí)

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

命題1 設(shè)A∈?n×n，若對(duì)某個(gè)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線性無(wú)關(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ù).對(duì)于系數(shù)陣為區(qū)間矩陣的線性方程組，如果Verifylss函數(shù)輸出一個(gè)區(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ū)間計(jì)算，以此驗(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滿足下列兩個(gè)條件:

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

注1 設(shè)f:?m→?n(m＜n)，A∈?m×n為隨機(jī)滿秩矩陣.可通過(guò)驗(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)用中，采取計(jì)算f(X)做補(bǔ)充驗(yàn)證.若f(X)是一個(gè)非常小的包含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.

問(wèn)題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ù)擾動(dòng)區(qū)間向量W=(W1，W2，…，Wl)T∈ ?l，使得必存在實(shí)擾動(dòng)∈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í)非奇異，假設(shè)為F(w)=0的近似解，計(jì)算在w=附近F(w)=0的可信解.

求解線性方程組(7)，可計(jì)算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è)計(jì)算法如下.

算法1

輸出:

步驟:

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

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

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

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

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

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

給定對(duì)稱矩陣

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

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

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

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

［1］ 李喆，周蕊.結(jié)構(gòu)方陣秩虧為1的可信性驗(yàn)證［J］.吉林大學(xué)學(xué)報(bào):理學(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)格證明.對(duì)于給定的問(wèn)題，利用可信性驗(yàn)證方法可以得出該問(wèn)題的一個(gè)近似解及相應(yīng)的誤差界，使得在近似解的誤差界范圍內(nèi)必存在一個(gè)精確解.令φ:?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)證是指對(duì)于給定的矩陣，計(jì)算該矩陣中每個(gè)位置元素相應(yīng)的區(qū)間擾動(dòng)，以保證擾動(dòng)后的區(qū)間矩陣中包含一秩虧為k的矩陣.結(jié)構(gòu)方陣秩虧為k的可信性驗(yàn)證是指對(duì)于給定的、具有特殊代數(shù)結(jié)構(gòu)的方陣A(p)，給出算法輸出具有相同代數(shù)結(jié)構(gòu)的區(qū)間方陣A(p+W)，其每個(gè)位置的元素為矩陣A(p)相應(yīng)位置元素的很小區(qū)間攝動(dòng)，使得A(p+W)中包含一個(gè)具有相同代數(shù)結(jié)構(gòu)且秩虧為k的矩陣A(p+^w).結(jié)構(gòu)矩陣秩虧為k的可信性驗(yàn)證可應(yīng)用于多項(xiàng)式因式分解的可信性計(jì)算，而多項(xiàng)式因式分解的可信計(jì)算是符號(hào)與數(shù)值混合計(jì)算中的基本問(wèn)題.本文利用邊界矩陣?yán)碚摚瑢Ⅱ?yàn)證結(jié)構(gòu)矩陣秩虧為k的問(wèn)題轉(zhuǎn)化為計(jì)算一個(gè)由k×k個(gè)非線性方程構(gòu)成的非線性方程組可信解.

2013-09-09.

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

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