Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 55
Текст из файла (страница 55)
Составляя линейную комбинацию векторов у'" ", у'" а', ..., у'а' с коэффициентами 1, дт о ..., п„т о в силу соотношений (2) и (3) находим: ,м-и (, „ш-а1 ( +,у,<а> = ср; (Л ) х'и+ саср, (Л ) хоп +... + с„ср; (Л„) х'"', (5) 417 й 8) метод ленеггьв Если положить 0 (й) 'р (") =х-х, (б) (д=1, 2, ..., л), то, очевидно, >р (7>)=0 при д~у р,.
().д) =О'(),.) ~0. Формула (5) при этом принимает вид д)нд = 1> у„. = ),.д,,, +р, й 8. Метод Леверрье Этот метод раскрытия векового определителя основан на формулах Ньютона [3] для сумм степеней корней алгебраического уравнения. Пусть де1()дŠ— А) = 7>" +рд)д" '+... + р„ (1) — хаРактеРистический полином данной матРицы А =(адд] и )дд, )дн,...
..., )д„— полная совокупность его корней, где каждый корень повторяетса столько раз, какова его кратность. Положим аа="д+ "н+ ° ° ° +)>л (Ф=О, 1, 2, ..., л). Тогда при й~л справедливы формула Ньютона (3] а„+р,е „,+... +Рн дгд= — лрн (7д=1, 2, ..., и). (2) Отсюда Рд = ад> 1 2 ( н+' д д)' 1 Р = й(ан+Рда -д+ ° ° +Рн-дзд). (3) Если суммы ад, ан, ..., а„известны, то с помощью формул (3) можно шаг за шагом определить коэффициенты рд, р, ..., Р„характери- стического полинома (1).
14 г>. и деннхоннч н И, А. мнрон сгдр;()ч)дсн'=З "+рд;р'" м+ +у У'"('=1, 2, ..., л) (7) Таким образом, если сд ~0, то полученная линейная комбинация векторов у>" д',у'" н>,,,у'н' дает собственный вектор хЮ с точностью до числового множителя. Коэффициенты д7;(7=1, 2, ... ..., л — 1) могут быть легко определены по схеме Горнера 416 нахождение совствннных значений и внктогов (гл. хп Суммы гы г„, „, г„вычисляются следующим образом: дли а, имеем (гл.
Х, $12): ат=Хт+)~в+ . +)~,=6РА т. е. г,= ~~', ап. (4-) Далее, как известно (гл. Х1, В 1), Х~ Х~ ..., Х~являютсясобственнымн значениями матрицы Аь. Поэтому за=11+Ха+... +Х~=ЗРАа, Аь=(аД, т. е. если то А-[ Решение. Образуем степени А" (6=2, 3, 4) матрицы А. Имеем: 1'2 3 4 2 1 2 3 3212~ 4 3 2 1 22 18 20 18 !6 18 16 18 22 16 22 30 32!218 А =~ Степени А» =Аа 1А находятся непосредственным перемножением. Таким образом, схема раскрытия векового определителя по методу Леверрье весьма простая, а именно: сначала вычисляются Аа (в = 1,,2, ..., л) †степе данной матрицы А, затем находятся соответствующие га — суммы элементов главных диагоналей матриц А и, наконец, по формулам (3) определяются искомые коэффициенты р;(1=1, 2, ..., л).
Метод Леверрье весьма трудоемок, так как приходится подсчитывать высокие степени данной матрицы. Достоинство его — несложная схема вычислений и отсутствие ясключительных случаев. П р и м е р. Методом Леверрье развернуть характеристический определитель матрицы (см. $ 3) 9 9) понятии о мктодк нкопгкдклкнных коэеемцикнтов 419 30 22 18 20 20 18 16 18 18 16 18 22 20 18 22 30 А'-[ 208 178 192 242 178 148 !54 !92 192 154 148 178 242 192 178 208 Заметим, что не было необходимости вычислять Аз полностью, достаточно было найти лишь главные диагональные элементы это!1 матрицы.
Отсюда гз = ЗрА .= 1+ 1+ 1+ 1 = 4; з, =- ЗрА' = 30+ 18+ 18+ 30 = 96; зз =- ЗрАз 208+ 148+ 148+ 208 712. з =ЗрА4 = 2108+ 1388+ 1388+2108 = 6992. Следовательно, по формулам (3) будем иметь: = — 4; (зз+Р з ) = — — (96 — 4 4) = — 40; 1 2 (зз+Рззз+Рззз) == —, (712 — 4 96 — 40 4) = — 56! 1 1 Рз = 4 (аз+Рззз+Рззз+Рззз) = 1 = — — (6992 — 4 712 — 40 96 — 56.4) = — 20. 4 Таким образом, мы получаем уже известный результат (см.
9 3): й — 1 — 2 — 3 — 4 4 — 3 —.2 А,— 1 7!4 4)!з 40Хз 561 20 й 9. Понятие о методе иеопределеиных коэффициентов Развертывание векового определителя можно также осуществить при помощи нахождения достаточно большого количества его числовых значений. Пусть - (1) 14» А' = [ Рз= 1 Р 2 '1 Р 3 — 2 !» — 1 — 2 — 3 — 3 — 2 !» — 1 — 2 1 2 3 4 2 1 2 3 3 2 1 2 4 3 2 1 208 178 192 242 178 148 154 192 192 154 148 178 242 192 178 208 2108 1704 1656 1992 !704 1388 1368 1656 1656 1368 1386 1704 1992 1656 1704 2108 420 нахождения совстввнных зньчвний и ввктогов (гл. хи есть вековой определитель матрицы А, т.
е. .0 (Х) = бе1(ХŠ— А). Если в равенстве (1) последовательно положить Х=О, 1, 2, ..., л — 1, то для коэффициентов р~ (1 = 1, 2, ..., «) получим систему линейных уравнений р»»»0(О), 1 +р, 1 +... +р. 0(1), 2" +р, 2"-~+... +р„=0(2), (2) (л — 1)»+р,(л — 1)" '+... +р„=0(л — 1). Отсюда р,+р,+... +р„,=в(1) — о(о) — 1, 2" 'р +2" ар +...
+2р, =0(2) — О(0) — 2", (л — 1)» гр +(л — 1)» зр +... +(л — 1)р„ = 0 (и — 1) — 0 (0) — (л — 1) и р»»» 0 (0) = бе1( — А). Из системы (3) люожно определить коэффициенты рг (1= 1, 2, ..., и) характеристического полинома (1).
Вводя матрицу ! 1 ... 1 2» ' 2" » ... 2 с.-[ (л — 1)» г (л — 1)»» ... л — 1- и векторы Р ъ 0 (1) — 0 (О) — 1" 0 (2) — 0 (О) — 2 0 (л — 1) — 0 (О) — (л — 1)» Р» и систему (3) можно записать в виде матричного уравнения фл» 0; (4) отсюда Р = С» 'О. (б) Заметим, что обратная матрица С„ ' зависит только от порядкал векового определителя и может быть найдена заранее, если приходится иметь дело с массовым раскрытием вековых определителей одного и того же порядка. 9 11) идхождиник ндинольшкго по модулю совствкнного зндчення421 Таким образом, применение этого метода сводится к вычнсленню числовых определителей й()г)=бе!(йŠ— А) (8=О, 1, 2, ..., л — !) и нахождению решения стандзртной линейной системы (4).
й 1О. Сравненяе различных методов развертывания векового определителя Таблнка 26 Колнчество действий, нспользуемыд разянчнммн методамн развертмвання векового омределнтеля, в завнснмостн от порядка его Порядок Метод , о ос н 2 о !м~ :Р\ З тт ом Н!м ом ойм ммй ! гро ег с-в у — д с — в у-д у — д с — в у — д с — в Непосредственное развертыванне Данилевского Крылова Лезеррье Неопределенных коэффициентов Интерполнрованна*) 46 36 118 1!4 320 92 389 4!4 238 !3 692 80 282 280 1 287 330 ! 79! 1О 078 252 10 22 1 533 986 400 632 32 09 52 28 10 60 12 42 38 179 27 153 12 14 67 41 725 758 576 2 688 4644 .
265 1 189 230 972 67 41 17! 38 125 2 481 2 202 2 525 279 826 е) см. гл. х!ч. 3 тз. Из этой таблицы видно, что для развертывания вековых определителей порядка выше пятого наиболее выгодным, с точки зрения количества действий, является метод А. М. Данилевского. й 11. Нахождение нанбольшего по модулю собственного значеняя матрицы м соответствующего собственного вектора Пусть имеем характеристическое уравнение де!(А — )!Е) = О. Корни этого уравнення )!ы )гз, ..., д, являются собственными значениями матрицы А.
Пусть им соответствуют линейно незавнснмые Об относительной эффективности различных методов развертывания векового определителя можно судить по приведенной ниже таблице 26141, з которой указаны количества действнй, требуемых каждым из рассмотренных методов, в зависимости от порядка определителя. 422 нахождение совстввнных зньчвний'и ввктотов [гл. хп собственные векторы х'", хж'...., х'"'. Укажем некоторые итерационные методы вычисления наибольшего по модулю собственного значения матрицы А, не требующие раскрытия ее векового определителя. С л у ч а й 1.
Среди собственных значений матрицы А есть одно, наибольшее по модулю. Для определенности предположим, что 1Х (> 1Х,()1Х 1~...~!й„(, (1) так что наибольшим по модулю является п е р в о е с об с т в е н н о е з н а ч е н и е. Очевидно, для действительной матрицы наибольшее по модулю собственное значение л, действительно.
Заметим, что такой случай имеет место, если матрица А †действительн и элементы ее положительны (гл. Х, $ 16, теорема Перрона). Укажем приближенный способ вычисления корня Х,. Возьмем произвольный вектор у и разложим его по собственным векторам хо/ матрицы А: где с, (у = 1, 2, ..., л) — постоянные коэффициенты. Произведя преобразование А над вектором у, будем иметь: Ау=,~~~ с Ах'Л. /=1 Отсюда, так как хп' есть собственный вектор преобразования А, т.
е. Ах~'="в/хи', получим: Ау = ~~.", с/Е/хи1; /=1 Ау назовем итерацией вектора у. Последовательно образуя итерации Ау, Аву, ..., А"у, находим: А"у = ~~'.~ с/)Р'х'~' (2» .,// (ю-я итерация). Выберем в пространстве Е,=(р» базис е, е, ..., е„(не обязательно единичный). Пусть А~у =у"" (/в = 1, 2, 3, ...) где у< )(1=1, 2, ..., и) — координаты вектора у' ' в выбранном базисе. Разлагая собственные векторы х<А по векторам базиса, будем иметь: « хоз=~ х;,еп < 1 (3) Отсюда, подставляя выражение (3) в формулу (2), получим: у' '= ~чР ~с Л; ~ч~~~х<уе< или, изменяя порядок суммирования, «« у' '= ~~ е<~ч~ ~с,х<.Л;.
<=1 / 1 (4) Козффициент при е< есть 1-я координата векторау' '. Следовательно, можно написать: « у<«о=~ с х< Л.. (4') !-1 Аналогично у<'"+ы=~~'„~ с х; Л. +', (4") Разделив вторую сумму на первую, будем иметь у<'"+ < с л Л'"+" +...+с л Л"'+' ! <<< 1 "° ° «<« у< с,««Л, +... +с«л<«Л„ <«о ~« «« Предположим, что с<фО и х< фО. Этого можно добиться, выбирая надлежащим образом исходный вектору и базис (еы е„..., е„). Преобразуем выражение (5) следующим образом: Отсюда, переходя к пределу при л< — «оо и учитывая неравенства (1), получим: <«1+ << И<п "' (6) м-«» У< $11).нахождвиив нливольшвго по модтлю совстввнного знлчвния 423 424 нАхОждение совстВенных знАчений и ВектОРОВ (Гл.
Еп УА1Лт так как 1нп ( †) =0 при у ) 1) или приближенно тм)1 (я+ 1) я( Рнв) (1'=1, 2, ..., п), (7) точнее, )(1= ~',, +0((~') ) Аз=А А, АА=АВ Ав, Ав Ав, Ав Ав =А' Ав Отсюда находим: р( '=А и (в1+П 4 Ов) где л) =2". Затем, как обычно, полагаем: Ов+ 1) 1(1 ж †' (1 = 1, 2, ..., И). (вп Вехтор у' ' =А"у приближенно представляет собой собственный вектор матрицы А, соответствующий собственному значению 1(1. Взяв достаточно большой номер итерации и), мы сможем с любой степенью точности определить по формуле (7) наибольший по модулю корень )(1 характеристического уравнения данной матрицыА. Для нахождения этого корня может быть использована любая координата вектора у'"', в частности, можно взять среднее арифметическое соответствующих отношений.
3 а м е ч а н и е 1. В исключительных случаях, прн неудачном выборе начального вектора у, формула (6) может не дать нужного корня или даже вообще может не иметь смысла, т. е. предел отпоров+1) щения ню может не существовать. Последнее легко заметить к( по «прыгающим» зкачениям этого отношения. В таких случаях сле-дует испробовать другой начальный вектор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
