Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 42
Текст из файла (страница 42)
нбо л;)~й — 1. ' Следовательно, ! г) ~ ) ( с ! ть,. (+ )~ А ~( ~~ ( гл, ! ( (т„~ (((А)) ~~ )лт,), а с, ~~ )а,~. «=Й-~ а ! г'"' ~а ( с,- (1 + Ц У, ~ т„1а. Следовательно, «« й ~г<а>!а=Я ~гт")~ (сдл(1+)) ~~ )лс )а 1(Х )=~А г«а), г(а)) (ЦА /! ! г~~') /~ (са Мр„ где са — — схл (1+ 1Ц А (~, Ма — ~~ ~ т« ~а. Таким образом, г~а)-+ 0 при й-+ оо и тем самым сходимость процесса доказана. Оценим быстроту сходимости. Из последнего неравенства следует.
что 247 8 87) теОРемА сходимости С другой стороны, Так"м образом, Х >И. <сз>ИА при всех 7а и при некотором с, > 1. Обозначим Тогда неравенство (б) представится в виде ~а < сз ( 'а ~а ~.1)' откуда оь г, < †" — — 5„ = 8,5а (где О < 8, < 1) и, следовательно,.оа < с,б~г. Далее, У(Х>а>)= У (7(Х<"-">) — У(ХО>)) <т. Х ° <т,~в< ° ТЕ8,'. Итак, 7'(Х( >) = 0 (8,). Вместе с этой оценкой справедливы и оценки ~ г>а> ( = 0 (8г>а); ) У~ > ) = 0 (8гы ) = 0 (8а), (1+ и — 1) ам опля 1дааг (1+ Ч вЂ” 1) ааа наг„ го (~)= (Ф+ д — 1) авв где 8 = 8г'*. Сходимость процесса может быть доказана и при более слабых предположениях относительно множителей релаксации (А. М.
Островский (81). Из доказанной теоремы следует, в частности, сходимость циклического релаксацнонного процесса с постоянным множителем релаксации о, удовлетворяющим неравенству О < д . 2. Сделаем еще одно замечание, касающееся этого случая. Полипом 248 итеелционныв методы вешания линейных систем (гл, ш максимум модулей корней которого определяет быстроту сходимости процесса, имеет старший коэффициент а„а„...
а„„и свободный член (у — 1)" а„а, ...'ап„. Поэтому произведение его корней равно ( — 1)" (() — 1)". Отсюда следует, что максимум его корней не меньше )() — 1! и может равняться этому. числу, только если все его корни равны по модулю >() — 1). Если Ок с)(2, то корни полинома Еч(Г) строго меньше единицы по модулю, так как релаксационный процесс сходится. В силу. непрерывной зависимости корней от коэффициентов полпнома, на границах интервала для су, т. е.
при с) =-0 и ().=2, корни Еч(Г) не превосходят единицы. Но, при ((=О и д=2. 1=-)() — 1( и, следовательно, в силу сделанного выше замечания, все корни Е (1) равны по модулю единице. Это обстоятельство для с) = 0 легко проверяется непосредственно, ибо Ев(Г) = ац ... а„„(1 в 1)".
Для о =-. 2 доказанное обстоятельство не тривиально. Лля квазнтрехдиагоиальных матриц оно было установлено в й 36 прямым подсчетом. 8 38. Управление релаксацией Вместо того, чтобы при проведении процесса координатной релаксации задаваться последовательностью ведущих индексов а рг(ог1 (как это делается, например, в циклическом процессе или в процессе, где управление задается.
десятичной записью числа е), можно выбирать индекс (и на каждом шагу, исходя из результатов предыдущего шага. Так, например, самое быстрое убывание функции ошибки при переходе от Х( ) к Л ) получается, если выбирать индекс („ так, чтобы (, ) г ) (1с — 1) '12 ("1 ) ( (2-1))2 число ь было бы наибольшим среди всех чисел ', где "(ь (ь аи (= 1, ..., и. Иными словами„индекс (ь выбирается тзк, чтобы ! г(ь-1) ~ число " было бы наибольшим.
Процесс релаксации с таким "уса( управлением носит название п р о ц е с с а 3 е й д е л я. С именем Гаусса связывается процесс„при котором ведущий ~ (Ь-1>~ ) гс индекс выбирается нз условия шах . Наконец, правило упрааи (2-1) вления Сауссела определяется вычислением шах)г(( Теорема 38.1. Если ведущий индекс (ь релаксационного коордипатнозо процесса для системы с положительно-определенной латрицей А выбирается так, что *>г~~™ ~> Т ~с(ь 1>~ (0(Т <1, 1'=1, ..., и), (1) 249 УПРАВЛЕНИЕ РЕЛАКСАЦИЕЙ и если е ((1„( 2 — е, то процесс неполной релаксации сходится А региению системы Х' и существует число 9, О(0 (1 такое, что ))Х* — Х(~) !( 0 . Из этой теоремы следует схолимость процессов неполной релаксации Гаусса, Зейделя н Сауссела, так как эти процессы удовлетвоплп аи ряют условию теоремы при т = " для процесса Гаусса, при П1аХ ан Г плп а;( ; = аг '- для процесса Зейделя и при т = 1 лля процесса У П1аХ ан Сауссела.
Действительно, длн метода Сауссела это очевидно. В методе Гаусса имеем г(Р-')) (А-Г) !". .» — — — прн 1=1...., п, а,),(ь ' аи и потому (в-ц( а(х.1Л ) (А ц(. иллан ! 'ь аи Л1ах а(( ~ Аналогичные неравенства имеют место и лля метода Зейлеля. Доказательство теоремы. Введем те же обозначения, что и при доказательстве теоремы предыдущего параграфа. Повторяя доказа'в~ 2 тельство упомянутой теоремы, получим, что рял ~ те сходится, т„ -+ О и г,, -+ О. Далее, из неравенства (Ф-х) 'А ~ (А-ц~ ( 1 ! (а-ц~ (2) 'А заключаем, что )г( ц(-+О при всех 1=1, ..., и. Тем самым схолнмость процесса доказана.
Для оценки быстроты сходимостн используем вытекающее из (2) неравенство Далее, .~ .(2-Ц) ~ -1 и;-Ц 1Н-Ц) )) „-:)) 2 2 С другой с1ороны, Е(Х ) — Е(Х ))» Тхта, и, следовательно, Е'(Х(а-ц) > т, Я т',. Положив ва = .'Е т'2. А 250 итевлционные методы еешения линейных систем [гл. в получим Т,зь ( (~ А (( с;л)ь, откуда аа < с,(аь — а„() (са > 1) ся — ) апач-1 < аа = 0!еа (О ( 01 < !). Таким образом, и, следовательно, ел с О, г. ((с-)) '(ь) (а -1) (в Х' =Х' +0а — е(„ ад,. („ следует г()с-1) (а-н " а)я(ь (а в а(л(г где через .А;„обозначен столбец с номером (ь матрицы А, Переходя к компонентам, получим (ь) (а-1) (а-1) на а.
) = — г; — г( Ч» ь а(я(; Положим г( ') г(а) — а(а) = =. ('и ' ' 7а(, Тогда Т =Т Т .Ч ( () аи у (Х ) ~~ Тз 1 т — Т а( ( с,0,, (3) г=я Справедливы и оценки (а) ~ 0ь ~,(а) ~ (0ь) 0 0ч, При пользовании релаксационными методами с управлением Сауселла, Гаусса, Зейделя на каждом шагу нужно вычислять все компоненты вектора невязки, но затем при определении ведущего индекса для следующего шага учитывается только одна.
Позтому представляют интерес такие вычислительные схемы, в которых испольвовалнсь бы все зги компоненты. Лля построения 'таких схем следует воспользоваться соотно)пением между двумя соседними векторами невявки. Именно. из соотношения й 38) 25! УПРАВЛЕНИЕ РЕЛАКСАЦИЕЙ Положив о,> а(г агу — =г>>ч — =с;; = йй, од >ос он ц ~/-„— )го — Ы ПОЛУЧИМ (>> (й-г> !»-~> г; = г> — гуйгг >>>> й ')( >='((» "— д )<й '>с.. й гй и» >й> (> « „<»-« о> =о> — о о дм (6) пли в векторной форме й > гй >(»> ~(й >> чй >(й «С4 'й о>й> = о>й й> — (г о>й >>Л 'й 'й (6') ои Х1"=Х~" +.Е ФТ" " или Х>' =Х'; +=~ (тйой (У> (о> ! ~ (й-« уй Сумма '~' распространяется на те вначенив л, для которых г(й-'> й 4 ( или у(й — » или о(й-й>) были подчеркнуты.
» » Лля уменьшения влияния ошибок округления, процесс следует время от времени прерывать с тем, чтобы, вычислив приближение, (>айти невязку' непосредственно и начать процесс сначала> Здесь Воч С. и )т> >-е столбцы соответствующих мзтриц (Ь;т), (с,") н (Д«), которые, очевидно, равны соответственно !) 'А, А0 '. О 'АВ '. Лля проведения выбранного процесса соответствующая вспомогательная матрица должна быть составлена заранее. Заранее должны быть выбраны и коэффициенты релаксации (>>, (та, ... Лалее вычисления располагаются так.
При помощи начального приближения составляются л чисел г(о> (или )>о> или о(">). Из них выбирается наибольшее по модулю, подчеркивается и его номер принимается за >Р По формулам (6) составляются числа г('> (или (('> или оу>), из них выбирается наибольшее по модулю, подчеркивается и его номер принимается за (й и т. д. После того, как выполнено достаточное число >(> шагов, компоненты приближения находятся по формулам; 252 итевлционные методы РешениЯ линеЙных систем 1гл. и1 Вычислительная схема становится особенно простой, если все ан — — 1.
В этом случае все три способа управления совпадают и нет надобности в вычислении вспомогательных матриц, ибо каждая из них совпадает с исходной. Если систему АХ= гч преобразовать посредством подстановки 1 1 Х=С7 ''г' и умножением на 1Э ' слева к виду В ЯА0 Я'г'=1'.7 ЯЙ матрица которой симметрична и имеет равные единице диагональнь1е элементы, то применение релаксационного процесса с управлением райносильно применению метода Зейделя к исходной системе. Таллапа 7П. 77 Вычисление последовательных приближений релаксационным процес- сом с управлением при 4=1 0 0 Еь 0 0,11562976 0.193861 13 0.07298031 ! 0 1.28924243 0.80714320 — 0.98675734 0.80714320 1.28924243 — 0.98675734 0 Х 9 г — АХ 0.00000003 1.0391661 0 1,4823928 — 0.00000004 0.0434874 0.00000007 — 1.2577936 В табл.
11!. 11 приведены результаты применения полного релаксационного процесса (ра —— 1) с управлением к системе (9) $23. 1 г" — АХ 2 3 4 5 6 7 8 0.3 — 0.294 — 0.56508 0 -0.16477733 — 0.29372899 О -О. 12794835 0.5 ° 0.104 — 0.05664 0.1806936 0.08304778 — 0.00291999 0.120446! 9 О 03514729 0.7 0.502 0 0.3051432 0 0,04298389 0.9 0 — 0.11044 О.
2625128 0.19538130 253 ф 39] Реллкслцня по длннв вектора невязкн Последовательные векторы невязкн вычисляются по формуле гйб=г1ь И вЂ” г~~ )А — гг где через А обозначен ~-й столбец матрицы А. Таким образом, решение системы, с точностью до 2 ° 10 в каждой компоненте, получено через 100 элементарных шагов, что эквнвалентно приблизительно 25 простым итерациям. Прнмененне процесса с управленнем прн д„= 1.2 приводит к такому же результату через о2 элементарных шага, прн 1т„ = 0.8 через !48 элементарных шагов. 9 39.
Релаксация по длине вектора невяэки Рассмотрим теперь процессы, основанные на мнннмнззцнн нлн уменьшении длины вектора невязкн за счет изменения, на каждом шагу, одной компоненты предыдущего прнблнження. Пусть Х некоторое приближение н 1 номер изменяемой компоненты. Положим Х' = Х+ йео Тогда г' = г — 3Ан и потому (г', г')=(г — 3Ао г — 6А!)=(г, г) — 28(г, А;)+3 (Ао А;)= =(г, г)+ 1 1 [(г,А~) — 3(А„Аз)!' — (А А Здесь А; — К-й столбец матрицы А. Величина (г', г') будет минимальной прн (г, Аг) (Аь Аг) ' так что в случае полной релаксации можно взять Л'=Х+ ' ') ем (Аь Аг) Если заданная система предварительно приведена к такому виду, что все (Ан А;)=1 (что всегда можно сделать посредством замены х; неизвестных х;= 1, мы будем пметь )Г(Аь Аг)/ Х'=Х+(г, Аг) е; (2) (г', г') =(г, г) — (г, Аг)з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
