Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Remez算法(The Remez Method)

Remez 算法 是一種定位函數有理逼近極值的方法。這篇簡短的文章給出了這種方法的一個概覽,但不能作為一個完整的理論對待,對於完整的算法說明,你需要參考你所喜歡的文獻資料。

假設你想要以一個逼近函數R(x)的方式來逼近一個函數f(x),其中 R(x) 可以是一個多項式,或者兩個多項式的比 P(x)/Q(x) (一個有理函數)。基本上,我們將會集中於多項式的情況,因為到目前為止它是最容易處理的情況,稍後我們將會擴展到完全的有理函數情況。

我們想要找到「最好的」有理逼近,這裡「最好」定義為這個逼近與函數f(x)只有最小的偏差。我們可以用過一個誤差函數來測量這個偏差:

Eabs(x) = f(x) - R(x)

以絕對誤差的方式來表示,但我們也可以使用相對誤差來表示:

Erel(x) = (f(x) - R(x)) / |f(x)|

實際上,通常我們可以將誤差函數以任意方式放大,在數學上它們沒有差別,雖然上面的兩種形式幾乎覆蓋你可能遇到的每一種情況。

極值逼近函數R(x)被定義為產生的誤差函數的極大值最小的那一個函數。Chebyshev表明對於R(x)有一個唯一的極值解,滿足下面的屬性:

這就意味著,如果我們知道誤差函數的極值的位置,那麼我們可以寫出N+2個聯立方程:

R(xi) + (-1)iE = f(xi)

其中 E 是極大誤差項,而 xi 是誤差函數的N+2個極值的橫坐標。然後求解這個聯立方程組來獲取多項式的係數和誤差項就很平凡了(trival)。

不幸的是我們不知道誤差函數的極值的位置!

Remez Method

Remez 算法是一種迭代技術,給定一個寬的假定範圍,將會在誤差函數的極值處收斂,因此也就是極值解。

在下面的討論中,我們將使用一個實際的例子來舉例說明Remez算法:在範圍[-1,1]上逼近函數 ex

在我們可以開始Remez算法之前,我們必須獲得誤差函數的極值的初始值。我們可以猜測這些值,但是一個更接近的第一次逼近可以通過先構造一個內插值多項式逼近到 f(x)。

為了獲得這個內插值多項式的N+1個係數,我們需要N+1個點(x0...xN):使用我們的內插值形式,這些點產生N+1個聯立方程:

f(xi) = P(xi) = c0 + c1xi ... + cNxiN

這可以用來求解P(x)中的 c0...cN 的N個係數。

很明顯這不是極值解,實際上,我們僅有的保證是 f(x) 和 P(x) 在這N+1個位置接觸,遠離這些位置,誤差可能是任意大。然而,我們可能想要初始的逼近與函數f(x)盡可能地接近,並且使用一個正交多項式的零值點作為初始的逼近點被證明是一個好的想法。在這個例子中,我們使用Chebyshev多項式的零值點,因為特別容易計算,對於一個度數為4的多項式進行插值,並且測量相對誤差。我們得到下面的誤差函數:remez-2

相對誤差的峰值為 1.2x10-3.

這已經是一個相當好的逼近了,由這個誤差函數的圖像判斷,我們明顯可以做得更好。在開始Remez method propper之前,我們需要進行另外一步操作:定義誤差函數的所有的極值點,並將這些點存儲為初始的Chebyshev 控制點

[Note] 注意

在一個多項式逼近的簡單例子中,通過在Chebyshev多項式的根處進行插值,我們實際上生成了對這個函數的一個Chebyshev 逼近 :以絕對誤差 的形式,這是我們可以達到的插值形式的最好的一個先驗選擇(priori choice),通常,這已經足夠接近極值解。

然而,如果我們想要優化相對誤差,或者如果逼近是一個有理函數,那麼初始的 Chebyshev 解將離理想的極值解非常遠。

這種理論的更技術性的討論可以在online course中找到。

Remez 第一步

Remez 算法的第一步,給定 N+2 Chebyshev 控制點 xi,求解 N+2 聯立方程:

P(xi) + (-1)iE = f(xi)

來獲得誤差項E以及多項式P(x)的係數。

這給我們一個函數f(x)的新的逼近,在每個控制點有相同的誤差E,並且誤差函數的值在控制點的符號交替變換。但這還不一定就是極值解:因為這些控制點可以不在誤差函數的極值點處。在這一步之後,下面是我們的誤差函數圖像:

remez-3

很清楚,這仍不是極值解,因為控制點並不是位於極值點處,但最大的相對誤差下降到 5.6x10-4

Remez 第二步

第二步是定位新的逼近的極值,我們以兩步來完成:首先,誤差函數在每個控制點發生符號的變化,在N+2個控制點之前我們必須有N+1誤差函數的根。一旦通過標準根查找技術找到這些根,我們知道每個極值點都位於每一對根之間,加上兩個位於範圍的端點和第一個與最後一個根之間。這個N+2個極值就可以使用標準的函數極小化(function minimisation)技術來找到。

現在我們有一個選擇:多點交換,單點交換。

在單點交換中,我們將們將最接近最大的極值的控制點移動到極值的橫坐標值處

在多點交換中,為了所有的極值的位置,我們交換所有的當前控制點。

在我們的例子中,我們使用多點交換。

迭代

Remez 算法然後對上面的步驟1和步驟2進行迭代,直到控制點位於誤差函數的極值點:這就是極值解。

對於我們當前的例子,兩次迭代收斂於一個極值解,且峰值相對誤差為 5x10-4 ,誤差函數類似於下面:

remez-4

有理逼近(Rational Approximations)

如果我們想要把Remez算法擴展到有理逼近的形式:

f(x) = R(x) = P(x) / Q(x)

其中 P(x) 和 Q(x) 是多項式,那我們進行與上面相同的過程,如果,P(x) 次數為 N 且Q(x) 次數為 M,那麼我們有N+M+2個未知項。假定Q(x) 是規範化的,以便它的第一個係數為1,給定總共 N+M+1 個多項式係數,加上誤差項E。

現在要求解的聯立方程為:

P(xi) / Q(xi) + (-1)iE = f(xi)

在N+M+2 個控制點 xi處計算。

不幸的是,這些方程在誤差項E中不是線性的:僅當我們知道E時我們才能求解這些方程,而現在E是另外一個未知項!

求解這些方程的方法通常採用迭代:我們猜測E的值,解這個方程組來獲得一個新的E值(以及多項式的係數),然而使用新的E值作為第二次猜測。這種方法一直重複到E收斂於一個穩定值。

這種複雜性將這種有理迭代的運行時間增加到非常長。通常是期望盡可能獲得一個多項式逼近:與多項式逼近相比,有理逼近通常匹配更難逼近的函數,更高的精度以及更高的效率。例如,如果我們使用先前的逼近例子,我們用次數為4的多項式獲得 5x10-4 的精度。如果我們將兩個未知項移動到分母中來給定一對次數為2的多項式,並重新求極小值,那麼峰值誤差下降為 8.7x10-5。對於同樣的項數,在精度上是5倍的增加。

實際的考慮(Practical Considerations)

大多數關於逼近理論的論文停留在這一點。然而,從一個現實的觀點看,大多數的工作在查找正確的逼近形式,然後讓Remez算法收斂於一個解。

到目前為止,我們使用一個直接的逼近:

f(x) = R(x)

僅當f(x)是光滑的(smooth)函數時,這才會收斂為一個有用的逼近。除此之外,當計算這個有理形式的均值的時候,捨入誤差永遠都不會比 a few epsilon of machine precision 更接近。因此這種直接逼近的形式通常為需要效率而不是精度的情況保留。

改進這種情況的第一步是將f(x)拆分為一個幟部分(dominant part),我們可以使用另外的方法進行精確的計算,以及一個緩慢變化的剩餘項,我們可以使用一個有理逼近來逼近。我們可以寫作:

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

其中 g(x) 是函數 f(x)幟部分(dominant part),但是如果 f(x)/g(x) 在整個區間上近似為常量,那麼:

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

將會產生一個更好的解:在這裡c 是一個f(x)/g(x)近似值的常量而R(x)與c比較非常小。在這種情況下,如果 R(x) 針對絕對誤差進行了優化,那麼誤差比常量c小,當R(x)被加到c 時,這個錯誤將會有效的 get wiped out 。

最難的部分明顯就是從你的函數中抽取正確的函數g(x):通常,這個函數的漸近性將會給出一個很好的提示,例如,在x 變大時,函數erfc與 e-x2/x 成比例。因此使用:

erfc(z) = (C + R(x)) e-x2/x

這個逼近看起來是一個明顯的嘗試,並且實際上產生一個有用的逼近。

然而,困難變為收斂到極值解。不幸的是,對於一些函數,Remez算法會導致多種行為,即使初始的逼近值非常好。此外在Remez算法的第一步中獲得的解是一個壞的解的情況是比較常見的:當求解的方程是非常"硬的(stiff)",經常非常接近於奇異的(singular),並且根本不能假定找到一個解,捨入誤差和快速改變的誤差函數會導致誤差函數在控制點沒有發生要求的符號變化的情況。如果發生了這種情況,它是Remez算法的嚴重錯誤。也可能產生完全符合數學,但是計算結果是無用的情況:可能是因為不可避免的大量的捨入誤差,也可能是分母中有一個根超出了逼近的區間。在後面一種情況中,儘管逼近會在根處有正確的極限值,但逼近卻是沒有用的。

假定逼近沒有任何嚴重錯誤,並且唯一問題是在極值解處收斂,這裡的目標是在開始Remez算法之前足夠接近極值點。使用Chebyshev多項式的零值點作為初始的插入點是一個好的開始,但是當處理相對誤差和/或有理逼近的時候可能不是一個好的主意。一種方法是將這些插入點偏移到一個端點:例如,如果我們把Chebyshev多項式的根變為一個指數大於1的冪,那麼這些根將偏向區間[-1,1]的中心。更有用的是,如果我們開始時放大在區間[0,1]上的點並變為一個正的冪,我們可以將這些點偏移到左邊或是右邊。回來我們的例子在區間[-1,1]上的函數ex ,初始的插值點形式:

remez-2

然而,如果我們首先偏移這些點到左邊(放大到[0,1]),變為指數為1.3的冪,然後把它們放大加到[-1,1],我們將誤差從1.3x10-3 變到 6x10-4

remez-5

很明顯,仍不夠 理想,但一我們預期的極值解(5x10-4)只差幾個百分比。

Remez Method Checklist

如果Remez算法發生錯誤,下面列舉了一些檢查的事項,它並不是一個完整的列表,但是希望它可以提供幫助。

參考文獻

初始的Remez算法和擴展到有理函數的算法都是以俄文寫的:

Remez, E.Ya., Fundamentals of numerical methods for Chebyshev approximations, "Naukova Dumka", Kiev, 1969.

Remez, E.Ya., Gavrilyuk, V.T., Computer development of certain approaches to the approximate construction of solutions of Chebyshev problems nonlinearly depending on parameters, Ukr. Mat. Zh. 12 (1960), 324-338.

Gavrilyuk, V.T., Generalization of the first polynomial algorithm of E.Ya.Remez for the problem of constructing rational-fractional Chebyshev approximations, Ukr. Mat. Zh. 16 (1961), 575-585.

一些英文的參考資料包括:

Fraser, W., Hart, J.F., On the computation of rational approximations to continuous functions, Comm. of the ACM 5 (1962), 401-403, 414.

Ralston, A., Rational Chebyshev approximation by Remes' algorithms, Numer.Math. 7 (1965), no. 4, 322-330.

A. Ralston, Rational Chebyshev approximation, Mathematical Methods for Digital Computers v. 2 (Ralston A., Wilf H., eds.), Wiley, New York, 1967, pp. 264-284.

Hart, J.F. e.a., Computer approximations, Wiley, New York a.o., 1968.

Cody, W.J., Fraser, W., Hart, J.F., Rational Chebyshev approximation using linear equations, Numer.Math. 12 (1968), 242-251.

Cody, W.J., A survey of practical rational and polynomial approximation of functions, SIAM Review 12 (1970), no. 3, 400-423.

Barrar, R.B., Loeb, H.J., On the Remez algorithm for non-linear families, Numer.Math. 15 (1970), 382-391.

Dunham, Ch.B., Convergence of the Fraser-Hart algorithm for rational Chebyshev approximation, Math. Comp. 29 (1975), no. 132, 1078-1082.

G. L. Litvinov, Approximate construction of rational approximations and the effect of error autocorrection, Russian Journal of Mathematical Physics, vol.1, No. 3, 1994.


PrevUpHomeNext