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

Алгоритм Ремеза (также алгоритм замены Ремеза) — это итеративный алгоритм равномерного аппроксимирования функций 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