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

Алгоритм Ремеза или алгоритм обмена Ремеза , опубликованный Евгением Яковлевичем Ремезом в 1934 году, представляет собой итерационный алгоритм, используемый для поиска простых приближений к функциям, в частности, приближений функциями в пространстве Чебышева , лучшими в смысле равномерной нормы L _∞ . Его иногда называют алгоритмом Ремеса или алгоритмом Реме .

Типичным примером пространства Чебышева является подпространство полиномов Чебышёва порядка n в пространстве действительных функций на интервале C непрерывных [ a , b ]. Полином наилучшего приближения в данном подпространстве определяется как тот, который минимизирует максимальную абсолютную разницу между полиномом и функцией. В этом случае вид решения уточняется теоремой об эквиколебаниях .

Процедура

Алгоритм Ремеза начинается с функции $f$ быть аппроксимированным и набором $X$ из $n+2$ точки отбора проб $x_{1},x_{2},...,x_{n+2}$ в интервале аппроксимации обычно это экстремумы полинома Чебышева, линейно отображаемые в интервале. Шаги:

• Решите линейную систему уравнений

$b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (где $i=1,2,...n+2$),

для неизвестных $b_{0},b_{1}...b_{n}$ и Э. ​

• Используйте $b_{i}$ в качестве коэффициентов для формирования многочлена $P_{n}$.
• Найдите набор $M$ точек локальной максимальной ошибки $|P_{n}(x)-f(x)|$.
• Если ошибки на каждом $m\in M$ равны по величине и чередуются по знаку, то $P_{n}$ – полином минимаксной аппроксимации. Если нет, замените $X$ с $M$ и повторите действия, описанные выше.

Результат называется полиномом наилучшего приближения или алгоритмом минимаксной аппроксимации .

Обзор технических особенностей реализации алгоритма Ремеза дан У. Фрейзером.

Выбор инициализации

Узлы Чебышева часто выбираются для начального приближения из-за их роли в теории полиномиальной интерполяции. Для инициализации задачи оптимизации для функции f интерполянтом Лагранжа L _n ( f ) можно показать, что это начальное приближение ограничено

$\lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert$

при этом норма или константа Лебега интерполяционного оператора Лагранжа L _n узлов ( t ₁ , ..., t _{n + 1} ) равна

$\lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),$

T — нули полиномов Чебышева, а функции Лебега —

$\lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}.$

Теодор А. Килгор, Карл де Бур и Аллан Пинкус доказал, что существует уникальный t _i для каждого L _n , хотя это не известно явно для (обычных) полиномов. Сходным образом, ${\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)$, а оптимальность выбора узлов можно выразить как ${\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.$

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

${\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}$

( γ — постоянная Эйлера – Маскерони ) с

$0<\alpha _{n}<{\frac {\pi }{72n^{2}}}$ для $n\geq 1,$

и верхняя граница

${\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1$

Лев Брутман получил оценку для $n\geq 3$, и ${\hat {T}}$ являющиеся нулями расширенных полиномов Чебышева:

${\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1}{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\approx 0.201.$

Рюдигер Гюнттнер получено из более точной оценки для $n\geq 40$

${\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.$

Подробное обсуждение

В этом разделе представлена ​​дополнительная информация о шагах, описанных выше. В этом разделе индекс i изменяется от 0 до n +1.

Шаг 1: Учитывая $x_{0},x_{1},...x_{n+1}$, решим линейную систему n +2 уравнений

$b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (где $i=0,1,...n+1$),

для неизвестных $b_{0},b_{1},...b_{n}$ и Э. ​

Должно быть ясно, что $(-1)^{i}E$ в этом уравнении имеет смысл только в том случае, если узлы $x_{0},...,x_{n+1}$ упорядочены . либо строго по возрастанию, либо строго по убыванию Тогда эта линейная система имеет единственное решение. (Как известно, не каждая линейная система имеет решение.) Кроме того, решение можно получить, используя только $O(n^{2})$ арифметические операции, в то время как стандартный решатель из библиотеки взял бы $O(n^{3})$ операции. Вот простое доказательство:

Вычислите стандартный n-й степени интерполянт $p_{1}(x)$ к $f(x)$ в первых n +1 узлах, а также стандартный n-й интерполянт степени $p_{2}(x)$ по ординатам $(-1)^{i}$

$p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.$

Для этого каждый раз используйте интерполяционную формулу Ньютона с разделеннымразличия порядка $0,...,n$ и $O(n^{2})$ арифметические операции.

Полином $p_{2}(x)$ имеет i -й ноль между $x_{i-1}$ и $x_{i},\ i=1,...,n$, и, следовательно, никаких дополнительных нулей между $x_{n}$ и $x_{n+1}$: $p_{2}(x_{n})$ и $p_{2}(x_{n+1})$ имеют тот же знак $(-1)^{n}$.

Линейная комбинация $p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E$ также является полиномом степени n и

$p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.$

Это то же самое, что и уравнение выше для $i=0,...,n$ и для любого выбора E .То же уравнение для i = n +1 имеет вид

$p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E$ требует специального рассуждения: решено для переменной E , это определение E и :

$E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.$

Как упоминалось выше, два слагаемых в знаменателе имеют одинаковый знак: E и, таким образом, $p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}$ всегда четко определены.

Ошибка в заданных n +2 упорядоченных узлах поочередно положительна и отрицательна, поскольку

$p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.$

Теорема де Ла Валле Пуссен утверждает, что при этом условии не существует полинома степени n с ошибкой меньше, чем E . Действительно, если бы такой полином существовал, назовем его ${\tilde {p}}(x)$, то разница $p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))$ все равно будет положительным/отрицательным в узлах n +2 $x_{i}$ и, следовательно, иметь не менее n +1 нулей, что невозможно для многочлена степени n .Таким образом, это E является нижней границей минимальной ошибки, которая может быть достигнута с помощью полиномов степени n .

Шаг 2 меняет обозначение с $b_{0}+b_{1}x+...+b_{n}x^{n}$ к $p(x)$.

Шаг 3 улучшает входные узлы $x_{0},...,x_{n+1}$ и их ошибки $\pm E$ следующее.

В каждом P-регионе текущий узел $x_{i}$ заменяется локальным максимайзером ${\bar {x}}_{i}$ и в каждой N-области $x_{i}$ заменяется локальным минимизатором. (Ожидать ${\bar {x}}_{0}$ в А , ${\bar {x}}_{i}$ около $x_{i}$, и ${\bar {x}}_{n+1}$ в B. ) Никакой высокой точности здесь не требуется,стандартного поиска по строке с парой квадратичных подгонок должно быть достаточно. (Видеть )

Позволять $z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})$. Каждая амплитуда $|z_{i}|$ больше или E. равно Теорема Валле Пуссена и ее доказательство.обратиться к $z_{0},...,z_{n+1}$ с $\min\{|z_{i}|\}\geq E$ как новыйнижняя граница наилучшей возможной ошибки с полиномами степени n .

Более того, $\max\{|z_{i}|\}$ пригодится в качестве очевидной верхней границы наилучшей возможной ошибки.

Шаг 4: С $\min \,\{|z_{i}|\}$ и $\max \,\{|z_{i}|\}$ в качестве нижней и верхней границы наилучшей возможной ошибки аппроксимации, имеется надежный критерий остановки: повторять шаги до тех пор, пока $\max\{|z_{i}|\}-\min\{|z_{i}|\}$ достаточно мала или уже не уменьшается. Эти границы указывают на прогресс.

Варианты

В литературе представлены некоторые модификации алгоритма. К ним относятся:

• Замена более чем одной точки выборки местоположениями ближайших максимальных абсолютных различий.
• Замена всех точек выборки на одну итерацию с расположением всех знакопеременных максимальных различий.
• Использование относительной ошибки для измерения разницы между приближением и функцией, особенно если приближение будет использоваться для вычисления функции на компьютере, использующем с плавающей запятой ; арифметику
• Включая ограничения точки с нулевой ошибкой.
• Вариант Фрейзера-Харта, используемый для определения наилучшего рационального приближения Чебышева.

См. также

• Лемма Адамара
• Ряд Лорана – Степенной ряд с отрицательными степенями.
• Аппроксимант Паде - «лучшее» приближение функции рациональной функцией заданного порядка.
• Серия Newton – дискретный аналог производных страниц, отображающих краткие описания целей перенаправления.
• Теория приближений - Теория получения приемлемо близких неточных математических расчетов.
• Аппроксимация функции - аппроксимация произвольной функции хорошо работающей.

Внешние ссылки

• Минимаксные приближения и алгоритм Ремеза , базовая глава в документации Boost Math Tools со ссылкой на реализацию на C++.
• Введение в ЦСП
• Аартс, Рональд М .; Бонд, Чарльз; Мендельсон, Фил и Вайсштейн, Эрик В. «Алгоритм Ремеза» . Математический мир .