Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 29
Текст из файла (страница 29)
При этом, для получения решения данной системы нам нужны только коэффициенты ЬО, а числа ам ь играют вспомогательную роль н нУжны лишь затем, чтобы опРеделить числа Ьчн Покажем' ), что числа Ьо можно получать процессом накопления, позволяющим избежать вычисления и записи всех коэффициентов аг!.„. Выделим элементы 1-го столбца каждой вспомогательной матрицы ат!.у !, 1) у, обозначив их через сн, 1) у. Анализируя процесс вычисления коэффициентов вспомогательных матриц, мы видим, что ао а —— а; а,— а!л.„!Ь„у = а! „, — сг„Ь„, =- =агь» ! — см,Ь„, — сглЬяу == ...
=— в = а! — снЬ!1 — с!зЬз! — ... — с,„Ь,; = ан — ~! снЬгу. г-! ('2) !) Дуайр [1]. Таким образом, любой элемент а;! „выражается посредством накопления через выделенные нами элементы с;„. и числа Ьо. В частности, дла самих элементов сн, !)~У, н Ьчн ! </, имеют место рекуррентные формулы у-! с! =а!ты ! — — ао — ~~.", слЬау (1)~у) ! ! ! †! агу — ,'~~~~ сизо лг! г-! ! ! Ьо — — — ' (1 С./). лн «-! сн б 181 !б! компьктные схемы По этим же формулам определяются, очевидно, и свободные члены преобразуемых уравнений, Схема проведения прямого хода по формулам (2) называется к о и п а к т н о й. Обратный ход остается таким же, как и в развернутой схеме единственного деления. Вычисления по компактной схеме удобно располагать так, как это указано в табл.
П. б. Таблаца 11. б Компактная схема метода единственного деления О.П вЂ” О.гз 1 0.67 О.З5 0.54 о.з ол 0.7 1.76 2,32 1ЛО ах ссг а а,б о.47 — О.вг -0.74 аа .а„ а аа а„! — ощ а„! 055 1.24 О.41 Олб 1 ~ 0.9 а, -олз ~ охи 0.85589 / — 0.62368 С,, 1 ! Ь„б„~за Ьа с„сс. 1 1,3.;ьп ь, о.з о.звон ь, Ь. 0.47 Ь„1 — О. П 0.656931 11 — 0.68602 0.89681 0.20949 ~ 1.05657! ! 0.39357 а ! а 1 х, х, 1 х„!'с хс х ~ 1 '~ '1 0.393 7 1.39357 2. Ыбзг озмб оз !.16681 0.44089 1.44091 Здесь вычисление элементов с и 17 мы производим последовательно по углам, начиная с вычисления элементов с: с!1 '7!2 Кз б~4 сю .
'сгг 7723 1724 2 и шаг сз! ! сч ! сзз )71~ 3-й шаг С4! 1 С42 . Сы При этом любой элемент получается как равность между соответствующим элементом а и суммой попарных произведений недиагональных элементов с, находящихся в данной строке (слева), и элементов (7, находящихся в данном столбце (выше). Конечно. при вычислении элементов 77 нужно еще произвести деление на соответствующий диагональный элемент с.
с!а ас азс а огп Озпа!! 1 ОЛ637 0.3305 1.76 1.62243 1.21080 1.39357 162 точныв методы вешания систем динкиных и лвненнй [гл. и Так см — — а„— с„Ьы — гмбаз —— = 0.36+ 0.55 0.21 — 0.3355 0.85589 = 0.20949 лат — сага!4 — смбм ьм = см — 0 74 + О. ! 1 0 54 + 03687 0 62363 0.66693 Скажем несколько слов о контроле, применяющемся при вычислении по компактной схеме. Так же, как и раньше, составляем столбец из контрольных сумм н над ним проделываем те же операции, что н над столбцом свободных членов. При этом каждое чисто преобразованного столбца должно совпадать с суммой элементов соответствующих строк матрицы В, расширенной посредством присоединения преобразованного столбца свободных членов. Действительно, матрица В есть матрица коэффициентов системы, получаемой из данной после окончания прямого хода по схеме единственного деления.
Вычисление по компактной схеме требует предварительной фиксации ведущих элементов, так что схеме главных элементов невоз. можно придать компактную форму. Компактная схема формально почти без изменений может быть распространена на решение систем линейных уравнений, матрицы которых разбиты на клетки с квадратными диагональными клетками. Обозначив через СО матрицу А; г н мы, так же как в числовом случае, будем иметь Эти формулы позволяют последовательно вычислять матрицы С.;,. и Вц в том же порядке, как и в числовом случае.
$19. Связь метода Гаусса с разложением матрицы на множители В 9 1 было показано, что систему и линейных уравнений с л, неизвестными можно записать в матричной форме АХ= В, (1) где А данная неособенная матрица, Х и В столбцы, состоящие из значений неизвестных и свободных членов, которые мы будем рассматривать как векторы арифметического пространства. $19) связь мзтодА ГАУсслс РАзложением матРицы ИА миожитети 163 Метод Гаусса. проведенный с ф и к с и р о в а н н ы и порядком ведущих элементов. состоит в том, что данная система заменяется равносильной треугольной системой посредством линейного комбинирования уравнений, что сводится к линейному комбинированию строк А.
При этом нам приходится (пользуясь схемой единственного деления) кроме делений на ведущие элементы добавлять к элементам с~рок числа, пропорциональные элементам предшествующих строк, т. е. совершать над матрицей А элементарные преобразования типа а) и Ь) пункта 11 9 1. Результат нескольких преобразований этого вида, как было там покааано, равносилен умножению матрицы А слева на левую треугольную матрицу ТЦО ...О '(21 '(22 ...
О (2) Ти! ТА2 ' ' ' ТАА В результате этих преобразований мы переходим к сисгеме с правой треугольной матрицей 1Ь„... Ь„ О 1 ... Ь,„ ОО ... 1 Таким образом, ГА= В, т. е. А =Г В и, следовательно, ма~рица А разлагается в произведение двух треугольных матриц. Компактная схема осуществляет это разложение. Действительно, Г '=С, где элементы матрицы С определены по формулам (2) 9 8, ибо нз этих формул следует, что ,1 — 1 а;;= СО+,1' слЬ —— ,~, сиь, ((~~У) [.1 ' 1-1 ' (из формул для см) и 1 — 1 л1у = '21 сиь22+ с1!Ь12 — ' ~'! саЬВ (1 < У) 1=1 1-1 (из формул для Ь; ).
Последние формулы означают, что А=СВ. Так как диагональные элементы матрицы В равны единице, такое разложение единственно. 112 !бч тОчные метОды Решения систем линейных УРАВнений [гл. и Компактная схема, примененная к клеточной матрице, очевидно, осушествляет ее разложение в произведение двух квазитреугольных матриц. Компактная запись для схем метода Гаусса, отличных от схемы единственного деления, также связана с разложением матрицы в произведение двух треугольных, но с другим выбором диагональных элементов, Заметим, по компактные схемы закрепляют порядок исключения, и по~ому они применимы только в том случае, как это слеаы а,а дует из теоремы 1.1, когда все определители а,;, , ...,!А', а21 а22 не равны нулю.
Покажем, что в случае, когда матрица А симметрнчнз, САЧ й;2 = —. сн' 14) Действительно, А = СВ, А' = В'С' и, так как А =- А', сп 0 ... 0 С„СТН 1 — ' СЫ ''' С22 0 1 с та СВ=- В'С' = В' О сы 0 0... с„„ 00...1 Отсюда, в силу единственности разложения матрицы А в произведе- ние двух треугольных матриц, следует, что СЕ„С,П СЫ 222 0 1 0 0 ...
1 Таким образом, элементы матрицы В находятся посредством деления элементов матрицы С на диагональные элементы. Тем не менее компактная схема требует а' записей и в случае, если матрица А симметрична (табл.!1. 7), так как в рекуррентные соотношения (2) й 18 входят как числа 122, так н числа саь Можно дать рекуррентные соотношения, в которых элементы Ьы выражаются друг через друга и через диагональные элементы са. Однако так построенные формулы оказываются более сложными.
Й 201 165 МЕТОД КВАДРАТНЫХ КОРНЕЙ Таблица П. 7 Компактная схема метода единственного деления в симметричном случае «„аа а,ь 1.ОО ОЛ2 а„аа аа аьь а, .42 !.ОО аа зм охв лб он аа аьь аа аа аа аа Ь ь Ь )! ОО ! 1~ О 42 0.54 0.66 0.1габ7 0.82360] 1! ОЛ1316 Ьь Ь„; .42 0.454!О !! сь, с с„] 0,09320 0.69785 ] 1 — 0.22185 0.71030 0.16280 — 0,164М ) 0.43787 ]1 ! 1Л8240 Са 1 Ь„( Ьь !]з.ба са са 1 х, ~х, ! 1.48240 хь хь й 20. Метод квадратных корней В этом параграфе мы покажем, что в случае, когда матрица системы симметрична, нахождение решения можно еще упростить, ') так как в этом случае матрицу можно разложить в произведение двух транспонировзнных друг другу треугольных матриц.
Итак, пусть где бп 612 ''' 810 (2) Определим элементы матрицы о. Имеем, в силу правила умножения матриц: он =61!бы+ 821822+ . + 9нзо 1(у ан = 9';4+ зм + ... + з,'-ч 1) Т. Б 8 н б к е в и ч ]4], 15]. хь х ! .с, с, ! 0.54 О.З2 1.00 0.22 0 822 ' ' ' 62!! о о 0.66 0.44 озв 1.ОО о,з 0.5 ол ОЛ 1.03917 0.04348 — 1.25760 2.92 2.68 2. 76 ЗЛ2 2.92 1.76493 1.48344 2,48239 2.48ьзз 2.03916 1.04348 — 0.25779 г— г!! ='к а,т, эы — — —, Ям а!1 — ~~~~ анзг) вн = ан — ~~', з,'-! (1 ) 1); э!Э вЂ”вЂ” — (.Г - 0 (6) ! гн э;,= — -О (1),У') Далее, решение системы сводится к решению двух треугольных систем. Действительно, равенство АХ= Г равносильно двум равенствам Я'К = Р и БХ = К Элементы вектора К определяются по рекуррентным формулам, ана- логичным формулам для э;~.
Именно, и!= —, !'! ап (4) Окончательное решение находится по формулам а! — ~~~~ апх! (5) л„ Х в авв В схеме применяется обычный контроль, причем при составлении контрольных элементов мы учитываем все элементы матрицы. Аналогично компактной схеме контрольным равенством является ь = я э!а+в!. а-! В методе квадратных корней приходится записывать только л(л+ 1) элементов матрицы о н 2л компонент векторов К н Х. В табл. И. 8 приведено решение системы по методу квадратных корней.
166 точные методы гашения систем линейных келвнвний [гл. и Отсюда получаем формулы для определения гг;ч 167 3 201 метод квздеатных когней Табла41а 11, 3 Метод квадратных корней О.вв 1 оз гы ощ 1 оз зом 4 ОО ~ Оа ( ЗДВ О.зв о.зв !.00 ао О, О, 4.ОО в, в, а, в, в, олз О.ы о.вв о.з ззв в„~ в 0,00752! 0.10070 ~0.55557 Оап4 ЬВО4Ы О МЗМ, Ьмвво ЬОКИ7 ~ взвыв ОЛНЗО -0.4 Ывз 0.70550 з, в,)! -4.0077В Оляввз 4 ОЗВЫ 4ЛВиб — О,ВЫ7О 4.04040 З.ОЗИ7 ВЛЕ Зв авв — зыз44 — з вв 4 0.22 — 0.54 0.06 — 0.10270 ' 0.17139 554 звв 0 83537 Обратный ход происходит по формулам 15). По существу прямой ход метода квадратных корней равноситен приведению квадратичной формы с матрицей А к сумме квадратов посредством преобразовзния переменных с треугольной матрицей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
