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

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

Алгоритм Ремеза применяется при проектировании КИХ-фильтровШаблон:Sfn.

Математические основания

Теорема Чебышёва

Теоретической основой алгоритма Ремеза является следующая теоремаШаблон:Sfn. Шаблон:Теорема

Теорема Валле-Пуссена

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

Алгоритм

Рассмотрим систему $n+1$ функций $\mathit{𝛷}=\{{\phi }_0,\dots ,{\phi }_n\}$, последовательность $n+2$ точек $X=\{x_i\},$ $a\le x_0<x_1<\dots <x_{n+1}\le b,$ и будем искать аппроксимирующий многочлен

$P_X=\sum _0^n{a}_j{\phi }_j$.

1. Решаем систему линейных уравнений относительно $a_j$ и $d$:
   $\sum _{j=0}^n{a}_j{\phi }_j(x_i)+(-1{)}^{i}d=f(x_i),i=0,1,\dots ,n.$
2. Находим точку $\xi$ такую, что $D=f(\xi )-P(\xi )=\max$.
3. Заменяем в X одну из точек на ξ таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки x_i были упорядочены на каждой итерацииШаблон:Sfn.
4. Повторяем все шаги с начала до тех пор, пока не будет |d| = D.

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

Выбор начальных точек

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

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

Модификация

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

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

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

Условие остановки

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

Сходимость

Алгоритм Ремеза сходится со скоростью геометрической прогрессии в следующем смыслеШаблон:Sfn: Шаблон:Теорема

Пример

f(x) = e^x, n = 1, P(x) = a x+b.

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Nadaniela Egidi, Lorella Fatone, Luciano Misici. A New Remez-Type Algorithm for Best Polynomial Approximation // Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Italy, June 15–21, 2019, Revised Selected Papers, Part I, Jun 2019, Pages 56–69 doi // Program NUMTA 2019, June 19, Wednesday morning (9.00): Room 1 // Book of Abstracts, page 50 // books google, pages 56-57, 60-64, 67-69