Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 34
Текст из файла (страница 34)
(Напомним, что свободные члены для единообразия вычисления мы записываем в левых частях уравнениИ). аы ам ам ам .„!! 0 с Схема состоит из трех частей. В первой части записана матрица коэффициентов системы (снмметричная по условию). Во второй части мы записываем постепенно элементы столбцов матрицы Л. В нижней части записываются диагональные элементы матрицы С и элементы матрицы Г'. Отметим, что элементы 1г-й строки матрицы Г' мы получаем, умножая столбцы матрицы А на а-И столбец матрицы 2 и деля полученные суммы на элемент с„а.
Столбец матрицы Е заполняется по формулам (9). В табл. !1. 15 дан иллюстративный пример. Таллина П. та Компактная схема эскалаторного метода 5 27. Метод Перселла С решением Х=(хн ..., х„) системы уравнений анх,+ ... +а„,х„— Л=О а„х, + ... -)- ан„х„— ун = О 19б тОчные методы РешениЯ систем линейных УРАВнений [Гл. и связывается ') вектор 2=(к«, ..., х„, 1)'=(Х, 1)' арифметического (и+ 1)-мерного пространства )[„ь«в естественном представлении. Уравнения системы истолковываются как условия ортогональностн вектора л с векторами А;=(ан...., а(„,— «()'((= 1. 2, ..., л). Решение разыскивается следующим образом.
Шаг за шагом строятся базисы подпространств убывающих размерностей ЯВ.,=Ф"= Л")=« .... Л("), где Й вЂ” подпространство, состоящее из векторов, ортогональных («) к векторам А,, ..., А„. Каждый последующий базис У]с+« ° ° ° Уч+« а) (л) строится из предыдущего „(а-«) „(ь-«) в виде двучленных линейных комбинаций У( )=У( ) — с( ~У), ) ((=1+1, ..., и+1), (2) Коэффициенты с(а) определяются из условия ортогональности к вектору А„, что дает (А, у(а ')) с(а) = ' "' (3) [Аа, Уа(" «)) Лля осуществимости процесса нужно, чтобы все скалярные произведения (Аа, У(А-')) были отличными от нуля.
В качестве базиса ФВ) =)с„+«берется естественный базис У«" =(1. О, .... О)',..., У'„",, =-(О, О, ..., 1)'. Из хода процесса ясно, что на всех шагах вектор 1'„+«будет иметь (а) (И+1)-ю компоненту, равную единице. Единственный базисный вектор Р„е, подпространства Й ортогонален ко всем векторам А,,... нн) (я) ..., А„и имеет последнюю компоненту, равную единице. Таким образом, вектор Уя("~)«дает численное ре«пение системы (1). Метод Перселла по существу очень близок методам, связанным с треугольной факторизацией и, в частности, если матрица системы симметрична, с эскалаторным методом.
«) Перс ел л [1], 197 9 271 6181 Х Т! ьо 1133 о ! оо о ! ю:=3 В с ь Я «. г оооо И ь ооо « оо о ! о оь ««о ь о о ! о 3 Ы оооо оо ! оооо Д « оо оо оо о Ж 3 ь оо Я Ы ! ооьо Ф о « Ы о оь ь' ь ь «! о о ь' оооо оооо ь о о о о о оооо О О' Х а О ! ! Х Х е. 8. О Х и Ф й И О О «.'! !" Й Х Х Х Ф Х О Ф О М Ф ! ч Х ч Ф Х Х О Ф О „Йу оЫо о ! о ь -3 о««ьо о о о о о'о оо о ооо ооо о оь ьо о о о о МЕТОД НЕРСЕЛЛЛ «Ы О «! О Х й Х 8. О Х «3 М Х О а й Х М О О Ы « М «й Х Х Ф Х О Ф О » Ф Х Х Й Ф О ооо о 63 ооо а ь оо оо о о о о оо оо о ооо ооо о оо ао ь ооо 193 точныв методы вешания систем линейных гвавнаний !гл.
1г действительно, если составить матрицу 1 ага ага ° ° ащ лаа ' ' ' заи йв столбцы которой состоят из первых п компонент векторов 1г,, кя, ..., $~„, то эта матрица будет очевидно правой треугольной, , ло ы-и а матрица АЛ, в силу условий ортогональности будет левой треугольной матрицей. Если матрица А симметрична, то матрица л совпадает с соответствующей матрнцей эскалаторного метода !Э 26, (3) ). В табл. И.16 и !1.17 приводится решение систем с несимметричной н симметричной матрицами, рассматривавшимися ранее в табл.
!!.1 и П.!а. Схема состоит из трех частей. В первой части записываются последовательно вычисляемые компоненты базисных векторов $Г; 1, во !ю второй осуществляется контроль вычислений посредством проверки выполнения условий ортогональности. В первой строке третьей части записываются (Аь Ъ'Ь '1), во второй строке коэффициенты с! 1. 5 28. Метод пополнения для обращения матрицы Метод пополнения для обращения матрицы основывается на следующей идее. Пусть  — неособенная матрица, обратная для которой известна, и — некоторый столбец, и — некоторая строка, А = В+ ип. Ясно, что и, и,п, игпа ... и1п„ иапг папа ...
иап (ог па* ' ' ' ' ои) — ияпг и~па есть матрица ранга один. Покажем, что матрица, обратная к А, находится по формуле ') А =В' — — В'ипВ', с» Т де -т.=1+. В:.'и. Конечно, предполагается, что т + О. а) дуайр н уо !ц. ' $28! метод пополнения для овгащяния матвицы 199 Действительно, (В+ им) (В ' — — В ~иоВ 11= Е+ иоВ ~ — — иоВ т / т — — и(оВ 1и) оВ 1=Е+иоВ а— 7 — — ио — — (Т вЂ” 1) иоВ = Е. 1 г 1 -1 т Тем самым справедливость формулы (1) доказана.
Установленная связь показывает, что элементы матрицы А легко находятся, если элементы матрицы В 1 известны. Полученную формулу можно, в частности, применять в случае, если матрица А получается из матрицы В изменением одной строки, т. е. если А = В+Ъ', где Ъ' матрица, все элементы которой равны нулю, кроме элементов изменяемой строки. Пусть эта строка имеет номер й. Тогда Ь' = ао = е,р, где о †ненулев строка матрицы У и е„ столбец, и-й элемент которого равен единице, а все остальные равны нулю.
Следовательно, А '= —, (В е»)(оВ )= 1+ о(В 'е») где р» — й-й столбец матрицы В '. Обозначив через и хй столбец матрицы А ', получим ( '. Ру) ау = ~~ — +, р». (2) Метод пополненпя для обращения матрицы заключается в следующем. Данная матрица А=(а;~) рассматривается как последний член последовательности Ае= Е, А,, ..., А„ = А, причем переход от матрицы А» , к матрице А» осуществляется посредством замены й-й строки матрицы А» , на й-ю строку матрицы А. Таким образом, матрица А получается в результате и-кратного применения описанного выше процесса. Выпишем формулы перехода на й-и шагу, Пусть а<») — у'-й столбец матрицы А» .
Тогда ~о а1 а(») — а(»- ) Ры,'3 ~ и(»- ). (3) 1+(о», а~," 1) ЗдеСь о» вЂ” — (аы... „а„»,, ..., а„„). В табл. В.18 дано обрашение матрицы табл. 1!. 1а методом пополнения. Каждый шаг процесса прОисхОдит по следуюшей схеме (й-1) я "» (й-1) а !+ Р), Здесь (тl ай 1)). Р РР В последней части таблицы расположена матрица А Метод пополнения можно проводить по другой вычислительной схеме, несколько более развернутой' ). Обозначим с(» М =Го'., аы 1)) В этих обозначениях с» (й -1) а(й) — а(й-1) ~ а(»-1) ~й-1) й Числа с;, связаны соотношением (й) (4) с(й-1) с(й-1) (й) (й 1) С,й Сй.
см — — см( [ с)й-1) Действительно. с; ) = (о',, а(й') = [о,' ( ~ „(й-1)1 (й-1) (»-1) (й 1) Сй( СС» 0 1, (й-1) + сйй Т(й) — г'-й столбец матрицы С»=[с(й)), будем Обозначив далее через иметь с),й ') Т'"'=т(" "— ', М," ". (б) !+С(»1, ') Таким образом, матрица Сй получается из матрицы Сй, совершенно так же, как матрица Ай из матрицы Ай,. Для перехода от матрицы Ай', к матрице А»' (и от Сй, к Сй) нужно кроме матрицы Ай'1 знать лишь элементы й-й строки матрицы Сй,. На следуюшем шаге понадобятся соответственно элементы а+1-й строки матрицы Сй, для построения которой по формуле (б) в свою очередь нужно знать элементы а+ 1-й строки 1) А.
П. И р ш о в [1 [. 200 точныв мвтоды гвшвния систвм линвйных гвйвнвний [гл. и 202 точные методы гашения систем линейных юеавнений [тл. и Таблица Д, 79 Обращение матрицы при помощи „склеенная схемы метода пополнения 164 0.42 0.42 0.66 0.66 1.62 ) — 0.42 1 0.09320 ~ 0.16280 — 0.17640 — 0.21418 0.09320 0.11316 0,42 О 50996 0.16280 0.19767 0.82360 0.60661 — 0 50996 1.21418 0 0.19767 0.49247 0.70570 — 0.30215 — 0.43297 — 0.15482 — 0.22185 0.11316 0.16216 0.69785 0.21304 — 0.43010 — 0.68623 ~ — 0.22277 0.22185 0.49788 — 0.50213 — 1.00854 0.68624 1.37832 0,22278 0.44746 — 022185 — 0.44559 0.37165 — 0.12304 1.33221 — 0.26143 0.44746 1 0.42 0.54 1( 0.66 ~) 1 0 0.54 0.66 1,21418 — 0.50996 0 0.57698 156172 — 0.43010 — 0.70570 0 2.50756 — 0,12305 — 1.01148 -1,37832 0 0 0.32 0,44 1.23253 — 0.16216 0 0 0.32 0 0.22 — 0.54 0 — 0.29160 — 0.13640 — 0,49247 ~ — 0.11316 1 — 0.15482 — 0.70569 — 0.16215 1.43297 0 — 1.01147 — 0.26141 1.53182 0.44559 0 0.44 0.22 — 0.66 Π— 0.13640 — 0.43560 — 0.57698 — 0.19767 0 — 0.46778 — 1.37832 — 0.44746 0.44559 2,00854 1 1.18 1.08 1.32 — 0.62 1 0.2052 0.2508 — 0.36523 0.39339 1 0.15205 — 0.26030 0.41751 0.78696 1 — 0.00527 0.50029 0.70450 0.62835 $28) мвтод пополнвния для оявлщвния матгицы 203 матрицы С„, и т.
д. Элементы же первых '7< — 1 строк матрицы С„, вообще не понадобятся в дальнейших вычислениях, и вычислять их нет необходимости. С другой стороны, для матрицы Аь > достаточно вычислять элементы первых л — 1 строк, так кзк последующие строки совпадают со строками единичной матрицы. Поэтому, целесообразно ввести в рассмотрение „склеенные" из Аа'< и Св >матрицы 5, и 5,, из которых первая 5„, имеет первые 7< — 1 строки совпадающими с первыми л — 1 строками матрицы Ат > и последние л — <<+1 строк из С„,, вторая — первые л строк из Аа '<, последние л — <е строк нз Св ,; матрица 5» < получается из 5„ , заменой Й-й строки на Ф-ю строку единичной матрицы, Очевидно, что элементами я-й строки матрицы 5в > будут числа сь> ° (а — » В силу формул (4) и (6) матрица 5„получается из матрицы 5а > по формулам е( о(а) = а — а(" » — (а-» 'а +сва (6) (в-» <ю <а» -(ь» Сч оау а „э< — — а„„.> — а), + (а-» Эдесь а( ) обозначает у-й столбец матрицы 5„, а; обозначает у-й (а) (а-1) столбец матрицы 5а >.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
