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

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

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

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

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

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

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

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

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

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

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

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

{ displaystyle | Q (x_ {i}) - f (x_ {i}) | <| P (x_ {i}) - 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}),}

И когда минимум п−ж происходит в Икс_я, тогда

{ 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}).}

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

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

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

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

{ Displaystyle е (х) сим сумма _ {я = 0} ^ { infty} с_ {я} T_ {я} (х)}

а затем обрезает серию после ${ displaystyle T_ {N}}$ срок, каждый получает Nth-степень полинома аппроксимации ж(Икс).

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

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

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

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

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

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

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

{ Displaystyle { begin {align} P (x_ {1}) - f (x_ {1}) & = + varepsilon P (x_ {2}) - f (x_ {2}) & = - варепсилон P (x_ {3}) - f (x_ {3}) & = + varepsilon & vdots P (x_ {N + 2}) - f (x_ {N + 2} ) & = pm varepsilon. end {align}}}

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

То есть,

{ displaystyle { begin {align} P_ {0} + P_ {1} x_ {1} + P_ {2} x_ {1} ^ {2} + P_ {3} x_ {1} ^ {3} + точки + 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} + точки + P_ {N} x_ {2} ^ {N} -f (x_ {2}) & = - varepsilon & vdots end {выровнены}}}

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

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

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

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

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

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

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

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

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

Содержание

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

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

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

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

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

Рекомендации

внешняя ссылка