《仿射算法研究綜述》3900字

仿射算法研究綜述目錄TOC\o"1-2"\h\u28804仿射算法研究綜述 1272471仿射算法 1210611.1仿射算法基本概念 1271861.2非仿射算法基本操作 39151.3誤差的傳播 8260202區(qū)間矩陣的仿射運(yùn)算 9327042.1區(qū)間矩陣的基本運(yùn)算 9204032.2仿射形式逆矩陣 9101052.3矩陣的指數(shù)運(yùn)算 121仿射算法1.1仿射算法基本概念（1）區(qū)間的另一種表達(dá)式區(qū)間也可以用“中點(diǎn)和半徑”來表示。假設(shè)存在一個(gè)區(qū)間，由式(2.2)到式(2.4)可以推出區(qū)間記為：(1)令，則區(qū)間可以表示為：（2）仿射算法由上一章可以得知，區(qū)間算法雖然可以求解不確定條件下的邊界解，但由于其局限性，區(qū)間算法可能會(huì)提供一個(gè)太寬的邊界，即求解出的最值點(diǎn)太保守，可能會(huì)包含一些真值永遠(yuǎn)達(dá)不到的區(qū)域。為了克服上述過于保守的問題，對式(1)進(jìn)行改進(jìn)，對每一個(gè)量都分配一個(gè)新的系數(shù)，并且當(dāng)兩個(gè)或者兩個(gè)以上的量同時(shí)出現(xiàn)了不確定性，就會(huì)自動(dòng)地分配同樣的系數(shù)。添加一個(gè)新的噪聲系數(shù)，且，則新的區(qū)間數(shù)可以表示成：(2)這種通過添加新的噪聲系數(shù)的方式即為“仿射方式”，噪聲系數(shù)代表著對于總體不確定量的獨(dú)立組成。繼續(xù)以章節(jié)2.1.3的例子為基礎(chǔ)，區(qū)間值可以用式(1)中的仿射形式表示出來：，由于，存在一定的關(guān)聯(lián)，所以兩個(gè)區(qū)間值具有相同的噪聲符號(hào)，則區(qū)間值的仿射形式可以表示為：，則。通過仿射算法改進(jìn)，消除了區(qū)間算法存在的過度估計(jì)問題。在噪聲模擬等實(shí)際環(huán)境中，可能會(huì)同時(shí)存在大量的變化對原始參數(shù)產(chǎn)生影響。包含各種不確定項(xiàng)的量的一般仿射形式可以表示為：(3.3)每一個(gè)表示一個(gè)不確定的獨(dú)立組成，表示要素的量級。所以我們能很容易地從式(3.3)中得到的上界為，下界為。（3）仿射算法基本操作假設(shè)輸入的仿射形式為：，之間的操作主要可以分為仿射操作和非仿射操作。仿射操作是對輸入的仿射形式進(jìn)行直接操作，得到的結(jié)果不包含二次項(xiàng)的。比如，，和在時(shí)的仿射操作分別可以表示為：(3.4)而非仿射操作就是接下來所要研究的內(nèi)容。1.2非仿射算法基本操作非仿射操作如乘法、除法、倒數(shù)、平方根等運(yùn)算方式會(huì)在結(jié)果中產(chǎn)生二次項(xiàng)的，在計(jì)算過程中需要做的是將新方程轉(zhuǎn)換成線性仿射形式，而轉(zhuǎn)換方式是采取添加新的噪聲系數(shù)來替換其計(jì)算結(jié)果中的二次項(xiàng)。（1）乘法運(yùn)算假設(shè)存在兩個(gè)區(qū)間的仿射形式為：和，則，相乘可以得到：(3.5)由結(jié)果可知，產(chǎn)生了新的二次項(xiàng)，添加一個(gè)新的噪聲符號(hào)來取代新產(chǎn)生的二次項(xiàng)，可以表示為：(3.6)這種方法雖然也能求出所需的結(jié)果的邊界，但也會(huì)引入新的誤差：添加新的噪聲符號(hào)跳過了它與其他符號(hào)的相關(guān)性，會(huì)出現(xiàn)同區(qū)間算法相同的過度估計(jì)的問題，同時(shí)計(jì)算出來的新系數(shù)也會(huì)計(jì)算出最大量級的，同樣無法避免過度估計(jì)的現(xiàn)象。令，則式(3.5)中的可以優(yōu)化為：(3.7)在仿射模型中，由于任何區(qū)間結(jié)果的上界與下界都是關(guān)于中心值對稱的，因此如果十分趨近區(qū)間真實(shí)的上界，到上界的距離遠(yuǎn)遠(yuǎn)小于到下界的距離，從而導(dǎo)致對前一個(gè)點(diǎn)過度估計(jì)，如圖1所示。圖1仿射形式乘法的過度估計(jì)另一個(gè)問題是在計(jì)算過程中添加了一個(gè)新的噪聲符號(hào)。隨著計(jì)算的復(fù)雜程度的增大，噪聲符號(hào)的數(shù)目也會(huì)隨之增加，反之，計(jì)算效率也就會(huì)降低。假設(shè)存在兩個(gè)受兩個(gè)不確定性影響的區(qū)間，其仿射形式可以表示為：和，則他們的乘積可以表示為：(3.8)結(jié)果中的二次項(xiàng)系數(shù)用新的噪聲系數(shù)替代，則，相應(yīng)的上下界區(qū)間是。然而，更精確的分析表明，二次項(xiàng)系數(shù)的確切范圍在，因此，的真值區(qū)間應(yīng)該為。由此可見，仿射近似法的相對精度為：這與圖1中過高估計(jì)的情況相對應(yīng)，得到的標(biāo)稱值更接近真實(shí)的上限，因此在這一側(cè)引入了誤差。（2）除法運(yùn)算除法相對于乘法更為復(fù)雜，它可以轉(zhuǎn)換為一個(gè)區(qū)間乘以另一個(gè)區(qū)間的倒數(shù)的形式：(3.9)為了更好地反求一個(gè)實(shí)際上是非仿射操作的仿射形式，我們借鑒了“極值仿射逼近”的結(jié)論：定理1：設(shè)為區(qū)間上定義的有界二次可微函數(shù)，并且其二階導(dǎo)數(shù)在區(qū)間內(nèi)不變號(hào)。令在區(qū)間內(nèi)是其極值仿射逼近。因此：系數(shù)表示，直線的斜率只與點(diǎn)和有關(guān)在端點(diǎn)范圍內(nèi)，當(dāng)時(shí)，會(huì)出現(xiàn)最大絕對誤差獨(dú)立項(xiàng)表示，最大絕對誤差為由定理1可知，求近似函數(shù)的問題可以轉(zhuǎn)換為求擬合系數(shù)的最優(yōu)解：(10)這就是所謂的“切比雪夫近似”算法。另外一種方法是“最小范圍近似法”，它在計(jì)算區(qū)間倒數(shù)的編碼中與之相似，但更容易。如圖2所示：假設(shè)存在，在最值處的切線和與之斜率相同的穿過另外一個(gè)最值點(diǎn)，組成和(圖2.4中的陰影部分)。虛線代表在區(qū)間范圍內(nèi)的中點(diǎn)。圖2最小范圍近似法注意該區(qū)間內(nèi)不能包含0，對此進(jìn)行分類討論。假設(shè)區(qū)間值全部為正數(shù)，則直線的斜率是在時(shí)的導(dǎo)數(shù)，即。經(jīng)過端點(diǎn)的虛線可以表示為：對上式進(jìn)行求解得：(11)將新的噪聲符號(hào)賦值給新的參數(shù)，結(jié)果函數(shù)表示為：(12)式中表示新的標(biāo)稱值，表示初始噪聲符號(hào)的系數(shù)，用新的符號(hào)和組成式(10)計(jì)算出的新符號(hào)系數(shù)。則仿射除法可以表示為：因此，除法是在乘法的基礎(chǔ)上進(jìn)行計(jì)算的，但是比乘法更復(fù)雜一些，需要先求出區(qū)間的倒數(shù)形式，再將兩者相乘，而這兩個(gè)過程中都會(huì)產(chǎn)生新的噪聲符號(hào)。另一種情況假設(shè)區(qū)間內(nèi)的值全部為負(fù)數(shù)時(shí)，需要進(jìn)行的操作是相同的，這里就不作重復(fù)敘述。（3）指數(shù)運(yùn)算根據(jù)定理1中的“切比雪夫近似算法”來計(jì)算區(qū)間在內(nèi)的指數(shù)算法。即近似求解：(13)如圖3.3所示：同時(shí)經(jīng)過端點(diǎn)和的直線1，在區(qū)間中有且只有一點(diǎn)的切線斜率與直線1斜率相等。圖中陰影部分包含的所有可能值，也就是最小近似范圍。陰影部分中間的虛線：與直線1平行，由此，可以求得虛線的斜率為：圖3.3切比雪夫近似算法求指數(shù)形式兩端點(diǎn)之間的最大誤差出現(xiàn)在圖中所示點(diǎn)，出現(xiàn)了異號(hào)，這一點(diǎn)的值為：同樣，最大誤差的大小被賦予一個(gè)新的噪聲符號(hào)，包括“最壞情況”。參數(shù)表示：最終，對所有線性近似值進(jìn)行篩選，函數(shù)最終可以表示為：(14)表示新的標(biāo)稱值，表示初始噪聲符號(hào)的系數(shù)，表示最大誤差。（4）對數(shù)運(yùn)算用“最小范圍近似法”求在上的區(qū)間的對數(shù)運(yùn)算，比如，估算函，近似參數(shù)為：(15)大多數(shù)單調(diào)函數(shù)都可以用上述兩種近似方法估算。值得注意的是，仿射算法和近似法不適用于周期函數(shù)，如正弦函數(shù)。綜上，仿射操作可以直接產(chǎn)生仿射形式，不會(huì)生成新的二次項(xiàng)；而非仿射操作更為復(fù)雜，會(huì)產(chǎn)生新的二次項(xiàng)，所以需要先將它轉(zhuǎn)變?yōu)榉律湫问?，將輸入的線性組合近似任何非線性函數(shù)，仿射和非仿射操作在精度和效率上都比區(qū)間方法有很大的提高，結(jié)合其他數(shù)值技術(shù)（如區(qū)間分割技術(shù)）有望減少過度估計(jì)產(chǎn)生的誤差。1.3誤差的傳播上面已經(jīng)說過，在非仿射算法中，每次單獨(dú)的操作都會(huì)產(chǎn)生附加的噪聲符號(hào)。在需要做大量乘法的情況下，隨機(jī)變量的數(shù)量會(huì)不斷增長，這在計(jì)算時(shí)間上是非常低效的。這里通過給現(xiàn)有的不確定量分配額外的二次項(xiàng)，可以表示為：(16)這種方法沒有生成新的不確定量，并且限定了的真實(shí)范圍，但是，由于沒有完整的對其進(jìn)行嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)理論公式推導(dǎo)，所以缺乏一定的嚴(yán)謹(jǐn)性，并不能達(dá)到最佳結(jié)果分布。2區(qū)間矩陣的仿射運(yùn)算2.1區(qū)間矩陣的基本運(yùn)算由式(2.6)和(2.7)可以得知，也可以用“中點(diǎn)和半徑”的方法表示為：(17)添加一個(gè)新的系數(shù)給變量進(jìn)行賦值，則區(qū)間矩陣的仿射形式可以表示為：(18)假設(shè)存在兩個(gè)區(qū)間矩陣和，其仿射形式可以表示為：由式(3.4)和(3.7)可以得知，區(qū)間矩陣的基本運(yùn)算可以表示為：(19)遺憾的是，由于切比雪夫法和最小范圍近似法只適用于標(biāo)量的求倒和指數(shù)運(yùn)算，不適用矩陣的相關(guān)運(yùn)算。2.2仿射形式逆矩陣區(qū)間矩陣的逆矩陣可以表示為：(20)除了標(biāo)稱值外所有的變量區(qū)間都包含了隨機(jī)系數(shù)，如果將全部帶入運(yùn)算，計(jì)算難度之大，耗費(fèi)時(shí)間精力之多，顯然都是不現(xiàn)實(shí)的，因此我們必須采取更適合的計(jì)算方式來解決這個(gè)問題。當(dāng)計(jì)算兩個(gè)區(qū)間矩陣和的逆矩陣，其中一個(gè)矩陣可逆時(shí)，可以表述為：假設(shè)是一個(gè)階可逆區(qū)間矩陣，和是維的任意向量，則有下面關(guān)系式：(21)其中表示和的輸出結(jié)果，且。不難發(fā)現(xiàn)就是的倒數(shù)形式。這個(gè)公式僅被應(yīng)用在秩時(shí)。為了快速地得到相應(yīng)結(jié)論，這里假設(shè)區(qū)間矩陣只包含一個(gè)隨機(jī)系數(shù)：，并且矩陣滿足秩為1，則有下列關(guān)系式：(22)是新的標(biāo)稱值，是的新系數(shù)，當(dāng)且僅當(dāng)時(shí)，秩為。接下來，考慮在式(20)中的標(biāo)準(zhǔn)表達(dá)形式，當(dāng)階區(qū)間矩陣隨著任意符號(hào)的變化而變化，并且每一個(gè)系數(shù)矩陣都以階次排序。為了滿足式(21)中對秩的要求，首先要把每個(gè)系數(shù)矩陣分解為秩的形式：(23)假設(shè)存在：(24)則由式(22)可以逐步推導(dǎo)出：(25)其中可以由“誤差的傳播”方法中的式(16)得出：如此反復(fù)，則式(23)矩陣中的第一行可以表示為：(26)兩個(gè)系數(shù)和都可以用式(16)的方法得出：對上述方法作一般性歸納：假設(shè)存在元素，下標(biāo)表示其位置是在矩陣的第行，第列，為前這一行所有噪聲符號(hào)的和，因此：(27)最后，的求逆計(jì)算為：(28)可由式(27)得出。在這種反復(fù)運(yùn)算的過程中，雖然計(jì)算步驟繁多，計(jì)算效率不高，不適用于大規(guī)模矩陣計(jì)算，但其優(yōu)點(diǎn)是矩陣的區(qū)間操作不會(huì)產(chǎn)生新的隨機(jī)系數(shù)。另外一種方法叫做泰勒擴(kuò)張法，兩個(gè)矩陣之和的逆矩陣可以表示為：(29)結(jié)合式(20)可得：(3.30)將方程展開為只有三項(xiàng)的泰勒展開式，所有的高階項(xiàng)都近似為一個(gè)新的噪聲符號(hào)。通過反復(fù)求解法得出的式(27)和泰勒展開近似法得出的式(3.30)都得出了精確的數(shù)字結(jié)果，并且都成功地將區(qū)間矩陣轉(zhuǎn)化為相應(yīng)的矩陣形式。反復(fù)求解的方法必須滿足區(qū)間矩陣秩為1的條件，如果不能滿足，就必須對矩陣進(jìn)行分解。前者在求解小規(guī)模矩陣的問題時(shí)能更精確也更高效，但如果矩陣較復(fù)雜，更適合用泰勒展開法，求解速度更快，效率更高。2.3矩陣的指數(shù)運(yùn)算區(qū)間矩陣的指數(shù)運(yùn)算同樣可以用泰勒展開近似求解，兩個(gè)矩陣之和的指數(shù)運(yùn)算的泰勒展開形式可以表示為：(3.31)其中為與A，B相同維度的單位矩陣。由上式不難看出，矩陣的指數(shù)運(yùn)算可以簡化為矩陣求和的乘法運(yùn)算。假設(shè)存在區(qū)間矩陣其指數(shù)運(yùn)算可以表示為：(3.32)根據(jù)式(16)