Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 47
Текст из файла (страница 47)
Д. к. Фаддеев а В. н, Фаддеева 2320.71 0 0 — -3149.53 ~ 1316.80 164.548 ~ --200.405 28.066 147233 3.5640 0.0947 — 179.01 66.388 — 23.087 — 0.6492 308.97 1 30.531 0.098815 19.212 0.062181 3.0095 0.009741 полила пговлкмл совстввнных знлчзний [гл. ш комбинации находятся посредством решения системы линейных уравнений (17), в методе Хессенберга искомая линейная комбинация получается как последний вектор в рекуррентно строящейся последовательности векторов Хп ..., л„, Е„„., при Л,=Се таких, что у вектора Л~ь, первые у' компонент равны нулю.
Каждый последующий вектор получается итерацией предшествующего с последующим „исправлением" посредством добавления подходящей линейной комбинации всех предшествующих векторов. Иначе говоря, О =А2,+Ь„Л,+ ... +Ь,,У,. (!) гу„., )~, В качестве вектора л, удобно взять вектор (1, О, ..., О)'. Указанный процесс не всегда возможно осуществить.
Естественное течение процесса нарушается, если на каком-либо шагу получится зп=О. Рассмотрим основной случай, предполагая г„ ~ О, ..., г„„ ~ О, В этом случае векторы Л,, ..., Л„ оказываются линейно-неаависимыми, так что матрица л=(л, ла, ..., Л„! будет неособенной. Ясно, что л) „— — э (А)2,, (2) где ~7з(1)=(З+ ... — некоторый цолином степени 1, В силу линейной независимости векторов Ли ..., Е„равенство 7(А)Е,=О невовможно, если только степень полинома 7 меньше л.
Полипом же у„ аннулирует Л, и его степень равна л. Следовательно, полипом у„ совпадает с характеристическим полиномом матрицы А. Полиномы ~,, очевидно, связаны рекуррентными соотношениями 'у;(г) =( + ь ) уу,(!)+ Ь'-, гг (г)+ ... +и,.~ (г), (з) где ъо(Г)= — 1 (./= — 1, ..., л).
Таким образом, коэффициенты характеристического полинома определяются, как только известны все коэффициенты Ььп Нетрудно видеть, что система векторных равенств Яв=АК,+Ь„г, х з = АЛз + Иал г + !ЪзДв О = Л„~, = АЕ„+ ЬшЕ, + ... + Ь„„Е„ 275 $ 44) метод хессензеРГА равносильна матричному равенству Аг+ЛН= О, (4) где й1з ~12 ~12 — 1 822 О О О ...— 1й22 Последнее равенство позволяет последовательно определять все элементы матриц Н и г.
Для уяснения вычислительной схемы целесообрззно равенство АР+ОН=О представить в форме (А / Л) ( — ) = О. !У1 Здесь (А ~ г) и ( — ) прямоугольные матрицы, составленные ив (,,Н) матриц А, л и Н в указанном порядке. Составим теперь следующую схему О О 211 О 221 222 а„а„... а,„ аа, а, ... а„, атп а„, ... а„„гтн г„а .., ди 1112 ~22 222 и О О ...— 1а,„ 182 Первые и строк этой схемы образованы матрицей (А! л), послед! Лт ние л столбцов матрицей ( — ).
В начале процесса нам известна мат- '1 Н)' трица А и первый столбец матрицы Л. Умножение 1-и строки ма/лт трины (А)Л) иа 1-й столбец матрицы ( — ) позволяет определить (,Н) элемент Ьп. умножение остальных строк на 1-й столбец матрицы (-)— У1 — ) — элементы гг, ..., г„, соответственно. Как только определены /7т эти элементы, умножение матрицы (А) 7) на 2-й столбец матрицы (Н) дает последовательно элементы а12, )22, гз,, ..., гвм Далее производится умножение матрицы (А ~ Л) на З-й..., и-й столбцы ма/ут трицы ( — ). Вычисления допускают обычный контроль при помощи 1Н)' составления строчных сумм.
~РЛ. Ю ~3 о о ! о о о О о с о с О Я оо'о с'4 с'с (О о о сс о сс о о о со с\' сс о с сс сс ! сс. й О Я о о о с со о со с с сс о о о ссс о с о .с сО сс о о о с-' с' оооо сс й. Р сС Ю Д о сЧ Й о о о х О сс й сс й сс с й й о Ф х й о с" й сс й Н Й й сс й й Ф Ф й йс й О ЙЬЛНАВ ПРВВЛЕМА СОБСТВЕННЫХ ВНАЧЕНИН 9 441 ййтбд хйссйнвййгд При осуществлении вычислений на настольных машинах целесообразно вычисления расположить в форме и заменить умножение строк на столбцы умножением столбцов.
1(войная запись матрицы 2 оправдывается простотой действий. Коэффициенты характеристического полннома определяются параллельно с определением чисел йн по рекуррентным соотношениям, вьпекающим из соотношений (3), Для контроля рекуррентно вычисляются значения полиномов при 1=1, равные суммам их коэффициентов. В табл. !Ч. 3 определяются коэффициенты характеристического полинома матрицы Леверье. Для контроля была вычислена левая часть равенства (4).
Наибольший по модулю элемент полученной матрицы оказался разинь~ 0.0000004. Как только собственное значение найдено, легко определяется принадлежащий ему собственный вектор. 1(ействительно, матричное равенство (4) показывает, что А = — дН7 ~, т. е. что матрица А подобна матрице — Н. Следовательно, собственный вектор Х; матрицы А, принадлежащий собственному значению )ч связан соотношением Х,=ЛУ; с собственным вектором Гг матрицы Н, принадлежащим собственному значению — )ч. Собственные же векторы для матрицы Н опрелеляются без труда, так как произвольно задавшись последней компонентой собственного вектора, мы определим остальные е~о компоненты из системы линейных уравнений: — У +- А, + ) ) У* + ...
+- й„, Уи — — 0 (6) — у„г+ (йвн+х) ув = 0 с треугольной матрицей. Отброшенное первое уравнение можно использовать для контроля. В качестве примера определим по табл. !Ч. 4 собственный вектор матрицы Леверье, принадлежзщий наименьшему по модулю собственному значению. Приближение к этому собственному значению, вычисленное как корень полинома 1а+ 47 888430(а+ 797.27877(а+ 5349.45551+ 12296.551, равно — 5. 298700. Ревультат подстановки компонент вектора у, в первое уравнение системы (6) равен — 0.0007.
полная пговлвма совстванных значаний (гл. 07 Таблица УК 4 Определение собственного вектора по методу Хессеиберга г' А'з Н+ Л,Š— 0.009390 308.95220 308.9522 — 0.217306 106.05866 30.5306 — 0.559152 5.537446 — 1 0.2И182 — 1 — 0.481662 — 22. 57711 9 8.62И32 1.000000 0.098820 — 0.205537 ~ 12.318870 19.2109 0.062181 12.318870 ( 1,000000 3.0095 0.009741 К изложенному методу можно подойти с несколько иной гочки зрения. Именно, метод может быть истолкован как метод приведения данной матрицы А преобразованием подобия к специальному виду йп йзз — ! й О О ...
— 1 йии причем преобразующая матрица Л выбирается треугольной. Поли- номы 7,(1), 47з((), ..., ~8„((), как легко видеть, бУдУт хаРактеРистическими полиномами для матриц йзз "зз й зз й, йзз — 1 )-й и т. д. О Действительно, развертывая характеристический определитель гакой матрицы по элементам последней строки, мы придем к прежним рекуррентным соотношениям (3). Рассмотрим теперь исключительные случаи, которые могут встретиться по ходу процесса. Может случиться', что на 1-м шагу процесса гн — — О, но хотя бы одна компонента вектора Лз отлична от нуля.
В этом случае, мы. заполняя столбец для Лз„з, поставим в него нули только на тех местах, на которых фактически можно добиться нулевого значения за счет добавлении линейной комбинации предыдущих столбцов. Процесс продолжается дальше таким же образом. Если при этом окажется, что мы построим л ненулевых векторов Лн ..., л„, то они автоматически будут линейно-независимыми, и матрица а (в данном случае уже не треугольная, но получающаяся иа треугольной перестановкой столбцов) будет осуществлять подобное преобразование матрицы А в матрицу Н.
Но может случиться, что на каком-либо шаге мы придем к нулевому вектору. Это, очевидно, произойдет 279 3 44) мвтод хассенввггь Таблица ЕК б Метод Хессеиберга в вырожденном случае 7 713 ~ — 14 14 9 — 14'3 О О О 3 О О !4 ! О 2 — 1'3 — 23 '3 — 1 73 О ! О Опишем кратко ход процесса. Последовательно определяем: из (1 Х 1) Ь„= — 2, из(2 Х 1) гш=О, нз(3 Х!) ям=3, Это позволяет считать газ=а„=О. Далее ив (4 Х 1) определяем зиа= 1, из (1 Х 2) Ьж=2, из (2 Х 2) гааз=О, из (3 Х 2) Ь„= — —, из (4 Х 2) ! 7 7 г,,= —. Полагаем за,— — О. Из(1 Х 3) определяем Ь,з= —,, из (2Х3) 3 ' ы — 3 14 23 гы=!4, из(3 Х 3) Ь,з — — — —, из(4 Х 3) Ь„=- — =. Наконегг, из О 3' (1 Х 4) определяем Ь, = — 14, из (2 Х 4) Ь = — 2, из (3 Х 4) 14 Ь, = — —, из (4 Х 4) Ьм = — 8.
После опрелеления матрицы Н определяем характеристический полипом, как указано выше. В качестве второго примера рассмотрим матрицу (18) из ф 42. В этом случае (табл. !Ч.б) а.з=(0, О, О)', и мы вычисляем лишь делитель характеристического полинома. в том и только в том случае, когда векторы Ло А то ..., А" 'Е, линейно-зависимы. т. е. когда минимальный аннулирующий полипом для л, есть только делитель характеристического полинома.
В этом случае, дойдя до нулевого вектора мы прекращаем процесс. последний полипом ~иг(г) будет минимальным аннулирующим полиномом для вектора Е, и его корни будут образовывать лишь час~ь спектра собственных значений. Рассмотрим два примера, иллюстрирующих оба возможных исключительных случая (табл. !Ч. 5 и табл. !Ч. б). Из табл.
!Ч. б мы видим, что в первом примере уже а.„=О. Олнако процесс все >ке удается довести до конца. 280 [гл. ш Таблица 1П б полная пговлемл созстзенных значений Метод Хессенберга в вырожденном случае 5 ( 30 ( — 48 1 3 14 — 24 ! О 3 13 — 23 О 1 О О 30 — 48 о 54 10 О О ЗО [ — 48 о о ' о Именно, имеем ег = — 1, ~8, =à — 5, ег — -К+ 10)(à — 5)+ 54 =- = 1г+ 51+ 4. В заключение этого параграфз заметим, что при вычислении коэффициентов характеристического полинома можно избежать использования рекуррентных соотношений для полиномов ун Вместо этого можно находить характеристический полипом о„(или его делитель в случае вырождения) непосредственно применяя способ А.
Н. Крылова') к мзтрице — Н, что приводит, как мы видели выше, к решению треугольной системы. Так, в последнем примере надо применить метод А, Н. Крылова к матрице (г — 54 ! Имеем С, =, ВС,=, ЫСЗ= Следовательно, коэффициенты полинома ~8г опРеделЯютсЯ из системы р,— бр, = — 29 рг= откуда р,= — 5, р,= — 4 т. е. чг=тг+51+4. б 45. Метод Самузльеона г) С е й б л, н б е р ж е р [1[. Близкнм к методу А. Н. Крылова является также и метод, предложенный Самуэльсоном [1[.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
