雷米茲演算法

维基百科,自由的百科全书
跳转至: 导航搜索

雷米茲演算法,或稱雷米茲交換演算法,由葉夫根尼·列維奇·雷米茲於1934年所發表。 雷米茲演算法為一尋找函式簡易近似之迭代演算法,特別是定義於切比雪夫空間的函式效果最佳。

一個在切比雪夫空間的典型例子是 n 次項切比雪夫多项式的子空間,屬於實數連續函式之向量空間,定義於 C[a, b] 區間。

給定一子空間,其最佳近似多項式的定義為:可將此近似多項式與原始函式之最大絕對差異最小化者。 在這個情況下,可由equioscillation theorem使其解更精確

程序[编辑]

雷米茲演算法由一函式 f 開始,欲近似一集合 X,且在近似的區間上工有n + 2 個取樣點  x_1, x_2, ...,x_{n+2} , 通常Chebyshev nodes可映射至該區間,步驟如下:

  1. 解線性系統之等式
 b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1) ^ i E = f(x_i) (其中  i=1, 2, ... n+2 ),
對於未知的 b_0, b_1...b_nE
  1. 使用  b_i 作為多項式 P_n 的係數。
  2. 找出集合 M ,為 |P_n(x) - f(x)| 之區域極大錯誤點。
  3. 若在 M 之中的所有 m 都是相同大小,僅正負號不同的話,則 P_n 為極小化極大近似之多項式。若否,則 M 取代 X 並重複上述步驟。

此結果稱為最佳近似多項式、切比雪夫近似、或最小化最大近似。

初始化選擇[编辑]

由於切比雪夫節點在多項式插值理論中所扮演的腳色,故通常選擇其為初始近似的方法。由拉格朗日插值法 Ln(f) 初始化一函式 f 之最佳化問題,可以證明此初始近似之邊界限制為:

\lVert f - L_n(f)\rVert_\infty \le (1 + \lVert L_n\rVert_\infty) \inf_{p \in P_n} \lVert f - p\rVert

其中節點 (t1, ..., tn + 1) 之拉格朗日插值法算子的常數為

\lVert L_n\rVert_\infty = \overline{\Lambda}_n(T) = \max_{-1 \le x \le 1} \lambda_n(T; x),

T 為切比雪夫多項式的零點,而

\lambda_n(T; x) = \sum_{j = 1}^{n + 1} \left| l_j(x) \right|, \quad l_j(x) = \prod_{\stackrel{i = 1}{i \ne j}}^{n + 1} \frac{(x - t_i)}{(t_j - t_i)}.

對提供次最佳之切比雪夫節點來說,其漸進線為

\overline{\Lambda}_n(T) = \frac{2}{\pi} \log(n + 1) + \frac{2}{\pi}\left(\gamma + \log\frac{8}{\pi}\right) + \alpha_{n + 1}

(γ欧拉-马歇罗尼常数),

0 < \alpha_n < \frac{\pi}{72 n^2} for n \ge 1,

而上界為

\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1

Lev Brutman 計算出對 n \ge 3 的邊界,而 \hat{T} 為切比雪夫多項式之零點

\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.

Rüdiger Günttner由對 n \ge 40 之較粗略的估算計算出

\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < 0.0196.

細節討論[编辑]

在此將提供先前簡述步驟的詳細內容,在這個章節令指數 i 從 0 跑到 n+1.

步驟 1: 給定 x_0, x_1, ... x_{n+1}, 求 n+2 條等式之線性系統之解

 b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1) ^ i E = f(x_i) (其中  i=0, 1, ... n+1 ),
對於未知的 b_0, b_1, ...b_nE.

可以很清楚地觀察到,在這個式子裡 (-1)^i E 若要成立,只有在節點 x_0, ...,x_{n+1}排序 的情況下才能達到,無論是嚴格遞增或遞減。這樣一來這個線性系統便有唯一解。(廣為人知的,並非每個線性系統都可以求解)。 此外,求解之複雜度最少為 O(n^2) ,而一個從函式庫求解的標準計算器需要 O(n^3) 的複雜度,在此有一簡單證明:

計算前n+1個節點之 f(x) 標準 n 階插值 p_1(x), 以及對於 (-1)^i 之標準 n 階插值 p_2(x)

p_1(x_i) = f(x_i), p_2(x_i) = (-1)^i, i = 0, ..., n.

至此,需要 O(n^2) 次數值運算。

x_{i-1}x_i,\ i=1, ...,n 之間,多項式 p_2(x) 有其 i-階 零點zero between x_{i-1} and x_i,\ i=1, ...,n,因此在 x_nx_{n+1}之間無任何零點,意即 p_2(x_n)p_2(x_{n+1}) 正負號 (-1)^n 相同。

線性組合 p(x) := p_1 (x) - p_2(x)\!\cdot\!E 亦為一 n 次多項式

p(x_i) = p_1(x_i) - p_2(x_i)\!\cdot\! E \ = \ f(x_i) - (-1)^i E,\ \ \ \  i =0, \ldots, n.

選擇任何 E ,對 i = 0, ... ,n ,下列式子與上述等式相同:

p(x_{n+1}) \ = \ p_1(x_{n+1}) - p_2(x_{n+1})\!\cdot\!E \ = \ f(x_{n+1}) - (-1)^{n+1} E

E 得:

E \ := \ \frac{p_1(x_{n+1}) - f(x_{n+1})}{p_2(x_{n+1}) + (-1)^n}.

如前述所提及,上式分母之兩項有相同正負號,因此

p(x) \equiv b_0 + b_1x + \ldots + b_nx^n

是完整定義的。

給定 n+2 階節點,其誤差為正負輪流:

p(x_i) - f(x_i) \ = \ -(-1)^i E,\ \ i = 0, ... , n\!+\!1.

de La Vallée Poussin 理論說明在這種形況下,沒有誤差少於 En 次多項式存在。

步驟 2 把多項式表示由b_0 + b_1x + ... + b_nx^n 轉為 p(x).

步驟 3 依照以下所述改善輸入節點 x_0, ..., x_{n+1} 的誤差 \pm E

在每個 P-領域,現在的節點 x_i 將被區域最大 \bar{x}_i 取代,同樣在每個 N-領域, x_i 將被區域最小取代, 在這部分並不要求高精確律。

z_i := p(\bar{x}_i) - f(\bar{x}_i), 其大小 |z_i| 皆大於或等於 Ede La Vallée Poussin 理論及其證明也可以應用至 z_0, ... ,z_{n+1}, 而使此 n 次多項式有最小可能誤差的新下界為 \min\{|z_i|\} \geq E


步驟 4: 分別以 \min\,\{|z_i|\}\max\,\{|z_i|\} 為新的上下界,此迭代演算法的終止條件為: 重複上述步驟直到 \max\{|z_i|\} - \min\{|z_i|\} 足夠小且不再遞減。

變異[编辑]

有時候在最大絕對差異點的附近,會有複數個點同時被取代。

有時候相對誤差會被用來衡量函式與其近似的差異,特別是在電腦上用浮點數做運算的函式。


外部連結[编辑]