Чебышевская и минимаксная аппроксимация

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

Definition

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

Scope

Эта тема охватывает наилучшую равномерную (минимаксную) аппроксимацию в максимальной норме, теорему Чебышева о равноколебании, роль и почти оптимальность полиномов Чебышева и чебышевской интерполяции, а также алгоритм обмена Ремеза для вычисления минимаксных полиномиальных и рациональных аппроксимаций.

Core questions

• Что характеризует наилучшую равномерную аппроксимацию и почему она уникальна?
• Почему полиномы Чебышева играют центральную роль в почти оптимальной полиномиальной аппроксимации?
• Как алгоритм Ремеза итеративно вычисляет истинную минимаксную аппроксимацию?
• Когда минимаксное приближение предпочтительнее приближения методом наименьших квадратов и какова его вычислительная стоимость?

Key theories

Теорема о равноколебании

Полином степени не более n является наилучшей равномерной аппроксимацией непрерывной функции тогда и только тогда, когда его ошибка достигает своей максимальной величины с чередующимися знаками по крайней мере в n+2 точках; эта характеристика делает наилучшую аппроксимацию уникальной и вычислимой.

Почти оптимальность чебышевской аппроксимации

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

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

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

Mechanisms

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

Clinical relevance

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

History

Теория берет начало в исследованиях Чебышева XIX века по наилучшей равномерной аппроксимации и принципу равноколебания; Евгений Ремез разработал свой алгоритм обмена в 1930-х годах, а вычисления на основе Чебышева стали практической основой численного программного обеспечения в конце XX века, в частности, благодаря бездифференциальной чебышевской технологии в современных системах.

Key figures

• Pafnuty Chebyshev
• Evgeny Remez
• Lloyd N. Trefethen

Seminal works

• trefethen2013
• powell1981
• cheney1966

Frequently asked questions

Что интуитивно означает равноколебание?

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

Почему используется чебышевская интерполяция вместо точного минимаксного полинома?

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