Беклемишев - Дополнительные главы линейной алгебры (947281), страница 34
Текст из файла (страница 34)
Ргссмотриы алгоритм получения 1. (/-разложения, носящий название колгаактной ехел!ы метода Гаусса. Матричное равенство А = 1Л/ равносильно и' числовым равенствам и ац — — ~ 1!ли,„. л=! Поскольку (. н (/ — треугольные матрицы, мы ил!Ест! 1!л = О при й ) ! и им — — О пРи й) 1. ПоэтомУ л а;;= ~, '1ли„п (б) л=! где г = ппп (1, /). Зги п' равенств могут быть разделены на группы по значениям г. Так, для г = 1 имеем или() 1 = 1, или ! = 1 = 1, и группа состоит из уравнений ам=1»ипп 1') 1, ап= 1»ил» 1--(=1. Так как (/ имеет единицы на главной диагонали, и» = 1, и мы находим 1„=ап для всех 1)1. В частности, 1» = а», и потому 1» Ф О, если главные миноры матрицы А отличны от нуля.
Теперь мы можем найти аы им — — — / для всех 1- 1. 1» Допустим теперь, что из групп уравнений, соответствующих значениям г = 1, ..., з — 1, мы нашли 1ил н и,/ для любых ! и 1 и всех 150 гл и! ВВедение В численные методы г ~ з — 1. Напишем группу уравнений, соответствукицих г ав в виде ! — ! аи — — 11,ич+ ~ 1гвивт, в=! Отсюда при ! ~ 1 = з в силу и„= 1 имеем ! — ! 1;,=а;, — ~ 1ввив,.
в=! Сумма в левой части равенства состоит из уже известных элементов, и, значит, мы нашли 1;, при ! ) з. При ! ( з положим 1в, = О. Если 1 ~ ! = з, имеем ! — ! 1„и„=а„— ~ 1,вивд в=! Докажем, что 1„чь О. В самом деле, в противном случае либо не найдется чисел иео удовлетворяющих последнему равенству, либо найдется бесконечно много (смотря по тому, равна или не равна нулю левая часть равенства). В обоих случаях мы приходим к противоречию с предложением 3. Итак, 5 — ! Вм,в,в 1ввив! в-! им = для всех 1) з, а при 1' (з полагаем и,~ — — О. Тем самым, используя уравнения (б) для г = 1, ..., з, мы нашли все 1в, и иеь Это показывает, что все элементы матриц 1. и У могут быть последовательно вычислены с использованием режима накопления.
Можно показать, что среди всех известных л!етодов описанная здесь компактная схема метода Гаусса имеет самую низкую верхнюю оценку для нормы возмущения исходных данных, эквивалентного влиянию ошибок округлении. Число проделываемых по этой схеме арифметических операций и необходимый объем памяти примерно таковы, как и для схемы единственного деления, т. е.
близки и минимально возможным. 3 а м е ч а н и е. Выше мы показали, что диагональные элементы, на которые приходится делить в компактной схеме, отличны от нуля. Но это гарантирует только теоретическую возможность осуществления вычислений. Для того чтобы эти вычисления были практически возможны и устойчивы по отношению к возмущениям исходных данных и к ошибкам округления, нужно, чтобы числа 1„не были малы, илн, что то же, числа и„не были велики. Для последних мы имеем и, = а!',1, где ац! — элемент матрицы А 1*1, которая строится в схеме единственного деления. Это же условие — отсутствие больших элементов в матрицах Апи — появляется и при исследовании устойчивости схемы единственного деления. $ Х ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ Мы рассмотрели здесь применение компактной схемы для получения ЬУ-разложения, т.
е. предполагали, что диагональные миноры матрицы А отличны от нуля. Следует отметить, что компактная схема обладает фундаментальным недостатком метода Гаусса: устойчивость вычислительного процесса зависит от выбора главных элементов или„в данном случае, от порядка, в котором расположены строки и столбцы матрицы перед началом вычислений. Выше мы показали, что симметричная положительно определенная матрица допускает разложение на множители вида А = Л~г, где Р' — нижняя треугольная матрица.
Модификация компактной схемы для получения этого разложения называется л!ео!одом квадратного корня. Искомое разложение, выраженное через элементы матриц, имеет вид ао — — У', омоты э=! где г = ппп (1, 1). Как и уравнения (6), эти уравнения могут быть решены последовательно. Действителыю, при ! = 1 = 1 и ! ) 1 = 1 имеем соответственно ам — — ои и ап — — оаооь откуда о„=) еа!!, оп — — ац/$'а!т.
Далее, если известны ооя для й = 1, ..., в — 1 и для всех 1, то из равенства (для ! = 1 = в) а~ю= оп+ ~! ом 2 э мы найдем о„, а пз равенств (при ! ~ ! = в) ! — 1 ам =омо„+ 'У, 'о!„,о,„ ь=! найдем о;,. Все деления и извлечения корня в принципе могут быть осуществлены, так как искомое разложение, как мы доказали, существует и единственно, Как и компактная схема, метод квадратного корня допускает использование вычисления скалярного произведения в режиме накопления. При этом может быть достигнута очень высокая точность, если матрица не является плохо обусловленной. В последнем случае ошибки округления могут привести даже к нарушению положительной определенности матрицы и тем самым к невозможности осуществления алгоритма.
6. Разложение на ортогональный и треугольный множители. Большую роль в численных методах линейной алгебры играет разложение квадратной матрицы А на множители (7) 152 Гл ПЕ ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ такие, что Я вЂ” верхняя треугольная матрица, а Я вЂ” ортогональная. Оно называется ЯК-разложением А. Если для матрицы системы линейных уравнений (1) известно ЯЯ-разложение, то система (!) сводится к системе Ех=ягй с треугольной матрицей, и после этого легко может быть решена способом, описанным на стр.
136. Применение 1К-разложения для решения систем линейных уравнений выгодно тем, что число обусловленности матрицы !с равно числу обусловленности матрицы А (ср. стр. 124). Один из путей получения ЯЕ-разложения носит название л~етода огпражений. Отражением в евклидовом пространстве Ф„называется самосопряженное преобразование, имеющее собственное значение 1 кратности п — 1 и собственное значение — 1 кратности 1.
Если собственному значению †! принадлежит собственный вектор з длины 1, то мы будем говорить, что отражение порождается вектором э. В ортонормированном базисе е„из собственных векторов отражения его матрица имеет вид — 1 1 =Š— 2ЕЕ м О 1 где Е, д — матрица, состоящая из нулей, за исключением единицы в левом верхнем углу.
Матрица Р, ортогональная и, следовательно, отражение является ортогональным преобразованием. С этим и связано применение отражений к решению систем линейных уравнений. В произвольном ортоиормированном базисе е, получаемом из е, при помощи ортогональной матрицы перехода Я, матрица отражения имеет вид Р= 5-'РаЗ=Š— 23 'ЕьтЯ, Обозначим через зм и о» соответственно элементы матриц Е„, и Я.
Тогда в матрице Я 'Еьт Я на пересечении 1-й строки и 1-го столбца стоит элемент ~ ', омемоц Ф,! (здесь учтено, что 8 ' = Яг). Все еы равны О, за исключением ем, равного 1. Поэтому написанная выше сумма равна оном, и 5-1ЕЕ,Я = пот где и — первый столбец матрицы Яг. Но Яг — матрица перехода от е к ем Столбец о является координатным столбцом в базисе Ь 3. ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ 153 е первого вектора базиса е„т.
е. вектора в, определяющего отражение. Мы видим, что в ортонормированном базисе матрица отражения имеет вид Р = Š— 2оот (8) где о — координатный столбец вектора, определяющего отражение. П р едл о же н и е 7. Каковы бь> ни были ненулевой вектор х и вектор 1, по длине равный 1, найдется такое о>пражсние, которое переводит вектор х в вектор о>. Заметим сразу же, что обязательно (а 1 = ~ х 1, так как отражение — ортогоналыюе преобразование. Для определенности будем считать, что а = (х ~, Мы дока>кем, что нужное отражение определяется единичным вектором г, коллинеарным с х — а). Введем для этого ортонормированный базис и обозначим через и ~р координатные столбцы векторов х и )'.
Вычислим длину Х вектора х — а7: ~ х — а) ~т = ($ — а>р)т (е — а>р) = $т Р— 2аььт <р + атрт<р Поскольку а' = ( х (г = ~тй и трт ч> = (7 (' = 1, имеем У= (х — а7(е=(2а' — 2ает>р). Рассмотрим вектор г с координатным столбцом Х'(Š— шр) и определяемое им отражение с матрицей Р = Š— 2Х '(Š— а<р) (и — ач>)т. Образ вектора х при этом отражении есть Рй= й — 2Х '(й — аь>) (Š— атр)тй Но д — а<р)тз Рте щрт7, >,а 1 2 Поэтому Р $ = е — и + а<р, и мы видим, что построенное отражение обладает нужным свойством. Предложение доказано. Докажем с его помощью следующее П р е дл о ж е н и е 8.
Квадратнал матрона А может бьипь разложена в произведение >г)к, где 1г — ортогональная, а К> — верхнял треугольная матрицы. Для доказательства отождествим пространство столбцов высоты и с евклидовым пространством, в котором выбран ортонормированный базис. Пользуясь предложением 7, мы будем последовательно преобразовывать столбцы матрицы. Если первый столбец А нулевой, то пропускаем его.
В противном случае строится такое отражение, которое переводит первый столбец А в столбец, пропорциональный первому столбцу единичной матрицы. Пусть матрица этого отражения есть Р1». Тогда РЕМА = Аа>, Гл нь Введение В численные методы и матрица Ан> имеет вид ааа ала ан '- ала О а",' ...
а"„' О аал ... а„",' с элементом а„равным евклидовой норме первого столбца матрицы А. Пусть теперь проделано й — 1 шагов и построены матрицы отражений Рн>, ..., Р'л-л> такие, что матрица А~л-н = Р<л-"... Р"'А с элементами а!,'.
и имеет в первых й — 1 столбцах нули ниже главной диагонали. На й-м шагу строится отражение, переводящее столбец !О, ... 0 ам-и ... а'л — н,т ы ' '''' ал л-1 (9) в й-й столбец единичной матрицы. Оба участвующих здесь столбца имеют нули на первых й — 1 местах и, следовательно, тем же свойством обладает и о — координатный столбец вектора, порождающего отражение. Согласно (В) отсюда прямо следует, что первые й — 1 строк и первые й — 1 столбцов матрицы отражения не отличаются от соответствующих строк и столбцов единичной матрицы, т. е. она имеет следующее строение: (10) Анн = Рлл!Аы-" те же, что н у матрицы А'л-л1, и, кроме того, Ьй столбец имеет вид а!л-'л, ..., а<л-л!,ал> О, ...„О!!т м ° ° л пл,м а-л Таким образом, матрица А ни в первых й столбцах имеет нулевые элементы ниже главной диагонали.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
