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

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

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

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

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

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

Для того, чтобы некоторый многочлен [math]\displaystyle{ P^*(x) }[/math] степени не выше [math]\displaystyle{ n }[/math] был многочленом, наименее уклоняющимся от [math]\displaystyle{ f\in C[a,b] }[/math], необходимо и достаточно, чтобы на [math]\displaystyle{ [a,b] }[/math] нашлась по крайней мере одна система из [math]\displaystyle{ n + 2 }[/math] точек [math]\displaystyle{ \{x_i\}, }[/math] [math]\displaystyle{ a\le x_0 \lt x_1 \lt \dots \lt x_{n+1} \le b, }[/math] в которых разность [math]\displaystyle{ f(x) - P^*(x) }[/math]: поочерёдно принимает значения разных знаков, достигает по модулю наибольшего на [math]\displaystyle{ [a,\ b] }[/math] значения. Такая система точек называется чебышёвским альтернансом. П. Л. Чебышёв, 1854

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

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

Если для функции f ∊ C[a,b] некоторый многочлен P(x) степени n обладает тем свойством, что разность f(x) - P(x) на некоторой системе из n + 2 упорядоченных точек xi принимает значения с чередующимися знаками, то [math]\displaystyle{ E_n(f) \ge \min|f(x_i)-P(x_i)|. }[/math] Ш.-Ж. Валле-Пуссен, 1919

Алгоритм

Рассмотрим систему [math]\displaystyle{ n + 1 }[/math] функций [math]\displaystyle{ \mathbf {\varPhi} = \{\varphi_0, \dots, \varphi_n\} }[/math], последова-тельность [math]\displaystyle{ n + 2 }[/math] точек [math]\displaystyle{ X=\{x_i\}, }[/math] [math]\displaystyle{ a\le x_0 \lt x_1 \lt \dots \lt x_{n+1} \le b, }[/math] и будем искать аппроксимирующий многочлен

[math]\displaystyle{ P_X = \sum_0^n a_j\varphi_j }[/math].

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

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

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

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

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

Модификация

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

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| ≤ ε для некоторого наперёд заданного ε.

Сходимость

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

Для любой функции f ∊ C[a,b] найдутся числа A > 0 и 0 < q < 1 такие, что максимальные уклонения от функции f(x) полиномов [math]\displaystyle{ P_n^{(k)}(x) }[/math], построенных по этому алгоритму, будут удовлетворять неравенствам [math]\displaystyle{ \max|f(x) - P_n^{(k)}(x)| - E_n(f) \le Aq^k, \quad k=1,2,\ldots, }[/math] где En(f) — величина наилучшего приближения на [a,b] функции f(x) при помощи полиномов Pn(x). Е. Я. Ремез, 1957

Пример

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

Шаг 1.	X1 −1 0 1 f(xi) 0.368 1.000 2.718	[math]\displaystyle{ \begin{cases} ({-}1)a + b + d = 0.368 \\ (0)a + b - d = 1.000\\ (1)a + b + d = 2.718 \end{cases} }[/math]
	Решение системы даёт 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	[math]\displaystyle{ \begin{cases} ({-}1)a + b + d = 0.368 \\ (0.16)a + b - d = 1.174\\ (1)a + b + d = 2.718 \end{cases} }[/math]
	Решение системы даёт P = 1.175x + 1.265, d = 0.279. D = max|eξ-P(ξ)| = 0.279 при ξ = 0.16.

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

См. также

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

Литература

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