Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
Различные итерационные методы отличаются первыми двумя шагами, а выбор конкретного метода должен производиться на основании оценки (8.3.4).
8.3.2. Метод простой итерации. В методе простой итерации матрица С (8.3.2) выбирается единичной:
С=Е.
Итерационный процесс описывается формулой
х{к+1) = Вх(к) + Д к = 0, 1, ... , (8.3.5)
где л:(0)—заданный вектор. В координатной записи (8.3.5) имеет вид
^+1)=й11х?)+...+г>1>пх<к)+^1, х%+1}=Ь2Лх<?1 +....+Ь2>+й2,
х!,*+1)=6ид*?Ч...+6„,и4*)+</в.
Теорема 8.6. Для сходимости последовательных приближений {лг(Л)} (8.3.5) к точному решению х системы уравнений
х = Вх + с1 (8.3.6)
достаточно, чтобы
|| Я || <1. .(8.3.7)
Доказательство. Пусть х(0)—произвольный вектор. Из
(8.3.5) находим
х{1) = Вх{0)+Д
х{2) = Вх(1) + сі=В {Вхі0) + (І) + (1= В2х(0) + В<і+ Д
х™ = Вх{2)+(1=в\в2х0 + В(і+(Ї) + <і=В2х{0)+{В2 + В+Е)Д (8.3.8)
д. (к+1) = в к+1 х <о > + (Лл+в* " 1 +...+ Е) й.
Покажем, что последовательность {х{к)} имеет предел, если выполнено условие (8.3.7). Действительно, в правой части (8.3.8) первое слагаемое имеет своим пределом нулевой вектор, поскольку
|| 2?*+1х<0>К||Я||к+1||*(0) 11—^ 0.
Второе слагаемое в (8.3.8) имеет предел, если сходится матричный
00
ряд ? В\ Но из (8.3.7) следует, что собственные числа матрицы 1 = 0
В удовлетворяют неравенству (см. теорему 5.2) |Х(В)|<1. Тогда из теоремы 5.1 последует сходимость матричного ряда к сумме— матрице
{Е-В)~' = ? В\
( = 0
Переходя в (8.3.8) к пределу при &-юо, получаем
х=(Е-В)~1Д
а это есть решение (8.3.6), что и требовалось доказать.
И* 323
Для иллюстрации итерационного процесса рассмотрим систему уравнений
хх = О,1 хх — 0,2*2 +1,
х2 = 0,05л:! + 0,1 х2 — 1.
Здесь ^
\\В ||= шах X |*,у| = 0,3<1.
Итерационный процесс
х{1 + 1) = 0Лх^-0,2х^+1,
’ л:?+1) = 0,05л;?Ч0,1x^-1
с начальным вектором л:(1О) = 0, л^О) = 0 дает следующие приближения:
*^=1,0; ‘ лг(2) = 0,1 • 1,0 —0,2(— 1, 0) +1,0= 1,3; *Р> = ...;
х^]= —1,0; л:^2) = 0,05 • 1,0+1,0(— 1, 0)—1,0= —1,05; х^ = ... .
Оценим число арифметических операций, выполняемых за один шаг итерационного процесса. Запишем (8.3.5) на фортране, используя следующие обозначения: вектор л:(*+1)->Х1 (I), */->0(1),
х{к)->Х(1), матрица В (1,1), 1^1,Имеем
ОО 2 1=1,N 8 = 0.
ОО 1 1=1,N
1 8 = 8 + В(и)*Х(1)
2 Х(1) = 8 + 0(1)
Таким образом, при л-> оо число арифметических операций .0(п2). Если заданная точность вычислений в достигается за К итераций, то общее число операций О (Кп2). Сравнивая с вычислительными затратами метода исключения О (л3), можно сделать вывод, что при больших п метод простой итерации будет менее трудоемким.
Слабым местом метода простой итерации, да и других итерационных методов, является отсутствие единого практического подхода к поиску преобразования (8.3.1) в систему (8.3.6), чтобы выполнялось условие сходимости (8.3.7) для любых невырожденных матриц А, хотя для некоторых частных видов А такое преобразование и можно указать, например для матриц А с преобладанием диагональных элементов
п
К,1> ? КЛ к к л.
Каждое из уравнений системы (8.3.1)
яи*1 + ... + аипхп = Ъь 1
разделим на аи и перенесем члены с хи х2, х1_1, х(+1, ..., хп
в правую часть. Получим
аи 1 аи-1 , аи+1 .. а1.п .. .
Нетрудно проверить, что матрица правой части В имеет норму меньше 1. В обозначениях
ьи=~Ч W, Ьи=0;
итерационный процесс (8.3.5) сходится.
8.3.3. Оценка погрешности метода простой итерации. Возьмем в качестве вектора л;(0) нулевой вектор.
Теорема 8.7. Пусть ||2?||<1. Тогда имеет место неравенство
1|х<*)_хК'Г=1^М|1’ к>и (8,19)
где х{к)—к-е приближение, полученное из (8.3.5), л;—точное решение
(8.3.6).
Доказательство. Приближение х(к) ^определяется из (8.3.8) x{k) = (Bk-1+Bk~2 + ... + E)d.
Точное решение:
x={Bk-1+Bk~2 + ... + E)d+(Bk + Bk+1 + ...)d.
Вычитая из первого равенства второе и оценивая нормы, получим
Н *<*>_* И = ця*+2?*+Ч...|| ИК(||Д||Ч||Д||*+1+...)М||. (8.3.10)
Сумма (|| В ||fc +1| В ||fc + 1H-...)—это сумма бесконечной геометрической прогрессии со знаменателем ||2?||; она равна
II д II */(1-ИII).
Отсюда и из (8.3.10) следует (8.3.9), что и требовалось доказать.
Оценка (8.3.9) называется априорной оценкой погрешности, так как, не проводя вычислений, по || В || и || d || можно оценить погрешность А>го приближения х(к\ а по заданной точности
в легко определяется необходимое число итераций. Действительно,
||8||‘|</||=в(1-||«!1),
к-адИ^о-тумо).
Теорема 8.8. Пусть ||2?||<1. Тогда имеет место неравенство
II II II II- (8-3.11)
Доказательство. Заметим, что
x(fc)_x = 5(x(fc-1)-4 (8.3.12)
Прибавим к левой и правой части этого равенства х(к~х) и перепишем его следующим образом:
х«-1)-х=х(к-1)-х{к)+в{х<к~1)-х).
Приравняв нормы левой и правой части и воспользовавшись неравенством треугольника, получим
II II < II *<*" »-х™ II + \\В II II 1}-jc ||.
325
Отсюда следует неравенство
(к- 1)
Из (8.3.12) имеем
Последние два неравенства дают оценку (8.3.11), что и требовалось доказать.
Оценка (8.3.11) называется апостериорной оценкой погрешности, так как ее получают по известной || В || и вычисленным приближениям х(*-1) и х{к). Целесообразно получать как априорную, так и апостериорй^ю оценку погрешности, поскольку их сравнение дает возможность оценить вычислительную погрешность итерационного процесса.
