14. Нелинейная аппроксимация. Аппроксимация функцией произвольного вида. Аппроксимация полиномом

Выбор степени многочлена. Предположим, что функцию f можно с высокой точностью аппроксимировать многочленом некоторой степени m. Если эта степень заранее неизвестна, то возникает проблема выбора оптимальной степени аппроксимирующего многочлена в условиях, когда исходные данные содержат случайные ошибки. Для решения этой задачи можно принять следующий алгоритм: для каждого m=0,1,2,.. вычисляется величина

.

За оптимальное значение степени многочлена принимаем то m, начиная с которого величина начинает возрастать.

15. Нелинейная аппроксимация. Метод вложенных алгоритмов

Вложенный алгоритм – это алгоритм рассмотренный «под микроскопом», включает в себя дополнительные алгоритмы для не понятных команд.

16. Численное дифференцирование. Устойчивость и выбор шага дифференцирования

Постановка задачи численного дифференцирования

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

Задача численного дифференцирования состоит в приближенном вычислении производных функции f(x) по заданным в конечном числе точек значениям этой функции.

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

В ряде случаев наряду с приближенным равенством удается (например, используя формулу Тейлора) получить точное равенство, содержащее остаточный член R (погрешность численного дифференцирования):

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

Ниже приводятся несколько распространенных формул численного дифференцирования с остаточными членами для первой (r=1) и второй (r=2) производных в узлах, расположенных с постоянным шагом h > 0. В приводимых формулах есть некоторая точка (своя для каждой из формул) из интервала . Остаточные члены этих формул находятся с помощью формулы Тейлора. При этом предполагается, что на отрезке у функции f(x) непрерывна производная, через которую выражается остаточный член.

Таблица 4.1 – Сводка формул численного дифференцирования

	Формулы численного дифференцирования с остаточными членами	№
r=1, N=1 (два узла)		(4.1) (4.2)
r=1, N=2 (три узла):		(4.3) (4.4) (4.5)
r=2, N=2 (три узла)		(4.6) (4.7) (4.8)
r=2, N=3 (четыре узла)		(4.9) (4.10)

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

Рисунок 4.1 – Геометрическая иллюстрация формул 4.1, 4.2 и 4.4

Из приведенного рисунка видно преимущество формулы (4.4) перед двумя предыдущими вычисления производной в точке х.

Теорема 4.1 Пусть и функция . Тогда существуют такие константы зависящие только от r, k, N и не зависящие от шага h и функции f(x), что

(4.11)

где - интерполяционный полином Лагранжа для функции f(x), .

Оценка (4.11) полезна тем, что она устанавливает скорость убывания погрешности относительно h на всем отрезке при фиксированных параметрах r, k, N.

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

Замечание 4.1. Другим способом нахождения производной табличной функции является использование формулы производной интерполяционного сплайна, построенного по этой таблице. В этом случае производная вычисляется на каждом отрезке [x_i-1 , x_i], i=1, ..., N, с использованием вектора (M₀ ,..., M_N )^T, найденного методом прогонки как решение системы уравнений.

Замечание 4.2. Есть два способа для повышения точности вычисления производной. Можно уменьшать шаг дифференцирования h, а можно увеличивать число точек N. Не рекомендуется делать h слишком малым, особенно для производных высших порядков - начинают проявляться погрешности операций с вещественными числами. В таких случаях лучше увеличить число точек N, оставив шаг h довольно-таки большим.

Замечание 4.3. Следует быть осторожным при вычислении производных высших порядков. С ростом порядка производной растет число точек, которое требуется для её вычисления. Если вы вычисляете десятую производную, то будьте готовы, что для её вычисления вам потребуется двадцать точек, а при меньшем их числе погрешность будет слишком велика.

Погрешность численного дифференцирования

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

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

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

Таким образом, в лучшем случае (при оптимальном шаге) можно лишь гарантировать, что производная , вычисленная по формуле (4.1) будет отличаться от истинного значения не более чем на .Например, при 0.01 и M₂ 1 шаг должен быть примерно 0.2 и при этом получим точность не выше 0.2.

Оценим погрешность формулы (4.4), которую называют также формулой с центральной разностью. Записать ее можно в виде:

Исследуем ее на аппроксимацию, т.е. оценим погрешность метода. Предположим, что функция, которую спроектировали на сетку, трижды непрерывно дифференцируема, тогда

Погрешность метода определяется 3-й производной функции. Введем тогда суммарная погрешность при вычислении по формуле с центральной разностью есть

для вычисления оптимального шага, находя минимум погрешности, как функции шага сетки, имеем откуда

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

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

В формулах численного дифференцирования с постоянным шагом h значения функции f(x) делятся на hr, где r-порядок вычисляемой производной. Поэтому при малом h неустранимые погрешности в значениях функции f(x) оказывают сильное влияние на результат численного дифференцирования. Таким образом, возникает задача выбора оптимального шага h, так как погрешность собственно метода стремится к нулю при h → 0, а неустранимая погрешность растет. В результате общая погрешность, возникающая при численном дифферецировании, может неограниченно возрастать при h → 0. Поэтому операцию численного дифференцирования называют некорректной.