Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 85
Текст из файла (страница 85)
Для обоснования треугольного степенного метода проведем следующие рассуждения. Пусть К и М проиавольные матрицы. Рассмотрим последовательность матриц А( )=КА М. Кажду>о из этих (а) а матриц представим в виде произведения левой треутольнои матрицы (.'» с единичными диагональными элементами, диагональной О» и правой треугольной Ва с единичными диагональными элементами' 525 9 781 тгяггольный степенной метод (л( Матрица минора Ь; есть произведение двух прямоугольных матриц, из которых первая составлена из первых» строк матрицы КР вторая из первых» столбцов матрицы Л. РМ. Поэтому Р»,» ...
Ру(» ч(д »»»и ... »)»»» Лл ... Л»,, (4) Руп ° Р»»» и «»» »(н . ° »Л»» Рп ° Ры аи= ..... ~О и Ри= ..... +О (б) »)»» ° ° ° Ч»» Рн ° Рн Последние условии мы будем предполагать выполненными при всех ». В этом предположении Ь~Ю=О»»Р»»Л(Лал ...Л; [1+0( — '„+') ]. (6) Следовательно, »-1 Подобным же образом ,(а-11 Я»»Р»» Лл — » ~1+О(Л» () ) О( Л» ) ~ Поэтому л(й) =Л»+0( — »+() +О( ' ) 1(=1, ..., и — !). 18) Для наименьшего по модулю собственного аначения мы получим ,„" „=Л„+О(ЛЛ'" ) . (9) в Обратимся теперь к исследованию матриц.
Вл и Св. Напомним явные формулы для элементов матриц Вь и С» Я 1, п.12), Именно, (л> лу' р(тр = р(ю (л] (ю т»» с» =— т(л» ° При достаточно большом»» преобладающим слагаемым в Ь(»Ю будет, вообше говоря, слагаемое, соответствуюшее г( = 1, ..., А=»'. Вторым по величине слагаемым будет слагаемое, соответствуюшее /»=1, ..., у»» вЂ”вЂ” » — 1, /»=1+1.
Это верно, если б26 итвгацнонные методы для гашения полной пговлимы [гл, чш где ргг = тгг = Ьг . а ~гг и Т,~ суть некоторые миноры г-го порядка матрицы А' '. Очевилно, что рассуждения, которые мы применяли для оценки !а! главных миноров Ь!г 1, остаются в силе для оценки любых миноров, так что ~!,"! =-()0Р;,)!'> ... ).", ~1+ О('+.')'~ т!7!=О,чР,;Л" ,...
Л," ~!+О['— ',— ') ). (1О) здесь Яы, Ро. Ягн Р~г некоторые миноры Иго порядка, составленные из элементов матриц [тР ~ и РМ. Поэтому б',","= " "~!+о( — ". ) 1 !Ю дггРМг Ь + О (тг+1Л (1 1) Таким образом, при сделанном выше предположении о неравенстве нУлю всех опРеделителей 1,!и и Рн, все элементы Ьо и с;; ы) !а! имеют пределы при Й -+ оо, причем равенства (11) дают оценку быстроты сходимости. Перейдем теперь к описанию вычислительной схеиы метода.
Пусть С произвольная матрица, А матрица с различными по абсолютной величине вешественными собственными значениями, для которой требуется решить полную проблему собственных значений. Строим последовательность левых треугольных матриц С,, Са ..., Са, ... с единичными диагональными элементами посредством рекуррентных соотношений: АСа = С,И, АС,=Сна (12) АСк-г = Сагта А Са=Сайайа-г ° Ям а (13) Здесь гго )т'„..., !та, ... — правые треугольные матрицы. Процесс следует вести до тех пор, пока матрицы С„не стабилизируются с достаточной точностью.
То, что йш Са сушествует, а-~со легко доказывается. Именно, исключая из соотношений (12) матрицы С,, Са, ..., С„ ,, получим 527 $781 тгаягольный степенной метод Матрица гс»й», ... )7,— правая треугольная, Поэтому матрицы С» и 77» Л», ... )1, совпадают с матрицами С» и »» в предыдуших обозначениях, построенных для матрицы Следовательно, 11ш С» = С существует. » -ь оэ Одновременно со стабилизацией матриц и матрицы й», ибо при л-+ со С» стабилизируются й»=С»~АС»- -+ С ~АС=И. (14) Знание предельных матриц С и )с дает возможность решить полную проблему собственных значений для матрицы А. Действительно, из равенства (14) следует, что собственные значения матриц А и й совпадают, а собственные векторы У,.....
У„ матрицы А равны соответственно С)го ..., СУ„, где собственные векторы матрицы Я. Матрица 77 треугольная, так что ее собственные значения равны ее диагональным элементам, а собственные векторы ~'м ..., 1г„легко определяются из решения треугольной системы. Быстрота сходимости диагональных элементов матриц к искомым собственным значениям может быть оценена из следующих соображений. Прежде всего из равенства Я )1», 71,=»» следует Я =0 В»В,В Поэтому диагональные элементы матрицы 71» совпадают с диагональными элементами матрицы 1)»)З»'ы быстрота сходимости которых к собственным значениям оценивается формулами (8) и 19).
Матрицы С» и й» можно вычислять на каждом шагу, пользуясь компактной схемой метода Гауса. Однако матрицы И» до стабилизации процесса вычислять нет необходимости, так как для решения поставленной задачи нужна лишь предельная матрица Я. Это позволяет ограничиться лишь вычислением матриц С», для чего можно использовать, например, схему единственного деления (с исключением по столбцам), применявшуюся в 9 17 для вычисления определителя.
Та же схема доставит нам диагональные элементы матрицы )с», так что приближенное определение собственных значений матрицы А не потребует дополнительных вычислений. Если же нужно определить и собственные векторы, то на последнем шагу процесса необходимо вычислить всю матрицу 77», которая дает приближенное значение для предельной матрицы )с. 528 итявлционныв мвтоды для гвшвния полной пговлвмы [гл, чш Треугольный степенной метод является самоиснравляющимся процессом, ибо каждое приближение С„можно считать начальным приближением.
В й 57 мы упомянули о связи ступенчатого степенного метода с треугольныи степенным методом. Теперь можно сказать об этом несколько подробнее. Именно, г-ступенчатый степенный метод можно излагать так. Исходя из прямоугольной матрицы с г столбцами СМ>, о надо образовать прямоугольную матрицу АСай>, которую затем представлять в виде произведения левой ступенчатой прямоугольной матрицы С,Ю с единичной главной диагональю и правой треугольной матрицы )с>,"> г-го порядка. Далее процесс повторяется, Легко видеть, что если матрицу С'> каким-либо образом дополнить ло кзадо ратной матрицы Сз и применить к ней треугольный степенной метод, то матрицы Сь~ будут совпадать с матрицами, составленными из первых г столбцов матриц Сь, а матрицы 7Щ> будут левыми верхними клетками г-го порядка матриц )га.
Поэтому суждения о сходимости треугольного степенного метода переносятся без изменения на г-ступенчатый метод. Треугольный степенной метод допускает модификацию со сдвигами. При надлежащем выборе сдвигов можно добиться квадратичной сходимости поочередно к каждому собственному значению. Обоснование такой модификации заключается в следующем.
Пусть (15) р„ (7) = (г — 7,) ... (~ — г„) последовательность полиномов, таких, что каждый последующий полипом получается из предыдущего умножением на линейный дзучлен. Предполагается, что 7а -+ т и собственные значения матрицы А в некоторой нумерации удовлетворяют условиям > >ч — т ) ) ! >я — т ~ ) ... )) ˄— т /. Тогда, как мы видели в й 77, та (>ч) -+0 при я-ьоо. та ('а — >) Рассмотрим последовательность матриц А'"' = К~„(А) М. (16) где К и М некоторые фиксированные матрицы, Нетрудно провести >я> оценки миноров любого порядка, составленных из элементов матриц А >. Именно, любой минор порядка 1 равен ЯР~ з)...
~ь)~1.>0( ')), 530 итеглционные методы для гашения полной пговлемы !гл, тлп Для обеспечения квадратичной сходимости следует за Г„е, принимать 12+ г„ до тех пор, пока, при некотором л = л1, число г„' )2) )и,) не станет равным нулю с' требуемой степенью точности. Затем нужно вычеркнуть из матрицы С1, последний столбец и перейти к ступенчатому алгорифму при числе столбцов, равном л — 1, принимая за сдвиги числа 12~1 — — 12+с„1, 12) 121.
После того как г„, ока- (2) )ли жется практически равным нулю, из матрицы С1, вычеркивается последний столбец и процесс продолжается как ступенчатый с л — 2 столбцами и т. д. Приближенными значениями для собственных значений будут числа 12,. Га„° ° ° Га„. й 79. Пс-алгорифм Ы-алгорифм (Рутисхаузер [5[) заключается в следующем. Матрица А раскладывается в произведение двух треугольных матриц (левой и правой) А = 5)Л), (1) причем левая матрица берется с единичными диагональными элементами. Далее составляется матрица Й1с1 и для нее строится аналогичное разложение ~1('1 1'2~2' (2) Затем процесс повторяется. Таким образом, в результате процесса строятся две последовательности матриц 1.1, 2я,...
и )с1, 1122, ..., связанных соотношениями А =51221 ~1~'1 ~ 2) 2 (3) 122-11.2 1=5Ф2 Установим связь между ьгс-алгорифмом и треугольным степенным методом при Се=Е. С втой целью положим (4) Ясно, что Са есть левая треугольная матрица с единичной главной диагональю. Докажем теперь, что АС,=С )[)г (5) Для л = 1 имеем АСа = А = 51221 = С1)с1. 531 1Я-ллгоеием й 791 Допустим, что равенство (б) справедливо для индексов, меньших Й, и докажем, что оно верно и для индекса Ф. Имеем АСв, — — АСл,7-ь, = С„,1сь Д,, = С„,1.,Я, = Сьй„.
с)ье)) ) ыа-)) е)ю ~ Ыл) е(ь ы р(в+)) = а<")р(ь), — ) лежащие в основе (~О алгорифма, равносильны следующим матричным равенствам ,га) о рш) ) О О 1 а") 1 г е<Ю 1 ! н-) О О Ри ) (ы )в+1) 1 го р(аз а) ) О О 1 а<в+)) 1 ) О О е(в) 1 Тем самым равенство (5) доказано. Из равенства (б) следует, ч)о матрицы Сл и 7.„Ж-алгорифма совпадают с одноименными матрицами треугольного степенного метода при Се = Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
