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

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