Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 48
Текст из файла (страница 48)
281 $ 45) метод слмгэльсонл схема этого метода такова. Вычисляется прямо- Вычислительная угольная матрица й !О 0 ИМ 10 0 0 0 0 0 0 0 0 0 1 — ац О 1 — а1! — Й5 1 — ан — )с5 — )сМ5 'О О )сМЯ:, .1 — а„— Ю вЂ” йМ5 ......... — -)сМо 5 где )с, 5 и М клетки в следующем разбиении данной матрицы а„*! :а„... а„ а„: а„... аа„ (2) а„, аоа ... а„н Х!о Пусть Хоо Хое произвольный вектор. Пусть далее Х!! Х!1 Х1, »-1 ' '1 Хо'= — Хо! Х1о Хоо А"Х = о— (4) оо Х Далее, посредством элементарных преобразований (как это делается в задаче исключения й 22) нужно добиться того, чтобы на мес~е строки )сМн оказалась нулевая строка.
Тогда остальные элементы поспею|ей строки дадут, вообще говоря, коэффициенты характеристического полинома. Процесс исключения, как мы видели, очень однообразен и прост. Это является основным достоинством схемы. Автор выводит указанную схему из преобразования системы линейных дифференциальных уравнений, связанной с матрицей, к одному ляфференциальному уравнению порядка л посредством специалыюго приема исключения. Краткое алгебраическое обоснование схемы заключается в след! ющем. 262 ПОЛНАЯ ПРОБЛЕМА СОбСТВЕННЫХ ЗНАЧЕНнй [гл. гч Из построения следует, что (б) хн,— — а„х, «, +РУ», У« = Яхь»-1+ МУ«-1 (7» = 1 ° .
и) (6) Таким обрааом, мы имеем л' соотношений (л и л(п — 1)) между и'+л величинами. Они дают возможность исключить из системы равенств (б) и (6) векторы Уп ..., У„, т. е, л(п — 1) величин. В результате этого исключения останется а равенств, связывающих 2л чисел, именно, компоненты вектора У, и числа хш, ..., х„,.
Проведем это исключение. Имеем прн 2 = 1, 2, ..., и: х,у, — — апх, „, + Р У» — ппхь «-г+ Рсхь»-«+ РМ»»-г = =. апх, «, + РЯх, ««+ РМЯх, «,+ РМ«У« =. анх, »,+Р5х, „,+ЙМ5х, « ., + + . +РМ охю+РМ )о или г ! «-я РМ' 1;=хм — а„х, «,— РЯх, «,— ... — РМ Зхш. (7) Коэффициенты этих н равенств образуют, очевидно, матрицу (1). Исключая нз этих п равенств компоненты вектора Уш мы получим одно линейное соотношение между числами хш, ..., х,„с постоянными коэффициентами, не зависящими от выбора исходного вектора. С другой стороны, исходя из соотношения Кепи — Гамильтона, мы имеем х,„— р,х, „,— ...
— р„хю — — О. Это равенство тоже является линейной аависимостью между числами хю, ..., х,„с постоянными коэффициентами, не зависящими от выбора вектора. Эта зависимость будет совпадать с зависимостью, полученной методом исключения, в том случае, если матрица А такова, что мы вправе считать числа хш...., х, „ , независимыми переменными, т. е.
если мы можем им придавать независимо друг от друга произвольные значения за счет подходящего выбора остальных компонент исходного вектора ХА илн, иными словами. Ва счет вектора Уе. Более строго обосновать метод Самуэльсона можно посредством следующего соотношения между коэффициентами харзктеристических полиномов окаймленной и окаймляемой матриц. 9 481 283 МЕТОД САМУЭЛЬСОНА Пусть р(г)=( — 1)" (С' +р,г" '+ ...
+Р„) г(г)=( — 1)" (1" '+д,с" '+ ... +д„,) (8) характеристические полиномы матриц А и М. (Мы, вопреки обычной записи полиномов, изменили знак у коэффициентов ра и да), Тогдз справедливы следующие соотношения: Р = пн+Чг Р, = — Й5 — Чгап +д, р, = — ЙМ5 — д,тт5 — д,ам+ дз (9) р„,= — 14М" '5 — тйМ" 5 — ... +Ч„, р„= — ЙМ 5 — Ч,АМ 5 — ...
— Ч„,Й5 — д„,ап. М'ю 'й'+Ч,М'" й'+ ... +д ~Р' =О (1О) Коэффициенты р,, р,,..., Р„являются в силу соотношений (9) линейными неоднородными формами от Ч,,..., д„, и, следовательно, могут быть одновременно вычислены методом исключения (см. э" 22). Из двух возможных модификаций метода исключения следует взять ту, в которой компоненты векторов Й'.
М')с', ... ..., М' ~)с' располагаются в строки схемы. Тогда эти строки, рассматриваемые как матрицы, суть )с', РсМ, ..., АМ ~. При этом коэффициенты соотношений (9) окажутся расположенными точно в согласии со схемой Самуэльсона. Из приведенного выше обоснования метода легко выяснить область его применения. Действительно, она совпадает с областью применимости метода А. Н. Крылова для матрицы М, исходя из вектора )с'. В качестве примера возьмем сновз матрицу Леверье. Вычисления коэффициентов характэристического полинома произведем согласно описанной схеме (см. табл. ВА 7).
Сначала мы вычисляем матрицу (1), располагая ее элементы в первых четырех строках. Далее проводим исключение, как было показано в 9 22. Последняя строка дает искомые значения коэффициентов, которые почти в точности совпадают со значениями, вычисленными по методу А. Н. Крылова, Последний столбец, как обычно, есть контрольный столбец.
Эти соотношения получаются из правила раскрытия окзймленного определителя. Далее, если применить к матрице М метод А. Н. Крылова, приняв за исходный вектор )с' (с компонентамя а,з, ..., а,„), то коэффициенты д,, д,, ..., д„ , будут определяться из системы уравнений 284 [гл, И Оо СЬ СО СО СО СЧ СО СС с О аь СЧ СО СС ЬЬ О сь сс СО сс с« Оа О «ь сса СЧ к Х О Ь Х к О О Ю СЬ ;О О сО с Ока О $ ' СО сО сО ь аь СО СО ОЪ СЬ С О сс„ О О СО СЧ О ь5 с с5 :О О й Ф Х О О ЬЕ О Я Д ОБ О СО «5 СО Я й О Х Х О О О СЧ СО \,'О Ю О Ъ Ь О О О Ю сО Б СЬ й~ О СО О сч СО СО СЬ С О СО О О О О О О О О О О О с' О СО с' «О С О «5 631 сь СО О сч с-.
ю :ь са с« с' с' О СО с'с СО СЧ о о СО С'Ь О с'5 Ф Х Х Ф Ф аа О О О ~ Й СЧ О О Х Ф Ф Ф О Ф к О Ф Х О О с Х Ф Х Х П Ф О Х ПОЛНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ 285 й 46[ метод А. м. дАнилейскОГО Число операций, нужных для определения коэффициентов характеристического полинома, по методу Самуэльсона немного меньше, чем в методе А. Н.
Крылова. Действительно, составление матрицы [1) требует и [и†1)' умножений, а процесс исключения в схеме Самуэльсона требует столько же операций сколько решение системы в методе А. Н. Крылова. 5 46. Метод А. М, Данилевского Элегантный и весьма эффективный метод вычисления коэффициентов характеристического полинома предложен А. М. Данилевским [1[.
Геометрический смысл этого метода состоит в следующем. Данная матрица А рассматривается как матрица оператора в базисе е,=-[1, О,..., 0)', ее=[0, 1,..., О)', ..., еч= — [О, О,..., !)'. Предполагается, что векторы ео Ае,,..., А е, линейно-независимы. Тогда Аче, = р,Ае) '+ рзА ' е, + ....+ р„еп Ясно, что коэффициенты р,, р,,..., р„сугь искомые коэффициенты характеристического полинома. В базисе е,, Ае,,..., А" е, рассматриваемый оператор, очевидно, будет иметь так называемую матрицу Фробеннуса 0 0 ...
р„ ря — 1 0 1. Р-з О О...р, содержащую в явном виде искомые коэффициенты характеристического полинома. Переход от базиса ео е,, ..., Гя к базису е,, Ае,, ..., А" )е, осуществляется постепенно в л — ! шагов. Каждый шаг состоит А-1 в переходе от базнсз ео Ае,,..., А ео е„.„, ..,, ея к базису а — 1 л г,, Ае,,..., А ео А'е,, е„„,..., е„. Для осуществимости всего процесса необходимо считать, что все промежуточные системы векторов действительно являются базисзми, т. е. состоят из линейно-независимых векторов. Ниже будет рассмотрено, как следует поступать в случзях вырождения. Пока же мы буден рассматривать лишь не- вырожденный процесс. Обозначим через А матрицу, полученную при )г — 1-м шзге (а) процесса, так что А = А, Р = — А( ). Столбцами матрицы А( )являются 0) (ч) (а координаты векторов Ае,, А П,..., А е,, Аеа „,,..., Аея в базисе 286 пОлнАя пРОБлемА соБственных значений [гл.
!ч В-1 е,, Ае,, ..., А е„ е„,,...., е„. Поэтому первые и — 1 столбцов матрицы А) ) будут совпадать с одноименными столбцами матрицы Фробениуса Р. Имеем А( +')=5 'А~")О, В В где В — соответствую)цая матрица преобразования координат. Ясно. что 1 ... а!В!!... 0 О.,. Баа„... Π— 0 ...Б„В1...
1 где з, Вчм з, В+о.... Б„,В+,суть координаты вектора Аае, в базисе Бо Ае,,..., АВ-'е,, е„„.„..., е„. Эти кооРдинаты, как мы видели выше, суть не что иное, как элементы а~~а~ й-го столбца матрицы А( ). Имеем далее В 1-1ВБ1 0 'В-! 1, В 1-1 О ...... 0 ВЕ1,В,! 3 Б,В ! 0 В1-1,В1.! а Вычисление матрицы А ') целесообрззно проводить в два приема. Сперва вычисляется вспомогзтельная матрица В' =ВВ А( ).
Это дей- )В] -1 (В) стане, в силу строения матрицы ВВ состоит в том, что (!з+ 1)-я строка матрицы А умножается на —, а от каждой из осталь- )В) 1 )В) аь„ ных строк отнимается полученная (л+ 1)-я строка матрицы В~ ), умноженная на соответствующий элемент л-го столбца матрицы А~"~. Очевидно. что в результате этих действий первые (л — 1) столбцов не изменятся, в л-и же столбце на (а+1)-м месте окажется единица, а все остальные элементы станут нулями. Вычисления остальных элементов матрицы В будут двухчленными, напоминающими 1В) вычисления метода Гаусса. Полученная матрица Вно умножается затем й 46) мвтод а.
м. данилевского справа на Ва. При этом изменяется только один, именно ()з + 1)-й столбец. Его элементзми будут, как нетрудно видеть, ~~'„,Ьзаиа,..., ХЬ„и„ (а) (а) (а') (ю 1 (-( Иначе говоря, !)а+ 1)-й столбец матрицы А( ь ) есть результат ите(аьп рации Ь-го столбца матрицы А( ) матрицей В( ), Таким образом, переход от матрицы А' ) к матрице А ) про(з) Яьг) исходит по формулам ~~ Ьху а)а (а) (а) 1 ма) 1 (а) Ь),эь, =,, иа., ну и(..)(, а Ьм —— . а(; — ага Ьач ь т (! + А+- 1) (а) (а) (а) (а) О+ А+1) (а-ь1) †, (а) (а) аьа„.( = Ъ Ь;,.
а(а. ) =. 1 п — А+(п — й)(п — 1)+(и — )з) п = 2п(п — А), и потому обшее число умножений и делений будет и' — и'. Метод А.М. Данилевского позволяет вычислять собственные векторы как самой матрицы А, так и ее транспонированной. Действительно„ так как 5 'АЗ=Р, где 5=3) Яз ... 5„(, (2) В качестве примера мы снова возьмем матрицу Леверье. Поясним табл. -1)7. 8. В графах 2, 3, 4, 5 последовательно записываются матрицы А('), В('), В() и В(). Графы 6 и 7 контрольные, графа 6 содержит суммы строк матриц В ), графа 7 суммы (а) строк матриц А ). В графу 1 записываются Ь-е столбцы матрицы А( ). (а) (а) вычисление которых сопровождается обычным контролем. Коэффицие(пы харзктеристического полинома располагаются, таким образом, в четырех последних строках графы 1.
Так как они вычисляются одновременно, контрольное совпадение р, со следом матрицы является вместе с тем и показателем точности вычисления остзльных коэффициентов; полученные результаты ближе к данным Леверье, чем результаты, найденные по методу А. Н. Крылова и методу Самуэльсона. Число операций, нужных для вычисления по методу А. М. Данилевского, значительно меньше, чем по двум указанным методам, и, как мы увидим ниже, меньше, чем по другим методам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
