Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 36
Текст из файла (страница 36)
Величина ~х(") — х(" " 1 здесь оказывается малой не потому, что приближения х'" ') и х'") близки к решению, а потому, что метод сходится медленно (ср. с замечанием на с, 98). Пример 6.1. Используя метод простой итерации в форме Якоби, найдем решение системы 6.25х( — хг + 0.5хз = 7.5, — х) + 5хг + 2. 12хз = — 8.68, 0.5х( + 2.12хг + 3.6хз = -0.24. (6.15) с точностью е = 10 з в норме ~ - '1 Вычисляя коэффициенты по формулам (6.5), приведем систему к виду (6.4) х1 0.1бхг — 0.08хз + 1.2, хг — — О. 2х) — 0,424хз — 1 736 хз = -0 1389х1 — 0 5889хг — О.
0667. (6,16) В последнем уравнении коэффициенты даны с точностью до погрешности округления. Здесь 179 Достаточное условие сходимости метода простой итерации выполнено, так ~Щ = и 10.24, 0.624, 0,7278) = 0.7278 ~ 1. Примем за начальное приближение к решению вектор х'о) = (О, О, 0)т и будем вести итерации по формуле (6.6) до выполнения критерия окончания (6.13), где в данном случае е( = (1 — 0.7278)/0.7278 10 з в 0.37 10 з.
Значения приближений в табл. 6.1 приводятся с четырьмя цифрами после десятичной точки. Таблица 61 и 0 1 2 3 4 х[ и) 1 1.2000 0.9276 0.9020 0.8449 -1.7360 -1.4677 -1.8850 -1,8392 -0.0667 0.7890 0.6688 0.9181 1.7360 0.8557 0.4173 0.2493 0.0000 .( и) 2 0.0000 х' и) з ~ (и),(и-)) ~ 0.0000 12 13 14 15 х( и) 1 0.8006 -1.9985 0.8003 -1.9993 ,( и) 2 .( и) з 0.9990 0.9987 ~ х( и) х( и-1) ~ 0.0008 0.0005 0.0003. 0.0018 При и = 15 условие (6.13) выполняется и можно положить х) = -0.800 х 1 0.001, х2 — — -2.000 1 0,001, хз = 1.000 х 0.001.
В данном случае точные значения решения х) = — 0.8, х2 = — 2, хз = 1 нам известны (см. пример 5.16). Заметим, что в действительности решение с точностью до в = 10 з было получено уже при и = 13. 5. Система с положительно опредененной матрнцей. В случае, когда А — симметричная положительно определенная матрица, систему Ах = Ь часто приводят к виду 180 0 0.16 -0.08 0.2 0 -0.424 -0.1389 -0.5889 0 1.2 -1.736 — 0.0667 0.8002 0.8001 -1.9995 -1.9998 0.9995 0.9997 (А* — в), (6.1Т) которому отвечает метод простой итерации: х' ь"' ~ = х~ гг~ — т(Ахг 1'> — Ь), (6.18) реально вычисляемые на ЭВМ приближения югп> отличаются от идеальных приближений х~ "'.
Поэтому нельзя утверждать, что для любого е ) О найдется номер ив(е), начиная с которого все приближения будут находиться в е — окрестности решения. В действительности же существует некоторая а — окрестность реше- ния, после попадания в которую приближения х' "' дальнейшего уточнения при выполнении итераций не происходит. В подтверждение сказанного приведем следующий результат. Т е о р е м а 6.2.
Пусть 1В~ < 1. Предположим, что вычисляемая на ЭВМ с помощью метода простых итераций последовательность хг и> удовлетворяет равенствам х~п" > = Вх~ "1 + с + ~гп~, п > О, (6,19) где ~~пг Е МР, ~~гпг ~ < о, Если вычисления по формулалг (6,6) и (6.19) начинаются с одного начального приближения х<вг = к~в', то для всех п 1 1 справедливьг следующие оценки погреиьности; 1 х' "' — х' п~ 1 < е, (6.20) 5х<и~ — х5 < ЦВ$п$хгв> — х$ + е, (6.21) 181 Здесь В = Š— тА и параметр т > О выбирают так, чтобы по возможности сделать минимальной величину ~В~2.
Пусть Л,ьгп и Л ~ — минимальное и максимальное собственные значения матрицы А. Известно, что условие ~В~г < 1 будет выполнено, если взять т е (О, 2/Л,„~„). Оптимальным является выбор г = 2/(Лып + Л„н„). В этом случае ~В~г принимает минимальное значение, равное (Л~„— Л„й„)/(Л~„+ Л„йп). ' Чаще известны не значенияЛвйп и Лнвх, а их оценки вида О <,а < < Л„,„~ Лагг„4 М либо вида Лвп„< М.
В первом случае полагают г = 2/(,и + М), а во втором т < 2/М (например, т = 1/М). Заметим, что в случае, когда Лгпгп < Лп1а„(а так бывает очень часто) при любом выборе т б (О, 2/Л~„), имеем ~В~г и 1. Поэтому в этом случае метод (6.18) сходится очень медленно.
6. Влияние ошибок округления. Из-за наличия ошибок округления (6.22) — ь Здесь е =— 1 — ~В~ Таким образом, метод простых итераций устойчив, но гарантированная точность метода ограничена величиной я. Критерий окончания (6.13) применим, если е < е.. З 6.2. Метод Зейделя ( Ь+1) Х1 Ь)2 '2 (ь) + Ь(ЗХЗ (ь) + Ьгзхз (И + " + Ь)аха + с1 (ь) + " + Ьгаха + с2 (ь) + - + Ьзаха + сЗ (Ь хг = 2131 (Ж) ь (Ь~1) (~1) =Ь (~1) +Ь 3 31 х1 3гхг (6.23) +' ' +Ь х' + — Ьа1*1 Ьагхг аз~3 Введем нижнюю и верхнюю треугольные матрицы 0 ь12 'ьз ...
Ьа 0 0 Ьгз " Ьга 0 О 0 " Ь3а 0 0 0 ... 0 ь, о о ... о Ь31 ь„ь ь ...о 0 0 0 ... 0 Тогда расчетные формулы метода примут компактный вид: 1 Людвиг Зейдель (1821 — 1896) — немецкий астроном и математик. 182 1 Описание метода. Пусть система (6.1) приведена к виду (6.4) с коэффициентами, вычисленными по формулам (6.5).
Метод Зейделя( можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что при вычислении очередного (х + 1)-го приближения к неизвестному х; при 1 > 1 используют уже найденные ((е + 1)~ приближения к неизвестным х), ..., х; ),-а не Ь-е приближения, как методе Якоби. На (Ь + 1)-й итерации компоненты приближения х(" " вычисляют. ся по формулам х<А 1) = В)х<«+1) + В2х<«) + с. (6.24) Заметим, что В = В) + В2 и поэтому решение х исходной системы удовлетворяет равенству (6.25) (6.26) 1В1+1В1 < 1 То)да при любом выборе начально)о приближения метод Зейделя схо- дится и верна оценка по)ре<аности 1х<п) — х1 ~ дп1х«)) — х1, (6,27) )де д = 1В21/(1 — 1В)1) < 1.
и Вычитая из равенства (6.24) равенство (6.25), имеем х< « ') — х = В)(х< « " — х) + В2(х< «) — х). (6,28) Вычисляя нормы левой и правой частей этого равенства и используя свойства норм, получим — 1 В)(х< «) ) — х) + В2(х< «) х) 1 < ЯВ)11х<« ') — х1 + 1В211х<") — х1, Следовательно, <«)) х1 4: Цх<«) х1, д — 1Щ/(1 1В<1). Так как это неравенство верно для всех к 1 О, то из него следует оцен- 183 Метод Зейделя иногда называют также методом Гаусса Зейделя, процессом Либмана, методом последовательных замещений. 2. Достаточные условия сходимости.
Т е о р е и а 6.3. Пусть 1В1 < 1, <де 1В1 — одна из норм 1В1, 1В1). То)да при любом выборе начально)о приближения х«)) метод 3ейделя сходится со скоростью геометрической про<рессии, зна.иенап)ель которой 4 4 1В1. Доказательство этой теоремы опускаем. Оно довольно громоздкое, хотя и не сложное. Приведем более компактное доказательство следующей теоремы, близкое к доказательству теоремы 6.1. Т е о р е м а 6.4.
Пусть выполнено условие ка (6.27). В силу условия (6.26) имеем О ч в < 1. Поэтому х(п) х при м. 9 Особо выделим часто встречающийся на практике случай систем с симметричными положительно определенными матрицами. Т е о р е и а 6.5. Пусть А — симметричная положительно определенная матрица. Tогда при любом выборе начального приближения х(в) метод Зейделя сходится со скоростью геометрической прогрессии. Отметим, что никаких дополнительных априорных условий типа малости нормы некоторой матрицы здесь не накладывается.
3 Апостериорная оценка погрешности. П р е д л о ж е н и е 6.2. Если выполнено условие ((В~ с 1, .то для метода Зейделя справедлива апостериорная оценка погрешности 1х'"' — И ~ ~ х( "' — х( " ') ~, и ь 1. 1 (6.29) и Положим й = и — 1 и запишем равенство (6.28) в следующем виде: Х( п) Х вЂ” В (Х(п) Х) + В (Х(п-1) Х(п) ) Тогда ~х(") — х1 К ~В~Дх("' — х1 + 1В 1 1х("" — х("' 1, Х(п)Х(и 1)~(я2 (6.30) где ег = ~ ~ е. 4. Геометрическая интерпретация метода. Приведем геометрическую интерпретацию метода Зейделя в случае т = 2, т.е.
в случае решения системы 01111 + а12У2 Ь) аг(х( + яг 2 = Ьг. 184 откуда и следует неравенство (6.29). И Полученное неравенство позволяет сформулировать простой критерий окончания итерационного процесса. Если требуется найти решение с точностью е > О, то итерации метода Зейделя следует вести до выполнения неравенства ()х(") — х'" ') ~ )(Вг~/(1 — ((В~~) < е, или эквивалентного ему неравенства х' )'+1) 1 .()( 1) г ЬгХг(((') + с1, + сг, — ( )с+1) где 6)г — — — а1г/а)1, с1 — — 61/а)1 1)г1 = — аг)lагг, сг = 6гlагг.
Рис. б.1 Пусть приближение х(") уже найдено. Тогда при определении х', ' координата хг — хг( ' фиксируется и точка х перемещается па( в)) ( lс) раллельно оси Ох) до пересечения с прямой 11, Координата х) точки пересечения принимается за х1~~~ . Затем точка х перемещается вдоль прямой х1 — — х) до пересечения с прямой 1г. Координата хг точки (А 1) пересечения принимается за хг На рис. 6,1, а, б приведены геометрические иллюстрации, отвечающие сходящемуся и расходящемуся итерационному процессу Зейделя. Видно, что характер сходимости может измениться при перестановке уравнений, Пример 6.2. Используя метод Зейделя, найдем решение системы (6.15) с точностью з = 10 з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
