Русская Википедия:Алгоритм Ремеза

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

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

Алгоритм

Рассмотрим систему <math>n + 1</math> функций <math>\mathbf {\varPhi} = \{\varphi_0, \dots, \varphi_n\}</math>, последовательность <math>n + 2</math> точек <math>X=\{x_i\},</math> <math>a\le x_0 < x_1 < \dots < x_{n+1} \le b,</math> и будем искать аппроксимирующий многочлен

<math>P_X = \sum_0^n a_j\varphi_j</math>.
  1. Решаем систему линейных уравнений относительно <math>a_j</math> и <math>d</math>:
    <math>\sum_{j=0}^n a_j\varphi_j(x_i) + (-1)^i d = f(x_i), \quad i=0,1,\ldots,n.</math>
  2. Находим точку <math>\xi</math> такую, что <math>D = f(\xi) -P(\xi) = \max</math>.
  3. Заменяем в X одну из точек на ξ таким образом, чтобы знак f — P чередовался в точках новой последовательности. На практике следят только за тем, чтобы точки xi были упорядочены на каждой итерацииШаблон:Sfn.
  4. Повторяем все шаги с начала до тех пор, пока не будет |d| = D.

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

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

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

<math>x_i = \frac{a+b}{2} + \frac{b-a}{2} \cos\left(\frac{\pi i}{n+1}\right), \quad i=0,\ldots,n+1.</math>

Модификация

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

  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| ≤ ε для некоторого наперёд заданного ε.

Сходимость

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

Пример

f(x) = ex, n = 1, P(x) = a x+b.
Шаг 1.
X1 −1 0 1
f(xi) 0.368 1.000 2.718
<math>

\begin{cases} 

   ({-}1)a + b + d = 0.368 \\
   (0)a + b - d = 1.000\\
   (1)a + b + d = 2.718

\end{cases} </math>

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

\begin{cases} 

   ({-}1)a + b + d = 0.368 \\
   (0.16)a + b - d = 1.174\\
   (1)a + b + d = 2.718

\end{cases} </math>

Решение системы даёт 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
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Ремеза&oldid=8940168