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

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

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

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

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

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

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

поочерёдно принимает значения разных знаков,

достигает по модулю наибольшего на $[a,\ b]$ значения.

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

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

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

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

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

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

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

Алгоритм

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

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

.

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

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

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

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

Так как по теореме Валле-Пуссена |d| ≤ E_n(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)\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	0	1
f(x_i)	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.
D = max|e^ξ-P(ξ)| = 0.286 при ξ = 0.16.

Шаг 2.

X₂	−1	0.16	1
f(x_i)	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.
D = max|e^ξ-P(ξ)| = 0.279 при ξ = 0.16.

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

См. также

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

Примечания

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

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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

[_2571641623d25825-2] Рабинер, 1978, с. 157.

[_46c9f08b1a4a3f4f-3] Дзядык, 1977, с. 12.

[_46c9ee8b1a4a3c24-4] Дзядык, 1977, с. 33.

[_3c6414ff5c9a893f-5] Лоран, 1975, с. 117.

[_46c9ea8b1a4a357f-6] Дзядык, 1977, с. 74.

[_3c6414ff5c9a893a-7] Лоран, 1975, с. 112.

[_4e58dccc681aaafc-8] Дзядык, 1977, с. 76-77.