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

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

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

Процедура

Запускается Алгоритм Ремеза с функцией , чтобы быть аппроксимированы и набором из точек выборки в интервале аппроксимации, как правило , экстремумы Чебышев полинома линейно сопоставляются с интервалом. Шаги следующие: ${\ 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 я = 1,2, ... п + 2}$

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

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

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

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

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

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

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

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

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

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

${\ displaystyle \ 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 , хотя это не известно явно для (обычных) многочленов. Аналогично, и оптимальность выбора узлов может быть выражена как${\ displaystyle {\ underline {\ Lambda}} _ {n} (T) = \ min _ {- 1 \ leq x \ leq 1} \ lambda _ {n} (T; x)}$${\ displaystyle {\ overline {\ Lambda}} _ {n} - {\ underline {\ Lambda}} _ {n} \ geq 0.}$

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

${\ displaystyle {\ overline {\ Lambda}} _ {n} (T) = {\ frac {2} {\ pi}} \ log (n + 1) + {\ frac {2} {\ pi}} \ слева (\ gamma + \ log {\ frac {8} {\ pi}} \ right) + \ alpha _ {n + 1}}$

( Γ является постоянной Эйлера-Mascheroni ) с

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

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

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

Лев Брутман получил оценку и, являющихся нулями расширенных многочленов Чебышева: ${\ Displaystyle п \ geq 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} (3 \ pi / 16)}} - {\ frac {2} {\ pi}} (\ gamma - \ log \ pi) \ приблизительно 0,201.}$

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

${\ displaystyle {\ overline {\ Lambda}} _ {n} ({\ hat {T}}) - {\ underline {\ Lambda}} _ {n} ({\ hat {T}}) <0,0196.}$

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

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

Шаг 1: Решите линейную систему из n +2 уравнений ${\ displaystyle x_ {0}, x_ {1}, ... x_ {n + 1}}$

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

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

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

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

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

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

I-й ноль многочлена находится между и , и, таким образом, никакие другие нули между и : и не имеют того же знака . ${\ Displaystyle p_ {2} (х)}$${\ 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.}$

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

${\ 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}$и нуждается в особой аргументации: решается для переменных Е , то это определение из Й :

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

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

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

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

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

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

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

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

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

Варианты

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

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

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

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

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

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

использованная литература

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

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