Том 2 (1160084), страница 5
Текст из файла (страница 5)
После того как матрица 4. найдена, переходят ко второму этапу. При этом сначала решают систему (.у= Ь, (6) а затем находят х из системы «.'х = у. Так как обе системы с треугольными матрицами, то они решаются без трудз. Схема квадратного корня очень удобна, требует небольшого количества операций умножения и деления и очень небольших записей. Всего при решении системы и уравнений придется и раз произвести извлечение корня и проделать из+ 9из+ 2и (8) операций улщожения и деления Произведя умножение матриц в правой части и приравнивая затем соответствующие элементы правой и левой частей, получим следующие уравнения: 9 41 метод оетогонллизлции Проиллюстрируем этот метод на примере системы шести уравнений с симметрической матрицей.
Часть коэффициентов мы не выписывали, пользуясь симметрией. 1 6,1818 0,1516 0,1526 0,2516 0,3145 5,3116 0,2141 7, 1818 0,3114 8,2435 0,2618 9,3141 0,6843 5,3116 0,8998 4,1313 4,1313 3,18!6 0,1415 0,1815 0,1214 9,3141 0,3141 0,2141 8,2435 0,1818 7,1818 0,056911 0,066199 0,038066 3,050415 0,060974 0,055300 0,083585 0,099720 2,299543 0,086111 0,113892 0,084472 0,219198 0,373697 1,978909 2.888522 2,998364 3,041100 1,584361 1,468632 0,726854 0,126331 0,076473 2,867349 0,073120 2,678891 2,48%23 0,367300 0,578973 1,026605 0,474071 1,040932 1,050668 Подставляя найденные значения в левые части системы, получим соответственно 7,181794; 8,243489; 9,314104; 5,311593; 4,131297; 3,181600.
(9) ф 4. Метод ортотоиализации Пусть дана система Ах=5 порядка и. Здесь мы, чтобы избежать в дальнейшем путаницы, над векторами поставили черточки. Решение системы будем разыскивать в виде х= >,еах1е1, (2) е-1 ' где х01, х1З1, ..., х<"1 — и векторов, удовлетворявших условиям (Ахм1. хй1)=О, при й)7 (7е, 1=1, 2, ..., и). (3) Здесь рассматривается обычное скалярное произведение векторов в и-мерном векторном пространстве, т. е. если х = (х,, х,,..., хз) и > (У1 Уы ° ° ° ув), то (х, у) =,~~х;уо Пусть такие векторы найг= дени. Как это делается, будет показано ниже. Рассмотрим скалярное произведение обеих частей системы (1) с х01: (Ах, хгй) =(Ь, х<0) (1=1, 2, ..., и).
(4) 26 Решение систем линейных ллгевелических Рвлвнений [гл, 6 Используя (2), получим: (Ах. х(')) =,~~~ а), (Ах(а), х(')) = (<), х(()) (1 = 1, 2, ..., п) (6) Н-1 или, в силу выбора векторов х(1), ~~.',аа(Ах(а), х()))=([), х(й) (1=1, 2, ..., п). (6) Е-1 Итак, лля определения коэффициентов аа мы получили систему с треугольной матрицей.
Определитель этой системы равен (Ах<1), х<')) (Ах(а), хй))... (Ах("), х<")). (7) Следовательно, если (Ах(а), х(")) ~ 0 (й =1, 2...., п), то аа возможно найти и находятся они без труда. Особенно легко определятся ае, если матрица А симметрическая. В этом случае, очевидно, (Ах<"), х(')) =(х<"), Ах(й) =(Ах('), х(е)) (8) и, следовательно, (Ах(е), х())) =0 при 1 ~ )г (Е, й = 1, 2, ..., п). (9) Тогда система для определения а„принимает вид аа(Ах(а), х<")) =(д, х<")) (1О) (е х(е)) и ( 1 — (а) -(и)) (11) Метод можно обобщить.
Пусть каким-то образом удалось найти систему 2п векторов х<'), х('), ..., х("); у('), у(е), ..., у(") так, что (Ах<"),у('))=0 при [г)1 (й, 1=1, 2, ..., и). (12) Умножая обе части равенства (1) на у'") и используя представление х через х(а), как и ранее, получим: г ~~ а), (Ах(") у(")) = (К ут)) Е-1 (г=1, 2, ..., п). (13) Опять получилась система линейных алгебраических уравнений с треугольной матрицей для определения аа. Несколько усложнив вычисления, можно получить систему диагонального вида, Для этого построим три системы векторов хн), х<е), ..., х( ); у(1), у',а) . Е<ч)1 а 41 метод оетогонллизлции г!», г<з)...., г<"), так что имеют место равенства: Тогда г-1 (го К)=~~.а! 1 ! (г<г), Ах<!)) + а„(г<г), Ах<в)) + + ~~~ а! (г(г>, Ах(й) = аг (г(г), Ах<к>), (17) так как при ((г 1-1 (г<г), АХ<1)) = г<г) Ау<(>+ ~~~ С<1>Ау<А а 1 1-1 = (А'г<г>, у<()) + ~ ~с<1)(А'г<", у<А) = О ,1 1 (18) и прн ()г г-1 = (Ах<!) у(г)) +,У, с(<!') (Ах<'), у(Л)) = О.
,(-1 (19) Таким образом, (г<г), Ь) (г ">, Ах<в)) (20) Остановимся подробнее на первом из описанных методов. Рассмотрим случай, когда матрица А симметрическая и положительно определенная. Последнее означает, что для любого вектора х квадратичная форма его компонент (Ах, х) больше или равна нулю, причем равенство нулю возможно в том и только том случае, если вектор х нулевой. Как мы видели ранее, нужно построить систему ~екторов х<». х<')...,, х<">, удовлетворяющих условиям (Ах<а) х< )) = О (в + г).
(21) Это построение можно осуществить следующим образом, Исходим нз какой-то системы линейно независимых векторов у<'>, у<'>...., у<и). В-1 хн) =у(»; х(е) =у(л)+ ~~ с)")у 1 а-1 г<» = у< )) г< ) = у< ) + .:~~ с(< )у 1 1 (Ах(">, у'">) = (А'г<">, у(г>) = О г-1 (г( 1, Ахн)) — у( ) .+ ~ (>)<")у0), Ах(') 1' 1 ()1=2, 3, ..., и), (14) (А=2, 3, ..., и)„(15) (и ) г). (16) 28 гашение систем линейных ллгевеличаских увлвнаний [гл.
6 например из системы единичных векторов динатным осям: у(п = (П О, О, ..., О) у(м=(о, [, о,..., О) направленных по моор (22) у (=(о, о, о... „[) Далее проводим «ортогонализацию» также, как это делалось в пре дыдущей главе. Принимаем х(п=у(О и ищем х(Я( в виде х(м = уса(+ Л<Я>х('Л 1 Из условия (х(з(. Ах(П) =О находим: (23) [з( Гу(~(, Ах('9 Гх('(, Ах(н) (24) Ищем х<н в виде х (з( у(п + Л(з(х(<> + Л~з(х(зо (25) условия (х(з(, Ахп>)=(хай Ахов)=0 влекут за собой л(,(= Гуси "'"'.
(28) (х(а>, Ах(з() (н Гу(~(, Ах<и) л (х('(, Ах(п) Далее поступаем так же. Процесс будет осуществим, так как все (х((Л Ах(Н) Ф О. Это же обеспечит нам разрешимость системы для определения коэффициентов с(„. Заметим, что в нашем случае это будет процесс настоящей ортогонализации, как он проводился в предыдущей главе, если в пространстве векторов ввести новое скалярное произведение при помощи соотношения [х, у[ =(х, Ау) =(Ах, у).
(27) Нетрудно проверить, что введенное таким способом скалярное произведение будет удовлетворять всем требованиям, которые к нему предъявляются. При решении системы и уравнений по настоящей схеме требуется произвести из+ Зля — л (28) операций умножения и деления. Приведем пример на применение этого метода. Возьмем опять ту же систему, которую мы решали по методу квадратного корня.
Верхняя часть схемы заполнена коэффициентами и правыми частями 29 9 4! МЕТОД ОРТОГОНАЛНЗАЦИИ системы. Мы не проверяем здесь положительную определенность матрицы А, так как это условие не является необходимым для проведения процесса. Вторая сверху часть схемы заполнена компоненТами векторов х!О и коэффициентами ).
Они разделены ломаной линней. Содержание остальных частей не вызывает сомнений, В силу ошибок округления недиагональные элементы нижней части будут отличны от нуля, Их можно подсчитывать для контроля. Их можно также использова~ь в системе и решать последнюю методом последовательных приближений. В силу значительного преобладания диагональных элементов метод будет быстро сходиться.
0,1415 0,1815 0,1214 9,3141 6,1818 0,1818 7,1818 0,3141 0,2141 8,2435 О,! 516 0,1526 0,2516 0,3145 5,3116 0,2141 0,3141 0,2618 0,6843 0,8998 4,1313 7,1818 8,2435 9,3141 5,3116 4,1313 3,1816 1 ~ — 0,0294( — 0,0508 — 0,0229 — 0,0245 — 0,0346 Х) л — 0,0294 1 — 0,0286 — 0,0247 — 0,0206 — 0,0425 0 0500 — 0 0286 1 0,0133 — 0 0292 — 0,0295 — 0,0215 — 0,0217 — 0,0268 — 0,0133 — 0,0288 — 0,023 1 ~ — 0,0327) — 0,0719 — 0,0327! 1 ~ — 0,1625, — 0,0243 — 0,0190 — 0,0368 6,1818 0,1818 7,1765 0,3141 0,2049 8,22! 7 0,1415 0,1773 0,1091 9,3050 Й, хб)) 6,1818 7,1765 8,2217 5,2879 3,9161 «1 —— 1,16181 ав = 1,1193; а = 1,0605; ав —— 0,5194; ав 0,6386; ав = 0,3672; х) — — 1,0410; хв = 1,0507;,тв — 1,0264; хв — — 0,4741; х,.
= 0,5789;хв = 0,3672. О! х)в) — А!3) х)) х1 ) -!в) Ах)1! Ахн! Ах<в) Ах!4! Ах!4) Ах!4) !Ахн), х1')) (Ах)т), хпв) (Ах)в), х!4)) (Ах)4) х!М) !Ах!в), х)в)) (Ах<в), х)4!) 0,1516 0,1481 0,2397 0,3042 5,2879 0,2! 41 0,3051 0,2422 0,6686 0,8593 3,9161 7,!818 8,0324 8,7192 4,8330 3,3769 1А381 30 Рещение систем линейных АлГеБРАических УРАВнений (гл, 6 В случае несимметрической матрицы процесс ортогонализациь проводится точно так же, Пусть векторы х<'1, х<з!... „хнч уже построены, Тогда х<"+'1 ищется в виде А х<»+1<=у<А"Н -! — ~ р<"+1<хи<. 1-1 (" 3) Система в случае несимметрической матрицы будет треугольной.
Аналогично строится система «биортогональных» векторов, т. Р. система 2Н векторов, удовлетворяющих условию (12). При этом у<1<, у<11, ..., у<я< — ПРОИЗВОЛЬНЫЕ Л ЛИНЕИНО НЕЗавИСИМЫХ веКтОрОВ, а векторы х<Н, х<11...,, х<"1 строятся последовательно в виде х<"+'1 =- у<А+11+ ~~'., Т)ьч'нх <'. 1-1 Коэффициенты Т)А"н находятся из системы а Х т(А+н(Ахи<, у<<<) = — (Ау<А+1), у<И) (/= 1 2... А).
(32) <-1 коэффициенты с)А< и с<(»1, при и (15), удовлетворяющих услосистемы: Так же поступаем, отыскивая построении систем векторов (14) виям (16). При этом получим две А-1 '„'„, с<ю(Ау«<, у<я) = — (А,ха<, у< в), 1-1 А-1 "~~ ~<А>(А'у<11, С<!)= — (А' <А>, <Д) <-1 1 (33) (г'=1, 2, ..., А — !), ~ нз которых и определяем с<Ю и «<<А<. $5. Метод сопряженных градиентов Пусть А — симметрическая положительно определенная матрица. Рассмотрим функцию у(х) =(х, Ах) — 2(б, х). (1) Это — целая рациональная функция второй степени относительно компонент (х,, ха, ..., х„) вектоРа х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
