Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 23
Текст из файла (страница 23)
Так как погрешность г,=х„— х удовлетворяет уравнению г,~, = г„— тк+,В-'Аг„, получим 1ге+, 1лл = ~~гь Д' — 2тьм (Агм В 'Аг~) + т3„(АВ 'Агы В 'Аге), или ((гь+1~~А~ 1~гЕ~!лл 2твм(ГМ ИЬ) + т1 (АИМ ИЬ). Следовательно, ~гь„~)~А будет минимальной, если положить (би аа) ть~1 = (Ав„, шь) (25) При этом для неявного метода скорейшего спуска справедлива оценка (24), где Л„м (П 'А) м1п Лвах (~ А) 4. Метод сопряженных градиентов. Метод сопряженных градиентов является двухшаговым итерационным методом, т. е. для нахождения новой итерации х„+, используются две предыдущие итерации х„ и х„,. Следовательно, здесь возрастает требуемый объем памяти, нужно помнить не только вектор х„, но и х„,.
Применение двухшаговых методов оправдывается тем, что при правильном выборе итерационных параметров скорость сходимости будет выше, чем у одношаговых методов. Например, рассматриваемый далее метод сопряженных градиентов при любом начальном приближении сходится за конечное число итераций. Пусть А — матрица системы (1) и  — симметричная положительно определенная матрица.
Рассмотрим следующий класс не- 120 Здесь а,+„т„,— итерационные параметры, которые будут определены далее. Для начала счета необходимо задать два начальных приближения х, и х,. Начальное приближение х„будем задавать произвольно, а вектор х, вычислять по одношаговой формуле, которая получается из (26) при й=О, а,=1, т.
е. по формуле В"' + Ахо =). т, (27) Если параметры а„+„т,+, найдены, то новое приближение х„+, выражается через два предыдущих значения х„и х,, по формуле х„+,— — а»+,х,+ (1 — сц~,) х,,— т,„,а,+,гв„, (28) где щ,=В-'гь г,=Ах„— )'. 6. Минимизация погрешности. Перейдем к вопросу о выборе итерационных параметров в методе (26). Для погрешности гх= =х, — х получим уравнения зА»! а~.~., (Š— т,~.,В 'А)х,-!- (1 — а».„,)г~,-„й= 1, 2, г,= (Š— т,В-'А)х,.
Введем, как и ранее, вспомогательную функцию о,=А1пгь для которой ~~оД=~1гД,. Функция о, удовлетворяет уравнениям о»„= а»м (Š— т»,С) о» + (1 — а» ) о» „й = 1, 2, ..., (29) о, = (Š— т,С) о„ (30) где С=А"'В 'А"'. Будем считать, что А и  — симметричные положительно определенные матрицы, удовлетворяющие неравенствам Т,В(А(7,В, 7,)7,)0. (31) Тогда С'=С)0, причем 7,Е( С("ОЕ. (32) Исключая последовательно из уравнений (29), (30) векторы о„ о„ ..., о„ „ найдем, что и,=Р„(С) и„ (33) где Р,(С) — многочлен степени й от оператора С, удовлетворяющий условию Р,(0) =Е. Поставим задачу выбрать итерационные параметры т„а, так, чтобы при любом п=1, 2, ... была бы минимальной ~1о„!!=1~я„~! . Обратим внимание на отличие от постановки задачи, возникающей при построении оптимального чебышевского набора итерационных параметров (см.
$6). Там при фиксированном п требовалось найти параметры, минимизируюшие 1~я„~~ . Теперь же требуется большее — минимизировать ~~г„~~ при каждом п. 121 явных двухшаговых итерационных методов: В " +' ' +Ах»=-1, й=1,2, ... (26) т»+1"»ы Далее, рассмотрим погрешность о,=Р„(С) о„ возникающую на й-й итерации, н запишем многочлен Р,(С) в виде Ро(С) =Е+ ~~ аР'С'„ 1=1 где а<о' — числовые коэффициенты, определяемые параметрами аь ти 1=1, 2, ..., й. Тогда (35) оо = о, + ~ а и С'о„й = 1, 2, ... о =- о Найдем условия, которым должны удовлетворять коэффициенты а!о>, минимизирующие !!о„!!'.
Из (36) получим Ф о !(о„!!'= ',"~ а';"'а';"'(С'оо, С'оо)+ 2,Я а)"'(оо С'оо)+!!оо!!', (37) ш=1 ! =1 т. е. !!о„!!о является многочленом второй степени по переменным аоо1, ..., а(о>. Приравнивая к нулю частные производные д!!о„!Р/ /да)"~, 1=1, 2,..., и, приходим к системе уравнений л ~', а,'"~ (С'о„Соо) + (С'о„оо) = О, е=1 решение которой а!о>, 1=1, 2, ..., и, и обращает в минимум !!о„!!о. 6. Выбор итерационных параметров в методе сопряженных градиентов.
Целью дальнейших рассуждений является нахождение параметров а„т„й=1, 2, ..., и, для которых выполнены условия (38). Заметим прежде всего, что (38) можно записать в виде (С'о„о„) =О, /=1, 2, ..., и. (39) Л ем ма 1. Условия (39) эквивалентны условиям (Со„о„) =О, /=О, 1, ..., и — 1. (40) Доказательство. Согласно (36) имеем 1 Со; = Со, + ~ а)пС'"о„ (36) (38) Параметр т, находится из условия минимума !!о,!! при заданном векторе о,. Так же, как и в методе скорейшего спуска, получаем (Со„оо) (34) !! Соо!!" Отметим, что при таком выборе т, выполняется равенство (Со„о,) = =О, т. е.
векторы о, и о, ортогональны в смысле скалярного произведения (и, о),=(Си, о). поэтому ! (Соп о,) = (Со„о,) + ~ а!и (С'"о„о„) = 1=1 !+1 = (Со„о„) + ~я~ а,'", (С'о„о„). (41) Пусть выполнены условия (39). Тогда, если /+!<и (т. е. !< <и — 1), то (Со„о„) =О, (С'о„о.) =О, ..., (С'+'о„о.) =О. Поэтому из (41) при !'<и — 1 получим (Соь о„)=0. Итак, условия (40) следуют из (39). Покажем, что верно и обратное, т. е. из (40) следует (39).
Доказательство проведем индукцией по числу !. Условие (40) при 1=0 совпадает с условием (39) при 1=1. Предположим, что условия (39) выполнены для 1= =1, 2, ..., й, и покажем, что они выполнены и для 1'=й+1, где й<и — 1. Из (40) при)=й получим, учитывая (36), 0 = (Соэ, о„) = Со, + ~Ч; а!" ~Сьио„о„ а=1 Ан =(Со,, о„)+ ~а!"', (С'о„о„). (42) По предположению индукции условия (39) выполнены при 1'= =1, 2,..., й. Поэтому из (42) получим аР' (С~ "о„о„) = О. Посколькуа<~~чьО (так как Р,(С) — многочлен степени й), отсюда получаем (С"э'о„о„) =О, т. е.
условия (39) выполнены и при 1= =й+1. Лемма 1 доказана. Она потребуется для построения оптимальных итерационных параметров в методе (26). Заметим, что число и в лемме 1 предполагалось фиксированным, в то время как при постановке задачи оптимизации мы требовали, чтобы !!о„!~ была минимальной при любом п=1, 2, ... Поэтому оптимальные параметры надо отыскивать не из условий (40) при фиксированном п, а из условий (Соь о„) =О, п=1, 2,..., !'=О, 1,..., п — 1.
(43) Если такие параметры будут найдены, то это будет означать, что построена ортогональная (в смысле скалярного произведения (и, о),=(Си, о)) система векторов о„о„..., о„, ... Поскольку пространство решений системы (1) имеет размерность т, постро- 123 Поэтому (о,„„Со!) = — а1+1т11-1(Со1, Со!) (47) при!=0, 1,..., й — 2. Покажем, что для этих же значений 1' выполняются равенства (Со„, Со,) =О. Запишем уравнение (29) прн /г=)': о э, = а!!.1(Š— т,~1С) о!+ (1 — а!+,) о,, и найдем отсюда ! 1 Со; = — о; — [о;„— (1 — а;„) о; 11.
1+1 "!11 1+1 Умножая предыдушее соотношение скалярно на Со, и учитывая симметричность матрицы С, получим (Соь Со1) = ! ! =- — (оь Со1) — [(о)аь Сц1) — (1 — а;„) (о! „Со1)1 = !'~1 /ыт/и ! ! = — (Соп о1) — [(Со;„, о1) — (! — а, „,) (Со; „оь)]. 1)м !11 !Ч1 Из (45) при (=й имеем (Соь о1) =О, (Со)„„ц1) = О, (Со, „о1) =О, /=0,1, ..., й — 1, 1=0,1, ..., й — 2 ! = 1, 2, ..., А.
124 енная ортогональная система будет содержать не более т векто- ров. Это означает, что начиная с некоторого и (п(т) погрешности о обратятся в нуль, т. е. метод сойдется за конечное число ите- раций. Перейдем к построению итерационных параметров, для которых выполнены условия (43). Параметры а, и т, найдены согласно (34): (Соо оо) 1со 11 (44) Пусть параметры т,, т„..., г„а„а,, ..., а, уже выбраны опти- мальным образом. Тогда согласно (43) выполняются условия (Соь о1) =О, 1=1, 2, ..., й, 1=0, 1, ..., ! — 1.
(45) Построим оптимальные параметры т1!.„а1+,. Согласно лемме 1 при п= в+ 1 должны выполняться условия (Соь о,+,) =О, 1=0, 1, ..., й. (46) Часть из этих условий, а именно условия (46) при 1=0, 1,..., й — 2, следует из (45). Действительно, согласно (29) имеем (оэ+„Со;) = а1„(ом Со)) — а1„т4„(Сом Со;) + (! — а1„) (о1 „Со;). Из (45) прн !=й и (=й — 1 получим, соответственно, (Сов о1) =О, 1=0, 1, ..., й — 1, (Соп о4,)=0, /=О, 1, „й — 2. (48) (49) из которого находим значение параметра т,+,.' (Со», о») т»+1 = /! Со»1» (51) Обратимся теперь к уравнению (50) и исключим из него выражение (Со„, Со„,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
