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

В Алгоритм Ремеза или же Алгоритм обмена Remez, опубликовано Евгений Яковлевич Ремез в 1934 году представляет собой итерационный алгоритм, используемый для поиска простых приближений к функциям, в частности приближения функциями из Чебышевское пространство это лучшие в единая норма L_∞ смысл.^[1]

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

Процедура

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

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

${displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$ (куда ${displaystyle i=1,2,...n+2}$),

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

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

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

Обзор технических особенностей реализации алгоритма Ремеза дан В. Фрейзером.^[2]

О выборе инициализации

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

${displaystyle lVert f-L_{n}(f)Vert _{infty }leq (1+lVert L_{n}Vert _{infty })inf _{pin P_{n}}lVert f-pVert }$

с нормой или Постоянная Лебега оператора интерполяции Лагранжа L_п узлов (т₁, ..., т_п + 1) существование

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

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

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

Теодор А. Килгор,^[3] Карл де Бур и Аллан Пинкус^[4] доказал, что существует единственная т_я для каждого L_п, хотя явно не известен для (обычных) многочленов. По аналогии, ${displaystyle {underline {Lambda }}_{n}(T)=min _{-1leq xleq 1}lambda _{n}(T;x)}$, а оптимальность выбора узлов может быть выражена как ${displaystyle {overline {Lambda }}_{n}-{underline {Lambda }}_{n}geq 0.}$

Для чебышевских узлов, что обеспечивает субоптимальный, но аналитически явный выбор, асимптотическое поведение известно как^[5]

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

(γ будучи Константа Эйлера – Маскерони ) с

${displaystyle 0<alpha _{n}<{frac {pi }{72n^{2}}}}$ за ${displaystyle ngeq 1,}$

и верхняя граница^[6]

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

Лев Брутман^[7] получил оценку для ${displaystyle ngeq 3}$, и ${displaystyle {hat {T}}}$ - нули развернутых полиномов Чебышева:

${displaystyle {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}(3pi /16)}}-{frac {2}{pi }}(gamma -log pi )approx 0.201.}$

Рюдигер Гюнтнер^[8] полученный из более точной оценки для ${displaystyle ngeq 40}$

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

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

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

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

${displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$ (куда ${displaystyle i=0,1,...n+1}$),

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

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

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

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

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

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

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

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

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

${displaystyle 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:

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

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

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

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

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

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

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

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

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

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

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

Варианты

Иногда более одной точки выборки заменяется одновременно местоположениями ближайших максимальных абсолютных разностей.

Иногда все точки выборки заменяются за одну итерацию с указанием местоположения всех, чередующихся знаков, максимальных различий.^[10]

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

Иногда ограничения точки с нулевой ошибкой включаются в модифицированный алгоритм обмена Ремеза.^[10]

Смотрите также

• Теория приближений

Рекомендации

1. Э. Я. Ремез, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Математика. Харьков 10, 41 (1934);
   "Sur un procédé convergent d'approximations, péterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
   "Sur le Calculated Effectiv des Polynômes d'approximation des Tschebyscheff", Compt. Ренд. Акад. Sc. 199, 337 (1934).
2. Фрейзер, В. (1965). «Обзор методов вычисления минимаксных и почти минимаксных полиномиальных приближений для функций одной независимой переменной». J. ACM. 12: 295. Дои:10.1145/321281.321282.
3. Килгор Т.А. (1978). «Характеристика интерполяционной проекции Лагранжа с минимальной нормой Чебычева». J. Прибл. Теория. 24: 273. Дои:10.1016/0021-9045(78)90013-8.
4. de Boor, C .; Пинкус, А. (1978). «Доказательство гипотез Бернштейна и Эрдеша об оптимальных узлах для полиномиальной интерполяции». Журнал теории приближений. 24: 289. Дои:10.1016 / 0021-9045 (78) 90014-Х.
5. Luttmann, F.W .; Ривлин, Т. Дж. (1965). «Некоторые численные эксперименты в теории полиномиальной интерполяции». IBM J. Res. Dev. 9: 187. Дои:10.1147 / rd.93.0187.
6. Т. Ривлин, "Константы Лебега для полиномиальной интерполяции", в сб. Труды Междунар. Конф. по функциональному анализу и его применению, под редакцией Г. Г. Гарнье и другие. (Springer-Verlag, Берлин, 1974), стр. 422; Многочлены Чебышева (Wiley-Interscience, Нью-Йорк, 1974).
7. Брутман, Л. (1978). «О функции Лебега для полиномиальной интерполяции». SIAM J. Numer. Анальный. 15: 694. Дои:10.1137/0715046.
8. Гюнтнер, Р. (1980). «Оценка констант Лебега». SIAM J. Numer. Анальный. 17: 512. Дои:10.1137/0717043.
9. Дэвид Г. Люенбергер: Введение в линейное и нелинейное программирование, Издательство Addison-Wesley Publishing Company 1973.
10. 2/73 «Оптимизация систем с ограниченной полосой пропускания» - Г. К. Темес, Ф. К. Маршалл и В. Барсилон. Труды IEEE.

внешняя ссылка

• Метод Ремеза, Boost Documentation
• Введение в DSP
• Аартс, Рональд М .; Бонд, Чарльз; Мендельсон, Фил и Вайсштейн, Эрик В. «Алгоритм Ремеза». MathWorld.