Числовые методы. Прецентация №1. 1. Источники и классификация погрешностей

• Название: 1. Источники и классификация погрешностей
• Анкор: Числовые методы
• Дата: 25.04.2023
• Размер: 3.47 Mb.
• Имя файла: Прецентация №1.ppt
• Тип: Решение; #1089280
• страница: 2 из 4

II. Итерационные методы

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


а) метод простых итераций.


Предположим, что диагональные элементы системы (1) не равны 0 (аij  0). Из первого уравнения выражаем х1, из второго – х2 и т.д. Из n-ого – хn.


Обозначим


,


(6)


Система (6) приведена к нормальному виду. Запишем ее в матричном виде: X =  +  x, где


,


,


х0 =  – нулевое приближение. Общая формула имеет вид:


Будем решать систему (6) методом последовательных приближений.


хk+1 =  хk + 


т.е. х0 =  ; х(1) =  х(0) +  ; х(2) =  х(1) +  …


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


Если последовательность приближений имеет предел, то


– точное решение системы (6) следовательно, системы (1).


Теорема 2. Необходимым и достаточным условием сходимости метода простых итераций при любом начальном векторе x0 к решению x* системы (6) является требование, чтобы все собственные числа матрицы  были по модулю меньше 1.


Условие окончания вычисления.


Пусть


– точное решение системы.


– k-ое приближенное значение неизвестных, вычисленных по методу итераций.


Тогда | xi(k+1) – xi(k) | <  для любого i = 1, 2, … , n.


Оценка погрешности:


Определим:


(Норма)


||  || = max {|1|, |2|, …, |n|}


Тогда


max {| x1 – x1(k) |, | x2 – x2(k) |, …, | xn – xn(k) |} 








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


|||| = max {0,42; 0,55; 0,4}  1


|||| = 0,55 – итерационный процесс сходится.


Найдем количество итераций, которое необходимо выполнить, чтобы найти неизвестные с точностью  = 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)