Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 60
Текст из файла (страница 60)
Примененный там прием заключался в вычислении коэффициентов квадратного уравнения, корнями которого являются лва наибольших по модулю собственных значения. Этот прием может быть естественным образом обобщен. Допустилс что элементарные делители матрицы взаимно просты и что ~ Л,/)~)Л2).- .. )~ ~>„) ) >>т.„~ )~ )~... )~ ) Л„~.
Обозначим через (У,, ..., У„канонический базис пространства. Допустим, что начальный вектор )', взят таким, что все компоненты в его разложении по векторам канонического базиса отличны от нуля, т. е. )'2= О,У, +алгlя+ ... +О„Сlг+О„~,У„~,+ ... +О„У„ а, эь 0 (1 = 1, 2, ..., и). (1) Пусть 1г+ Ьг(г-г+ ... + Ьг = (Š— Л,)...
(1 — Л„) полинам, корнями которого являются Л,, ..., Л„. Тогда, как нетрудно видеть, (2) с точностью (в каждой компоненте) до величии поРЯдка ))тэ, +21». Действительно, в написанной линейной комбинации исчезают все СОСтаВЛяЮщИЕ ПО ВЕКтОраМ УО ..., Ь'г, а КОЭффнцнситЫ Прн (/„ ..., (г'„умножаются не более чем на Л„г, и, быть может, на величину Аея порядка некоторой степени й (если у матрицы имеются нелинейные элементарные делители).
Векторное равенство (2) равносильно системе и равенств для соответствующих компонент. Взяв какие-либо г из них, получим систему г линейных уравнений относительно Ьо ..., б„. Будем, для простоты, считать, что компоненты перенумерованы так, что выбранными будут г первых компонент векторов 1'2,„„..., Гл г) Фрезер, Дункан н Коллар [1). 23" 356 чАстнчная пРозлРМА сояставнных ЗНАчвннй 1гл.
ч Решая полученную систему У,ьэ„+б,У,АА„,+ ... +б„у,а =О У,а.„+д!у„и,„1+ ... +Ь„У„А — О (3) по формулам Крамера, получим для коэффициентов Ь1, ..., Ь„при- ближенные значения ~ — уг А+ у11 + -г ° У12 ! Уг А'-гг Уга 1-г-2 Уга ~ У1 1г+г-1 У1 А+г-2 ° Уьь Уг 2.1.г-1 Уг11+г 2 ' ' ' Уга У1 А+г-1 — У1 А ~ У. А+г-1 — Угггэг ! У1 lг гг-1 . ° У12 Угьэг-1 . Угь Можно показать, что эти равенства справедчивы с точностью до величин порядка 1 г~.' + ~, Лля я= 2 эти оценки были проведены выше.
Определив коэффициенты бо ..., Ь„находим собственные значения как корни полинома Гг+Ь11г-1-+ ... +Ь,. Если среди них окажутся равные, это будет свидетельствовать о наличии нелинейных элементарных делителей у матрицы А. Заметим, что для определения коэффициентов бп ..., Ь„можно брать вместо г различных компонент векторов У„,г, ..., 1'А какую-либо одну компоненту векторов уа «А'12-2» . 12-' .'уь — . "А При практическом вычислении нет необходимости на самом деле вычислять определи~ели, Можно написанную систему решать численно, одним из описанных выше способов. Заметим, что сколько-нибудь удовлетворительный результат получается, если определяемые г собственных значений близки по модулю, а следующее (г+1)-е сильно отрывается от иих.
Если же это обстоятельство не имеет места, то полученная система (3) будет очень плохо обусловлена и определители в формулах (4) будут очень близки к нулю. Теоретически говори, указанным процессом можно построить весь характеристический полином (вернее минимальный аннулирующий вектор У полипом), приняв г = и. В этом случае мы придем к методу Крылова, аыполненному исходя из начального вектор А"гя. Конечно, здесь целесообразно считать 12 = О, чтобы не вычислять лишних итераций. К тому же с увеличением м падает обусловленность системы метода Крь(лова. В случае, если !Л1())Л2)) ... ))Л,()(Л„+1!) ... )~)Л„,~, можно несколько изменить описанный процесс.
Именно, в этом случае достаточно вычислять лишь свободные члены последовательных полиномов (à — Л1)(1 — А,), ..., (~ — Л1)(1 — )е) ... (1 — Лг), так как 9 56) ОТЫСКАНИЕ НЕСКОЛЬКИХ СОБСТВЕННЫХ ЗНАЧЕНИЕ 357 эти числа с точностью до знака равны произведению последовательных собственных значений. Выпишем соответствующие формулы '): Уса эг 1 Уга ! Уга+ 2 Л,)я ',Уга ' ~ Уга+~ У22+1 у!а+! У22+1 ~ Уга Уга Уга+г ° Уга+1 ~ ) Л Уга+г Уга+1 ~ Ута Г г -1 .
Уга| Угаьг-1 ° ° Уга 4.6792336 4,6779433 ) 8.4112637 8.4032694 ! — 0.0265541 0 667353 4.6779433 4.6700089 ) — 0.0397902 ! 8.4032694 8.3912886 ! Исходя из вторых и четвертых компонент тех же итераций, получим Л,Л, 0.666110. В 9 54 мы вычислили, используя эти же итерации, что Л, = =1.001. Это дает для )я значения 0.6667 или 0.6654.
Точное значение ); = 0,66666... 1) Эйткен [3). Заметим, что определение произведения даже двух собственных значений наталкивается на препятствие в виде исчезновения значащих цифр, так как при лостаточно большом числе итераций строки определителей становятся почти пропорциональными (в случае, если первое собственное значение сильно отрывается от второго). Поэтому, как правило, даже второе собственное значение определяется при помощи степенного метода с гораздо меньшей степенью точности, чем первое. В 9 53 мы уже рассмотрели примеры на вычисление коэффициентов уравнений.
корнями которых являются наибольшие по модулю собственные значения для г=2. Мы ограничимся этими примерами и проиллюстрируем здесь лишь второй описанный прием. Именно, определим второе собственное значение для матрицы (7) 9 54. Взяв л=- 18, получим, исходя из первых двух компонент соответствующих векторов, 858 ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ [ГЛ. ч Наконец. определим )я через отношение определителей, составленных из одноименных компонент соседних итераций. Используя первые компоненты 17-й, 18-й, 19-й и 20-й итераций, получим 4.6792336 4.6779433 4.6779433 4.6760039 ~ — 0.0030156 ! 4.6779433 4.6760089 ( — 0,0045170 4.6760089 4.6731097 так ~то )аж 0.6669. й 57.
Ступенчатый степенной метод Определение двух н более себе~венных значений при помощи степенного метода наталкивается, как мы только что видели, на две трудное~и. Это, во-первых, возможное уничтожение значащих цифр при составлении нужных линейных комбинаций и, во-вторых, отсутствие критерия, по которому можно было бы судить о достижении удовлетворительной точности. От обоих этих недостатков свободен нескоЛЬКО более трудоемкий ступенчатый степенной метол.
к изложению которого мы сейчас переходим. Мы его разберем подробно в применении к задаче определенив двух наибольших по модулю собственных значений и принадлежащих нм собственных векторов 1нли собстаенного и корневого, если наибольшее по модулю собственное значение входит в канонический ящик второго порядка) и лишь коснемся его обобщения на задачу определения первых г собственных значений. Мы рассмотрим три модификации метода.
При этом мы будем считать, что (Х,! )~ !1Я~ ) ~>,з! )~ ... ~1.„!. Для простоты изложения будем также предполагать, что собственные значения, начиная с 1.з имеют линейные элементарные делители. 1. Вполне стабилизирующийся ступенчатый метод. Пусть Х„и ӄ— два произвольных вектора. Образуем векторы АХ„и АУ, и построим такие их линейные комбинации Х, и У,, что первые две компоненты векторов Х, н У, образуют матрицу Для этого нужно умножить прямоугольную матрицу, составленную из компонент векторов АХВ, АУ на матрицу второго порядка, обратную к матрице, составленной из первых.
двух компонент векторов АЛВ, АУВ. Это можно сделать, например, так. Построим вектор Х,, поделив все компоненты вектора АХ„на первую компоненту. Вектор У1 строится посредством вычитания из вектора АУ, вектора Хо умноженного на первую крмпоненту вектора АУВ н деления всех компо- 359 СТУПЕНЧАТЫЙ СТЕПЕННОЙ МЕТОД нент полученного вектора на его вторую компоненту.
Наконец„ вектор Х, строится посредством вычитания из вектора Х, вектора У,, умноженного на вторую компоненту вектора Л;. Далее процесс повторяется. Именно, векторы Хь и У„ строятся как линеиные комбинации векторов АХь , и АУ„ , тзкне, что их первые две компоненты образуют единичную матрицу второго порядка. Теорема б7.П Пусть собственные значения матрицы А удовлетворяют неравенствам ~)ч~~~~1г~)~)'г1~~ еь1)ь! Тогда, если 1) отличен от нчля определитель из первых двух компонент собственных векторов П, и сгг, принадлежащих собственным значениям 1ч и )ч, или собственного вектора П, и корневого сгг, принадлежащих собственному значению )ч = Лг; 2) не равен нулю определите.гь с,дг — сгд, из коэффициентов ратл нгсния Хо=сад +сгПг+ . +с П У,=б,и,+ди,+ ... +б„П„ векторов Хь и 1'ь по собственным (корневым) векторам; 3) все определители, составленные из первых двух компонент векторов АьХь и АьУь отличны от нуля, то последовательности векторов Хь и Уь имеют пределы Х и У и эти предельные векторы лежат в инвариантном подпроспьранстве, натянутом на векторы П, и иг.
Доказательство, Из процесса построения векторов Хь и У„ ясно, что векторы Хь и У„являются линейными комбинациями векторов АьХь и Аь1'ь. Пусть х,ь ут хгь угь хяь усь — двухстолбцовая матрица, составленная из компонент векторов А"Х и А'У,, ь ь 1 0 0 1 сги ага збО ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ (ГЛ. У вЂ” матрица, составленная из компонент векторов ХА н Уь. Из построения следует, что матрица Фь получается из матрицы сь линейным комбинированием столбцов, что равносильно умножению справа на некоторую матрицу второго порядка. В качестве этой матрицы, очевидно, нужно взя~ь матрицу так что ~22 У22 Третье условие теоремы обеспечивает су2цествование матриц — -1 хга Уж , т, е.
обеспечивает бесконечную продолжимость про- х2А У2А 1 цесса. ПеРейдем тепеРь к оценкам компонент вектоРов Х„ н Уа илн, что то же самое, к оценкам элементов матрицы ФА. Для этого выразим элементы матрицы ФА через х;А и Уси Имеем хга хаа уаа и, следовательно, прн (>3 ()) х,ауаа — хтау,а т)2А — — У " '" '"У'А при ()~ 3.
(2) хтлуть — хтаутх Допустим сначала, что (у, и ()2 — собственные векторы, отвечаюгцие, может быть, равным собственным значениям Л, и ) . Из разложений Хе= с,()2+сала+ ... +с„(у„ (3) уе=тт,и,+гтаи,,-+ ... +2)„()„ следует А"у, = и,лт(),+ у,ла(),+ ... +2(„Л'„'и„. Следовательно, а в ь хи,—— С,Л,им+С,Л,и„+ ... +Е„Л,и„2 у;„= с(2Л2 иы+ 222Лаи„+... + а'„Лви„а Ь А А 361 стяпенчлтый ствпвнной метод и потому хиуаа — хьаудд — =(с,Лди,д+ саЛ иад+ ... + с„Л„и„;)(г(дЛд~ид + а а л + г)аЛа иа, + ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
