Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 33
Текст из файла (страница 33)
о„А„1и«1У„+ а„„1Уп = — 1 -1 о Ап, (а„„вЂ” ип) 1)и+ ап«1уи = пиАи-1+ а«1уп = О. Отсюда оиАи-1 1Уп =— «,1 Наконец, — 1 Ап,и Р,=А 1+ — 1 «ив "и-1 Таким образом, окончательно; Аи-1ив «п (у) ип 4« — 1 «и .— 1 где ив=а „вЂ” о Ап 1и„. А«,Р«, + и«1)п = Е о„Р„1 + ап, у„= О -1 Ап,ип Г п а, Подставляя значение гп в (4), получим -1 ип = апп — О«А„1ип. Далее, из (1) имеем — 1 -1 Рп,= А„т — Ап си«у„ А ~ииА л — 1 ~ и-1 и и п-1 Аи 1+ ав (1) (2) (8) 189 метод оклймлвния й 25] Очевидно, что построенная формула является частным случаем формул обращения матрицы методом разбиения на клетки при р=и — 1и17=1. Выведенная формула кладется в основу метода обращения матрицы посредством последовательного окаймления.
Именно, последовательно строятся обратные матрицы для матриц ап ап аы а„азз а.„ азг азз азз 11 12 из которых каждая следующая получается из предыдущей посредстволз окаймления. Каждый шаг это~о процесса осуществляется на основании формулы (7), Именно, если А... уже известна, для нахождения А,,' нужно произвести следующие действия: 1) Вычислить столбец — А,,'1а„, Элементы столбца 12„.. находятся при помощи накоплений, -1 2) Вычислить строку — о„А„1 с элементами 7„1,...,7з „1. 3) Вычислить число ч-1 п -1 ъ = + зр1 = +ь' 171ч. 1=1 1=1 (Двойное вычисление числа а„является хорошим контролем предшествующих вычислений). 4) наконец, найти элементы 211в обратной матрицы по формулам: ,1„— а',з+ 'ММ; Д (п 1 зи "и Р -1 Здесь 2112 — элементы матрицы А„:1.
В случае симметричной матрицы А схема сокращается, очевидно, ровно вдвое. В табл. !1. 14 дано обращение матрицы 17) й 23 при помощи последовательного окаймления. Каждый шаг процесса оформлен по следующей схеме А„, ~~ и„— А„'га„ вЂ” п„А„:1) )! Ян Метод окаймлення может быть полезен и в применении к решению системы линейных уравнений. Особенно целесообразно использовать этот метод в случае, когда нужно решать систему, для которой уже ранее решена усеченная система, получающаяся из данной !90 точныв методы гзшвния систем линейных явлвнвний 1гл.
и Тиблица 15 И Обращение матрицы методом окаймлеиия — 0.42 0.42 0.42 — 0.42 0.82360 - -0.50996 1г21418 — 0.49247 — 0.11316 1.21418 —. 0.50996 0.54 0.32 0.32 — О.! 1316 0.54 — 0.49247 0.69785 ! 0.66 ! — 0.68624 0.44 ! — 0.22277 0.22 0.22186 — 0.43010 1.23253 — 0.16216 — 0.70570 — 0.16216 1.43297 1,56172 0.43010 --0.70570 О.бб 1 0.44 0.22 0.22186 — ОХ8624 — 0.22277 0.49787 2.50759 — -0.12304 †.1.01149 1.37835 — 1.01149 — 0.26143 1.53183 0.44562 — 0.12304 1.33221 — 0.26143 — 0.44745 — 1.37835 — 0.44745 0.44562 2.00856 вычеркиванием одного уравнения и одного неизвестного.
Такая ситуация часто встречается в приложениях. Например, при решении задач математической физики по методу Б. Г. Галеркина ялн Ритца может оказаться, что решение, полученное в результате использования и†1-й координатной функции, недостаточно точно; если для построения более точного решения достаточно добавление еше одной координатной функции, то новая система лля определения коэффициентов получается из предшествуюшей системы окаймлением.
Метод окаймления может быть применен к решению системы линейных уравнений следуюшим образом. 191 ч 251 метод оклймлания Пусть система имеет вид .4иХи = ~и. Обозначим Тогда — -1 — 1 — 1 Ап ! ипо«,Ап ! — Ап ! нп ' Г„ «п А— 1,1и — 1 -1 — ! А... а„о«А„!Р„! — А...аиуп — о.4« -'1 ~'и-1+ Л~ Но А„~!1«п ! есть решение у сече иной систем ы, т. е, системы анХ,+ ... +а, и,Хи,=у, а„1,х!+ ., +ли, „,х„!=у„!.
которое мы обозначим Хи,. Аналогично — А„гип = — А„'1 ~ .. аи Ь«Л есть решение системы с той же матрицей коэффициентов, но с доугнми свободными членами. Зная Хп, и Яп 1, мы легко вычислим Хп. Действительно, Хи = и и-1 — Я„!о„Х„!+ !',1„!у„ 0 лип+ ои!Ги-1 ~ — о«Хи-1+7« — х ~ + и-! ~ уи — Ю«Хи 0 ~ а«,«4 опФ„-1 1 1 Таким образом, для нахождения Хинам надо кроме Хи, вычислить еше Я„ 192 точныз методы ввшвния аистам линейных гвавнвннй [гл. н Если усеченная система была решена по методу Гаусса, то лля нахождения Я„, в схему нужно добавить еще один столбец. Вычисление прямого хода выполняется лишь для этого столбца, с использованием уже известной левой половины схемы. Затем определяется обычным обратным ходом.
5 26. Эскалдториый метод Прн обращении матрицы методом окаймления существенную роль прн переходе от обрашения матрицы Ав, к обрашению окаймленной матрицы Ав играет вычисление выражений — Ав,ил и — тяАс. ы При этом компоненты вектора — А,ив представляют собой не что иное, как решение системы уравнений: а„а, +агав,+ ...
+ а, в гг„,+ ам- — — О ав ь,юг+аз, гв , '... +ав, в,вл,+а„, л —— .О. Аналогично, компоненты — оьАс, образуют решение транспонированной системы. Последовательное решение таких систем при а = 2, ..., и, л + 1 лежит в основе так называемого эскалаторного метода решения систем линейных уравнений '). Тем самым эскалаторный метод тесно связывается с методом окаймлення. Существенным достоинством метода являешься наличие надежного контроля, при помощи которого можно регулировать точность вычислений, добиваясь выполнения контрольных равенств за счет привлечения большего числа значаших цифр. Следует, однако, заметить, что эскалаторный метод не является в этом отношении единственным среди точных методов решения систем. Р!адежным контролем обладзет также рассмотренный выше прием биортогонализацин столбцов и целый ряд других методов, которые будут рассмотрены ниже.
Мы изложим эскалаторный метод .лишь в применении к системам с симметричной матрицей, придав вычислительной схеме компактную форму. При этом обнаружится связь эскалаторного метода с методом Гаусса. Итак, пусть дана система уравнений: анх, + а„х, + ... + а,„ха+ а, „„=- О агах,+ плаха+ ... +-а„„х„+а„„,, = О, матрица коэффициентов которой симметрична. г) Моррис [4]. !93 3 26) ЭСКАЛАТОРНЫй МЕТОД Обозначим чеРез з,г„.. „2„, в Решение системы: а„з,+ ... +а, „,зв,+а!в — О (2) ав ь.з,+ ...
+ав, е,г„,+ав ! „— — О. Числа 2; „ег=2! очевидно образуют решение системы (1). Поэтому, если мы установим способ последовательного вычисления чисел 2ц для 1< и ( и+1, то тем самым дадим способ построения искомого решения. Допустим сначала, что уже вычислены все числа зц для ! и 4 а. Построим с их помощью матрицу зп 2ы ° 2гв 22! ' ' 2!в зев О О (3) О О О ... 1 Легко видеть, что матрица А7 имеет нули выше главной диагонали. Действительно, С,= Ал. = аге, а!!2!2+ и!в, . °, аи2гв+ а!22!в + ' ' + а!и !"2!2!2+ а!2, ., ., ае!2!в+ а!22!в+ ', .
+пав аап (4) аеп а„,з„+ а„,, а„,г,„-+ а„езв„+ ... +а„в 13 Зев. ВГЕ Д. К. Февлеее в В. Н. Февлеевв и, в силУ опРеделениЯ чисел зчп все элементы, лежащие выше главной диагонали, равны нулю. Ненулевые элементы матрицы С, вычисляются по формулам с„"=апз„+амзю+ ... +а;1 гзу ! г+абь1)~/. (5) Отсюда вытекает связь этого метода с методом Гаусса, рассматриваемого в свете разложения матрицы на множители. Действительно, из (4) имеем А =. Сел. (6) Но матрица 2. ! †треугольн матрица с единичной диагональ.о и нулевыми элементами ниже диагонали, С, †треугольн матрица с пулевыми элементами выше диагонали. Сравнивая это разложение с разложением матрицы, соответствующим схеме единственного деления метода Гаусса (А = СВ), мы получаем, в силу единственности такого разложения, что 2.
'=В, С,=С. (7) 194 точныв мвтоды гвшвния систвм лиивйных гвлвнвний 1гл. и Представим матрицу С в виде 1 0 0 ... 0 о ... о Т21 Т22 1 ° О с„ С,а = ГЛ. (8) С22 Ти! Тча Тпг 1 спп Здесь ТΠ— — —, 1>!'. ='Ц О= с"' Докажем, что матрица Г=СЛ является матрицей, транспонированной к матрице 2 . При этом мы будем сушественно пользоваться симметричностью матрицы А. Имеем: А = ГЛЛ"' = А' = (л"') ЛГ'. Тье1, 1+ Те 1,2а12+ ' ' ' +Та!1,2 !2 + 1, в!1 ...+- г +а =0 Тье1, 2+ ' ' ' + !ье!.2 яв+ (9) Т„ь„+гм„,=О определяющие влементы (!2+1)*го столбца матрицы л.. Упомянутым выше надежным контролем является действительное обращение в нуль нижедиагональных элементов матрицы Г'. Но (Л ~) — треугольная матрица с нулями выше диагонали, Г'— треугольная матрица с нулями ниже диагонали и единицами на диагонали.
В силу единственности разложения, Г' = к !. Это обстоятельство позволяет указать рекуррентные формулы для последовательного определения чисел гы. Допустни, действительно, что мы уже вычислили элементы первых Й столбцов матрицы к.. Тогда по формулам (5) можно определить й столбцов матрицы С, следовательно — !2 столбцов матрицы Г, т. е.
и строк матрицы Л 1. Для продолжения процесса нам нужно вычислить элементы (Д+ 1)-го столбца матрицы 2. Так как диагональный элемент этого столбца равен единице, а элементы ниже диагонали равны нулю. нам остается дать формулы для вычисления г1,2„1, где 1 ( Й. Из равенства ЛГ' = Е мы получаем, в силу правила умножения матриц, следуюшие рекуррентные формулы: 195 метОд пвгсвлла Приведем компактную схему эскалаторного метода для системы 4 уравнений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
