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

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

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

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

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

Ошибка между оптимальным полиномом и log(x) (красный) и аппроксимацией Чебышева и log(x) (синий) на интервале [2, 4]. Вертикальных делений 10 ⁻⁵. Максимальная ошибка оптимального полинома составляет 6,07 × 10. ⁻⁵.

Ошибка между оптимальным полиномом и exp(x) (красный) и аппроксимацией Чебышева и exp(x) (синий) в интервале [−1, 1]. Вертикальных делений 10 ⁻⁴. Максимальная ошибка оптимального полинома составляет 5,47 × 10. ⁻⁴.

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

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

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

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

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

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

Когда максимум P − f возникает в точке x _i , тогда

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 , тогда

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. Эта функция

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

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

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

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

а затем прерывает серию после $T_{N}$ термин, можно получить полином N- й степени, аппроксимирующий f ( x ).

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

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

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

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

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

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

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

{\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}}

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

То есть,

{\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}}

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

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

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

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

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

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

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

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

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

См. также

Ссылки

Н. И. Ахиезер (Ахиезер) , Теория приближения, Перевод Чарльза Дж. Хаймана Фредерика Унгара Паблишинг Ко., Нью-Йорк, 1956 x +307 стр.
А. Ф. Тиман, Теория приближения функций действительной переменной , 1963 г. ISBN 0-486-67830-X
К. Гастингс-младший. Приближения для цифровых компьютеров . Издательство Принстонского университета, 1955.
Дж. Ф. Харт, Э. У. Чейни , К. Л. Лоусон, Х. Дж. Мэйли, К. К. Мештеньи, Дж. Р. Райс , Х. К. Тэчер-младший, К. Вицгалл, Компьютерные аппроксимации . Уайли, 1968, Либ. Конг. 67–23326.
Л. Фокс и И.Б. Паркер. «Полиномы Чебышева в численном анализе». Издательство Оксфордского университета, Лондон, 1968.
Пресс, WH ; Теукольский, С.А. ; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 5.8. Приближение Чебышева» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8 , заархивировано из оригинала 10 апреля 2020 г. , получено 9 августа 2011 г.
У. Дж. Коди-младший, У. Уэйт, Руководство по программному обеспечению для элементарных функций . Прентис-Холл, 1980 г., ISBN 0-13-822064-6 .
Э. Ремес [Ремез] , «Об эффективном вычислении полиномов аппроксимации Чебышева». 1934 г. ЧР акад. наук. , Париж, 199 , 337–340.
КГ. Стеффенс, «История теории приближения: от Эйлера до Бернштейна», Биркхаузер, Бостон, 2006 г. ISBN 0-8176-4353-2 .
Т. Эрдейи , «Расширения теоремы Блоха-Пойа о количестве различных действительных нулей многочленов», Journal de theorie des nombres de Bordeaux 20 (2008), 281–287.
Т. Эрдели, "Неравенство Ремеза для линейных комбинаций сдвинутых гауссианов", Math. Учеб. Кэмб. Фил. Соц. 146 (2009), 523–530.
Л. Н. Трефетен , «Теория приближения и практика приближения», SIAM 2013. [1]

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