Том 2 (1160084), страница 32
Текст из файла (страница 32)
Так как Рз(Л) отрицателен при достаточно больших по абсолютной величине, но отрицательных Л и положителен при достаточно больших положительных Л, то имеются три корня Р, (Л): ))2), Л)", Л~~), таких, что Л~~) (Л)1) (Л)2~) (Л)2~) (Л)2). Теперь нетрудно по индукции показать, что рсе корни многочленов Рь(Л): Л,, Л,, ..., Л~А, (ю (2) ы) действительны, различны и удовлетворяют условиям: Л',"'(Л'," ')<Лон(Л'" "( .. <Л),"'1(Л'~:п(Л~ф). (54) Пусть это выполнено для 4= 1, 2, 3, ..., 1. Тогда в силу (53) (55) н, следовательно. в силу (52) Р,„, (Л) )) Р,, (Л) ~) ( О. (56) По предположению индукции Р,, (Л) не имеет кратных корней, поэтому Р) 1(Цг) меняет знак прн переходе от ! к Е-+!. Следовательно, в силу (бб) это верно и для Р)~1(Л, Р Так как степени (1)' Р,,(Л) и Р,,(Л) имеют одинаковую четность, то эти многочлены должны иметь одинаковые знаки левее и правее множества всех их действительных корней.
Л) лежит левее всех нулей Р,, (Л), а Л) — правее 11) и> всех нулей Р), (Л). Поэтому Р).>1(Л) должен обратиться в нуль левее Л)1) и правее Л~~). Так как он должен обратиться в нуль между каждыми двумя соседними Л,, то утверждение доказано. 11) Из доказанного следует, что совокупность м но гочле но в Р„ (Л), )2 = О, 1, 2, . . ., гл образует систему Штурма (с м .
главу 7, Э ! ) . Поэтому мы можем использовать ее дл я отделения корней много- члена Р,„ (Л), ка к это указано в предыдущей главе. Подсчитаем число операций умножения и деления, необходимых дл я получения характеристического м ногоч ле н а симметрической м ат р ицы А порядка п по способу Ланцоша . Пусть процесс, начинающийся с вектора са, может быть продолжен вплоть до с„. Конечно.
1'„= О, Вычисление Ас потребует иа умножений. Получение "12=(Асе, са)7(са, са) потребует 2л+-! умножений и делений. поэтому переход от с к с,=Ас — а)зса потребует всего ла+ 3п.+1 операций умножения и деления, На следую.цем шаге, при переходе от с, к са, придется затратить лз операций умножения для получения Ас,, Зп+2 операций умножения и деления для получения 196 вычисления совстввнных знлчвний и ввктооов млтгиц !гл. 8 коэффициентов йг, = (Ас„сг)1(с„сг) и й,о — — (Ас,, со)!(со, со), 2а операций Умножениа длЯ полУчениЯ сг —— Ас, — йг,с, — йгосо. Таким обРазом, всего второй шаг потребует л'+ 5а+ 2 операций умножения и деления.
Столько же потребует и каждый следующий шаг. Всего для получения последовательности векторов со, с,, ..., с„, потребуется (а'-+ За+-!)+-(а — 2) (а'+ 5а-+ 2) = а'+-4л' — 5а — 3 (57) операций умножения и деления. Нам еще придется подсчитать й„„1 и йо, о-г, для чего нужно За-»-2 операций умножения и деления. Наконец, получение многочлена Ро().) требует 1+3+ 5-+ ... +-(2а — 3) =(а — !)' (58) операций умножения.
Таким образом, всего для получения характе- ристического многочлена матрицы А потребуется лг.»- 4а' — 5а — 3+ За-»-2+ (а — !)2 = а'-+ баг — 4а (59) операций умножения и деления. 2. Отыскание собственных векторов. В заключение остановимся на отыскании собственных векторов, Предположим, что, применяя метод Ланцоша, мы получили сщ = О.
Пусть )! — какой-нибудь корень минимального многочлена вектора со. Тогда будем разыскивать собственный вектор, соответствующий этому собственному значению в виде гсг = Того + Тгсг + + Т1О-1С1О-1. (60) Условие Ах! = )чхг дает "!О (С1 + й1ОСО) '+ 11 (Сг +. Й21С1 + йв1СО) + +'"!1О2(Сщ1+йщ1щгСщг+й1211огсщ2)+ + Тщ, (йщ, сщ, + й, щ гсщ 2) = =)чТосо +)1Т1с1+ +)чТщ-1сщ-1 (61) В силу линейной независимости векторов со, с,, ..., с,„, из (61) следует: То Оч — йш) ОООТ1 = 0 Т1 О г йм) "ОД2 — То = 0* ТООч — йм) — йггТΠ— Т = 0 (62) Тщ — 21 'г 1"щ-1, О1-2) йщ щ-2Т -1 Т -2 0 Т -1(ог — й, .-1) — Т -2= О.
1 197 6 з1 метод ланцоц»л Коэффициент То, 1 должен быть отлучен от нуля, так как в противном случае и все остальные коэффициенты 7» были бы равны нулю. Положим, например, 7„,, = 1. Тогда остальные коэффициенты»П последовательно находятся из равенств: 72»-2 = (Л» — ао1, т-1) 715-2 То1 2(» ао1-1. о»-2) 1112, о1-2 (63) То =7 (Л» — ) — анум 7»=л» а22=0 7о= 71 ОЧ вЂ” ао») — ао» = б (64) л»=(0 6 0 0)+ (О 0 6 6)=(0 6 6. 6) (65) При Л»= 6 соответственно получим: 72=1, 7,=Л» — а„=З, То — 71 (л» а»1)»121 = 6 и (66) л» = (О, 6, О. 0).+ (б, О, — 6, 0) +-(О, О, 6, 6) = (6, б, О, 6). (67) Можно ввести в рассмотрение многочлены: 170 (Л) 1 7, (Л) = (Л вЂ” а„1, „, 1)»72 (Л), »7 (Л)=(Л вЂ” а ц .)»7,(Л) — а,~,»7 (Л), (68) »7 (Л)=(Л а )»7 2(Л) а!»7 (Л) »7 (Л) — (Л а10)»7 -1 (Л) а 0»7 2 (Л) Тогда собственный вектор хо соответствующий собственному зна- чению )ч, можно записать в виде л»=»7,2 1(Л») с,+»7,2 2(Л») с,+...
+»71(Л») с 2+ уо(Л») с,. (69) Многочлен»7„,(Л) в (68) совпадает с многочленом Р,„(л). Как и для метода Крылова, первое из равенств (62) будет следствием остальных и условия, что Л» является корнем минимального многочлена вектора со. Найдем собственные векторы матрицы (44) 9 2.
Если за вектор со принять (30), то вычисления при Л»=З дают »2 198 вычислвнив совстввнных значений и вектоеов млтгиц (гл. 8 ф 4. Метод Данилевского Довольно простой и изящный способ получения характеристического многочлена дал А, М. Данилевский. Суть его метода состоит в преобразовании уравнения 0 (Л) = ! А — ЛУ ) = О к виду Р| " Рз Ра " ° Рп — ь Рн ! — Л О ...
О О О 1 — Л ... О О (2) О О О ... ! — Л При этом определитель (2) легко раскрывается, и мы получим: В(Л)=( — Ц"(Л" — Р,Л"-' — Р,Л"-' — ... — Р„1. (З) Проиллюстрируем ход вычислений по методу Данилевского на примере матрицы четвертого порядка ан аз ам ам лн лн ам лм а, азз ам аа, ам а т ам аы (4) Эта матрица должна быть преобразована к виду Р! Рз РЗ Р4 1 О О О О 1 О О О О 1 О (нормальная форма Фробениуса) преобразованиями подобия.
Делим все элементы третьего столбца на а,м Если по=О, то предварительно находим среди элементов а„и а4з отличный от нуля. Пусть это оказался атз. Тогда меняем местами вторую и третью строки и второй и третий столбцы. Если ам — — а„=а„= О, то характеристический многочлен матрицы (4) примет вид ап — Л ам ам — л ам ам — Л (а„— Л) ам (6) ам и наша задача сведется к отысканию характеристического много- члена матрицы третьего порядка.
199 мвтод длнилввского Вычтем теперь из 1-го столбца (1 = 1, 2, 4) полученной матрицы а«З ан ае, — а«„1 азз ам ам — ' аз« аьз (7) а.« аз« вЂ” ' аз« аа а«З а«1 а«2 1 а«4 третий столбец, умноженный на а,«. При этом матрица примет вид а«з а«за«4 — ам— а42 а44 а,за4, а„— а«з ама«2 «112— азз а — ааа«, аз,— а«з аяз аззам — аз«вЂ” а«з а„ а«за«2 азз азз (8) азз яма«4 — п„—— а«з а«з 1 О ааааа «:1 2— а«з О Напз процесс эквивалентен умножению матрицы (4) справа на матрицу 1 О О О О 1 О О (9) в,= Чтобы получить матрицу, подобную исходной, мы должны умно- жить (8) слева на матрицу В,, равную 1 О О О О 1 О О В« '= (10) а«1 а«з азз а«4 О О О 1 При этом получим: а1за44 ам а«з «'«зам а на«а ам аз — — ' 1 аж аз ан —— «144 азза«з ам а 2 —— аж а«з азз азз О 1 а — ав«аз, аз,— аьз ь О В,'АВ = (11) Умножение на В« не изменяет первой, второй Третья же строка получается путем сложения ных соответственно на азм а«2, а«з и а„.
и четвертой строк. строк (8), умно>кеи- аззаз, ам— а«з О а«1 а«з О а«з а«з О 1 аз« а«з а за О 1 аз«аз« 24 «142 ЬЗ« О 200 вычислвнив совстввнных знлчвний и вактовов мэтгиц !гл. 8 На следующем этапе преобразуем третью строку. Это достигаетсяя путем умножения матрицы (!0) справа на матрицу 0 0 ь ь„ 1 0 йм а ь 0 0 ам аээ 1 0 0 1 (12) 0 0 и последующего умножения слева на матрицу Вэ, равную 1 О 0 0 ам аээ аээ аы Вэ 0 0 1 0 0 0 0 1 Ход вычислений подобен предыдущему, Матрица А будет приведена к виду (! 3) сц с,э сээ сээ сц сээ с,ц см 0 1 0 0 0 0 1 0 (14) Наконец, умножая (!4) справа на 1 см сээ сц сц 0 1 бц 0 1 0 ьц 0 0 1 .Вэ —— (!5) 0 0 0 0 и слева на (! 6) использованную (17) с',ц с,а сээ сы 0 1 0 0 Вэ 0 0 1 0 0 0 0 1 мы придем к нормальной форме Фробениуса.
Приведем числовой пример. Возьмем уже в главе 6 матрицу А: ~ 6.1818 0,1818 0,3141 0,1415 0.1516 0,1818 7,1818 0,2141 0,1815 0,1526 0,3141 0,2141 8,2435 0,1214 0,2516 0,1415 0,1815 0,1214 0,3141 0,3145 0,1516 0,1526 О',2516 0,3145 5,3116 О!2141 О:,3114 0,2613 0,6343 0,8998 Вычисления сведены в следующую таблицу: 0,2141 0,3141 0,2618 0,6843 0,8998 4, 1313 201 интал ДССННЛВВСКОГО !!!! 3.м СО О СО ао 04 СЧ о о ! ИОД о о о о р Р СЧ СЧ о" о Ф- со „Й чо с-„о„я с-" оо ао о" о." О СО С 4 СО СО 4' 4' '4' оО Осо Со С4 ОССЧ О СО О о о О О Ч' О О СО О О 00 СЧ 'Ф О4 00 00 оо Оо ООООСОО 0О 4' Осо --- 4 4"4 Ч' СО СЧ СО С'0 С'0:0 о о о"о" о" о ио 4' О СО 4' 4'00 4'СЧ ОСО С'0 СЧ СЧ С'4 СЧ О О" оо"О"О"О СО СО ио СО Ч' сч СОСО 00 0 со Ос ОООО СОСО 4О О 'С 4' СОСО С 44 со сч ФООООо $ 00 о ! С- с- Оо О О ЫВЯф ССГС..
Л ОО О $$83р ОООО О СЧ 4'ЯО404 ВоЗо . о о о О4 со о ! ! '=.М ООСОО О ОСОО О О С'44 О О О 4'СОСЧ ЙЙЙВ= О" О" О" О =О о"о"ооо" г" Оо Я! 3 Л сч о о о О" о ОООСО ЯРОВ СО"С=С= С С'0 ВЕС у СЧ=~ОЧ с~ о «ао о о СО яяВо р о" о" о ф о ФЯ3 о о" о" со" о Я 0С'ССЧ о~В~ С'4 4' О" О СО С 0 О О Оо $ Оо СО ос осчоо 44 4 СО Ч' ЯО4 ООО ОО О44 ОССЧС СЧ СО 4О ио \' оо счаосо со 04. Х $ о ! ! Со я 4О ! 202 вычисввнив совстввнных знвчвний и ВИКТОРОВ МАТРИЦ 1ГЛ. О С4Л 4 Ос О '44 О ООООО $ ФЧ' С'ООО С ЧОО ОС С ОООО ) сс О чс О О О ЙЯ Ч' О л сч С' О С'4 Сч ло о о о 1И Ч4О- ООО ОООО 44" СЧ ~ СО СЧ сс ~4СЮ Ос О Т Р Чс фОО 44 Т Жлл Я Ос л" чсоч о «о ЯД~ ООСЧ ОО ! фс Я СЧЙ 4 Осс ОООО Т Я Ос О О Ос О О О Я 4 ОВ О 8 сО Ъ| О ОО о ®а Ос'3 ООО О Ос сс О О О О О ф сч о В я с' И ! ! ~Й д л $= О ! С4 сч О СО ОООО 444 О 8 ОООО О 3 а 0ОО ОО й ! зЯЩ Й ОВ ФОО~Ф 1= Ос з л 203 метод длнилввского 8 4! Теперь поясним схему.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
