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

Теория получения приемлемо близких неточных математических расчетов

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

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

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

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

Оптимальные многочлены

После выбора области определения (обычно интервала) и степени полинома сам полином выбирается таким образом, чтобы минимизировать ошибку в худшем случае. То есть, цель состоит в том, чтобы минимизировать максимальное значение , где P ( x ) — аппроксимирующий полином, f ( x ) — фактическая функция, а x изменяется в выбранном интервале. Для хорошо себя ведущих функций существует полином степени N , который приведет к кривой ошибок, которая колеблется вперед и назад между и в общей сложности N +2 раз, давая ошибку в худшем случае . Видно, что существует полином степени N , который может интерполировать N +1 точек на кривой. То, что такой полином всегда оптимален, утверждается теоремой о равноколебательности . Можно создать вымышленные функции f ( x ), для которых такого полинома не существует, но на практике это случается редко. ${\displaystyle \mid P(x)-f(x)\mid }$ ${\displaystyle +\varepsilon }$ ${\displaystyle -\varepsilon }$ ${\displaystyle \varepsilon }$

Например, графики, показанные справа, показывают ошибку аппроксимации log(x) и exp(x) для N  = 4. Красные кривые для оптимального полинома находятся на уровне , то есть они колеблются между и точно. В каждом случае число экстремумов равно N +2, то есть 6. Два из экстремумов находятся в конечных точках интервала, на левом и правом краях графиков. ${\displaystyle +\varepsilon }$ ${\displaystyle -\varepsilon }$

Ошибка P ( x ) −  f ( x ) для полинома уровня (красный) и для предполагаемого лучшего полинома (синий)

Чтобы доказать это в общем случае, предположим, что P — многочлен степени N , обладающий описанным свойством, то есть он порождает функцию ошибок, которая имеет N  + 2 экстремума, чередующихся знаков и равных величин. Красный график справа показывает, как может выглядеть эта функция ошибок при N  = 4. Предположим, что Q ( x ) (чья функция ошибок показана синим цветом справа) — другой многочлен степени N , который является лучшим приближением к f, чем P . В частности, Q ближе к f, чем P для каждого значения x _i , где встречается экстремум P − f , поэтому

${\displaystyle |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|.}$

Когда максимум P − f достигается при x _i , тогда

${\displaystyle Q(x_{i})-f(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=P(x_{i})-f(x_{i}),}$

И когда минимум P − f достигается при x _i , тогда

${\displaystyle f(x_{i})-Q(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=f(x_{i})-P(x_{i}).}$

Итак, как видно из графика, [ P ( x )  −f ( x )]−[ Q ( x )  −f ( x )] должны менять знак для N  +2 значений x _i . Но [ P ( x )  −f ( x )]−[ Q ( x )−f  ( x ) ] сводится к P ( x )  −Q ( x ), который является многочленом степени N. Эта функция меняет знак по крайней мере N +1 раз , поэтому по теореме о промежуточном значении она имеет N +1 нулей, что невозможно для многочлена степени N.

Чебышевское приближение

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

Если вычислить коэффициенты в разложении Чебышева для функции:

${\displaystyle f(x)\sim \sum _{i=0}^{\infty }c_{i}T_{i}(x)}$

а затем отсекаем ряд после члена, получаем полином N- й степени, приближающий f ( x ). ${\displaystyle T_{N}}$

Причина, по которой этот полином близок к оптимальному, заключается в том, что для функций с быстро сходящимися степенными рядами, если ряд обрезается после некоторого члена, общая ошибка, возникающая из-за обрезания, близка к первому члену после обрезания. То есть, первый член после обрезания доминирует над всеми последующими членами. То же самое верно, если разложение выполняется в терминах многочленов bucking. Если разложение Чебышева обрезается после , ошибка примет форму, близкую к кратной . Многочлены Чебышева обладают тем свойством, что они ровные — они колеблются между +1 и −1 в интервале [−1, 1]. имеет N +2 экстремумов уровня. Это означает, что ошибка между f ( x ) и ее разложением Чебышева до близка к функции уровня с N +2 экстремумами, поэтому она близка к оптимальному многочлену N -й степени. ${\displaystyle T_{N}}$ ${\displaystyle T_{N+1}}$ ${\displaystyle T_{N+1}}$ ${\displaystyle T_{N}}$

На графиках выше синяя функция ошибок иногда лучше (внутри) красной функции, но иногда хуже, что означает, что это не совсем оптимальный полином. Расхождение менее серьезно для функции exp, которая имеет чрезвычайно быстро сходящийся степенной ряд, чем для функции log.

Приближение Чебышева является основой квадратуры Кленшоу–Кертиса , метода численного интегрирования .

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

Алгоритм Ремеза (иногда пишется как Ремес) используется для получения оптимального полинома P ( x ), аппроксимирующего заданную функцию f ( x ) на заданном интервале. Это итеративный алгоритм, который сходится к полиному, имеющему функцию ошибок с N +2 уровнями экстремумов. По теореме выше этот полином является оптимальным.

Алгоритм Ремеза использует тот факт, что можно построить полином N- й степени, который приводит к ровным и чередующимся значениям ошибок, если заданы N +2 контрольные точки.

Учитывая N +2 контрольных точек , , ... (где и предположительно являются конечными точками интервала аппроксимации), необходимо решить следующие уравнения: ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{N+2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{N+2}}$

${\displaystyle {\begin{aligned}P(x_{1})-f(x_{1})&=+\varepsilon \\P(x_{2})-f(x_{2})&=-\varepsilon \\P(x_{3})-f(x_{3})&=+\varepsilon \\&\ \ \vdots \\P(x_{N+2})-f(x_{N+2})&=\pm \varepsilon .\end{aligned}}}$

Знаки правых сторон чередуются.

То есть,

${\displaystyle {\begin{aligned}P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}+\dots +P_{N}x_{1}^{N}-f(x_{1})&=+\varepsilon \\P_{0}+P_{1}x_{2}+P_{2}x_{2}^{2}+P_{3}x_{2}^{3}+\dots +P_{N}x_{2}^{N}-f(x_{2})&=-\varepsilon \\&\ \ \vdots \end{aligned}}}$

Поскольку , ..., были даны, все их мощности известны, и , ..., также известны. Это означает, что приведенные выше уравнения представляют собой всего лишь N +2 линейных уравнений относительно N +2 переменных , , ..., , и . Учитывая контрольные точки , ..., , можно решить эту систему, чтобы получить многочлен P и число . ${\displaystyle x_{1}}$ ${\displaystyle x_{N+2}}$ ${\displaystyle f(x_{1})}$ ${\displaystyle f(x_{N+2})}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{N}}$ ${\displaystyle \varepsilon }$ ${\displaystyle x_{1}}$ ${\displaystyle x_{N+2}}$ ${\displaystyle \varepsilon }$

На графике ниже показан пример этого, производящий полином четвертой степени, приближающий по [−1, 1]. Тестовые точки были установлены на −1, −0,7, −0,1, +0,4, +0,9 и 1. Эти значения показаны зеленым цветом. Результирующее значение составляет 4,43 × 10 ⁻⁴ ${\displaystyle e^{x}}$ ${\displaystyle \varepsilon }$

Ошибка полинома, полученного на первом шаге алгоритма Ремеза, аппроксимирующего e ^x на интервале [−1, 1]. Вертикальные деления составляют 10 ⁻⁴ .

График ошибок действительно принимает значения в шести контрольных точках, включая конечные точки, но эти точки не являются экстремумами. Если бы четыре внутренние контрольные точки были экстремумами (то есть функция P ( x ) f ( x ) имела там максимумы или минимумы), многочлен был бы оптимальным. ${\displaystyle \pm \varepsilon }$

Второй шаг алгоритма Ремеза состоит в перемещении контрольных точек в приблизительные местоположения, где функция ошибки имела свои фактические локальные максимумы или минимумы. Например, глядя на график, можно сказать, что точка в −0,1 должна была быть около −0,28. Способ сделать это в алгоритме — использовать один раунд метода Ньютона . Поскольку известны первая и вторая производные P ( x ) − f ( x ) , можно приблизительно рассчитать, насколько далеко нужно переместить контрольную точку, чтобы производная стала равна нулю.

Вычисление производных полинома является простым. Также необходимо уметь вычислять первую и вторую производные f ( x ). Алгоритм Ремеза требует способности вычислять , , и с чрезвычайно высокой точностью. Весь алгоритм должен быть выполнен с более высокой точностью, чем желаемая точность результата. ${\displaystyle f(x)\,}$ ${\displaystyle f'(x)\,}$ ${\displaystyle f''(x)\,}$

После перемещения контрольных точек линейная часть уравнения повторяется, получая новый полином, и метод Ньютона снова используется для повторного перемещения контрольных точек. Эта последовательность продолжается до тех пор, пока результат не сойдется с желаемой точностью. Алгоритм сходится очень быстро. Сходимость квадратичная для хорошо себя ведущих функций — если контрольные точки находятся в пределах правильного результата, они будут приблизительно в пределах правильного результата после следующего раунда. ${\displaystyle 10^{-15}}$ ${\displaystyle 10^{-30}}$

Алгоритм Ремеза обычно начинается с выбора экстремумов полинома Чебышева в качестве начальных точек, поскольку конечная функция ошибки будет подобна этому полиному. ${\displaystyle T_{N+1}}$

Основные журналы

• Журнал теории аппроксимации
• Конструктивное приближение
• Восточный журнал по аппроксимациям

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

• Теория оценки
• ряд Фурье
• Аппроксимация функции
• Ортонормированный базис
• Аппроксимация Паде
• основа Шаудера
• фильтр Калмана

Ссылки

• Н.И. Ахиезер (Ахиезер) , Теория приближения, Перевод Чарльза Дж. Хаймана Frederick Ungar Publishing Co., Нью-Йорк 1956 x+307 стр.
• А.Ф. Тиман, Теория приближения функций действительного переменного , 1963 ISBN  0-486-67830-X
• C. Hastings, Jr. Аппроксимации для цифровых компьютеров . Princeton University Press, 1955.
• JF Hart, EW Cheney , CL Lawson, HJ Maehly, CK Mesztenyi, JR Rice , HC Thacher Jr., C. Witzgall, Computer Approximations . Wiley, 1968, Lib. Cong. 67–23326.
• Л. Фокс и И. Б. Паркер. «Полиномы Чебышева в численном анализе». Oxford University Press, Лондон, 1968.
• Press, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (2007), «Раздел 5.8. Чебышевское приближение», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8, заархивировано из оригинала 10 апреля 2020 г. , извлечено 9 августа 2011 г.
• WJ Cody Jr., W. Waite, Руководство по программному обеспечению для элементарных функций . Prentice-Hall, 1980, ISBN 0-13-822064-6 . 
• Э. Ремес [Ремез] , «Sur le Calcul effectif des полиномы аппроксимации Чебышева». 1934 г. ЧР акад. наук. , Париж, 199 , 337–340.
• К.-Г. Стеффенс, «История теории приближений: от Эйлера до Бернштейна», Birkhauser, Бостон 2006 ISBN 0-8176-4353-2 . 
• Т. Эрдейи , «Обобщения теоремы Блоха-Полиа о числе различных действительных нулей многочленов», Journal de théorie des nombres de Bordeaux 20 (2008), 281–287.
• Т. Эрдейи, «Неравенство Ремеза для линейных комбинаций сдвинутых гауссианов», Math. Proc. Camb. Phil. Soc. 146 (2009), 523–530.
• Л. Н. Трефетен , «Теория приближений и практика приближений», SIAM 2013. [1]

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

• История теории приближений (HAT)
• Опросы по теории приближений (SAT)