Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 42
Текст из файла (страница 42)
е. для итерационного процесса д~ь~ ау+ Ып (ь 1 2 ) (х'ь' произвольно) достаточное условие сходимости есть )(а'й' ~ 1. (2) Д о к а з а т е л ь с т н о. Отправляясь от произвольного век. тора х'~>, строим последовательность приближений х"'= р+ах"' хио = р+ ах'н, х'ь'=()+ссх'ь ". Отсюда хрн (Е+ы ),зь+ +ссь-1) и+иьх(ы 316 сходнмость итвглцнонных пгоцвссов (гл.
~х Так как при )!а(! < 1 имеем )!а !! — +О при й — оо, то (см. гл. У(1, ф 10) 1пп аа=О ОФ Иш (Е+а+аз+... +аз ') = ~ а"=(Š— а) А ю А=о Поэтому, переходя к пределу прн и — оо в равенстве (3), получим; х= Иш х' '=(Š— а) ' р. (4) т. е. предельный вектор х является решением системы (1). Так как матрица системы (1) Š†а †неособе, то решение х единственно. Следствие 1. Процесс итерации для системы (1).сходится, если: н (!а(!и=шах ~л~~~(ау ! < 1; а) илн (! а !! с = шах Х ! аг1 ! < 1' ! г 1 или / л и )(а)!ь — — )/ ~ч! Д(а~ (в < 1. в) В частности, процесс итерации заведомо сходится, если элементы матрицы а удовлетворяют неравенству где и †чис неизвестных в системе (1).
Действительно, а), б) и в) являются простейшими каноническими нормами матрицы а. Следствие 2. Для системы (5) Этим доказана сходимость итеративного процесса. Кроме того, из равенства (4) имеем: (Š— ) =В или х=ах+р, оценка поггвшности пгнвлижений пгоцвссх итвглции 317 процесс итерации сходится, если выполнены неравенства: л а') (ап(> ~~.','(а;7( (1=1, 2, ..., и) 7=» илн б') где штрих у знака суммы означает, что при суммировании пропускаются значения 7 =у, т. е. сходимость имеет место, если модули диагональных элементов матрицы А= [а;7] системы (1) или для каждой строки превышают сумму модулей неднагональных элементов этой строки, или же для каждого столбца превышают сумму модулей недиагональных элементов этого столбца. В самом деле, при наличии неравенства а'), очевидно, выполнено соответствующее неравенство а) следствия 1. Для доказательства второго утверждения в системе (5) положим: х; = — — ' (1 = 1, 2, ..., л), вп где я~ — новые неизвестные.
Тогда получим систему — а =.Ь; (1=1, 2, ...„и), (5) (, нут для которой процесс итерации сходится или расходится одновременно с процессом итерации для исходной системы (5). Приведя обычным способом систему (5') к специальному виду (1) и используя условие б) следствия 1, получим достаточное условие сходи- мости процесса итерации для системы (5): ~~~„~ — "~ < 1 (7'=1, 2, ..., и) с=~ нли )а7 (> ~~/аО( (7'=1, 2, ..., п). »=1 й 2.
Оценка погрешности приближений процесса итерации Пусть х'» и и х'»~ (а~1) — два последовательных приближения Решения линейной системы д=оск+ р. При р~1 имеем: ((х' "ю-х'»'() - 11 х'»+" — х<" ((-)- +((х'»»" — д"""!)+... +11 х'"'ю — х"'г и('. (1) 318 СХОДИМОСТЬ ИТЕРАЦИОННЫХ ПРОЦЕССОВ >Х Так как х'"+и=ах' >+р хнм = ах' '>+ р, х'"+и — х' '=а(х' ' — х' и) то при >с~1, или !!х х>~>!!н.. !! !! !(х>~> х>а и(! 1 — ))а!) Если )! !)~ —,', то предыдущая формула принимает вид !! х — х>"> !! ~ !! хох> х>ь-» (), т. е. в этом случае, если !! х'"' — х'" и !! ( е, то и !!х-х'"'!! ( е. В общем случае, если в процессе вычислений будет обнару>кено, что ))х'"' — х'" »!)~ — е, где >у=!)а!! (1, то !!х — х'"')! (в и, таким образом, !х> — х<">! =е (>=1, 2, ..., л).
н, следовательно, ,>)х' " — х>">!(~ ((а(! ()х' ' — х'" ~()а(! ")/х>"+» — хмч(! при н»й)1. Поэтому из формулы (1) получаем: (! х>Р+"' — х'"' (! ~ (! х'"+" — х>а>!!+ + )! а (! (! '"+" — '"' ((+... -)- (! а !! ' (! '"+" — > "> !! =к, )! х'А+ и — х>а> !).
1 1 — )! о!1 Переходя в последнем неравенстве к пределу при р- ою, получим окончательно: (! х — х'" )! ~ )! (2) 1 — !)а!! аа 2) оцвнка погевшности пеивлижвннй пеоцвсса нтвелции 319 Прн ЯтОИ предполагается, конечно, что последовательные приближения х»> (/=О, 1, ..., >>д) вычисляются точно, т. е.
в них полностью отсутствуют погрешности округлений Из формулы (2), используя полученные выше оценки для нормы разности двух последовательных приближений, будем иметь: !( а 11» (,д> ! — Цай ц частности, если выбрать х>о> () то х>д> Цхп' — х>а>!) =Цап Ц» ЦаЦ Ц 3Ц. Следовательно, Цх — х>д>цч-,!~"!! ц()ц. П р им е р. Показать, что для системы (2') 1Охд — ха+ 2хд — Зхд = О, х +10х,— х„+ 2х,=5, 2хд+ Зхд+20х,— х, = — 10, Зх + 2хд+ ха+20хд=!5 (3) х,= 0,1х, — 0,2х, +0,3хд; х = — 0,1х, + 0,1х — 0,2хд + 0,5; ха= — 0,1х, — 0,15х,+0,05х,— 0,5! х,= — 0,15х,— 0,!х, — 0,05ха+0,75.
(3') Отсюда матрица системы 0 О,! — 0,2 0,3 — 01 0 0! — 02 — О,! — 0„!5 0 0,05 — 0,15 — О,! — 0,05 0 Используя, например, норму ЦаЦ„получим: ЦаЦ>=идах(0,35; 0,35; 0,35; 0,55) =0,55 (1. С~~довательно, процесс итерации для системы (3') сходится. процесс итерации сходится. Сколько итераций следует выполнить, чтобы найти корни системы (3) с точностью до 10 а? Р е ш е н и е. Приводя систему (3) к специальному виду, получим' 320 сходимость нтвтационных птоцессои (гл. ~х За начальное приближение корня х примем — 0.5 ~' хы'=В= Отсюда Ц р !! с = О+ 0,5+ 0,5+ 0,75 = 1,75.
Пусть й — число итераций, необходимое для достижения заданной точности. Применяя формулу (2'), будем иметь: !!и!!,'+'!!5!1, 0,55'+ 1,78 !!Х вЂ” Х''!!» ! !)а!! = 0,5 Отсюда 0,55ле' < — 10 ' 178 и (Й+ 1) !и 0,55 ( !и 45 — !д 175 — 4, т. е. — (й+ 1) . 0,25964 < 1,65321 — 2,24304 — 4 = — 4,58983.
Следовательно, О 25964 4,58983 й ) 16,7. 9 3. Первое достаточное условие сходимости процесса Зейделя Т е о р е м а. Если для линейной системы х= ах+ р выаолнено условие !!а!1. <1 где и ))сс!! „=гпах ~ )а;.), /=! (2) то процесс Зейделя для системы (1) сходится и единственному ее решению при любом выборе начального вектора хм'.
Можно принять й= 17. Следует отметить, что теоретическая оценка числа итераций, необходимых для обеспечения заданной точности, практически оказывается весьма завышенной. ф 31 первое достаточное Условие схолнмости процесса зейлеля 321 доказательство. Пусть х>~1=(х>1>, ..., х>ь>) — й-е при блнжение процесса Зейделя. Имеем: л х/!ь> =,Я~ а//х/!1>+ ~~'„а /хы-1>+ ц (3) /=/ (/ = 1, 2, ..., л; Й = 1, 2, ...).
При выполнении условия (2) система (1) допускает единственное решение х= (х1, ..., х„), которое может быть найдено, например, методом итерации. Имеем: х, = ~.', а,. х + ()/ (!'= 1, 2, ...). (4) / 1 Вычитая из равенства (4) равенство (3), получим: 1 — 1 л х/ — х)а> = ~ а// (х/ — х!">)+ ~ а/ (х — х!1-1>)1 /= / 1 отсюда /-1 л (х/ — х!'> ( ~ ~ ( и/ ( ~ х; — х!'> (+ ~~."> ! а,; ( ) х/ — х!а-1> ~ /=1 >=/ (! = 1, 2, ..., Л). Согласно смыслу принятой нормы ((х — х/а> )! = шах ~ х/ — х!"' (, позтому ! х/ — х!1> ! ( 1( х — х'"' )) „ (/= 1, 2, ..., Л). Следовательно, из неравенства (5) выводим! ~х — х!Я>~в.
р,.((х — х>а>(! +>/ ((х — х/Я ~>))~, (6) где р;= ~ (а/ ) и >// — — ~~'„)а//(. > 1 /=> Пусть а=а(й) есть то значение индекса !, для которого ~х,— х!1>)=шах(х/ — х!/а>(=)(х — х>">>1 „. ! Полагая 1 =а в неравенстве (6), получим: ((х-х>а>(! ~р,()х — х'")(„+//,)(х — х'" 1>>>„ нлн ((х-х>">'й ~, ~' ((х — х!а "!( Отсюда )(х — х'"')( и )ь й х — х'" 1> >) „, В П. Лояядовял я Н.
Л. Маров (7) (гл. ~х 322 оходимость итвгационных пгоцвсоов где )ь=шах— ш 1 — Р~ (8) Покажем, что р яь, !! а (! „( 1. Действительно, так как л р1+д1 ~~„', (аО)<(!а!! (1, /=а то р, ( !! а !),„— Р1 и, следовательно, — ь~3|х — я ~3 и и 1-Р( 1 — Рг 1 — Р1 Поэтому р=(!а(!.С 1. Из неравенства (7) вытекает, что !)х кпч!! ~„а!!» ...,!! и, следовательно, й 4. Оценка погрешности приближений процесса Звйделя по ш-иорме Пусть х' ' и к' +" — две последовательные итерации процесса Зейделя. Применяя к этим итерациям преобразования, использованные при доказательстве теоремы 8 3, получим неравенство, аналогичное неравенству (7) из $ 3: !!к,е+,> — х,а,)! (р)(ха, »,ь „(! !пп х'"'=х, тем самым сходнмость процесса Зейделя к искомому решению до- казана.
3 а м е ч а н и е. Так как для метода итерации мы имеем !!х — х(ь)()~!!а((„))х — хй и!), а для метода Зейделя получим к<а~!!~р(!» х~а-ы)(, где )а «( (! а (!, то в условиях теоремы 1 сходимость процесса Зейделя в общем несколько лучше, чем сходимость процесса простой итера- ции. Из формулы (8) следует, что в этом случае, при применении метода Зейделя, систему (1) выгодно располагать так, чтобы первое уравнение системы имело наименьшую сумму модулей коэффициентов Ча= Х !ату!. 1 1 я ч) втотов достаточное тсловив сходимости птоцвссл звадвлв 323 Отсюда () х1ь+р1 — хйм 'й „< )) х"'г1 — х"" "() „+ +~)х — х (~ + +~) ' — '3 < <р ~) "-""-"~(.+р'-'~!"" — "--((.+...
...+)ь~!х1"1 — хь "1) <1 ,~ ))х1"1 — х' -"((„. При р — со будем иметь: 1!ю х'"+"'=х и, следовательно, ~) х — хдо ~( < —," ~|х1" — х'" "1) где ~ ~аО( (а=свах ~,, 11 а(1 „. ' — Хl гу( 1=1 В частности, из полученного неравенства выводим: 11 х — х'ь' (( < — ' '11 хо'-х1ь1 '3 „, т. е. )х х(и(< вал)х<1> — х~ь>~ (1=1, 2, ..., и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
