Алгоритм Ремеза (Glikjnmb Jyby[g)

Перейти к навигации Перейти к поиску

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

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

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

[править | править код]

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

[править | править код]

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

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

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

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


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

[править | править код]

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

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


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

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

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

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

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

[править | править код]

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

Модификация

[править | править код]

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

  1. Находим многочлен q(x) степени n+1 такой, что q(xi) = f(xi) (задача интерполяции).
  2. Находим также многочлен q*(x) степени n+1 такой, что q*(xi) = (-1)i.
  3. Выбирая 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) полиномов , построенных по этому алгоритму, будут удовлетворять неравенствам

где 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
Решение системы даёт 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.

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

Примечания

[править | править код]
  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. Рабинер, 1978, с. 157.
  3. Дзядык, 1977, с. 12.
  4. Дзядык, 1977, с. 33.
  5. Лоран, 1975, с. 117.
  6. Дзядык, 1977, с. 74.
  7. Лоран, 1975, с. 112.
  8. Дзядык, 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