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

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

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

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

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

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

Для того, чтобы некоторый многочлен степени не выше был многочленом, наименее уклоняющимся от , необходимо и достаточно, чтобы на нашлась по крайней мере одна система из точек в которых разность :

  1. поочерёдно принимает значения разных знаков,
  2. достигает по модулю наибольшего на значения.

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


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

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

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


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

Алгоритм

Рассмотрим систему функций , последовательность точек и будем искать аппроксимирующий многочлен

.
  1. Решаем систему линейных уравнений относительно и :
  2. Находим точку такую, что .
  3. Заменяем в X одну из точек на ξ таким образом, чтобы знак f P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки x i были упорядочены на каждой итерации .
  4. Повторяем все шаги с начала до тех пор, пока не будет | d | = D .

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

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

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

Модификация

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

  1. Находим многочлен q ( x ) степени n+1 такой, что q ( x i ) = f ( x i ) (задача интерполяции ).
  2. Находим также многочлен q * ( x ) степени n+1 такой, что q * ( x i ) = (-1) i .
  3. Выбирая 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.
X 1 −1 0 1
f ( x i ) 0.368 1.000 2.718
Решение системы даёт 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
Решение системы даёт P = 1.175 x + 1.265, d = 0.279.
D = max|e ξ - P ( ξ )| = 0.279 при ξ = 0.16.

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

См. также

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

Примечания

  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
  2. , с. 157.
  3. , с. 12.
  4. , с. 33.
  5. , с. 117.
  6. , с. 74.
  7. , с. 112.
  8. , с. 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 // //
Источник —

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