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

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

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

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

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

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

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

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

Алгоритм

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

Решаем систему линейных уравнений относительно aj и d:
∑ j = 0 n a j φ j ( x i ) + ( − 1 ) i d = f ( x i ) , i = 0 , 1 , … , n . {displaystyle sum _{j=0}^{n}a_{j}varphi _{j}(x_{i})+(-1)^{i}d=f(x_{i}),quad i=0,1,ldots ,n.}

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

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

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

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

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

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

x i = a + b 2 + b − a 2 cos ⁡ ( π i n + 1 ) , i = 0 , … , n + 1. {displaystyle x_{i}={frac {a+b}{2}}+{frac {b-a}{2}}cos left({frac {pi i}{n+1}} ight),quad i=0,ldots ,n+1.}

Модификация

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

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

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

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

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

Условие остановки

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

Сходимость

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

Пример

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

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