Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

極值逼近以及Remez算法(Minimax Approximations and the Remez Algorithm)

在 libs/math/minimax 目錄下包含一個命令行驅動的程序用於使用Remez算法生成極值逼近。多項式逼近和有理函數逼近都得到支持,雖然後者很驗證收斂:有理函數不能收斂是很常見的。對於永遠都會順利收斂的多項式就沒有這些限制。

值得強調的是:為函數開發有理逼近通常不是一件容易的工作,對於這方面的研究有很多書籍。為了使用這個工具,你需要對Remez算法有一個瞭解,以及你想達到的逼近的一般形式。

除非你已經瞭解了Remez算法,否則推薦你先閱讀解釋Remez算法原理的背景文章

這個程序由兩部分構造:

main.cpp

包含一個命令行的解析器,以及所有對Remez算法代碼的調用。

f.cpp

包含逼近的函數。

因此,為了使用這個工具,你必須修改 f.cpp 返回逼近的函數。這個程序支持使用同一個編譯好的程序來逼近多個函數:每一個作為一個單獨的變量:

NTL::RR f(const NTL::RR& x, int variant);

返回在x外的函數variant的值。所以,如果你願意,你可以在已存在的例子後面加上一個新的逼近函數作為一個新的變量。

除了這兩個文件,這個程序需要與一個patched NTL library 進行鏈接。

注意,函數f 必須返回逼近結果的有理數部分:例如,如果你逼近一個函數f(x) ,那麼使用下面的等式就很常見了:

f(x) = g(x)(Y + R(x))

其中g(x) 是函數 f(x)的幟部分( dominant part ),Y 是某個常量,R(x) 是有理逼近部分(rational approximation part),通常進行絕對誤差優化。

在這種情況下,你需要定義函數f 返回f(x)/g(x) 然後設置與逼近Y的偏移為 y-offset (參看下面的命令行選項)。

許多其它的形式也是可能的,但在所有的情況中,目標是將函數f(x) 拆分為一個可以很容易使用標準的數學函數進行計算的幟部分(dominant part)以及一個光滑且緩慢變化的有理逼近部分。參考你所喜歡的教科書參看更多的例子。

程序的命令行選項為:

variant N

設置當前函數的變種( function variant )為N。這使得多個被逼近的函數可以編譯到同一個可執行文件中。缺省為0。

range a b

設置逼近的範圍 [a,b],缺省為 [0,1]。

relative

設置 Remez 代碼針對相對誤差進行優化。這在程序的啟動時是缺省的。僅當在被優化的區間上函數f(x)沒有根才可以使用相對誤差。

absolute

設置 Remez 代碼對絕對誤差進行優化。

pin [true|false]

"Pins" 代碼,使得有理逼近函數穿過坐標原點。如果R(0)必須為0,則設置為true。通常這會在試圖在 [0,0]處保留一個根同查又針對相對誤差進行優化時發生。

order N D

設置分子中的逼近次數為N 且分母中的逼近次數為D 。如果D 為0,那麼結果是多項式逼近。總共有N+D+2 個係數,如果pin設置為真,那麼分子的第一個係數為0,分母的第一個係數永遠為1.

working-precision N

設置 NTL::RR 庫的計算精度為N 個二進制數字。缺省為 250。

target-precision N

設置打印出結果精度為N 個二進制數字:與將用於逼近的類型的數字個數設為同樣個數。缺省為53(對於double精度)。

skew val

將初始的內插值控制點( initial interpolated control points)向範圍的一個或另一個端點"偏斜(Skews)"。正值向範圍的左邊界編斜,負值向範圍的右邊界偏斜。如果一個逼近不能收斂(常見情況),調整偏斜值,使得第一步產生最小的可能誤差。val 應當在範圍 [-100,+100]之中,缺省為0。

brake val

設置每一步的減速值(brake),使得在控制點中減速(brake)val% 。缺省為50,如果逼近不會收斂,那麼嘗試一個更大的值,如果逼近很快收斂,設置一個更小的值。

x-offset val

設置與val的x-offset值:逼近將會針對f(S * (x + X)) + Y 生成,其中X 是 x-offset,S 是 x-scale 而 Y 是 y-offset。缺省為0。為了避免傳入誤差,注意指定一個可以精確表示為浮點數的值。

x-scale val

設置與 val的 x-scale : 逼近將會針對f(S * (x + X)) + Y 生成,其中X 是 x-offset,S 是 x-scale 而 Y 是 y-offset。缺省為1。為了避免傳入誤差,注意指定一個可以精確表示為浮點數的值。

y-offset val

設置與val的y-offset值:逼近將會針對f(S * (x + X)) + Y 生成,其中X 是 x-offset,S 是 x-scale 而 Y 是 y-offset。缺省為0。為了避免傳入誤差,注意指定一個可以精確表示為浮點數的值。

y-offset auto

設置與函數f(x)在兩個端點處以及區間中心處的的函數值的均值的 y-offset 。計算結果被有意截斷為float 精度 (並且應當在你的代碼中存儲為一個float 值)。 逼近將會針對f(S * (x + X)) + Y 生成,其中X 是 x-offset,Y 是 y-offset。缺省為0。

graph N

在被優化的範圍上打印 N 個 均勻分佈的點。如果沒有指定,那麼N缺省為3.用於檢查函數f(x)是不在區間上是光滑的。

step N

進行N 步,或者如果沒有指定N,則進行一步 在每一步之後打印:打印逼近的誤差函數(error function)在極值點處的 peek error,在最後一步打印求解的理論誤差項,以及在 Chebyshev control points的最大相對改變。當兩個誤差項(近似地)相等並且在控制點處的改變已經減小到一個合適的值時,逼近在極值解處收斂。

test [float|double|long]

以 float, double,或 long double 精度測試當前逼近。用於檢查以固定的精度進行逼近的捨入誤差。測試在逼近的誤差函數的極值處進行,以及在誤差函數的函數值為0的點進行。

test [float|double|long] N

以 float, double, 或 long double 精度測試當前的逼近。用於檢查以固定的精度進行逼近的捨入誤差。測試在整個逼近區間上的N個均勻分佈的點上進行。如果沒有指定 [float|double|long]中的任何一個,那麼測試使用NTL::RR,這可以側重於獲取逼近的誤差函數( error function )。

rescale a b

取當前的 Chebeshev control points,並在一個新的區間[a,b]上將它們改變尺度(rescale)。有時這可以用於為那些不能收斂的函數設置起始控制點。

rotate

將分子中的一項移到分母中,但保持 Chebyshev control points 不變。有時這可以用於為那些不能收斂的函數設置起始控制點。

info

打印當前的逼近值:誤差函數(error function)的值為0的位置, Chebyshev control points控制點的位置, x 和 y 偏移,以及多項式的係數。


PrevUpHomeNext