自適應積分的遞歸實現研究

唐珺 楊道杰

摘要：文章首先介紹了分治算法與自適應積分的原理，然后用分治算法對自適應積分進行編程實現，最后將自適應積分在計算復雜度、誤差等方面與組合辛普森積分公式進行了比較，分析了自適應積分的優越性。

關鍵詞：自適應積分；組合辛普森積分；分治算法；復雜度；誤差 文獻標識碼：A

中圖分類號：O172 文章編號：1009-2374（2016）27-0013-04 DOI：10.13535/j.cnki.11-4406/n.2016.27.007

使用等距節點的組合積分公式，在整個積分區間使用相同的小步長h，以保證整體精度，但這并沒有考慮曲線的某些部分劇烈變化的情況。而自適應積分能夠根據函數的變化趨勢自動選擇合適的步長，本文在算法上以遞歸的方式對其進行了實現。

本文所用的遞歸算法屬于分治算法：為了解決一個給定的問題，算法要一次或多次地遞歸調用其自身來解決相關的子問題。分治算法一般有著對數函數的復雜度，計算量較小，用在自適應積分上可用較少的計算量得到較高的精度，不失為一種好的算法，將在本文的開頭進行介紹。

由于自適應積分的基礎是辛普森積分，因此文中接下來會對辛普森積分公式進行簡要介紹，最后再引入正題自適應積分。

1 分治算法簡介

為了解決一個給定的問題，算法要一次或多次地調用其自身來解決自身相關的子問題，這些算法通常采用分治策略。將原問題分成n個規模較小而結構與原問題相似的子問題，遞歸地解決這些子問題，然后再合并其結果，就得到原問題的解。

分治算法在每一層遞歸上都有三個步驟：分解：將原問題分解成一系列子問題；解決：遞歸地解決各子問題，若子問題足夠小，則直接求解；合并：將子問題的結果合并成原問題的解。

2 組合辛普森積分

2.1 辛普森公式

3.3 遞歸計算

接下來，從開始（其中是區間上數值積分的容差）將區間細分，在自區間上分別采用作為容差進行積分，利用式（7）測試精度，不斷遞歸，直至滿足精度要求。

4 算法實現

自適應積分在算法上基本上吻合上文提到的分治法的思想：分解：將原區間分解成兩個子區間；解決：遞歸地算各區間的積分，并進行精度測試，如果滿足要求就停止遞歸，否則繼續；合并：將子區間的積分和

相加。

4.1 算法流程

自適應積分具體的算法流程見圖1所示：

4.2 核心代碼

5 細節處理及改進

5.1 細節處理

5.1.1 自適應積分要求每次遞歸保存該區間直接積分以及子區間組合積分的和，甚至要保存誤差，因此不能簡單地用返回值來保存，要用變量的指針或者引用來保存。

5.1.2 本程序屬于遞歸程序，一定要有終止條件，即上述程序的9～11行。

5.1.3 void函數雖然可以不用返回值，但在遞歸程序中，一旦計算精度符合要求，就要層層向上返回，否則程序會無窮遞歸，不斷壓棧，最終導致溢出。

5.1.4 計算子區間的積分時，別忘記將誤差容限減半，保證子區間誤差容限和等于原區間。

5.2 程序改進

上述程序僅僅能計算出最終的積分值，然而有時候需要保留最終的誤差值和每一步的端點變化，這樣能清晰地看出遞歸過程的區間細分的變化情況，因此上述程序可以做以下改進：

5.2.1 誤差err的保存。誤差的保存很簡單，只需在函數的參數列表中傳入誤差的指針或引用即可，如float*err或者float&err。

5.2.2 端點值的保存。端點值要用數組來保存，且要有兩個數組來保存，一個數組LeftPoints保存做端點值，另一個RightPoints保存右端點值。本文的編程采用C++程序，而C++標準庫中有個可以很方便進行數組處理的容器，叫做vector，該容器定義了很多方便的操作，支持自動增長，并且安全性高，廣為程序員所采用。因此本文也將采用vector來保存端點值，且用到容器上的兩個操作：插入（任意位置插入insert和后插入push_back）和排序sort。

保存端點值時需要在程序特定地方加入push_back操作，具體放在哪里需要先分析程序的區間的遞歸過程，區間的遞歸示意圖如下：

用數組LeftPoints存儲區間左端點，根據上圖，每層遞歸的左端點序列依次為{a}，{a，c}，{a，d，c，d}……根據大小進行插入添加端點的方法可以直接得到按照從小到大順序排列的端點序列，但是操作上可能有一定的麻煩性，本文沒有好的方法，可以留給讀者討論研究。本文采用先直接從數組后面添加（push_back操作），之后進行排序（sort操作）的方式得到最后的左端點序列，將push_back操作添加到上述代碼的14與15行之間。而對于右端點序列的保存有個簡單的辦法，實際得到的端點序列有著以下的形式：

上面代碼加黑的地方即是保存左端點序列的地方，不過程序最開始的時候需要先把端點a添加進去。

6 示例分析

用自適應積分求定積分的數值逼近，起始容差。真實值為-1.5487883725279481333……我們這里取11位精度-1.54878837253用于對比兩種方法計算的結果。

6.1 自適應積分的計算結果

從圖中可以看出，函數趨勢變化較快的地方取點較密集，變化緩慢之處取點相對稀疏，具有自適應過程，而且在更少的計算次數下得到較高精度。本次計算的結果為-1.54878823413，誤差為0.00000505957。而如果要達到11位精度（即計算結果為-1.54878837253），實際的計算次數為360次。

6.2 與辛普森計算結果的對比

如果單純用辛普森積分的話，當劃分區間數達到1300次左右才能使精度達到10-11，因此可以看出自適應積分可以大大減少計算次數，因為在曲線變化緩慢的地方劃分的子區間更少，相對于完全等分區間來說，減少了不必要的計算量。

7 結語

本文所采用的分治算法是一種很重要的算法，有著完善的理論基礎，在一些場合中非常實用，如一些需對原問題進行分割再綜合的一類問題，實現方便，并且容易分析其復雜度。自適應積分公式有著極大的優越性，在工程或科學計算中應用廣泛，本文通過分治算法對其進行了實現，效果良好，而且可以方便地通過設置誤差容限來達到想要的精度。

我們在生活中要學會培養自己的算法素養，掌握一些基本的算法思想，如分治算法，并嘗試將其用于一些實際問題中，如科學計算，提高分析并解決問題的能力。

參考文獻

[1] John H.Mathews，Kurtis D.Fink.Numerical Method Using MATLAB[J].Fourth Edition，2014，（11）.

[2] Stanley B.Lippman，Josée Lajoie，Barbara E.Moo. C++ Primer[J]. Fourth Edition，2012，（2）.

[3] Thomas H.Cormen，Charles E.Leiserson，Ronald L.Riverst，Clifford Stein. Introduction to Algorithm [J].Second Edition，2001，（49）.

（責任編輯：黃銀芳）