Том 2 (1160084), страница 7
Текст из файла (страница 7)
„г(е), ... будут обладать слелуюшими свойствами: 1. Вектор г<а' является линейной комбинацией векторов г(е), Аг<о) Аа ),(е)< 36 гзшвнив систем линейных ллгввгличвских гвлвнвний [гл. 6 векторам базиса, будет ортогональным и ко всему линейному многообразию. 3. Вектор г<"> = 0 тогла и только тогда, когда ) <'), Аг<'>,..., А'г(') линейно зависимы. Если г<а> Ф О, то векторы г(з>, г()>,..., г<"> как ненулевые взаимно ортогональные векторы линейно независимы. Это может быть только в том случае, если порождающие их векторы г(~>, Аг(~),..., Аагм) также линейно независимы.
Если же г(а)=-0, то (39) дает линейную зависимость векторов г("), Аг(з>, ..., А"г(з). 4. Если г<"> Ф- О, то коэффициент с),") в (39) отличен от нуля. Это свойство есть следствие второго, так как вектор, ортогональный к некоторому многообразию, не может принадлежать этому многообразию. 5. Каждый из векторов А г(~> (л(= О, 1, 2, ..., )г) может быть представлен как линейная комбинация векторов г(з>, г(1>, ..., г(л>, Коэффициенты этой линейной комбинации определяются однозначно, если ни один из векторов г('>, г<'>, ..., г("> не равен нулю. Среди векторов г('>, Аг('),..., Ааг("> имеется максимальное число линейно независимых.
Таково же число ненулевых векторов среди г(з), г('), ..., г(а). Эти ненулевые векторы образуют базис наименьшего линейного многообразия, содержащего векторы г(з>, Аг<"), ..., А~г(з>. Отсюда и следует утвержление. Рассмотрим теперь наряду с обычным скалярным произведением скалярное произведение, определенное равенством (27) прелылушего параграфа. Последовательность векторов г(~), Аг((), А'г(з)... Ааг(з), можно ортогонализировать в смысле этого скалярного произведения.
Получим новую послеловательность векторов рм> = г(з>, р<')... ры)„.. Для этих векторов будут. справедливы высказанные нами утверждения 1 — 5. Кроме того, системы векторов [г(()[ и (р(0[ будут связаны некоторыми соотношениями. Векторы р(0 при ! (л принадлежат линейному многообразию, порожденному векторами г(з>, Аг<'>,'..., А"г(а>, а вектор г("+') ортогонален к этому многообразию. Таким образом, мы будем иметь: (гО, рб>)=0 при () (. (40) Аналогично показывается, что [рй), гЯ=(р<(), АгП())=(Арр), г(г))=0 при (>)'. (4!) Воспользуемся равенствами (40) и (4!) для установления формул, связывающих векторы р(а>, г(">, р<" э'>, г<"э'>, Ар(">.
Пусть векторы г(з), метод сопгяжвнных гвадивнтов 5! ;н! ..., г<"> отличны от нуля. Тогда и векторы р(э),р<'), ..., р(а) отличны от нуля. Вектор г("э') по (39) принадлежит линейному многообразию, порожденному векторами г(э), Аг(е), ..., А"+1Г(Е), В этом линейном многообразии можно взять в качестве базиса векторы г(э), г<!)...,, г<"), Аа+1г(а). с дРУгой стоРоны. Ааэ1г(а) = А(Ааг(е)) а вектор Ааг(') может быть представлен как линейная комбинация векторов р(э), р(').....
р(а). Таким образом, вектор Аа+!г(е) может быть представлен как линейная комбинация векторов Ар(а), Ар<'>, ..., Ар(а). Векторы Ар(э), Ар<'), ..., Ар(а — ') принадлежат линейному многообразию, порожденному векторами г('),Аг(~), ..., Ааг(<) и, следова)ельно, могут быть представлены как линейные комбинации векторов г(е), г('), ..., г(а).
Поэтому вектор 1(""'> можно записать в виде (аэ') = д)(""1) (~)+а((~ч ~) ()+ -(-<(~"э') ((а) — а Ар("). (42) Помножим обе части равенства (42) скалярно на г<(> ((=О, 1, ..., л — 1). В силу ортогональности векторов ги> и гбо при 1'.—,ь у и равенства (41) получим; (43) Итак, (44) Умножим это равенство скалярно на р<">. В силу (40) будем иметь: 0 =!(а ~') 1(г("), р(")) — а„(Ар( ), р( )1!.
(45) Коэффициент аа отличен от нуля. Действительно, если г(ач 1).= О, то условие аз=О означает, что векторы г('), г(!), ..., г(") линейно зависимы, если же г(а+!) ~ О, то Условие ад=О означает линейнУЮ зависимость векторов г<'), г(1), ..., г(ач-н. И то и другое невозможно. Скалярное произведение (Ар(а), р(а)) также отлично от нуля, По~тому ))а э Ф 0 и (г( ), р< )) чь О.
Так как векторы г ) определяются с точностью до постоянного множителя, то мы всегда можем считать а))",. +н =!. Тогда из (45) получаем: (46) гп'+1> = г(а) — ааАр(а). (47) 38 Решение систем линейнъ>х АлгеБРАических УРАВнений [Гл. 6 Обозначим через х<А> решение уравнения <> — Ах = г<А>, Подставляя в (47) вместо г<1> их выражения по (48), получим: (48) А (х<" +1> — х<">) = ЕААр<А>.
к<а+1> — к<а>+ а у<А>, (49) Итак, (50) г<А+1> — р<А+0= 8 р<о>+8,> <1>+ +8 р<А> (51) Умножим скалярно равенство (5!) на Ар<'> (<=О, 1, ..., При этом получим: ~.=~,= ... =8в,=о. После умножения на Ар<А> будем иметь: (г<А+1>, Ар<А>) = Йа(р<А>, Ар<А>) й — 1). (52) (53) или (г<А+1>, Ар<А>) (р<А> А р<А>) (54) Итак, р<А->-1» — <А->-1> [ ~ > <А> (55) где ра определяются равенствами (54). Нетрудно заметить, что коэффициенты ил и рв можно также вычислять по формулам: (-.<">, .<'>) ( <А> А <А>) (1 <А-ь 1> г<А+1>) (г< >, г<А>) (56) (57) Мы снова пришли к методу сопряженных градиентов. Рассуждая, как и прежде, мы придем к выводу, что процесс должен закон- Рассмотрим теперь разность векторов г<ач-1> — р<А+'>.
Каждый из этих двух векторов представляется в виде линейной комбинации векторов г<~>. Аг<~>, .... АА"1г<~>. Так как векторы р<1> определяются с точностью до постоянного множителя, то мы всегда можем предполагать, что коэффициенты этих линейных комбинаций при АА+>г<в> равны. Тогда разность г<АР'> — р<А+'> может быть представлена в виде линейной комбинации векторов г<в>, АР<В>...,, А"гва или векторов ,<а>,<О,<А» метод сопгяжинных гвадивнтов я (а) <а)) аа= (- ) В-<а)) <<<ао 1) = 1)<а) — а),Вр<а), Е 1), Ч(ао1)) ок 1) ° 47 р<а+ 1) 1 <а+ 1) + о рр<а) (58) Эти последовательности будут обладать указанными выше свойст- вами, конечно с заменой матрицы А на матрицу В.
В частности, д~") = О. Следовательно, и-! 1у<~) = ~ ааВр<а). (59) а-о Пусть теперь р<о) о(о) С (Ь вЂ” Ахи ), (60) где хаа — произвольный начальный вектор и С вЂ” произвольная неособенная матрица. Тогда из (59) следует: о-1 х'= А Ч1=х<о)+~~,'оааА С Вр<а). а-о (61) Итак. если последовательно, начиная с выбранного х<о), вычислять векторы х<"+и= х< )+ааА 'С 'ВР<"), (62) то получим х<")=х'. Для векторов г<а)=Ь вЂ” Ах<") из(62) получим; аа (63) Если вспомнить, что 9<о)=Сг<о) и сравнить (63) и соответствующее равенство (58) для д<ао1), то получим д(а1 = сг<") при любом й.
читься после й ~( л шагов. При этом г(") = О и х<а) = А-<Ь. Может оказаться, что вследствие ошибок округления г<") будет отлично от нуля. Тогда можно проделать еше несколько шагов до тех пор, пока не получим достаточно малое г<а). С другой стороны, может оказаться, что уже после небольшого числа шагов г<") мало. Тогда можно и не продолжать процесса.
Метод сопряженных градиентов можно обобщить на случай произвольной неособенной матрицы А. Пусть  — некоторая положительная определенная симметрическая матрица. Выбираем произвольные векторы р<о)=9<о) и строим последовательности векторов (р<а)) и (<)<а)) при помощи рекуррентных формул: 40 гашение систем линейных йлгеьгйических хвлвнений [гл.
6 Таким образом, (58) можно переписать в виде (о) С. (о) (Сг (й), Сг(й)) ай = = (р(", вр(й)) ' х( +" = х' '+ а А С ' Вр( ), =х +а„ (й+ 1) (й) — ! (й) г + = г — айС Вр (Сг(й+'), Сг(й+')) (Сг(й), Сг(")) р'""') = Сг("+') -+ рй р("). (64) Это и буду~ формулы, соответствующие (29) — (34) для несимметричного случая. Рассмотрим два частных случая. 1-й случай, Выбираем В=А'А и С=А'. При этом получим: А )(о) ,(о) (А'г (й), А'Р(~)) (Ар(й) Ар(й)) х(йо + а„р("), 1'(") — айАР(й), (А'г(й+1) А'г( +1)) (А'г(й).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
