Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 28
Текст из файла (страница 28)
Заслуживает внимания модификация метода исключения, при котором в качестве вспомогательных матриц, управляющих линейным комбинированием уравнений, берутся элементарные матрицы вращений. При этом вычисления располагаются следующим образом. Берем !54 точныя методы гзшвния систвм линвйных ававнвний [гл.
и Результативная система с треугольной матрипей располагается в строках 1", 2"', 3"', 4"', исходная — в строках 1, 2, 3, 4. Строки 1', 2', 3', 4' и 1", 2", 3", 4" заняты промежуточными линейными комбинациями исходных уравнений. Их удобно получать в порядке. совпадающем с порядком следования строк в таблице. В последней строке таблицы расположено решение системы. Шестой столбец во всех нумерованных строках контрольный, Таблица 7?.
3 Решение линейной системы методом вращений 0.17 — 0.25 1.00 0.67 1 1.ОО 2 0.47 !.2209 ! 1.10494! 35260 Г !.10495 0.57922 0.05873 3 — 0.11 0.35 1,00 2.57969 039508 1:20 0.09906 О. 1 0.48419 — О.?4 ! О.? 1.23301! 1.11041 ) 0.42417 1.00 0.41247 2.44813 0.89610 0.9 ! 3.24 ! — 0.44385 1'" ! !.23916 ( 0.6762?! 0.12339 ~ 333184 ! 0.82395 0.76908 0.83272 0.40566 — 0.51930 — 0.70143 0.32491 0.74452 0.71271 !.00090 1.35104 0.89900 1.
44964 — 0.43795 0.92627 ~ 0.85798 1.84945 ~ 0.98799 1.816?6 ~ — 0.15455 0.92627 1.07907 ( — 0.77404 0.14489 0.34063 ) О.?0783 0,61816 0.62342 0.87897 ! 0.93753 ! 0.93754 ( 1.11875 ! — 0.%536 2"' ) 2.10800 ! 0.70708 0.58768 — 0.40316 ! О. ! 6978 0.8 ! 895 0,7!154 0.96072 1.50913 — 0.27?55 0,52703 0.52040 ) 0.37419 ) 0.61171 ! 0.6!172! — 0.16002! 0.%077 ! 1.10245 ) 3"' 0.89868 0.35368 ~ 1.25236 ! 0.44089 ) — ОЛ6302 ! ! ч 6679 ~ 0.39356 4"' 1" !.11041 0.54176 — 0.04062 4 0.55 0.43 0.36 1.53551 ! 1.23916 / 0.54 0.3 1.76 0.90503 — 0.32 0.5 2.32 — 0.42536 9 1б[ мзтод ГАуссА Вместо элементарных мзтриц вращения для приведения системы к равносильной системе с треугольной матрицей можно использовать и другие ортогональные матрицы.
Удобными оказываются матрицы отражений от п — 1-мерной плоскости' ). Пусть )Г вектор единичной длины, ортогональный к заданной и — 1-мерной плоскости 1,>. Тогла матрица отражения относительно с',> есть (>' = Š— 2(Г)Г' (здесь )Г(Г' есть произведение столбца на строку, т. е. матрица ранга 1). Действительно, если вектор Л ортогонален к )Г, то сгЛ = л — 2(Г[Г'л = Л, ибо )Г'Е = ()Г, е ) = О, а (ЛГ = )à — 21Г1Г')Г = — )Г, ибо )Г'[Г = =()Г, )Г)=1. Матрица (>', очевидно, ортогональная н ,'(Г~= — 1. Вектор )Г можно всегда подобрать так, чтобы матрица (/ пере- водила любой заданный вектор 8 в вектор задзнного направления, нзпример в вектор, направленный по одному из координатных век- торов е.
Для этого достаточно взять )Г = — (5 — ае), 1 Р где а = Ч- [8 ), р = ( 5 — ае [ = [l 2аз — 2а (5, е) . Действительно. при таком выборе [Г имеем (/В = 5 — 2 (1Г, 5) )Г =- Я вЂ” р(Г = 5 — 5+ ае = ае, так как 2()Г, 8) = — (2аз — 2а(5, е)) = р. 1 Р Выбор знака для а, вообще говоря, безразличен.
Им поясно распорядиться так, чтобы число р было большим нз двух возможных, для чего следует взять з1дп а = — з>дп(5, е). Для любого вектора У имеем (.>1' = У вЂ” 2 ([Г, 1') )Г. (9) Для преобразования системы АХ= гч к треугольной системе поступаем так. На первом шагу вектор (Г строится по первому столбцу 5 = А, матрицы А и по вектору е = еп После умно>кения обеих частей системы на мзтрицу с>' (что равносильно применению формулы (9) к столбцам матрицы А и к вектору В) приходим к сн[а о[ стеме с матрицей вида ~ .
~, где В квадратная матрица и — 1-го ~О В~ порядка. Далее процесс повторяется для системы с матрицей В и т. д. После и — 1-го шага мы придем к треугольной системе. Легко видеть, что матрица этой системы, с точностью до знаков строк, совпадает с матрицей, полученной методом вращений, >) Хзусхольдер [13[. 156 точные методы вешания систем линейных явлвняний (гл. н Приведем результат первого шага для системы табл. П.
1. Имеем а = — 1.23915 р = 2.35569 ' В'=.(0.95053, 0.19952, — 0.04670, 0.23348)' — 1.23917 — 0.67628 — 0.12339 — 0.82397 — 0.00001 0.82236 0.69658 — 0.60630 0.00001 0.39158 0.99378 — 0.67299 — 0.0000! 0.22213 0.39110 0.66497 '!а в~ Авгх!+ Аизхз+ . +Аппхв = Рв. Пусть|А!!)ныл. Найдем матрицу А!! и умножнм на нее слева первое уравнение системы. Получим матричное уравнение Х„+ В„Х + ...
+ В,„Х„= О,, где -! -! — ! В!! = Ац А!з .. Вге = Ан А!в, О! = Ап Р!. Умножим это уравнение слева на Аан ..., А„, и вычтем, соответственно, из 2-го, ..., и-го уравнений исходной системы. Получим систему 4яз !Хя + ° ° + Азв !Хп = Р! ! Авя.!Хз+ ... +Аев гЛ'д,—— — Рв ! где А!Р! — А!7 — АпВ (0 /)~ 2) Р!.! =Р; — А„О,. Поступая аналогично дальше, придем в конце концов к системе с квазитреугольной матрицей с единичными диагональными клетками х,-+в„х,-(- ...
+в,„х„=о, Хв — — О . Неизвестные векторы Х,, ..., Х находятся последовательно от Х„к Х, по формулам Х,= О,— Вг!+гХз+! — ... — В!вх„. ОР- — -( — 0.76908, 0.27560, 0.75252, 0.63740)'. Метод единственного деления может быть следующим образом обобщен на системы, матрицы которых разбиты на клетки с квадратными диагональными клетками. Разбив соответственно решение и столбец свободных членов на векторы, размерность которых равна порядкам диагональных клеток, запишем систему в виде Аг!Л!+А!!Ха+ .
+А!ехл=Р! А„Х, +А.яХ + ... +А „Х„= Ра 1б7 вычисления опгвдвлиталвй ф 17. Вычисление определителей Метод Гаусса, развитый в предыдущем параграфе для решения линейной системы, может быть применен и для вычисления определителей. Мы остановимся отдельно на описании соответствующей схемы единственного деления, так как вычисление определителей часто встречается в приложениях. Пусть и11 а12 . а1„ Л„Л22...
П2„ ая1 а 2 ... а„„ и пусть а„+О. Вынесем элемент аы из первой строки. Тогда, применяя обозначения Е 16, получим: ~!2 ''' ~12 пж ...л,„ аш а„а... а„„ 72= ан Затем из каждой строки отнимем первую строку, умноженную соответственно на первый элемент этой строки, Мы получим, очевидно, б!2 ... бш О а22.1 .. ааа.1 п22 1 ° ° ' !12и.1 1=а!, = ан ПЯ2.1 .
Лча.1 Далее, с оставшимся определителем а — 1-го порядка поступаем совершенно таким же образом, если только а22.1чьО. Продолжая пропесс, мы получим, что искомый определитель равен произведению ведущих элементов: Ь = а1!а22.1... а„„.„ Если на каком-либо шагу окажется, что ан.1, — — О или ан.1, близко к нулю (что влечет за собой уменьшение точности вычислений), можно предварительно изменить порядок строк и столбцов определителя так; чтобы в левом верхнем углу оказался неисчеаающий элемент.
Разбиение мзтрипы на клетки, вообще говоря, не изменяет числа элементарных операций, нужных для решения системы. Однако можно получить значительный выигрыш в объеме работы, если существует разбиение, при котором возникают упрощения прн обращении ведущих клеток. 188 точныв мвтоды гвшвния систвм линвйных звлвнвний [гл. и Наилучший в смысле нздежности результат получится, если на каждом шагу процессз переводить в левый верхний угол наибольший по абсолютной величине элемент матрицы, для которой вычисляется определитель. Число умножений и делений, нужных для вычисления определителя и-го порядка, равно †, [и'+ и+ 3).
8 В табл. Н. 4 дана схема вычисления определителя и численный пример. Таблица П. 6. Вычисление определителя по схеме единственного деления (с исключением по строкам) — 0.25 067 1.00 О.вб ОЛ7 1.00 О.ЗО олз 0.54 1.46 — 0.32 !.82 - ООЧ ООО 1,00 2 34 ам ~ 1.08 а25 р ОА7 авь ! — 0.11 аб- [! 0.55 аы а,з а12 «23 ;и "зз а42 043 "н а!4 а24 а24 '444 ам авз ьи ( ьж 515 ~ ! 445,1 — 0.25 олви 0.9725 ахи!5 Ол7 0.920! 0.3687 0.3356 О бц 1ЛΠ— 0.5738 1.1338 — ОЛВОВ ОЛВОО О.7ОЗО 1ЛЗ70 Ь!4 а24.1 авз 1 а4Ь! азз,! 423 1 а3,1 азз 1 азз 1 443,1 1 0.85589 — 0.62303 1.23226 0.65693 — 0.4ЯМ7 0.20627 0,20949 0.91285 1Л2231 Ь28 Ь24 азз2 ам 2 043 2 а41 2 Ьзз азь.з а4Ь 1 1 ' Ьзз Ь3 ам.з ~ ам з — 0.68502 О.ЗЫШ 1.06836 1.05606 1 ! ( ! ь= ) 1.0о х олио! х 0.65691 х 1.овшб - О.бззбз Схема единственного деления для вычисления определителей может применяться не только с исключением по строкам, но и по столбцам (табл.
И.б). Это, очевидно, равносильно вычислению определителя транспонированной матрицы по строкзм. Из рассмотрения процесса вычисления определителя мы видим, что он, за исключением последнего умножения, совпадает с прямым ходом процесса Гаусса, примененным для системы с матрицей, для которой вычисляется определитель. Известные формулы Крамера [й 1) показывают, что решение линейной системы можно находить в виде хз= —; 1= 1,..., и, где!3 В1 обозначает определитель из коэффициентов систеиы, бз — определитель из коэффициентов, в котором элементы !'-го столбца заменены свободными членами. Таким образом, для решения системы приходится вычислять и+1 определитель и-го порядка.
159 9 171 вычисление опввдвлителвй Таблица П. 5 Вычисление определителя по схеме единственного деления (с исключением по столбцам) — 0.25 0.67 1.00 0.36 !.ОО 0.47 — 0.11 0.55 0.54 — 0.32 — 0.74 !.ОО 0.17 1.00 0.35 0.43 1.00 0.47 — ОЛ! 055 1.78 0.48 1.91 1.95 1.91 0.7875 0.9725 0.4975 — 0.5738 — 0.6806 0.7030 0.920! 0.3687 0 3365 1 0.40072 0.36572 2.2575 1.6253 — 0.55! 4 1.76644 — ОЛ 5067 0.91285 0.65693 0.20949 1 0,31 889 1 31891 0.86643 ОА62!8 !.05651 1.05656 1 Х 0 9201 Х О 65693 Х 1.05656 = 0.63863 Сравнивая процесс Гауссз для решения системы с процессом вычисления определителя, мы видим, что объем вычислений для решения системы лишь немногим превышает вычисление одного определителя.
Поэтому пользоваться формулами Крамера для численного решения системы нецелесообразно. По сути дела, в способе Гаусса производятся вычисления всех определителей Ь и Ь! одновременно, причем деление на Ь = аиазза ... а„„ „ , производится постепенно, по одному множителю на каждом шаге.
Получение нулей прн вычислении определителя можно осуществить также посредством линейного комбинирования строк матрицами вращений. Это требует значительно большего числа операций, чем 160 точные методы вешания систем линейных углвнений [гл. и схема единственного деления, но дает значительно более стабильный процесс вычислений. Для вычисления определителя можно так же разбить его матрицу на клетки с квадратными диагональными клетками и затем „получить нули' подобно тому, как это делается в соответственно видоизмененной схеме единственного деления для решения систем линейных уравнений. В конце концов искомый определитель окажется произведением определителей .ведущих" клеток а=[А!!! ° [Аа!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
