Интерполяционная формула Лагранжа

Интерполяция – это отыскание значений функции, соответствующих промежуточным значениям аргумента. Т.е. в точке (а) f(a) известно; в точке (b) f(b) – известно. Найти значение функции f в промежуточных точках отрезка [аb].

Итак рассматривается функция f(х), для которой заданы значения y_i = f(x_i) (i =0,1,2,…,n), причем все x_i и y_i известны. Требуется определить многочлен y = F(x) степени n, для которого F(x_i) = f(x_i) (i=0,1,…n).

Такой многочлен называется формулой Лагранжа.

Построим такой многочлен.

В озьмем формулу, предполагая, что сетка равномерная (см. рис.1).

х х х х х

0 1 2 n-1 n

Рис. 1.

Это многочлен степени n – очевидно. При х = х₀ он равен 1, а при х = х₁, х₂, х_n он равен нулю. Умножим его на у₀ и обозначим

,

получим многочлен F₀(x), который при х = х₀ равен у₀.

Теперь построим такой же многочлен F₁(x)

Этот многочлен F₁ (x) принимает значение у₁ при х = х₁ при всех остальных х_i он равен нулю.

Теперь возьмем

Этот многочлен и будет искомым.

Запишем его в развернутом виде

Полученная формула называется интерполяционной формулой Лагранжа.

Такой многочлен единственный. Докажем это. Пусть существует еще один многочлен R(x) степени n, принимающий в заданных точках заданные значения. Тогда разность F(x) – R(x) представляет собой многочлен степени не выше n, который обращается в ноль в точках х = х_i (i = 0, 1, 2,…n) т.е. имеет (n+1) корень. Значит он равен нулю тождественно, так как многочлен степени n не может иметь n+1 корней.

Порядок точности этого многочлена О(hⁿ⁺¹) .

Квадратурная формула прямоугольников

Если в интеграле возьмем левую точку а или правую b, то получаем следующие формулы для вычисления интегралов

или .

Такие формулы называются квадратурными формулами прямоугольников. Первая формула – левый прямоугольник, вторая – правый. Эти формулы имеют первый порядок точности, что доказывается также размножением в ряд Тейлора

Сгущая сетку, получим при равномерном шаге

т.е. здесь порядок точности первый.

Метод Ньютона решения уравнений с одним неизвестным

Это метод решения линейных и нелинейных уравнений с одним неизвестным. Он называется также методом касательных или методом линеаризации. Если х_n есть некоторое приближение к корню , а f(x) имеет непрерывную производную, то уравнение f(x) = 0 можно преобразовать следующим образом

Приближенно заменяя на значение в известной точке х_n, получим такой итерационный процесс

Выводится он из уравнения = 0,

Метод Ньютона можно рассматривать как частный случай метода простых итераций, если положить .

Исследуем условия сходимости. Если имеет непрерывную производную, тогда

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

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

Пусть справа от корня, то на этом отрезке итерации сходятся, причем монотонно. То же будет, если слева от корня на отрезке [b, ], и на этом же отрезке выбрано нулевое приближение. Таким образом, итерации сходятся к корню с той стороны, с которой .

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

,

т.е. погрешность очередного приближения примерно равна квадрату погрешности предыдущего приближения. Например, если (n-1)-я итерация давала 3 верных знака, то n-я даст примерно 6 верных знаков, а (n+1) – примерно 12 знаков.