Алгоритм Ремеза (также алгоритм замены Ремеза) — это итеративный алгоритм равномерного аппроксимирования функций f ∊ C[a,b], основанный на теореме П. Л. Чебышёва об альтернансе. Предложен Е. Я. Ремезом в 1934 годуE. Ya. Remez (1934). Sur le calful effectif des polynômes d’approximation de Tschebyscheff. C.P. Paris 199, 337—340; Ch. 3:78.
Алгоритм Ремеза применяется при проектировании КИХ-фильтров.
Математические основания
Теорема Чебышёва Теоретической основой алгоритма Ремеза является следующая теорема.
Теорема Валле-Пуссена Пусть En — величина наилучшего приближения функции f(x) многочленами степени n. Оценку En снизу даёт следующая теорема:
Алгоритм Рассмотрим систему функций , последовательность точек и будем искать аппроксимирующий многочлен . Решаем систему линейных уравнений относительно и : Находим точку такую, что . Заменяем в X одну из точек на ξ таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки xi были упорядочены на каждой итерации. Повторяем все шаги с начала до тех пор, пока не будет |d| = D.
На втором шаге мы можем искать не одну точку ξ, а множество Ξ точек, в которых достигаются локальные максимумы |f — P|. Если все ошибки в точках множества Ξ одинаковы по модулю и чередуются по знаку, то P — минимаксный многочлен. Иначе заменяем точки из X на точки из Ξ и повторяем процедуру заново.
Выбор начальных точек В качестве начальной последовательности X можно выбирать точки, равномерно распределённые на [a,b]. Целесообразно также брать точки:
Модификация Если аппроксимирующая функция ищется в виде многочлена, то вместо решения системы на первом шаге алгоритма, можно воспользоваться следующим методом: Находим многочлен 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| ≤ ε для некоторого наперёд заданного ε.
Сходимость Алгоритм Ремеза сходится со скоростью геометрической прогрессии в следующем смысле:
Пример f(x) = ex, n = 1, P(x) = a x+b.
Шаг 1.
X1 −1 0 1 f(xi) 0.368 1.000 2.718 Решение системы даёт 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 Решение системы даёт P = 1.175x + 1.265, d = 0.279.D = max|eξ-P(ξ)| = 0.279 при ξ = 0.16.
Так как в пределах данной точности получили ту же самую точку, то найденный многочлен следует рассматривать как наилучшее приближение первой степени функции ex.
См. также Аппроксимационная теорема Вейерштрасса
Примечания
Литература
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
Категория:Численные методы Категория:Теория приближений Категория:Многочлены Категория:Цифровая обработка сигналов