求解信賴域子問題的Adams四階預(yù)報(bào)校正格式算法

范曉宇，李丹琳，王希云

(1.太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024；2.合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，合肥 230601)

求解二次模型信賴域子問題[1-2]是信賴域算法中極其重要的步驟，也就是求解如下形式：

(1)

當(dāng)Δ變化時(shí)，(1)的解δ在空間構(gòu)成一條曲線，稱為最優(yōu)曲線[3]。

傳統(tǒng)的精確求解方法可以求解二次模型子問題，但過程較為繁復(fù)。利用該方法，可得到最優(yōu)曲線的參數(shù)方程。在參數(shù)方程的基礎(chǔ)上，可建立最優(yōu)曲線的微分方程模型。模型如下所示[4]：

(2)

此時(shí)求解信賴域子問題就變成了求解微分方程問題。據(jù)此思想，文獻(xiàn)[4]-[9]在求解微分方程模型時(shí)，聯(lián)合一些常見、簡(jiǎn)單的單步法公式構(gòu)造折線，進(jìn)而替代最優(yōu)曲線。分別提出了求解二次模型子問題的顯式歐拉算法、隱式歐拉算法、平均歐拉算法以及R-K類算法。為了充分利用已有的信息，文獻(xiàn)[10]聯(lián)合多步法公式構(gòu)造折線，進(jìn)而替代最優(yōu)曲線。提出了求解二次模型子問題的Adams多步法算法。求解子問題時(shí)，文獻(xiàn)[10]中的Adams四階顯式算法計(jì)算簡(jiǎn)單，Adams四階隱式算法精度高，為發(fā)揮各自優(yōu)點(diǎn)，進(jìn)一步提高精度，本文聯(lián)合求解微分方程時(shí)常用的Adams四階預(yù)報(bào)—校正格式[11]：

(3)

fk=-(B+μkI)-1δk，(k=n，n-1，n-2，n-3)

提出了Adams四階預(yù)報(bào)—校正格式算法，求解信賴域子問題。文章分析了算法對(duì)應(yīng)折線的性質(zhì)，在理論上給予證明，在實(shí)驗(yàn)上給予驗(yàn)證。通過與文獻(xiàn)[10]提出的Adams四階顯式算法、Adams四階隱式算法的數(shù)值實(shí)驗(yàn)比較，驗(yàn)證了該算法的數(shù)值解可達(dá)到更高的精度，是可行的且是一種數(shù)值效果較好的新算法。

1 Adams四階預(yù)報(bào)—校正格式折線的構(gòu)造

第一步：從初始點(diǎn)P0(μ0，δ0)開始，其中μ0=0，δ0=-B-1g，選取步長(zhǎng)h，用公式：

(4)

第二步：由常用的經(jīng)典Runge-Kutta公式：

計(jì)算δ1.記:

則記為:

(5)

從而得到下一個(gè)節(jié)點(diǎn)P1(μ1，δ1)，其中μ1=μ0+h.同理可得到節(jié)點(diǎn)P2(μ2，δ2)，P3(μ3，δ3).

δ(τ)=

(6)

則步長(zhǎng)h需滿足下式：

h=

(7)

2 Adams四階預(yù)報(bào)—校正格式折線的性質(zhì)

引理1設(shè)B對(duì)稱正定，則當(dāng)0≤n≤2時(shí)，不等式①成立。

則當(dāng)3≤n≤N-1時(shí)，不等式②成立。

由引理1，可知步長(zhǎng)h為正。

定理1設(shè)B對(duì)稱正定，且0≤n≤2時(shí)有(8)式成立；

gT(fn1+2fn2+2fn3+fn4)+

(8)

n≥3時(shí)有(9)式成立。

(9)

則δ(τ)滿足：

(1)‖δ(τ)‖2關(guān)于τ為單調(diào)減函數(shù)。

(2)q[δ(τ)]關(guān)于τ為單調(diào)增函數(shù)。

證明：(1)當(dāng)τ∈[μ0，μ1]，即τ∈[0，h0]時(shí)，

則：

由(7)式與引理1可知，

同理τ∈(μ1，μ2]，τ∈(μ2，μ3]時(shí)，

因而，‖δ(τ)‖2在區(qū)間[μ0，μ1]，(μ1，μ2]，(μ2，μ3]上遞減。

當(dāng)?τ∈(μi，μi+1]即(τ-μi)∈(0，hi]，3≤i≤N-1

則:

由(7)式與引理1可知，

(2)當(dāng)τ∈[μ0，μ1]，即τ∈[0，h0]時(shí)，

B(f01+2f02+2f03+f04)

2f03+f04)+δ0TB(f01+2f02+2f03+f04))

由已知條件(8)，可得(q[δ(τ)])′≥0，τ∈[μ0，μ1].同理(q[δ(τ)])′≥0，τ∈(μ1，μ2]，(μ2，μ3].因而，q[δ(τ)]在區(qū)間[μ0，μ1]，(μ1，μ2]，(μ2，μ3]為遞增，得證。

當(dāng)?τ∈(μi，μi+1]即(τ-μi)∈(0，hi]，3≤i≤N-1時(shí)，

q[δ(τ)]=

由已知條件(9)得(q[δ(τ)])′≥0，τ∈(μi，μi+1].

因而，q[δ(τ)]在區(qū)間(μi，μi+1]，i=3，…，N-1為遞增，得證。證畢。

3 Adams四階預(yù)報(bào)—校正格式算法

步0.給定g，B，Δ.令n=0.

步1.令δ0=-B-1g.

步2.若Δ≥‖δ0‖2，則取δ*=δ0，此時(shí)計(jì)算終止。否則，令n=n+1，轉(zhuǎn)步3.

(R-K法計(jì)算起步值)對(duì)n=1，2，3，做步3到步4.

步3.計(jì)算δn。由公式(4)和經(jīng)典RK公式計(jì)算

步4.若Δ≥‖δn‖2，則:

其中：

計(jì)算終止。否則令n=n+1轉(zhuǎn)步3.(Adams四階預(yù)報(bào)-校正法計(jì)算δn) 對(duì)n=4，5…做步5到步6.

步6.若Δ≥‖δn‖2，

計(jì)算終止。否則令n=n+1轉(zhuǎn)步5.

4 Adams四階預(yù)報(bào)—校正格式算法的適定性

定理2在定理1成立的情況下，B對(duì)稱正定，利用Adams四階預(yù)報(bào)—校正格式折線δ(τ)求解信賴域子問題的極小點(diǎn)，解在信賴域邊界上，且η滿足：

其中:

證明：分情況進(jìn)行討論：

①當(dāng)n=1，2，3時(shí)，η滿足方程：

其中：

②當(dāng)n=4，5，…時(shí)，η滿足方程：

其中：

5 數(shù)值實(shí)驗(yàn)

對(duì)于子問題(1)的求解，步長(zhǎng)固定為h=0.1，信賴域半徑Δ依次改變，依據(jù)本文提出的新算法，對(duì)附錄中選取的兩個(gè)簡(jiǎn)單的測(cè)試函數(shù)，分別進(jìn)行數(shù)值實(shí)驗(yàn)(參考文獻(xiàn)[12]).算法獲得最優(yōu)解的時(shí)間復(fù)雜度O(n2).表1和表2為該算法的數(shù)值結(jié)果，以及與文獻(xiàn)[10]提出的Adams四階顯式算法、Adams四階隱式算法數(shù)值結(jié)果的比較。

表1 測(cè)試函數(shù)1的數(shù)值結(jié)果

表2 測(cè)試函數(shù)2的數(shù)值結(jié)果

比照表1和表2的數(shù)值結(jié)果，有如下結(jié)論：當(dāng)信賴域半徑Δ≥‖B-1g‖2時(shí)，三種算法求得的數(shù)值結(jié)果是完全相同的(此時(shí)為牛頓算法)。在信賴域半徑Δ<‖B-1g‖2時(shí)，對(duì)Funtion1進(jìn)行實(shí)驗(yàn)，Adams四階預(yù)報(bào)-校正格式算法的效果一直比Adams四階顯式算法的效果要好。當(dāng)信賴域半徑Δ=9和9.2時(shí)，Adams四階隱式算法的效果略微好于Adams四階預(yù)報(bào)-校正格式算法的效果；而信賴域半徑取其他值時(shí)，通過對(duì)比數(shù)值結(jié)果，發(fā)現(xiàn)Adams四階預(yù)報(bào)-校正格式算法比Adams四階隱式算法更好。對(duì)于Funtion2，Adams四階預(yù)報(bào)-校正格式算法的數(shù)值結(jié)果均好于Adams四階顯式算法、Adams四階隱式算法。因而本文提出的Adams四階預(yù)報(bào)-校正格式算法是一種有效且可行，數(shù)值效果較好的新算法。

其中，對(duì)于測(cè)試函數(shù)Funtion1

‖B-1g‖2=9.42，

對(duì)于測(cè)試函數(shù)Funtion2‖B-1g‖2=10.46

附錄：測(cè)試函數(shù)

Function1: Powell’s 4-variable function在初始點(diǎn)(2,5,3,6)T處的信賴域子問題。

s.t.‖δ‖2≤Δ

Function2: Wood-Colville’s function在初始點(diǎn)

(3,8,2,4)T處的信賴域子問題.

s.t.‖δ‖2≤Δ