Том 2 (1160084), страница 12
Текст из файла (страница 12)
Нетрудно показать, что первое и второе достаточные условия (9) и (10) 9 9 для сходимости метода простой итерации будут одновременно достаточными условиями и для сходимости процесса Зейделя. Иногда метод Зейделя дает более быструю сходимость, чем простая итерация, Так будет, например, если выполнено условие (14) предыдущего параграфа. Обозначим ~! а01 у 1 р= гпах 1 ~'З (9) 1аи1 * 9 10) линейные ОдношАговые методы пеРвого поРядкА ез 64 гашении систем линейных ьлгвагьичвских ягьвнвний [гл. 6 Так как условие (14) выполнено, то р < 1. Обозначим также ач, ВЧ аи аи !р 1 (10) Тогда простой итерации будет соответствовать вычислительная схема х(а+!1= ~~'., с.
хт>+д, 1 ьг г 1 1 (1ч1Л д методу Зейделя схема (11) х("+о= ~~'., с, х("+н+ ~~'., сь хга>+д,. 1 г ч+1 По (11) и (9) разность между точным решением х и (я+1)-м приближением. полученным простой итерацией. будет иметь оценку (12) [[х — хгь+н[[! < р.[[х — хга>[[!. (13) З то же время, если ввести обозначения 1-1 ч Х [сч [=рч; ~~~~ [сг [=71' ,шах "' =р'.
1 — Рч г 1 В 1.1. 1 (14) то для разности между точным решением х и (я — 1)-м приближе- нием, полученным по методу Зейделя, получим оценку [хч — х(а+о ( < ~1[[х — х<"+'>[[, + Те[(х — х(г1~! (15) -и [[х — х(ьч !![[! < р.'[[х — х!"![[о (16) Но Х! с,у[=Ь+71 <р <1 1 В-ьг) (17) Р1+71 — — = ) О.
'И рч (1 — рч — тч) 1- [н 1 — рч (18) О геюда р= шах(рч+71)) шах гг =р', (19) что и требовалось доказать. Теорема. Если матрица А симметрическая и положительно .определенная. а приведение системы Ах=К к виду х=Сх+с7 осуществляется путем деления уравнений на диагональные элементы и последующего перенесения всех членов кроме хо где г — номер уравнения, направо, то метод Зейделя сходится. 6 10] линвйныв одношаговые методы паевого пояялка 66 — (в + с) ' в = — (в + с) с (20) по модулю меньше единицы. Пусть Л; и Лу — лва каких-то собствен- ных значения этой матрицы, а г; и гу — соответствующие им соб- ственные векторы, Тогда мы можем записать: — (В+.С)-'С,, = Л,го — (В+С) 'С'гу=Л)г~.
(21) Отс юла С'г; = — Л;Вг, — Л;Сго (22) Рассмотрим скалярные произведения (С'го г;) и (С'г, г;). Они бу- дут представляться в виде (С'го г;)= — Л;(Вго г;) — Л;(Сго гу), (С'г., г;) = — Лу(Вг, г;) — Лу(Сгу, г1). (23) Используя свойства скалярного произвеления, получим: (С'гу, г;) = (г ч Сгв = (Сго гу), (Сгч г;) =(ггн С'г;) = (С'го г)), (24) (Вг), гз) = (г;, Вг;) = (Вгп г)). Поэтому второе из равенств (23) можно переписать в виде (Сгз гу) Лу (Вг гу) Л (С гз г)) (25) пли (Сгз, гу)= — Л,(вго г;) — Л, (С'го г.), (26) Решая (26) и первое из равенств (23) относительно (Сг,, гу) и (С'гп гу), получим: Т,(л,-ц (Сг;, г.) = ~ (Вгп г1), 1 — Л,Л) 4(л; — П (С'го гу) = (Вг;, г.).
1 — ЛЛ (27) Проверим, что при выполнении наших условий все собственные значения матрицы (Аго г.)=(Вгь г)+(Сг;, г;) Лу(Лг П Л (Лу — П + 1 Л,Лу + 1 Л,ЛТ =[ +(С',, гу)= П вЂ” ЛВ (1 — Л;) (Вгн гу) = — (Вгн гу). 1 — ЛгЛ) (28) Положив здесь 1=у, найдем: (29) Отсюда р (1 ) ~г ( гг.го (Агь го (3О) Так как А положительно определенная, то все ее диагональные элементы положительны. Поэтому (Аго гг) ) О, (Вго гт) ) О. (31) Заметим, что Л=1 не является собственным значением матрицы — (В+ С) 'С'. Действительно, если бы существовал такой вектор г, что — (В+С) 'С'г=г, (32) то мы имели бы — С'г = (В + С) г (33) или (В+С+С') г = Аг= О. (34) а это равенство возможно только при г = О, так как существует обратная матрица А Итак, из (30) следует, что 1 — (Л,Р>О, (35) и утверждение доказано.
Можно доказать также, что если матрица А симметрична и ее диагональные элементы положительны, то положительная определенность матрицы А необходима для сходимости метода Зейделя. 8. Релаксационный метод '). Метод Зейделя является разновидностью метода наименьших квадратов. При этом в качестве векторов сл, о которых говорилось в 9 8, берутся в циклическом порядке единичные векторы, направленные по координатным осям. т) См.
обзорную статью М. В. Николаевой сО релвксвционном методе Саусвеллвн Труды математического института им. Стеклова,т. ХХИ!1, 1949 г. 66 гишиник сисгвм линвйных алгивнаичискнх гвдвниний (гл, 6 Тогда ф 111 67 метод скОРВЙшеГО спускА Иногда бывает целесообразно для упрощения вычислений или для улучшения сходимости изменить порядок уравнений в заданной системе или же нумерацию неизвестных. Можно пойти и еще дальше, а именно при каждом цикле процесса последовательных приближений брать свой порядок. Так, например, поступают в рглансацаонном методе. Выбирают начальное приближение (х<е), х<е), ..., х<е)). Вычисляют так называемые невязки 3 =а. х<е)+а. х<е)+ ... +а.
х<е) — <) . (36) Находится х<'), удовлетворяющее равенству а. х<))+а,х~")+ .. +а. х<е)=)) (37) а,х<И+аех<))+азх<е)+,. +а, х<е) = Ь (39) где 7' — номер уравнения с наибольшей по модулю невязкой, Так продолжаем и дальше, пока не используем все л уравнений. При этом будут найдены все хВ. Тогда начинаем второй цикл, который производится так же, как и первый, но вместо (х<е), х<")...,, х<е)) используется (х<)), х<')...,, х~<)). Повторение циклов прололжают до тех пор, пока не достигнут требуемой точности. Иногда при выборе уравнения, из которого вычисляется «улучшенное» приближение, руководствуются не принципом максимальной по модулю не- вязки, а каким-либо лругим.
Бо всех случаях стараются брать уравнения в таком порядке, чтобы в кратчайший срок получить нужное решение. Этот довольно-таки неопределенный принцип требует от вычислителя навыка и искусства, Поэтому релаксационный метод трулно осуществить на машинах. Релаксационный метод является нестационарным. ф 11. Метод скорейшего спуска В качестве примера нелинейных методов рассмотрим в этом параграфе метод скорейшего спуска, о котором уже говорилось в й 4. В методе скорейшего спуска исходят из некоторого начального приближения х<е)=(х<е), хы), ..., х<% и по нему находят следующее приближение х<') =(х<)), х<)), ..., х<ч)) по формуле х<1) х<о) + < ) <о) (1) где < — номер уравнения с максимальной по модулю невязкой. Затем полсчитываем невязки 3'=а х<)~)+а "<ао)+ .
+а. х<о) д (< чь<) (33) и подбираем х<'), уловлетворяющее равенству 68 гвшанни систем линейных алгввваичвских твавнвний (гл. 6 гдв г(о) (г<о) г<о) .<о)1 г(о) () ~ о д(0) ц'' 1 (3) ~Ч,1 г(0) Яо (4) 0 „(о) <о) ) 111 о~ П) 1 ч,1 г(о)1 а— (6) ~ л 1.(0) После того как будет найден вектор х(1), по нему находят вектор х(а) так же, как Рп находилось по х(о), Процесс продолжают до тех пор, пока не достигнут требуемой точности, Мы не будем входить в подробности вычислительных схем для метода скорейшего спуска, а рассмотрим вопросы сходимости.
Ограничимся случаем симметрической положительно определенной матрицы А. Обозначим собственные значения матрицы А через Л1>~)~> ... >~Л0~0 (7) и соответствуюшие им ортонормированные собственные векторы через г1, ао, ..., г„. Тогда, если х — произвольный вектор л=~,а,+разо+ ...
+р„з„, (8) то будем иметь: (Ах, л)= ~1Л +~9, + ... +Д1Л . (9) Отсюда Л (~~+Я+ ... +Д~) =Л (х, х) ((Ах, х) ( <Л,(8,+8",+ ... +8„')=Л,(х, л). (10) Если матрица А не является симметрической и положительно определенной, как это предполагалось при выводе формул (3) и (4). то можно рассмотреть систему А'Ах=А'б, матрица которой симметрична и положительно определена. В этом случае вместо формул (3) и (4) мы получим: (6) 1,0 1 1 68 5 11! мвтод скогвйшвго спускА Следовательно, для нашей матрицы всегда можно найти две такие постоянные т ) О и М ) О, что т(х, х) ((Ах, х) ~ М(х, х).
Рассмотрим разность ) (х<'>) — ) (х<о>), где >" (х) — функция, определенная формулой (1) й 5. Простые вычисления лают (г(о) г(о))з )'(х<1)) )'(х(о>) аа(г<о> Аг<о>) — 2ц (г<о>, г<а>) * (1з) о ' а ' (г(о) АР(о)) Для разности У'(х(а>) — у(х*), где х* — точное решение системы, по- лучим: Таким образом, у(»о)) — Х(к<о>) (г<о>, р~'Р У(»(о)) У(» ) (г<о> 4г<о)) (А-<Р(о> —,.<а)) ' (14) <1з~ + Тала+ ' ' ' + То»о (15) Тогда (18) (19) (1~+та+ ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
