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