雷米茲演算法,或稱雷米茲交換演算法,由葉夫根尼·列維奇·雷米茲於1934年所發表。
雷米茲演算法為一尋找函式簡易近似之迭代演算法,特別是定義於切比雪夫空間的函式效果最佳。
一個在切比雪夫空間的典型例子是 n 次項切比雪夫多项式的子空間,屬於實數連續函式之向量空間,定義於 C[a, b] 區間。
給定一子空間,其最佳近似多項式的定義為:可將此近似多項式與原始函式之最大絕對差異最小化者。
在這個情況下,可由equioscillation theorem使其解更精確
算法的主要目的是从一个集合
得到一个可以逼近函数
的多项式。集合
由近似的区间上的
个取样点
组成,通常由Chebyshev多项式线性映射至该区间得到。算法步骤如下:
- 解线性方程组
(其中
),
- 未知数为
和
。
- 使用
作為多項式
的係數。
- 找出
的局部极大误差点,组成集合
。
- 若所有
都是相同大小,仅正负号不同的话,则
为极小化极大逼近多项式。否则的话,使用
取代
并重复上述步骤。
此结果称为极小化极大逼近算法的最佳逼近多项式。
由於切比雪夫節點在多項式插值理論中所扮演的角色,故通常選擇其為初始近似的方法。由拉格朗日插值法 Ln(f) 初始化一函式 f 之最佳化問題,可以證明此初始近似之邊界限制為:
![{\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8494d63c0d249bc41b88423fc00aafb151609ecf)
其中節點 (t1, ..., tn + 1) 之拉格朗日插值法算子的常數為
![{\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a108ac745b822c419112d18a7c1fef461b995b40)
T 為切比雪夫多項式的零點,而
![{\displaystyle \lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13ceae32ea6e00edc3c1b20219b19f28cc60ef84)
對提供次最佳之切比雪夫節點來說,其漸近線為
![{\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/623195986be2dae0f192a73a87cd1c8740426cbb)
(γ 為 欧拉-马歇罗尼常数),
for ![{\displaystyle n\geq 1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc38ec6af7dd11fdc9baa67365f23906d76da4bb)
而上界為
![{\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/392018b61323b6769528849fdd641f917bff25b1)
Lev Brutman 計算出對
的邊界,而
為切比雪夫多項式之零點
![{\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1}{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\approx 0.201.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/646d942c1298201cb1ee7e58b66866994a065045)
Rüdiger Günttner由對
之較粗略的估算計算出
![{\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f17e8c3d67e0d767dd891d277127defd87c6be0)
在此將提供先前簡述步驟的詳細內容,在這個章節令指數 i 從 0 跑到 n+1.
步驟 1: 給定
, 求 n+2 條等式之線性系統之解
(其中
),
- 對於未知的
和 E.
可以很清楚地觀察到,在這個式子裡
若要成立,只有在節點
為 排序 的情況下才能達到,無論是嚴格遞增或遞減。這樣一來這個線性系統便有唯一解。(廣為人知的,並非每個線性系統都可以求解)。
此外,求解之複雜度最少為
,而一個從函式庫求解的標準計算器需要
的複雜度,在此有一簡單證明:
計算前n+1個節點之
標準 n 階插值
,
以及對於
之標準 n 階插值
![{\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caea78d7ce133134d92dfda6abe756d3eadf1c1c)
至此,需要
次數值運算。
在
與
之間,多項式
有其 i-階 零點zero between
and
,因此在
與
之間無任何零點,意即
與
正負號
相同。
線性組合
亦為一 n 次多項式
![{\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a18b5de18b9f260be884f7d98f00ab45cadc643d)
選擇任何 E ,對
,下列式子與上述等式相同:
![{\displaystyle p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3003073e90e2b99b7ae21c352c2b80045cfde0d3)
解 E 得:
![{\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d47a70c63e7f8f141291e02e94ec6e6349f5091)
如前述所提及,上式分母之兩項有相同正負號,因此
![{\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b17906de89ced54aae1644876138412e295d6b9c)
是完整定義的。
給定 n+2 階節點,其誤差為正負輪流:
![{\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d81d3b394104d77f8917e35d68f3b11c7e677f5)
de La Vallée Poussin 理論說明在這種形況下,沒有誤差少於 E 之 n 次多項式存在。
步驟 2 把多項式表示由
轉為
.
步驟 3 依照以下所述改善輸入節點
的誤差
。
在每個 P-領域,現在的節點
將被區域最大
取代,同樣在每個 N-領域,
將被區域最小取代,
在這部分並不要求高精確律。
令
, 其大小
皆大於或等於 E。de La Vallée Poussin 理論及其證明也可以應用至
,
而使此 n 次多項式有最小可能誤差的新下界為
。
步驟 4: 分別以
與
為新的上下界,此迭代演算法的終止條件為:
重複上述步驟直到
足夠小且不再遞減。
有時候在最大絕對差異點的附近,會有複數個點同時被取代。
有時候相對誤差會被用來衡量函式與其近似的差異,特別是在電腦上用浮點數做運算的函式。