8. Экстраполяция. Правила Рунге и Ричардсона практической оценки погрешности. Многокомпонентная модель погрешности. Метод Ромберга. Численная фильтрация.

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

Допустим нам известна зависимость результата вычислений Zn при использовании какого-то метода (например значение интеграла,) от числа узловых точек, то есть N

Мы можем представить этот приближенный результат как сумму точного значения, произведения С на n в степени -k, и также некоторой погрешности, где С- коэффициента, независящий от n; k-порядок точности метода.

Правила Рунге и Ричардсона практической оценки погрешности. Правило Ричардсона основано на математической модели, где приближенный результат вычислений равен сумме точного значения, произведения С на n в степени -k, при этом отбрасывается погрешность в силу того, что она очень мала.

Мы расписываем по этой формуле два члена последовательности Zn и Zn/q, оттуда находим уточненное значение Z и с помощью этого можем найти погрешность вычисленных значений.

Правило Рунге – это оценка, при которой берем вместо точного значения – уточненное (экстраполированное) значение.

Численная фильтрация. Приближенное значение (математическая модель погрешности) расписывается на отдельные компоненты, точное значение плюс с1*n^-k1 плюс с2*n^-k2 и так далее, в конце прибавляется некая погрешность, каждое значение k должно быть меньше предыдущего. Мы расписываем таким образом Zn1, Zn2 и так далее, и начинаем отфильтровывать одну компоненту за другой: то есть попарно рассматриваются значения сначала Zn1 и Zn2, составляется их линейная комбинация, коэффициенты при Z выносятся за скобки и приравниваются единице, при С – приравниваются 0, и все это постепенно пересчитывается. В конце выходит формула, которая совпадает с формулой Ричардсона.

Многокомпонентная модель погрешности. Если мы найдем оценку погрешности оценки погрешности, то она должна быть существенно меньше единицы. Критерий качества оценки погрешности: пока модуль отношения погрешности экстраполяции более высокого порядка к погрешности экстраполяции более низкого порядка значительно меньше единицы – точность растет, как только это неравенство нарушается – не имеет смысла продолжать экстраполировать

Метод Ромберга. Допустим у нас есть посчитанные приближенные значения, для n, которое увеличиваем в 2 раза, по правилу Ричардсона находим экстраполированные значения по парам Zn, затем аналогично находим значения после 2 экстраполяции и так далее. Вот такое повторное применение правила Рунге – это метод Ромберга.

9. Численное решение нелинейных уравнений. Метод бисекций. Метод касательных. Метод хорд. Метод простых итераций. Сравнение скорости сходимости методов. Условия сходимости и скорость сходимости методов.

Численное решение нелинейных уравнений. Дано какое-то нелинейное уравнение f(x)=0, корни которого необходимо найти. Мы разбиваем отрезок на определенное число кусочков, на каждом из которых не более 1 корня

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

Сравнение скорости сходимости методов. Мы сравниваем на сколько уменьшается погрешность за одну итерацию. В методе бисекций интервал неопределенности уменьшается в 2 раза после каждой итерации.

В методе простых итераций необходимо чтобы итерационный процесс сходился к точному решению, нужно чтоб выполнялось неравенство: модуль производной фи(х)<= альфа, где альфа<1. Если же <1/2, то скорость сходимости метода итераций выше, чем метода бисекций.

Для метода касательных за одну итерацию погрешность уменьшается в квадрат. У этого метода самая высокая скорость сходимости.

По скорости сходимости метод хорд почти такой же как метод касательных

Метод простых итераций. В этом случае мы ищем корень, т.е. точку пересечения кривой y=фи(x) и прямой y=x. За первое приближение принимается какое-то произвольное значение х0, тогда x1=фи(x0), x2=фи(x1) и т.д. Чтобы итерационный процесс сходился к точному решению, нужно чтоб выполнялось неравенство: модуль производной фи(х)<1/2.

Условия сходимости и скорость сходимости методов. Для ускорения процессов сходимости используется экстраполяция, например процесс Эйткена.

Для метода простых итераций чтобы итерационный процесс сходился к точному решению, нужно чтоб выполнялось неравенство: модуль производной фи(х)<1/2

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

По скорости сходимости метод хорд почти такой же как метод касательных

Метод касательных. (Метод Ньютона). Нам известно, что функция непрерывно дифференцируема и как в методе биекций, надо найти точку пересечения функции с осью x. За первое приближенное решение берется произвольная точка x0, в этой точке строится касательная к кривой y=f(x), касательная пересекает ось x в какой-то точке x1, теперь эта точка считается следующим приближенным решением и так далее, пока мы сами не остановим процесс. Имеет квадратичную скорость сходимости, но при этом нужно на каждой итерации вычислять производные и в целом нет гарантированного способа оценки погрешности, т.к. за погрешность берется разница между значениями на двух итерациях, и попадание в решение зависит от насколько близко к точному решению мы взяли первое приближенное

Метод хорд. Похож на метод касательных, в котором, по сути, устраняются некоторые недостатки метода касательных, тут производную находят численным методом. Берутся 2 приближенных значения x0 и x1, через значения функции в этих точках строится секущая до пересечения с осью x, получаем точку x2, которая является следующим приближенных решением, дальше секущая строится через точки x1,x2 и так далее.