Теория приближений - Approximation theory

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

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

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

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

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

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

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

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

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

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

Когда максимум P - f возникает в x i , тогда

И когда минимум P - f встречается в x i , тогда

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

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

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

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

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

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

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

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

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

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

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

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

Правые части меняются знаками.

То есть,

Поскольку , ..., были даны, все их силы известны, и , ..., также известны. Это означает , что приведенные выше уравнения являются лишь N +2 линейных уравнений в N переменных +2 , ..., и . Учитывая контрольные точки , ... ,, можно решить эту систему, чтобы получить многочлен P и число .

На графике ниже показан пример этого, производящий полином четвертой степени, приближающийся по [−1, 1]. Контрольные точки были установлены на -1, -0,7, -0,1, +0,4, +0,9 и 1. Эти значения показаны зеленым. Результирующее значение составляет 4,43 × 10 −4.

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

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

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

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

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

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

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

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

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

  • Н.И. Ачиезер (Ахиезер) , Теория приближения, Перевод Чарльза Дж. Хаймана Фредерика Унгара Паблишинг Ко., Нью-Йорк, 1956 x + 307 с.
  • А. Ф. Тиман, Теория приближения функций действительной переменной , 1963 ISBN  0-486-67830-X
  • К. Гастингс-младший. Приближения для цифровых компьютеров . Издательство Принстонского университета, 1955.
  • JF Hart, EW Cheney , CL Lawson, HJ Maehly, CK Mesztenyi, JR Rice , HC Thacher Jr., C. Witzgall, Компьютерные аппроксимации . Wiley, 1968, Lib. Конг. 67-23326.
  • Л. Фокс и И.Б. Паркер. «Многочлены Чебышева в численном анализе». Издательство Оксфордского университета, Лондон, 1968 год.
  • Нажмите, WH ; Teukolsky, SA ; Феттерлинг, штат Вашингтон; Фланнери, Б.П. (2007), «Раздел 5.8. Приближение Чебышева» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8
  • WJ Cody Jr., W. Waite, Руководство по программному обеспечению элементарных функций . Прентис-Холл, 1980, ISBN  0-13-822064-6 .
  • Э. Ремес [Ремез] , "Sur le Calculated Effectif des Polynomes d'approximation de Tschebyscheff". 1934 ЧР Акад. Sci. , Париж, 199 , 337-340.
  • КГ. Стеффенс, "История теории приближений: от Эйлера до Бернштейна", Биркхаузер, Бостон, 2006 ISBN  0-8176-4353-2 .
  • T. Erdélyi , "Расширения теоремы Блоха-Полиа о числе различных действительных нулей многочленов", Journal de théorie des nombres de Bordeaux 20 (2008), 281–287.
  • T. Erdélyi, "Неравенство Ремеза для линейных комбинаций сдвинутых гауссианов", Math. Proc. Camb. Фил. Soc. 146 (2009), 523–530.
  • LN Trefethen , "Теория приближений и практика приближений", SIAM 2013. [1]

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