王愛祥

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

0 引言

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

絕對值方程（1）和（2）引起了許多學者的關(guān)注.不僅因為其簡單和特殊的結(jié)構(gòu)，還因為它可以作為研究線性規(guī)劃、二次規(guī)劃、雙矩陣對策等優(yōu)化問題的統(tǒng)一研究框架[1].近年來，絕對值方程（1）和（2）的研究集中在解的存在條件和求解算法上.在理論方面，研究了絕對值方程和線性互補問題的等價性[2]、可解性[3，4]、求解的復雜性[5]等；在算法方面，當絕對值方程存在唯一解時，提出了求解的逐次線性規(guī)劃法[6]、牛頓型迭代法[7]、投影梯度法[8]和智能算法[9]等.

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

例1考慮廣義絕對值方程

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

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

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

引理1[10]設A是一個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ū)間擴張.

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

1 初始含解區(qū)間

在建立區(qū)間算法之前，首先構(gòu)造含有廣義絕對值方程準確解的區(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|.

證明廣義絕對值方程等價于x-A-1b=A-1B|x|.進一步，可以得到|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）的零點恰是廣義絕對值方程（1）的根.f（x）的自然區(qū)間擴張為

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

定理3設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中至少存在一個解.

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

算法1

步驟1：由（3）式計算初始含解的區(qū)間，記為X（0）.設定ε＞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上有唯一解，設其為x*.

1）由定理1知，x*X（0）∩G（X（0）），即x*X（1）.假設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不僅證明了算法的收斂性，還給出了每步迭代中近似解和準確解的誤差關(guān)系.此外也說明了該區(qū)間算法收斂速度至少是線性的.為減少計算量，提高計算效率，利用點迭代來代替區(qū)間迭代.

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

證明用歸納法證明.當任意點x0X（0），有xkXk，k=0，1，2，….當k=0時，成立.

假設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‖.故當k→∞時，xk→x*.證畢.

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

算法2

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

步驟2：計算點迭代：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ù)值測試

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

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

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

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

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

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

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

4 結(jié)論

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