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

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

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

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

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

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

Для того, чтобы некоторый многочлен P*(x) степени не выше n был многочленом, наименее уклоняющимся от f ∊ C[a,b], необходимо и достаточно, чтобы на [a,b] нашлась по крайней мере одна система из n + 2 точек xi, a ≤ x0 < x1 < … < xn+1 ≤ b, в которых разность f(x) - P*(x): поочерёдно принимает значения разных знаков, достигает по модулю наибольшего на [a,b] значения. Такая система точек называется чебышёвским альтернансом. П. Л. Чебышёв, 1854

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

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

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

Рассмотрим систему n + 1 функций Φ = {φ0,…,φn}, последовательность n + 2 точек X = a ≤ x0 < x1 < … < xn+1 ≤ b и будем искать аппроксимирующий многочлен .

1. Решаем систему линейных уравнений относительно aj и d:
   

2. Находим точку ξ такую, что D = |f(ξ) — P(ξ)| = max.

3. Заменяем в X одну из точек на ξ таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки xi были упорядочены на каждой итерации.

4. Повторяем все шаги с начала до тех пор, пока не будет |d| = D.

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

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

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

1. Находим многочлен q(x) степени n такой, что q(xi) = f(xi) (задача интерполяции).

2. Находим также многочлен q*(x) степени n такой, что q*(xi) = (-1)i.

3. Выбирая d так, чтобы многочлен P(x) ≡ q(x) — d q*(x) имел степень n-1, получаем P(xi) + (-1)id = f(xi).

Дальше повторяются шаги по основной схеме.

Так как по теореме Валле-Пуссена |d| ≤ En(f) ≤ D, то условием остановки алгоритма может быть D — |d| ≤ ε для некоторого наперёд заданного ε.

А.Р. сходится со скоростью геометрической прогрессии в следующем смысле:

Для любой функции f ∊ C[a,b] найдутся числа A > 0 и 0 < q < 1 такие, что максимальные уклонения от функции f(x) полиномов , построенных по этому алгоритму, будут удовлетворять неравенствам где En(f) — величина наилучшего приближения на [a,b] функции f(x) при помощи полиномов Pn(x). Е. Я. Ремез, 1957

Пример:

f(x) = ex, n = 1, P(x) = a x+b.

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

Литература:

• DeVore R. A., Lorentz G. G. Constructive Approximation — 1993.

• Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся ВТУЗов — 1980.

• Дзядык В. К. Введение в теорию равномерного приближения функций полиномами — 1977.

• Лоран П.-Ж. Аппроксимация и оптимизация — 1975.

• Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов — 1978.