Меню Главная Случайная статья Настройки Алгоритм Ремеза Материал из https://ru.wikipedia.org Алгоритм Ремеза (также алгоритм замены Ремеза) — это итеративный алгоритм равномерного аппроксимирования функций f C[a,b], основанный на теореме П. Л. Чебышёва об альтернансе. Предложен Е. Я. Ремезом в 1934 году[1]. Алгоритм Ремеза применяется при проектировании КИХ-фильтров[2]. Содержание 1 Математические основания 1.1 Теорема Чебышёва 1.2 Теорема Валле-Пуссена 2 Алгоритм 2.1 Выбор начальных точек 2.2 Модификация 2.3 Условие остановки 3 Сходимость 4 Пример 5 См. также 6 Примечания 7 Литература Математические основания Теорема Чебышёва Теоретической основой алгоритма Ремеза является следующая теорема[3]. Для того, чтобы некоторый многочлен ${\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)}$: поочерёдно принимает значения разных знаков, достигает по модулю наибольшего на ${\displaystyle [a,\ b]}$ значения. Такая система точек называется чебышёвским альтернансом. Теорема Валле-Пуссена Пусть En — величина наилучшего приближения функции f(x) многочленами степени n. Оценку En снизу даёт следующая теорема[4]: Если для функции f C[a,b] некоторый многочлен P(x) степени n обладает тем свойством, что разность f(x) - P(x) на некоторой системе из n + 2 упорядоченных точек xi принимает значения с чередующимися знаками, то ${\displaystyle E_{n}(f)\geq \min |f(x_{i})-P(x_{i})|.}$ Алгоритм Рассмотрим систему ${\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}}$. Решаем систему линейных уравнений относительно ${\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.}$ Находим точку ${\displaystyle \xi }$ такую, что ${\displaystyle D=f(\xi )-P(\xi )=\max }$. Заменяем в X одну из точек на таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки xi были упорядочены на каждой итерации[5]. Повторяем все шаги с начала до тех пор, пока не будет |d| = D. На втором шаге мы можем искать не одну точку , а множество точек, в которых достигаются локальные максимумы |f — P|. Если все ошибки в точках множества одинаковы по модулю и чередуются по знаку, то P — минимаксный многочлен. Иначе заменяем точки из X на точки из и повторяем процедуру заново. Выбор начальных точек В качестве начальной последовательности X можно выбирать точки, равномерно распределённые на [a,b]. Целесообразно также брать точки[6]: ${\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.}$ Модификация Если аппроксимирующая функция ищется в виде многочлена, то вместо решения системы на первом шаге алгоритма, можно воспользоваться следующим методом[7]: Находим многочлен q(x) степени n+1 такой, что q(xi) = f(xi) (задача интерполяции). Находим также многочлен q*(x) степени n+1 такой, что q*(xi) = (-1)i. Выбирая 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) полиномов ${\displaystyle P_{n}^{(k)}(x)}$, построенных по этому алгоритму, будут удовлетворять неравенствам ${\displaystyle \max |f(x)-P_{n}^{(k)}(x)|-E_{n}(f)\leq 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 ${\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.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 ${\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.175x + 1.265, d = 0.279. D = max|e-P()| = 0.279 при = 0.16. Так как в пределах данной точности получили ту же самую точку, то найденный многочлен следует рассматривать как наилучшее приближение первой степени функции ex. См. также Аппроксимационная теорема Вейерштрасса Примечания E. Ya. Remez (1934). Sur le calful effectif des polynmes 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. 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