Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 36
Текст из файла (страница 36)
Доказательство. Пусть Х< ) -+ Х*. Тогда, кзк мь) видели, Х' есть решение системы и, слеловательно, Х* — Х< )= В(Л вЂ” Х< ))= =... = В (Х* — Х'о)), откуда Вь (Л" — Х< )) -+ О. Так как зто должно иметь место при любом векторе Х' '. необходимо, чтобы  — + О, <о) ь лля чего, в свою очерель. необходимо, чтобы все собственные значения матрицы В были меньше елиницы по модулю [теоремз 13.2[. Достаточность условия непосрелственно вытекает из формулы (3), ибо В -+0 и Е+В+ ... +В -+(Š— В) <=А <, если все собственные значения матрицы В меньше единицы по модулю.
Так как условие теоремы 30.1 трудно проверяется, судить о схолимости процесса послеловательных приближений лучше при помощи достаточных признаков, связанных непосредственно с элементами матрицы В. Некоторые достаточные признаки вытекают из теоремы 30.2, % 30) метод последовательных пгивлижений 209 Теорелеа 30.3. Для того чтобы процесс последовательных приближений сходился, достаточно, чтобы какая-либо норма матрицы В была меныие единицы. Доказательство. Действительно, если ',)В!)(1, то все собственные значения матрицы В меньше единицы и потому на основании теоремы 30.1 процесс последовательных приближений сходится. Ладим теперь оценки быстроты сходимости процесса последовательных приближений в терминах нормы. При этом выбор нормы векторов совершенно безразличен, но норма матриц должна быть согласована с выбранной нормой векторов.
Теорема 30,3. Если )(В',! (1. то !!Л. Х(гн!!(!В!!ь!!Х(0)!!+!!6Ц!!В!!" ь .ь 1 — !!В!! Доказательство. Имеем !(Х' — Х 1)! =-!!(Š— В) Π— (Е+В+ ... -(-Вв ')6 — Вьхгф!! ( (!!(Š— В) ~б — (Е+В+ ... + В ~)6!!+!!В~Л ~1!!( ( !!(Š— В) 0 — (Е + В + ... + В ~) й !+ !! В !!!! Л ~! !!, ( (!,В!!ь! Х!Ю!!+ !!ЙЦ 1В!!" 1 — !!В!! Часто бывает важно сравнить точность двух последовательных приближений, т. е. сравнить величины;!Х* — Х'и1;! и !!Х* — Хь '!!. Такое сравнение можно проводить на основании следующей теоремы. Теорема 30.4. !!Х* — Хь1/! (!!В!!!!Л" — Хь '!!!. Доказательство. Лействительно, из равенств х'=вх'+о, л"'=-вх"' "+0 следует, что Х' — Х'"'= В(Х* Х!и-'г) 1.
Если лье !ЬВ ! ( !ь ( 1 при 1 = 1, 2. ° ° . и то процесс после- 1-1 довательных приближений сходится, причем ! х; — х!ь) ! ( (ь гоах ! ха — х~~~ ~! !, где Х =-(х„..., х„) и Х =(хт, ..., х„) . !ь) г (ь! !ь1Ю (б) гд ч ьы л к в » в н е в Отсюда !!л" — л""'!', = !! в (х" — лч'-'!) ',! (! в!!'!л лч — 1!! (б Введенные нами в й 13 векторные нормы (кубическая, октоэдрическая и сферическая) и согласованные с ними нормы матриц дают следующие легко проверяемые достаточные признаки сходимости процесса последовзтельных приближений и оценки быстроты его сходимости.
210 итеРАционные метОды РешениЯ линейных систем [гл. 1п в В. Если ~ ~бы[ (2(1 при 1'=1, 2...., п, то процесс после- 1-1 довательных приближений сходится, причем ~~.'„( х! — х( ~ «( 2 ~~„'~ ~ х! — х( (7) 2 П1. Если ~2 Ь!2 (р ( 1, то процесс последовательных прибли- ,, А.! жений сходится и ( х х ! ! 1 ) ( 2 2 (8) Укажем еше на один путь построения достаточных признаков сходимости процесса последовательных приближений. В уравнении Х=ВХ+О с матрицей (2Н (!! ...
(21„ ~21 ~22 ' ' ' ~~2в — ЬВ1 222 ' ' ' (2ав введем новые неизвестные хг =Ргао где Рз некоторые положительные числа. Тогда система (1) превратится в систему Р1Я1 = Х (22урззу+ и! Д-1 или ччч РУ 1 . = Э:(2" ° — г + — д. 4 4 У Р1 У Р! (9) Очевидно, что компоненты последовательных приближений Х~~~ для системы (1) и Л! ! для системы (9) тоже связаны соотношениями х, =р;в1, если только эти соотношения имеют место для исход- (2> <21 ных приблнкений Х~ ~ и Л~ ~. Поэтому процессы последовательных приближений для систем (1) и (9) сходятся или расходятся одновременно. и, следовательно, всякое достаточное условие сходимости процесса последовательных приближений для системы (9) является вместе с тем достаточным условием сходимости для системы (1), мятод послвдовлтвльных пвивлижаннй 211 $301 при 1=1, ..., н 2) ~~)Ьг ~ ° — ~1 при /=1, ..., л (10) г=т 3) ~; — "Р'<1, Р( то процесс последовательных приближений для системы (1) сходится. Замечание.
При практическом вычислении итераций мы можем поступать двумя способами. 1) Положим Х~~~= О. Тогда Хпо=о+ВО+ ... +В'а. Для вычисления Х' ~ мы вычисляем последовательно векторы О, Вб, ..., В~о и находим нх сумму. Это удобно вследствие единообразия процесса вычисления, а также потому, что каждое последующее слагаемое является лишь поправкой к сумме предыдущих. Недостатком этого способа является возможное накопление ошибок от округления с возрастанием числа слагаемых.
2) Вычисление ведется непосредственно по формулам Х1" 1 = ВХ1~ 0 + 6. Здесь каждое приближение является как бы исходным и поэтому нет необходимости на первых шагах процесса проводить вычисления с большой точностью; возникающие ошибки впоследствии сглаживаются. В качестве примера найдем решение системы О. 78х, — 0.02хг — 0.12х, — 0.14х„= О. 76 — 0.02хз+ 0.86хг — 0.04хз+ 0.06хз — — 0.08 — 0.12х, — 0.04х, + 0.72хз — 0.08х, = 1.12 — 0.14х, + 0.06хг — 0.08х, + 0.74хз = 0.68. Решая эту систему по схеме единственного деления, находим (1 1) х, = 1.534965 хг= 0 122010 хз — — 1.975156 х, = 1.412955.
Таким образом, если можно указать тзкие положительные числа Р„ ..., Р„, что выполняется одно из условий и12 итеРАционные методы РешениЯ линейных систем 1Гл. !и Для применения процесса последовательных приближений приведем систему к виду Х=ВХ+6, положив В= — А. Получим х, = 0.22х, + 0.02х, + 0.12х, + 0.14х, + 0.76 х,= 0.02х,+0.14х,+0.04х,— 0.06х,+ 0.08 х, = О.! 2х, + 0.04х, + 0.28х, + 0.08х, + 1.12 (12) х4 — — 0,14хг — 0.06ха+ 0,08хо+ 0.26хг+ 0.68. Нетрудно видеть, что достаточные условия сходимости процесса последовательных приближений выполнены. Таблица )П. 7 а Схема вычислений по формуле Х!"! = ~~~~ Вго г-о 1) Вго, 1=0,..., 14. 0.68 2.64 0.76 0.08 1.12 2) Лцаг = ~ Вгб для Ф = 12, 13, 14, г-о 0.3984 О.!95264 0.09421056 0.04527913 0.02174095 0.0!043649 0.00500961 0.00240463 0.00115422 0.00055403 0.00026593 0.000!2765 0.00006127 0.00002941 0.0304 0.008640 0.00223488 0.00055572 0.00013570 0.00003285 0.00000792 0.00000190 0.00000046 0.00000011 0.00000003 0.00000001 ОЛ624 0.207936 0.09692928 0.04589292 0.0218836! 0.01047017 0.00501763 0.00240654 0.00115468 ОЛ10055414 0.00026596 0.00012765 0.00006127 0.00002941 0.3680 О.
! 86624 0.09197568 гг! 0.04172340 ! 0,02160525 ~ 0,01040364, 0.00500170 ~~ 0.00240272 ~ 0.00115376 0.00055392 ( 0.00026591 0.00012764 О.О!я!06127 О.ОООО 94! ) 1.2592 0.598464 0.28535040 0.13645117 0.06536551 0.03134316 0.01503686 0.00721580 О. 00346312 0.00166219 0.00079783 0.00038295 0.00018381 0.00008823 9 30! метОд последовательных пвивлижений 213 Для сравнения хода итерационного процесса в разных вариантах проведем его тремя способами. Именно: 1) Вычисление последовательных приближений производим по формуле Х( ) = ~~~ В 0 (см. табл. !!!. 1).
)=о 2) Вычисление последовательных приближений производим по формуле Х("> = ВХ(а '>+ О при Х(о> = 0 (см. табл. Н!. 2). 3) Снова вычисляем Х()=ВХ( '>+6 при Х(>=(1, О, О, О)' (см. табл. !!1. 3). Поясним табл. !В. 1. Первая часть таблицы содержит компоненты последовательно вычисляемых векторов В)(4. Последний столбец является контрольным, В нем записываются числа ~~~с(х1, где с = (у) ;=1 =-.~46( (числа с должны быть вычислены заранее и приписаны Таблица !11. 2 Вычисление приближений по формуле Х()'> = ВХ(а-"+ а; Х(о> = а 0.68 Х(о) 0.08 132 0.76 3,8992 4.4977 1,1584 1.3537 1.4479 1.5824 1.7903 1,8873 1.9332 0.1104 1.0480 1.2346 0.1190 0.1213 1.3266 4.7830 4.9195 4.9849 5.0162 1.3713 0.1218 !.3929 1,4033 5.0312 5.03838 1.41072 1.41188 1.41244 5.04! 87 5.04354 5.04434 5.04473 5.044920 5.0450069 1.41271 1.41284 1.4129(6 1.4129289 Х(1) Х(а) Х(о) Х(4) Х(о) л"'> Х( > Хчо> Хо о> Х04) Хо о) Хч)о) Х04) 1.4932 1.5149 1.5253 1.5303 1.53273 1.53389 1.53445 1.53472 1.53485 1.534910 1.5349385 0.1220 0.1220 0.1220 О.! 2201 0,12201 0.12201 0.12201 О.! 2201 ОЛ 22010 0.1220096 1.9551 ! 9655 1.9705 1.97292 1.97408 1.97464 1.97491 1.97504 1.975101 1.9751299 214 итзглционныв катоды ввшзння линайных снствм !гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
