Файл: 1. Источники и классификация погрешностей.ppt

Найдем количество итераций, которое необходимо выполнить, чтобы найти неизвестные с точностью  = 10–4.


|||| = 0,41,


,


(k + 1) lg 0,55 + lg 0,41 – lg 0,45 < – 4;


,


(k + 1) lg 0,55 < – 4 – lg 0,41 + lg 0,45;

б) метод Зейделя.

Пусть дана система линейных уравнений


Ax = b,


(7)


Где у матрицы все диагональные элементы отличны от нуля, т.е. aii  0, i = 1,2, …, n.


Если i-ое уравнение системы (7), i = 1,2,…,n, разделить на aii, а затем все неизвестные, кроме xi, перенести вправо, то мы придем к эквивалентной системе вида


x = Cx + d,


(8)


где d = (d1, d2, …, dn),


,


Метод Зейделя состоит в том, что итерации производятся по формуле


(9)


где произвольны, i = 1, 2, …, n, k = 1, 2, …


Итерации (9) по методу Зейделя отличаются от простых итераций тем, что при нахождении i-ой компоненты k-ого приближения сразу используются уже найденные компоненты k-ого приближения с меньшими номерами.


Условия сходимости метода простых итераций и метода Зейделя не совпадают, но пересекаются.


В некоторых случаях метод Зейделя дает более быструю сходимость.


Сформулируем теорему о двух различных достаточных условиях сходимости метода Зейделя.


Теорема 3. Для существования единственного решения системы (7) и сходимости метода Зейделя достаточно выполнения хотя бы одного из двух условий:


а)


, i = 1, 2, …, n;


в) матрица А – симметричная положительно определенная (все ее собственные значения положительны).


§1. Интерполяционные многочлены


Пусть в точках x0, x1, …, xn заданы значения функции f(x0), f(x1), …, f(xn) (a<x0<x1<…<xn<b).


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


Возникает задача приближенного восстановления функции f в произвольной точке x.


Часто для решения этой задачи строится алгебраический многочлен Ln(x) степени n, значения которого в точках xi совпадают со значениями функции в заданных точках.


(1)


Точки x0, x1, …, xn называются узлами интерполяции.


Сам многочлен Ln(xi) называется интерполяционным многочленом.

---

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


Например, если fi = 0, i = 0, 1, …, n, то интерполяционный многочлен Ln(x)  0 фактически имеет нулевую степень, но его тоже будем называть интерполяционным многочленом n-ой степени.


Приближенное восстановление функции f по формуле


f(x)  Ln(x)


(2)


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


Если x расположен вне минимального отрезка, содержащего все узлы интерполяции x0, x1, …, xn, то замену функции f по формуле (2) называют также экстраполяцией.


Терема 1. Существует единственный интерполяционный многочлен n-ой степени, удовлетворяющий условиям (1).


Доказательство. Запишем выражение интерполяционного многочлена.


Пусть n = 1, тогда


(3)


При n = 2


(4)


и, наконец, в общем случае при любом натуральном n


(5)


где


(6)


(i = 0, 1, …, n.)


Действительно, выражение (3) представляет собой линейную функцию, т.е. многочлен первой степени, причем, L1(x0) = f0, L1(x1) = f1.


Таким образом, требования (1) при n = 1 выполнены.


Аналогично, формула (4) задает некоторый многочлен L2(x) второй степени, удовлетворяющий при n = 2 условиям (1).


При произвольном натуральном n функции (6), описываемая дробью, в числителе которой стоит произведение n линейных множителей, а в знаменателе – некоторое отличное от нуля число, являются алгебраическими многочленами степени n.


Следовательно, функция (5) тоже является алгебраическим многочленом степени n, причем, поскольку pni(xi)=1, а pni(xj) = 0 при j  i, 0  j  n, то выполнены требования (1).


Докажем единственность интерполяционного многочлена.


Допустим, что кроме интерполяционного многочлена (5) имеется еще некоторый алгебраический многочлен n-й степени, удовлетворяющий условиям


(7)


Тогда согласно (1) и (7)


(8)


Если , то эта разность, будучи алгебраическим многочленом не выше n-ой степени, в силу основной теоремы высшей алгебры имеет не более n корней, что противоречит равенствам (8), число которых равно n + 1.


Следовательно, .


Теорема 1 полностью доказана.


Интерполяционный многочлен, представленный в виде (5), называется

---

интерполяционным многочленом Лагранжа, а функции (многочлены) (6) – лагранжевыми коэффициентами.


Запишем равенство f(x) = Ln(x) + Rn(x), где Rn(x) – остаточный член, т.е. погрешность интерполяции.


Возьмем некоторую точку [a, b], обозначим n(x)= (x – x0) (x – x1) …(x – xn)


Тогда Rn(x) = n(x)


(9)


Следовательно, f(x) = Ln(x) + n(x)


(10)


Из равенства (10) вытекает оценка погрешности интерполяции (в частности, экстраполяции) в текущей точке x  [a, b]:


|f(x) – Ln(x)| 


|n(x)|,


(11)


где


Мn+1 =


|f(n+1)(x)|   ,


и оценка максимальной погрешности интерполяции на всем отрезке [a, b]:


|f(x) – Ln(x)| 


|n(x)|


(12)

---

§4. Интерполяционный многочлен Ньютона

Предположим, что узлы интерполяции отстоят друг от друга на одинаковом расстоянии


x0, x1 = x0 + h, x2 = x0 + 2h, … xk = x0 + kh,


(1)


h > 0, k = 0, 1, …, n


(т.е. узлы интерполяции образуют арифметическую прогрессию с разностью h)


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


Определение. Пусть xk = x0 + kh, где k – целое, h > 0, fk = f(xk). Величина fk = fk+1 – fk, называется конечной разностью первого порядка функции f в точке xk (с шагом h),


Т.е. f0 = f(x1) – f(x0) = y1 – y0,


f1 = f(x2) – f(x1) = y2 – y1,


……………………………


fk = f(xk+1) – f(xk) = yk+1 – yk,


а величину nfk = n–1fk+1 – n–1fk, называют конечной разностью n-ого порядка функции f в точке xk.


Т.е. 2fk = fk+1 – fk(xk),


3fk = 2fk+1 –2fk(xk), и т.д.


Конечные разности функции f удобно записывать в таблице


x0
x1
x2
x3
x4


f0
f1
f2
f3
f4


f0
f1
f2
f3


2f0
2f1
2f2


3f0
3f1


Пусть x0, x1 = x0 + h, x2 = x0 + 2h, … xk = x0 + kh - узлы интерполяции функции f(x).


Тогда интерполяционный многочлен имеет вид


Pn(x) = a0 + a1(x – x0) + a2(x – x0)(x – x1) + … + an(x – x0) …(x – xn-1)


где a0 , a1 , …, an найдены из условия, что Pn(xi) = f(xi), i = 0, 1, …, n.


Pn(x0) = a0 = y0


Pn(x1) = a0+ a1(x1 – x0) = y1


y0 + a1h = y1;


a1 =


;


a1 =


;


Pn(x2) = a0+ a1(x2 – x0) + a2(x2 – x0)(x2 – x1) = y2


y0 + 2h + a2 2h h = y2


2h2 a2 = y2 – y0 –  y0 2;


a2 = ;


a2 = ;


итак,


a2 =


Pn(x3) = a0+ a1(x3 – x0) + a2(x3 – x0)(x3 – x1) + + a3(x3 – x0)(x3 – x1)(x3 – x2) = y3


y0 + 3h + 3h2h + a3 3h2h h = y3


6h3 a3 = y3 – y0 – 3  y0 + 3 2y0;


a3 = =


и т.д.


Общий вид


an =


Таким образом, формула Ньютона для интерполирования вперед имеет вид


Pn(x) = y0 + (x – x0) + (x – x0)(x – x1) + + (x – x0)(x – x1)(x – x2) + … + (x – x0) …(x – xn-1)


(2)


В нем начало отсчета расположено в крайнем левом узле x0, а используемые конечные разности идут в таблице разностей от

---

f0 вправо вниз.


Интерполяционный многочлен (2) удобно использовать в начале таблицы и для экстраполяции левее точки x0, т.е. < 0.


Интерполяционный многочлен с узлами x0, x –1 , …, x –n,


где x – k = x0 – kh, имеет вид


Pn(x) = yn + (x – xn) + (x – xn)(x – xn-1) + + (x – xn)(x – xn-1)(x – xn-2)+ … + (x – xn) …(x – x1)


(3)


И называется интерполяционным многочленом Ньютона для интерполирования назад.


В нем начало отсчета расположено в крайнем правом узле x0, а используемые конечные разности идут в таблице от f0 вправо вверх:


x-4
x-3
x-2
x-1
x0


f-4
f-3
f-2
f-1
f0


f-4
f-3
f-2
f-1


2f-4
2f-3
2f-2


3f-4
3f-3


Интерполяционный многочлен (3) удобно использовать при интерполяции в конце таблицы и для экстраполяции правее точки x0, т.е. > 0.


Рассмотрим численный процесс приближения производной f(x):


(1)


Выберем последовательность {hk} так, что hk  0, и вычисляем ее предел:


для k = 1, 2, …, n, …


(2)


Будем вычислять только конечное количество членов D1, D2, …, Dn последовательности (2).


Следовательно, для ответа следует использовать Dn.


Причем необходимо выбирать значение hn так, чтобы Dn было хорошим приближением к производной f (x).


Для примера рассмотрим функцию f (x) = ex и используем длину шагов, равную h = 1, ½ и ¼, чтобы построить секущую линию, которая проходит между точками (0; 1) и (h, f (h)) соответственно.


Так как h уменьшается, то секущая приближается к касательной, как показано на рисунке.


y


x


0


0,25


0,5


0,75


1


y = f(x)


1


Нужно произвести вычисления при h = 0,00001, чтобы получить приемлемый численный ответ, и для этого значения h графики касательной и секущей должны быть неразличимы.


§1. Приближенные методы вычислений определенных интегралов


Формула Ньютона-Лейбница для вычисления определенного интеграла имеет вид .


Однако, вычисление по этой формуле не всегда возможно.


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


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


Пусть дан интеграл:

---