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

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

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

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

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

Для того, чтобы некоторый многочлен ${\displaystyle P^{*}(x)}$ степени не выше ${\displaystyle n}$ был многочленом, наименее уклоняющимся от ${\displaystyle f\in C[a,b]}$ , необходимо и достаточно, чтобы на ${\displaystyle [a,b]}$ нашлась по крайней мере одна система из ${\displaystyle n+2}$ точек ${\displaystyle \{x_{i}\},}$ ${\displaystyle a\leq x_{0}<x_{1}<\dots <x_{n+1}\leq b,}$ в которых разность ${\displaystyle f(x)-P^{*}(x)}$ :

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

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

П. Л. Чебышёв , 1854

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

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

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

${\displaystyle E_{n}(f)\geq \min |f(x_{i})-P(x_{i})|.}$

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

Алгоритм

Рассмотрим систему ${\displaystyle n+1}$ функций ${\displaystyle \mathbf {\varPhi } =\{\varphi _{0},\dots ,\varphi _{n}\}}$ , последовательность ${\displaystyle n+2}$ точек ${\displaystyle X=\{x_{i}\},}$ ${\displaystyle a\leq x_{0}<x_{1}<\dots <x_{n+1}\leq b,}$ и будем искать аппроксимирующий многочлен

${\displaystyle P_{X}=\sum _{0}^{n}a_{j}\varphi _{j}}$ .

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

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

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

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

${\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.}$

Модификация

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

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 ) полиномов ${\displaystyle P_{n}^{(k)}(x)}$ , построенных по этому алгоритму, будут удовлетворять неравенствам

${\displaystyle \max |f(x)-P_{n}^{(k)}(x)|-E_{n}(f)\leq Aq^{k},\quad k=1,2,\ldots ,}$

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

Е. Я. Ремез , 1957

Пример

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

Шаг 1.	X 1 −1 0 1 f ( x i ) 0.368 1.000 2.718	${\displaystyle {\begin{cases}({-}1)a+b+d=0.368\\(0)a+b-d=1.000\\(1)a+b+d=2.718\end{cases}}}$
	Решение системы даёт P = 1.175 x + 1.272, d = 0.272. D = max|e ξ - P ( ξ )| = 0.286 при ξ = 0.16.
Шаг 2.	X 2 −1 0.16 1 f ( x i ) 0.368 1.174 2.718	${\displaystyle {\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.175 x + 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 . // Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Italy, June 15–21, 2019, , Jun 2019, Pages 56–69 // , June 19, Wednesday morning (9.00): Room 1 // //