Алгоритм Ремеза

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Ремеза (также алгоритм замены Ремеза) — это итеративный алгоритм равномерного аппроксимирования функций f ∊ C[a,b], основанный на теореме П. Л. Чебышёва об альтернансе. Предложен Е. Я. Ремезом в 1934 году[1].

Алгоритм Ремеза применяется при проектировании КИХ-фильтров[2].

Математические основания[править | править вики-текст]

Теорема Чебышёва[править | править вики-текст]

Теоретической основой алгоритма Ремеза является следующая теорема[3].

Для того, чтобы некоторый многочлен P*(x) степени не выше n был многочленом, наименее уклоняющимся от f ∊ C[a,b], необходимо и достаточно, чтобы на [a,b] нашлась по крайней мере одна система из n + 2 точек xi, ax0 < x1 < … < xn+1b, в которых разность f(x) - P*(x):

  1. поочерёдно принимает значения разных знаков,
  2. достигает по модулю наибольшего на [a,b] значения.

Такая система точек называется чебышёвским альтернансом.


Теорема Валле-Пуссена[править | править вики-текст]

Пусть En — величина наилучшего приближения функции f(x) многочленами степени n. Оценку En снизу даёт следующая теорема[4]:

Если для функции f ∊ C[a,b] некоторый многочлен P(x) степени n обладает тем свойством, что разность f(x) - P(x) на некоторой системе из n + 2 упорядоченных точек xi принимает значения с чередующимися знаками, то

E_n(f) \ge \min|f(x_i)-P(x_i)|.

Ш.-Ж. Валле-Пуссен, 1919

Алгоритм[править | править вики-текст]

Рассмотрим систему n + 1 функций Φ = {φ0,…,φn}, последовательность n + 2 точек X = ax0 < x1 < … < xn+1b и будем искать аппроксимирующий многочлен P_X = \sum_0^n a_j\varphi_j.

  1. Решаем систему линейных уравнений относительно aj и d:
    \sum_{j=0}^n a_j\varphi_j(x_i) + (-1)^i d = f(x_i), \quad i=0,1,\ldots,n.
  2. Находим точку ξ такую, что D = |f(ξ) — P(ξ)| = max.
  3. Заменяем в X одну из точек на ξ таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки xi были упорядочены на каждой итерации[5].
  4. Повторяем все шаги с начала до тех пор, пока не будет |d| = D.

На втором шаге мы можем искать не одну точку ξ, а множество Ξ точек, в которых достигаются локальные максимумы |f — P|. Если все ошибки в точках множества Ξ одинаковы по модулю и чередуются по знаку, то P — минимаксный многочлен. Иначе заменяем точки из X на точки из Ξ и повторяем процедуру заново.

Выбор начальных точек[править | править вики-текст]

В качестве начальной последовательности X можно выбирать точки, равномерно распределённые на [a,b]. Целесообразно также брать точки[6]:

x_i = \frac{a+b}{2} + \frac{b-a}{2} \cos\left(\frac{\pi i}{n+1}\right), \quad i=0,\ldots,n+1.

Модификация[править | править вики-текст]

Если аппроксимирующая функция ищется в виде многочлена, то вместо решения системы на первом шаге алгоритма, можно воспользоваться следующим методом[7]:

  1. Находим многочлен q(x) степени n+1 такой, что q(xi) = f(xi) (задача интерполяции).
  2. Находим также многочлен q*(x) степени n+1 такой, что q*(xi) = (-1)i.
  3. Выбирая d так, чтобы многочлен P(x) ≡ q(x) — d q*(x) имел степень n, получаем P(xi) + (-1)id = f(xi).

Дальше повторяются шаги по основной схеме.

Условие остановки[править | править вики-текст]

Так как по теореме Валле-Пуссена |d| ≤ En(f) ≤ D, то условием остановки алгоритма может быть D — |d| ≤ ε для некоторого наперёд заданного ε.

Сходимость[править | править вики-текст]

Алгоритм Ремеза сходится со скоростью геометрической прогрессии в следующем смысле[8]:

Для любой функции f ∊ C[a,b] найдутся числа A > 0 и 0 < q < 1 такие, что максимальные уклонения от функции f(x) полиномов P_n^{(k)}(x), построенных по этому алгоритму, будут удовлетворять неравенствам

\max|f(x) - P_n^{(k)}(x)| - E_n(f) \le Aq^k, \quad k=1,2,\ldots,

где En(f) — величина наилучшего приближения на [a,b] функции f(x) при помощи полиномов Pn(x).


Пример[править | править вики-текст]

f(x) = ex, n = 1, P(x) = a x+b.
Шаг 1.
X1 −1 0 1
f(xi) 0.368 1.000 2.718

\begin{cases}
    ({-}1)a + b + d = 0.368 \\
    (0)a + b - d = 1.000\\
    (1)a + b + d = 2.718
\end{cases}
Решение системы даёт P = 1.175x + 1.272, d = 0.272.
max|eξ-P(ξ)| = 0.286 при ξ = 0.16.
Шаг 2.
X2 −1 0.16 1
f(xi) 0.368 1.174 2.718

\begin{cases}
    ({-}1)a + b + d = 0.368 \\
    (0.16)a + b - d = 1.174\\
    (1)a + b + d = 2.718
\end{cases}
Решение системы даёт P = 1.175x + 1.265, d = 0.279.
max|eξ-P(ξ)| = 0.279 при ξ = 0.16.

Так как в пределах данной точности получили ту же самую точку, то найденный многочлен следует рассматривать как наилучшее приближение первой степени функции ex.

См. также[править | править вики-текст]

Аппроксимационная теорема Вейерштрасса

Примечания[править | править вики-текст]

  1. E. Ya. Remez (1934). Sur le calful effectif des polynômes d’approximation de Tschebyscheff. C.P. Paris 199, 337—340; Ch. 3:78
  2. Рабинер, 1978, с. 157
  3. Дзядык, 1977, с. 12
  4. Дзядык, 1977, с. 33
  5. Лоран, 1975, с. 117
  6. Дзядык, 1977, с. 74
  7. Лоран, 1975, с. 112
  8. Дзядык, 1977, с. 76-77

Литература[править | править вики-текст]

  • DeVore R. A., Lorentz G. G. Constructive Approximation. — 1993.
  • Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся ВТУЗов. — 1980.
  • Дзядык В. К. Введение в теорию равномерного приближения функций полиномами. — 1977.
  • Лоран П.-Ж. Аппроксимация и оптимизация. — 1975.
  • Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. — 1978.
  • Ремез Е. Я. Основы численных методов чебышёвского приближения. — 1969.