Лекции. Источники и классификация погрешностей
 Скачать 3.8 Mb.
|
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) |