Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 50
Текст из файла (страница 50)
Таким образом, в рассматриваемом случае процесс нахождения характеристического полинома только упрощается. Однако вычисление канонического базиса (в частности и собственных векторов) несколько усложняется. Мы не будем останавливаться на решении этого вопроса. Метод А. М. Данилевского допускает следующее обобщение. Приведение к канонической форме можно осуществить посредством перехода от базисз е,, е,, . „е„к базису г. Аг'...., А" 'г', где г некоторый вектор, выбираемый, вообще говоря, произвольно, требуется только, чтобы векторы ~, Ау, ..., А" 'у были линейно-независимыми, $ 47) мвтод лввввьв и видоизмвнвнив д. к.
чаддязва 295 Если элементарные делители матрицы взаимно просты, тзкой вектор всегда нзйдется. Этот вариант требует уже и шагов, так как добавляется еще один „нулевой" шаг, состоящий в переходе от базиса (ео еа ..., е„) к базисУ (уг, еа ..., е„), что осУществлЯетсЯ посРедством пРеобРазования подобия А1=3о А3о, где 5е — матрица, первый столбец которой составлен из компонент вектора у', остальные совпздают со столбцами единичной матрицы. Дзльнейший ход процесса ничем не отличается от описанного выше.
Бауэр [6) рекомендует выбирать начальный вектор так, чтобы его координаты по собственным векторам, соответствующим большим по модулю собственным значениям, были бы малыми. Методы построения таких векторов будут описаны в гл. !Х. 5 47. Метод Леверье и видоизменение Д. К. Фаддеева В этом параграфе мы изложим метод, известный под названием метода Леверье 111, требующий большего числа операций, чем все рассмотренные выше методы, но совершенно не чувствительный к частным особенностям матрицы, в частности, к „провалам" промежуточных определителей.
Пусть 9(1)=( 1) 1г Ргг Ра1 ° Рп1 харзктеристический полипом матрицы и Л,, ~. .. Л его корни, среди которых могут быть равные. Обозначим Я;л,"=„. (2) Тогда справедливы соотношения, известные под названием формул Ньютона: ДР, — з Р,за,— ...
Рл з (д= 1...,, и). (3) Если числа зл известны, то, решая рекуррентную систему (3), мы сможем найти нужные нам коэффициенты Р„. Покажем, как определяются числа зь. Имеем гг=Лг+)ч+ ... +Л„= Бр А. Далее, в силу 3 1 п. 1О, характеристические числа матрицы А" булут Л,", Л,", ..., Лч.
Следовательно, гл =Лг+Ла+ .. +Лч==аЗр А . Таким образом, процесс вычисления сводится к последовательному вычислению степеней матрицы А, затем к вычислению их следов и, наконец, к решению рекуррентной системы (3), Вычисление и 296 ПОЛНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ (гл. ш степеней матрицы А (у последней матрицы А" нужно вычислить только диагональные элементы) требует большого числа, правда однообразных, операций, и потому метод Леверье гораздо более трудоемкий, чем вышеизложенные методы. Его ценность состоит, как это уже упоминалось„ в его универсзльности.
Число необходимых по методу Леверье умножений рзвно —, (и — 1) (2 и' — 2 ля+ л + 2) . 2 Заметим, что при вычислении степеней мзтрицы полезно осуществлять контроль при помощи столбца, состоящего из сумм элементов каждой строки матрицы А.
Результат умножения матрицы А на этот столбец должен совпадать с аналогичным столбцом матрицы Аз. Действительно, пусть Е, столбец сумм матрицы А, 2'з столбец сумм матрицы А". Пусть У=(1, 1, ..., 1)'. Тогда 2ч = А(У. 2' = А~(У, Е,=АКР Очевидно, сказанное верно и для других степеней. Изложим теперь видоизменение метода, предложенное Д. К. Фаддеевым '), которое кроме упрощений при вычислении коэффициентов характеристического полинома позволит нам определить обратную матрицу и собственные векторы матрицы. Будем вместо последовательности А, Аз, ..., А" вычислять последовательность А,, А,, ..., А„, построенную следующим образом: А,=А, ЗрА =дп В,=А,— ОЕ Яр Аз Аз — — АВ,, 'уз 2 В,=А,— дзЕ (6) КР Аи-г А„,=АВ„З, —— гу„п В„,=А„,— О„,Е А„= АВ„,, —" = и„, В„= А„— у„Е.
зр Аи Докажем, что а) д,=рп дз=р, ..., д„=р„; Ь) „— нулевая матрица; с) если А неособенная матрица, то Вн А Рн (Если матрица А особенная, то ( — 1)" 'В„, будет матрицей, союзной с матрицей А). 1) Д. К. Фаддеев и И. С. С о минский. Сборник задач по высшей алгебре, 1949, задача га 979. См. также Сурьо [1) и Фрейм (Ц. 5 47) мвтод лввввьи и видоизмвнвнив д.
к. елддввв» 297 Докажем сначала а) методом математиче".кой индукции. Очевидно, что р,=8рА=д,. Предположим, что о,=р,, о»=р», ...,д»,—— =р»,, и докажем, что д» = р». Согласно нашей конструкции: А»=А» д»А -г д»-»А=А» Р А»» . Р»-»А. Следовательно. 8р А» = йЧ» — — Бр А» — р, Вр А» ' — ... — р», 8р А = = э» — ргэ»-г — ° — р»-Л. Отсюда, в силу формул Ньютона йд»=7»р» и, следовательно, Ч» = Р». Далее, в силу соотношения Келн — Гамильтона В„=А" — р,А — ... — р„Е= О.
Наконец, нз равенства (7) следует, что АВ„, = А„= В„+ Р„Е = Р„Е, (7) так что (8) Рч Равенство А„=р„Е может .быть использовано для контроля вычисления; очевидно, что отклонение А„ от скалярной матрицы является мерой точности вычислений. Кроме этого окончательного контроля. целесообразно пользоваться частным контролем, составляя для матриц В; столбцы сумм. Прн етом справедливо соотношение Е~„» —— АХ вЂ” ";„, Х = АХр — р» (9) где Е» столбец сумм матрицы Вп а'„— аналогичный столбец матрицы А.
Формула (8) дает алгорифм для обращения матриц. Для матриц не очень высокого порядка в случае, если нужно решить как зздачу нзхождеьия собственных чисел, так и задачу обращения матрицы, указанный метод очень удобен. Число операций, нужных для получения коэффициентов р; (включая и вычисление матрицы В„), равно (а — !) и» умножений.
В табл. 1Ч. 10 на прежнем примере показана схема вычисления по методу Д. К. Фаддеева коэффициентов характеристического поли- нома и элементов обратной матрицы. Перейдем теперь к определению собственных векторов матрицы А. Пусть собственные числа уже вычислены и при этом оказались различными. Построим матрицу Я~=ЛЭя ~Е+Л» ~В + ... +В„ (10) 298 [ГЛ. РЕ СТВЕННЫХ ЗНАЧЕНИЙ ПРОБЛЕМА СОБ ПОЛНАЯ о й О :О Ос сс а '« О": сч о "с- сч с«о О О о с- В =' О О с' сО О О Ос с Б сС И О й О О СО О О Ф сс М О О О О Э сс И ОО ЮО[ Й» с сЧ О ю О О Х О ° с сс Х Ю О Ф О П О М М Ф В.~ О О О О с сО а :ч сч с с«сс с8 О с'с о сч «с О О О с ««[ я '.О сО О Я сО с- Я сз а~ 'о о о о а'О\О О сч с« а .О О С сО О О О О о с ~ с«ис о о с Оагсо яаасч ОС«СО О «ос-сс Ос«О сч очс со С'С О СО О СЧ СО СЧ СО С«Ф' О О с СО СО С« с «с'с О О С СО с' ~ сч СО о с О О с.~ О с'с 'Ф О с« О О ФФЙ".
СО С .;,,~о счасч «с ОООО О О О оооф ~[ у о ОофО $ 47] метод леВВРье и Видоизменение д. к. Фаддеева 299 где В; матрицы, вычисленные в процессе нзхождення коэффициентов характеристического полинома, а Лл есть й-е собственное число матрицы А, Можно докзззть, в предположении, что все Л,, ..., Л„различны, что матрица Я„ненулевая. Покажем, что каждый столбец матрицы Яе состоит из компонент собственного вектора, принадлежащего собственному числу Лю Действительно, (ЛВЕ А) 1~а = (>ВЕ А) (Ле 'Е-1-Ц.- Вг+ ° ° + Вп-г)= =)ДЕ+Ли ( — А)+Ли (В,— АВ,)+ ...
— АВ„,= =)ВŠ— ргЛй Š— р)~; Š— ... — рпЕ=0. Отсюда следует, что (ЛВŠ— А) сс = О, где а любой столбец построенной матрицы 1,)ю т. е. что ).„а = Аа. (11) Это равенство показывает, что и есть собственный вектор. 3 а л~ е ч а н и е 1. Вычисляя собственные векторы описанным образом, нет необходимости, конечно, находить все столбцы матрицы Ою Следует ограничиться вычислением одно~о столбца; его элементы получаются з виде линейной комбинации с прежними коэффициентами одноименных столбцов матриц В;. Замечание 2. Для вычисления столбца и матрицы ЯВ, удобно пользоваться рекуррентной формулой: (12) г+ 1гг где Ь, — взятый нами столбец матрицы Ви а е — одноименный столбец единичной матрицы.
Тогда а=а„,. В качестве примера вычислим собственный вектор Хп матрицы Леверье, принадлежащий собственному числу Л„= — — 5.29870. Таблица Ъ7 П Определение собственного вектора по методу Д. К. Фаддеева зоо полнья пговлемА совстзенных знАчениЙ 1гл. щ В графах 1, Ц, П! расположены компоненты 1-го столбца матриц Вь умноженные на соответствующие степени )ч, в графе 1Ч компоненты вектора А,'(1, О, О, 0)'.
Графа Ч содержит компоненты вектора Х, графа Ч! — его компоненты после нормирования. 5 48. Эскалаторным метод') Оригинальный метод определения собственных чисел и собственных векторов матрицы известен под названием эскалаторного метода. Этот метод дает индуктивную конструкцию, посредством которой, зная собственные чнсла и собственные векторы матрицы Аь, и ее транспонированной, можно составить уравнение для определения собственных чисел матрицы А„, полученной из Ав, окзймленнем, и затем вычислить по несложныч формулам компоненты собственных векторов для матрицы Аь и ее транспонированной.
Применение эскалаторного метода начинается с отыскания собственных векторов матрицы 2-го порядка. Эта задача решзется совсем просто. Большим достоинством метода является наличие мощного контроля, дающего возможность вычислителю на каждом шзгу быть уверенным как в своих вычислениях, так и в отсутствии потери значащих цифр. Кроме того, сама форма уравнения для определения собственных значений оказывается очень удобной при применении метода Ньютона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
