Interested Article - Алгоритм Ремеза
- 2020-05-18
- 2
Алгоритм Ремеза (также алгоритм замены Ремеза) — это итеративный алгоритм равномерного аппроксимирования функций f ∊ C[ a , b ], основанный на теореме П. Л. Чебышёва об альтернансе. Предложен Е. Я. Ремезом в 1934 году .
Алгоритм Ремеза применяется при проектировании КИХ-фильтров .
Математические основания
Теорема Чебышёва
Теоретической основой алгоритма Ремеза является следующая теорема .
Для того, чтобы некоторый многочлен степени не выше был многочленом, наименее уклоняющимся от , необходимо и достаточно, чтобы на нашлась по крайней мере одна система из точек в которых разность :
- поочерёдно принимает значения разных знаков,
- достигает по модулю наибольшего на значения.
Такая система точек называется чебышёвским альтернансом .
П. Л. Чебышёв , 1854
Теорема Валле-Пуссена
Пусть E n — величина наилучшего приближения функции f ( x ) многочленами степени n . Оценку E n снизу даёт следующая теорема :
Если для функции f ∊ C[ a , b ] некоторый многочлен P ( x ) степени n обладает тем свойством, что разность f ( x ) - P ( x ) на некоторой системе из n + 2 упорядоченных точек x i принимает значения с чередующимися знаками, то
Ш.-Ж. Валле-Пуссен, 1919
Алгоритм
Рассмотрим систему функций , последовательность точек и будем искать аппроксимирующий многочлен
-
- .
-
Решаем
систему линейных уравнений
относительно
и
:
- Находим точку такую, что .
- Заменяем в X одну из точек на ξ таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки x i были упорядочены на каждой итерации .
- Повторяем все шаги с начала до тех пор, пока не будет | d | = D .
На втором шаге мы можем искать не одну точку ξ , а множество Ξ точек, в которых достигаются локальные максимумы | f — P |. Если все ошибки в точках множества Ξ одинаковы по модулю и чередуются по знаку, то P — минимаксный многочлен. Иначе заменяем точки из X на точки из Ξ и повторяем процедуру заново.
Выбор начальных точек
В качестве начальной последовательности X можно выбирать точки, равномерно распределённые на [ a , b ]. Целесообразно также брать точки :
Модификация
Если аппроксимирующая функция ищется в виде многочлена, то вместо решения системы на первом шаге алгоритма, можно воспользоваться следующим методом :
- Находим многочлен q ( x ) степени n+1 такой, что q ( x i ) = f ( x i ) (задача интерполяции ).
- Находим также многочлен q * ( x ) степени n+1 такой, что q * ( x i ) = (-1) i .
- Выбирая d так, чтобы многочлен P ( x ) ≡ q ( x ) — d q * ( x ) имел степень n , получаем P ( x i ) + (-1) i d = f ( x i ).
Дальше повторяются шаги по основной схеме.
Условие остановки
Так как по теореме Валле-Пуссена | d | ≤ E n ( f ) ≤ D , то условием остановки алгоритма может быть D — | d | ≤ ε для некоторого наперёд заданного ε .
Сходимость
Алгоритм Ремеза сходится со скоростью геометрической прогрессии в следующем смысле :
Для любой функции f ∊ C[ a , b ] найдутся числа A > 0 и 0 < q < 1 такие, что максимальные уклонения от функции f ( x ) полиномов , построенных по этому алгоритму, будут удовлетворять неравенствам
где E n ( f ) — величина наилучшего приближения на [ a , b ] функции f ( x ) при помощи полиномов P n ( x ).
Пример
- f ( x ) = e x , n = 1, P ( x ) = a x + b .
Шаг 1. |
|
|||||||||
Решение системы даёт
P
= 1.175
x
+ 1.272,
d
= 0.272.
D = max|e ξ - P ( ξ )| = 0.286 при ξ = 0.16. |
||||||||||
Шаг 2. |
|
|||||||||
Решение системы даёт
P
= 1.175
x
+ 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
- , с. 157.
- , с. 12.
- , с. 33.
- , с. 117.
- , с. 74.
- , с. 112.
- , с. 76-77.
Литература
- 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 // //
- 2020-05-18
- 2