廣義絕對值方程的區(qū)間算法

王愛祥

（1.中國礦業(yè)大學(xué) 數(shù)學(xué)學(xué)院，江蘇 徐州 221008；2.常州工學(xué)院 航空與機(jī)械工程學(xué)院，江蘇 常州 213032）

0 引言

考慮如下形式的廣義絕對值方程：

絕對值方程（1）和（2）引起了許多學(xué)者的關(guān)注.不僅因?yàn)槠浜唵魏吞厥獾慕Y(jié)構(gòu)，還因?yàn)樗梢宰鳛檠芯烤€性規(guī)劃、二次規(guī)劃、雙矩陣對策等優(yōu)化問題的統(tǒng)一研究框架[1].近年來，絕對值方程（1）和（2）的研究集中在解的存在條件和求解算法上.在理論方面，研究了絕對值方程和線性互補(bǔ)問題的等價(jià)性[2]、可解性[3，4]、求解的復(fù)雜性[5]等；在算法方面，當(dāng)絕對值方程存在唯一解時(shí)，提出了求解的逐次線性規(guī)劃法[6]、牛頓型迭代法[7]、投影梯度法[8]和智能算法[9]等.

然而，仍有一些問題值得考慮.調(diào)查發(fā)現(xiàn)，目前較少有文獻(xiàn)研究算法的近似解與絕對值方程的精確解之間的誤差界.而兩者在實(shí)際計(jì)算中是否接近是很重要的.可以看下面的例子.

例1考慮廣義絕對值方程

容易檢驗(yàn)，x*=（1，1）T是這個(gè)方程的準(zhǔn)確解.但對于近似解，常用的檢驗(yàn)標(biāo)準(zhǔn)是范數(shù)充分小.但若=（2，0）T，雖有=2.236×10-11，卻并不能說明近似解和準(zhǔn)確解x*充分接近.基于此，本研究的目的是建立數(shù)值穩(wěn)定的求解廣義絕對值方程的算法.

首先簡要列舉需要用到區(qū)間數(shù)學(xué)的基本概念和符號.對于任意區(qū)間定義中點(diǎn)、寬度和絕對值分別為

類似地，n×n的區(qū)間矩陣的中點(diǎn)、寬度和范數(shù)分別表示為

引理1[10]設(shè)A是一個(gè)n×n區(qū)間矩陣，X是n維區(qū)間向量，則.

定義1如果函數(shù)f（x）和區(qū)間函數(shù)F（x）滿足F（x）=f（x），f（x）F（x），?xX則稱F（x）為的f（x）區(qū)間擴(kuò)張.

有關(guān)區(qū)間數(shù)學(xué)的其他概念和內(nèi)容可參見文獻(xiàn)[10].

1 初始含解區(qū)間

在建立區(qū)間算法之前，首先構(gòu)造含有廣義絕對值方程準(zhǔn)確解的區(qū)間.通篇用In表示n階單位矩陣.對于矩陣A，用|A|表示矩陣A的所有元素取絕對值.λ（A）、ρ（A）和‖A‖分別表示矩陣A的特征值、譜半徑和范數(shù).

引理211]對于矩陣ARn×n，則ρ（A）＜‖A‖.

引理3[11]如果矩陣ARn×n滿足ρ（A）＜1，那么

引理4[4]如果矩陣A是非奇異的且ρ（|A-1B|）＜1，那么對于任意bRn，廣義絕對值方程（1）有唯一解.

定理1如果矩陣A是非奇異的且‖A-1B‖＜1，那么對于任意bRn，廣義絕對值方程（1）有唯一解.

證明由引理2知，矩陣A是非奇異的且‖A-1B‖＜1，就有ρ（|A-1B|）＜‖|A-1B|‖=‖A-1B‖＜1.

定理2如果矩陣A是非奇異的且‖A-1B‖＜1.記x*是廣義絕對值方程的唯一解，則

式中：⊿=（In-|A-1B|）-1|A-1B||A-1b|.

證明廣義絕對值方程等價(jià)于x-A-1b=A-1B|x|.進(jìn)一步，可以得到|x-A-1b|≤|A-1B||x|≤|A-1b||x-A-1b|+|A-1B||A-1b|，于是，（In-|A-1B|）|x-A-1b|≤|A-1B||A-1b|.由引理1得ρ（|A-1B|）＜1.那么，In-|A-1B|是非奇異矩陣.由引理2得到，（In-|A-1B|）-1=≥0.從而有：|x-A-1b|≤（In-|A-1B|）-1|A-1B||A-1b|.

記⊿=（In-|A-1B|）-1|A-1B||A-1b|，則|x-A-1b|≤⊿，即.證畢.

2 區(qū)間算法及其收斂性分析

定義映射f：D?Rn→Rn，

顯然，f（x）的零點(diǎn)恰是廣義絕對值方程（1）的根.f（x）的自然區(qū)間擴(kuò)張為

假設(shè)矩陣A可逆，定義映射g（x）=x-A-1f（x）=A-1B|x|+A-1b.顯然，f（x）的零點(diǎn)是g（x）的不動點(diǎn).對于區(qū)間向量X，g（x）的中值型區(qū)間擴(kuò)張為G（X）=g[m（X）]+G（′X）[X-m（X）]，G（′X）=A-1BD（X）.

定理3設(shè)x*為廣義絕對值方程（1）的解，且x*X，那么x*G（X）.

證明對于任意向量xX，由泰勒公式得g（x）=g m（X）[ ]+A-1B·?|ξ|（ξ-x）g m（X）[ ]+A-1B·D（X）[X-m（X）]=G（X），于是，（fx*）=0且x*=g（x*）.即x*=g（x*）G（X）.證畢.

推論1若X∩G（X）=?，則廣義絕對值方程（1）在區(qū)間X中不存在解.

證明由定理1易知，若廣義絕對值方程在X中存在解x*，則x*X∩G（X），與條件矛盾.證畢.

推論2若G（X）?X，則廣義絕對值方程（1）在區(qū)間X中至少存在一個(gè)解.

證明由定理1知，G（X）?X說明g（x）把區(qū)間X映射到X本身.又g（x）是連續(xù)映射且X是閉凸集，由Brouwer不動點(diǎn)定理知，g（x）在區(qū)間X中至少有一個(gè)不動點(diǎn)，即f（x）在X中至少有一個(gè)零點(diǎn).證畢.由此，可以構(gòu)造區(qū)間迭代算法.

算法1

步驟1：由（3）式計(jì)算初始含解的區(qū)間，記為X（0）.設(shè)定ε＞0.

步驟3：如果w（X（k+1））≤ε，輸出m（X（k+1））.否則，轉(zhuǎn)步驟2.

定理4若矩陣A是非奇異的且‖A-1B‖＜1，則算法1產(chǎn)生的迭代序列{X（k）}滿足：

證明由定理2知，f（x）在X上有唯一解，設(shè)其為x*.

1）由定理1知，x*X（0）∩G（X（0）），即x*X（1）.假設(shè)x*X（k），則x*G（X（k）），故x*X（k+1）.由歸納法，對一切的正整數(shù)k，成立x*X（k），且X（k）?X（k-1）?…?X（0）.于是算法得到區(qū)間向量序列{X（k）}，且w（X（k+1））≤m（X（k））.根據(jù)D（X）的定義知：‖D（X）‖=1.記q=‖A-1BD（X）‖，則q≤‖A-1B‖‖D（X）‖＜1.由引理2知，w（X（k+1））=w{G（′X）[X-m（X）]}≤‖A-1BD（X）‖w（X（k））=q·w（X（k））.

于是，w（X（k+1））≤q·w（X（k））≤q（k+1）·w（X（0））.從而

2）根據(jù)算法1，易知X（k+1）?X（k）且‖m（X（k+1））-m（X（k））.于是，任取p＞k（p是正整數(shù)），有

定理4不僅證明了算法的收斂性，還給出了每步迭代中近似解和準(zhǔn)確解的誤差關(guān)系.此外也說明了該區(qū)間算法收斂速度至少是線性的.為減少計(jì)算量，提高計(jì)算效率，利用點(diǎn)迭代來代替區(qū)間迭代.

定理5設(shè)算法1產(chǎn)生的迭代序列為{X（k）}.以任意x0X（0）為初值，點(diǎn)迭代xk+1=A-1B|xk|+A-1b（k=0，1，2，…）生成序列{xk}.該點(diǎn)序列{xk}收斂到廣義絕對值方程（1）的解x*，且|xk-x*|≤βkw（X（0）），其中q=‖A-1B‖.

證明用歸納法證明.當(dāng)任意點(diǎn)x0X（0），有xkXk，k=0，1，2，….當(dāng)k=0時(shí)，成立.

假設(shè)k=m（m≥0），xmXm，有xm+1=A-1B|xm|+A-1bG（X（m））.也就是：xm+1G（X（m））∩X（m）=X（m+1）.由定理3知，由于xk，x*X（k），因此，|xk-x*|≤w（X（k））≤βkw（X（0）），其中q=‖A-1B‖.故當(dāng)k→∞時(shí)，xk→x*.證畢.

定理5說明了雖然用點(diǎn)迭代代替區(qū)間迭代，仍然可以同步顯示近似解和準(zhǔn)確解之間的誤差.下面總結(jié)點(diǎn)迭代的算法.

算法2

步驟1：由（3）式計(jì)算初始含解的區(qū)間X.取中點(diǎn)x0=m（X）.設(shè)定ε＞0.

步驟2：計(jì)算點(diǎn)迭代：xk+1=A-1B|xk|+A-1b，k=0，1，2，….

步驟3：如果‖Axk+1-B|xk+1|-b‖≤ε，輸出xk+1.否則，轉(zhuǎn)步驟2.

3 數(shù)值測試

為了測試算法的有效性，進(jìn)行如下的數(shù)值實(shí)驗(yàn).程序利用區(qū)間程序包Intlab5.4編寫，在Matlab平臺上實(shí)現(xiàn).計(jì)算環(huán)境為酷睿i5，2.40 GHz，RAM 16 G.

例2（隨機(jī)測試）考慮絕對值方程Ax-B|x|-b，其中

容易驗(yàn)證，‖A-1B‖=0.3947＜1.利用（3）式計(jì)算，得到含有準(zhǔn)確解的區(qū)間是

例3[7]（線性互補(bǔ)問題）考慮線性互補(bǔ)問題LCP（M，q），其中M=N+μIRn×n，q=-Mz*且：是單位矩陣.

當(dāng)m=3時(shí)，取μ=1，則‖A-1B‖=0.7553＜1，初始含解區(qū)間的最大寬度w（X（0））=57.3492，得到近似解滿足：和

為保證得到初始含解區(qū)間，設(shè)定參數(shù)μ=4，選擇不同維度n.計(jì)算結(jié)果見表1，其中n表示問題維數(shù)，ERR表示算法得到的近似解和準(zhǔn)確解之間誤差的歐氏范數(shù)，T表示算法的CPU時(shí)間，單位為s.

表1 例2的計(jì)算結(jié)果（μ=4）

4 結(jié)論

提出了廣義絕對值方程的一類區(qū)間型算法.首先得到一個(gè)含有準(zhǔn)確解的區(qū)間，然后用區(qū)間迭代的方法去縮小區(qū)間，得到準(zhǔn)確解.由于區(qū)間運(yùn)算的代價(jià)較大，提出用點(diǎn)迭代的方法來代替區(qū)間迭代.算例測試也驗(yàn)證了算法的有效性.但是，初始區(qū)間的運(yùn)算涉及到矩陣求逆運(yùn)算.對于大規(guī)模問題，求逆運(yùn)算代價(jià)較大.如何優(yōu)化初始區(qū)間計(jì)算，值得進(jìn)一步考慮.