Том 2 (1160084), страница 31
Текст из файла (страница 31)
188 вычисление совственных значений и вектоеов матгиц (гл. 8 В 3. Метод Ланцоша 1. Отыскание собственных значений. Решение систем (25) или (42) предыдущего параграфа для определения коэффициентов характеристического илн минимального многочлена можно осуществлять методами ортогонализацин, изложенными в Э 4 главы 6. Процесс ортогонализации целесообразно проводить после каждого умножения на матрицу А, В настоящем параграфе мы и рассмотрим возникающие при этом алгорифмы. Выбираем произвольный начальный вектор со чь О и находим Асо. Подберем теперь коэффициент аго так. чтобы вектор с, = Асо — кгосо (1) был ортогонален к вектору со.
Это всегда возможно и условие ортогональности дает (Асо* со) (2) ею= (оо оо) Может оказаться, что с, = О, В этом случае векторы со и Асо линейно зависимы и Р,(Л)=Л вЂ” а, будет делителем минимального многочлена матрицы А. Тогда дальнейшие действия с вектором с„ прекращаются.
Если же с, чь О, то образуем вектор Ас, и подбираем коэффициенты ам и а,о так, чтобы вектор сз = Ас, — аыс, — аюсо (3) был ортогонален к векторам со и с,. Это также всегда возможно. При этом (Ась оо) мог (Ась ог) . (4) (о,, с,) Если окажется, что с, = О, то А (Асо "юсо) ам (Асо — аюсо) сао со = О (5) даст линейную зависимость между векторами со„и Асо и А'со, а многочлен Р, (Л) = (Л вЂ” аа,) (Л вЂ” ам) — аоо = (Л вЂ” ссзг) Р, (Л) — аю (6) будет делителем минимального многочлена матрицы А. Если же со~ О, то продолжаем процесс ортогонализацин, Пусть нами уже найдены векторы со, с,, ..., с,, удовлетво- ряющие условиям: слог= Ась — па+в ьсь — пь+ь ь гса г —... — во+косо (й = 1, 2..., т — 1), (7) (сн су)=О при (чьу, са +О (1, /, 1=О, 1, 2, ..., т — 1).
(8) 189 й з) МЕТОД ЛАНЦОША Тогда подбираем коэффициенты аяь т-н ат. т-г ° ° ° а ь о так чтобы вектор с =Ас, — а„..т вот в — свт, гс г — ... — атосо (9) был ортогонален к каждому из векторов со. с,, ..., ст, Это возможно. Коэффициенты а г должны быть определены по формулам (Ас„, в, св) аол (сь св) (10) Параллельно с построением системы взаимно ортогональных векторов со, с,, ..., с, ... строим последовательность многочленов Так как в нашем пространстве имеется не более и взаимно ортогональных векторов. то на каком-то шаге будем иметь от=О. При 9ТОМ Ас,„в — ат, ов-вот-в — свт, в, гсо,-г — ° ° .
— ат, осе — — 0 (12) даст линейную зависимость векторов с, Асо, ..., А со и, следовательно, многочлен во-г РтО) =() — «т, во-В)Рт ВО) — ..'!~ат,гРАО) А-о будет делителем минимального многочлена матрицы А. При ги = и Р (А) будет являться характеристическим многочленом матрицы А. Если ги С и, то выбираем новый начальный вектор с', ортогональный к векторам со. с,, ..., с,, и повторяем с ним тот же процесс.
Если этого окажется недостаточно, т. е. общее количество ортогональных векторов все еще будет меньше и, то проводим наши рассуждения с новым вектором с", ортогональным ко всем предыдущим, и т. д. Для симметрической матрицы А равенства (7) упрощаются. Действительно, в этом случае (Асм с,) (св, Ас.) (с„с.+ +а + о + ... +а+,с) аг (еь сг) (сь св) (св, сг) (1=0, 1, 2, ..., и).
(14) и если 1(и — 1, то аг+, в=О. Таким образом, если матрица А симметрическая. то вместо (7) будем иметь: сге.= Ас„— аь+ьгсг — агев. А всь,. (1О) Ро й = 1; Р й = (Х вЂ” а, ) Х Х Рт-в()) — аво,т-гРт-г()) — ° ° — атоРо(~). (11) 190 вычисление совственных зн«чений и вектооов млтгиц [гл.
8 Аналогичное упрощение можно получить и для несимметрической матрицы, заменив процесс ортогонализации процессом биортогонализации, подобно тому как это сделано в э 4 главы 6. Будем исходить из двух начальных векторов со и Ьо. Найдем по ним векторы Асо и А'Ьо и образуем линейные комбинации с| = Асо — аюсо: Ьг = А'Ьо — 1юЬо. (16) Коэффициенты а,о и рю подберем так, чтобы оказалось (с,, Ь„) = = (Ьг, со) = О. Это возможно, если начальные векторы со и Ьо не были ортогональны, так как л (Аоо.
Ьо) (со А'Ьо) аю = Рю = (сь Ьо) (оо, Ьо) (17) В дальнейшем будем предполагать, что (со, Ьо) ~0. Тогда ло найденным с, и Ьг строим векторы Ас, и А'Ьг и образуем линейные комбинации с, = Ас, — а„с, — аюс,, Ьз — — А'Ь, — рз|Ь» — [ЗюЬо (18) так, чтобы оказалось (сз, Ь,) =(с,, Ьо) =(Ь,, с,) =(Ьа, со) =О.
(19) (20) (с|, Ь,) Ь) (с,Ь) (,Ь) и наше построение возможно, если (с,, ЬД чь О, (со, Ьо) чь О. Будем предполагать, что эти условия выполнены, и продолжим построение дальше. Пусть у нас уже построены векторы с,с,,...,с», Ьо, Ь,, ..., Ь«, (2! ) (22) причем эти две системы биортогональны, т. е. (Ьг, сЬ)=0 пРи | +/ (|, 7'=О, 1, ..., Й). (23) Тогда строим векторы с»ы= Ас« — а«+|, «с» — а»+|, «|с«| — ...
— а«+|,осе, — (24) Ь«| — — А'Ь» — ~»~.ь «Ь» — ~«+ь» |Ь«-| — ... — ~»«ьоЬо 1 При этом будем иметь: о (Ас| ае| = гм=- ( |. (Ас, "|о= гю— (с, Ьг) (с|. А'Ь|) Ь) (сн ЬО ' Ьо) (со. А'Ь|) 6 З) 191 мвтод ланцошл так, чтобы (сь,о Ьг)=(ЬЬ„,, сг)=0 (1=0, 1, 2, . „й) (2зб Условия (25) дают (Ас,Ь А'Ь, с ( 0 (Асы Ьс) (А'Ьы сО (сь Ьг) (сь Ь;) При этом, если 1(й — 1, то (Асм Ьг) (сь, А Ьг) (сы Ь;+з) 0 аа+ь = йа+ь ~— (сэ Ьг) (сэ Ь;) (сл Ь;) Таким образом соотношения (24) примут вид (27) с., = Ась — аа+н аса — аз+ ь а-гса о (28) Ь„,,= А Ьа — аа+ь ьЬЬ вЂ” аь+н а-~Ьь г ) (29) Ьэ= се=(0, 1, О, 0). Асо=(2 3 — 2 0)' А~Ьо=(3 3 0 0) (ЗО) Тогда (31) а, =-( — Ф= =з.
(Ас, Ьо) (со |'о) (32) Следовательно, с1 — — (2, О, — 2, 0); Ь, = (3, О, О, 0). (33) Далее, Ас =(12, 6, — 6, 6), А'Ь, = (15, 6, — 3, — 3). (34) Отсюда ааэ= ' —— 6; аз,= ' =6 (Асэ Ьэ) . (Ас| Ь~) (Ьо сэ) (сь ЬО (35) са = (О, О, 6, 6); ба=( — 3, О, — 3, — 3). (36) Наши построения будут возможны до тех пор, пока (с„, Ьа) + О.
Это условие может нарушаться в следующих трех случаях: а) са=О и ЬЬ=О; б) либо са — — О, либо Ьь=О; в) са ь О, Ь» ~ О, но са ) Ь„. Все эти три случая могут встречаться фактически. Продемонстрируем это на примере матрицы (44) 9 2. а) Возьмем сначала 192 вычисланив совстввнных знлчвний и вектооов млтгиц !гл. 8 Продолжая процесс, найдем: А'Ь,=( — 27, О, — 9, — 9), (Ась Ьо) иоо = — ' — — 3, (оь !1о) Ь,=(О, О, О, О). Ас,=( — 12, О, 30, 18) (Асм Ьт) "ог = (сь Ьг) (37) со = (О, О, О, 0), б) Возьмем теперь Ьо = с = (1, О, О, О).
(38) При этом Асо=(5 3 1 3) им= (39) в) Наконец, если взять (40) .го Асо=(5 3 1 ° 3) А'Ьо=(4+)Г 3 1+~/3 — 1 — 1)~ „=-4+УгЗ, с, =(! — р 3, 3, 1, 3), Ь, =(О 3, — 1 — 1) (41) (с,, Ь,)=0. (42) Если минимальный многочлен матрицы А имеет степень и, то векторы со. Асо, ....
А~со и Ьо, А'Ьо, ..., А' Ьо линейно зависимы. В силу этого наш процесс обязательно закончится не позже чем через й ( ш шагов. При этом в случаях а) и б) мы найдем линейнУю зависимость междУ вектоРами со, Асш ..., Аьсо или ы Ьо, А'Ь, ..., А' Ьо, а следовательно, и минимальный многочлен матрицы А или его делитель. Случай в) может встретиться лишь как исключение при неудачном выборе начальных векторов со и Ьо и его всегда можно избежать, выбрав другие начальные векторы. с,=(0,3, 1, 3), Ас, = (2, 9, 1, 9), (Асн Ьо) ~Ъ = (с, Ь,) са=(0, — 3, — 3 А Ьо = (5, 2, — 1, — 1), (Асо, Ьо) (со Ьо) Ь,=(0, 2, — 1, — 1), АЬ,=(2,8, — 4, — 4), 2, азг= ' =4, (Ась Ь!) (сь Ь,) , — 3), Ь = (О, О, О, 0). !93 мвтод ллнцошл Предполагая, что мы получили с„ = О, или Ьа —— О, последовательно находим минимальный многочлен А или его делитель по формулам: РО (Л) ! Р, (Л) = (Л вЂ” сг, ) Р„(Л), Ра (Л) = (Л вЂ” ам) Р, (Л) — птеР„(Л), (43) Р,, г(Л) =(Л вЂ” аь-ь ь-а)Ра — е(Л) — аь-ь ь-зРь-э(Л) Рь(Л) =(Л вЂ” ан, а г)Рь г(Л) — иь, ю аРь (Л).
В частности, в рассмотренных нами примерах будем иметь: в слу- чае (30) Ро(Л) = ! Р,(Л) =Л вЂ” 3, Р, (Л) = (Л вЂ” 6) (Л вЂ” 3) — 6 = Л' — 9Л + ! 2, Ра (Л) = (Л вЂ” 3) (Л' — 9Л -+ 12) -+ 6 (Л вЂ” 3) = !' — 12Ла+- 45Л вЂ” 54. в случае (38) Ро(Л) = ! Р,(Л) =Л вЂ” 5, Р, (Л) = (Л вЂ” 4) (Л вЂ” 5) — 2 = Л' — 9Л+- 18. Такой способ получения минимального многочлена или его делителя будем называть методом Ланяоша. Пусть процесс, осуществляемый по методу Ланцоша, продол- жается до (г = и — 1.
Рассмотрим матрицы (45) см саа ... с„ Ьм ан ° Ьн — ь г С= ссе см .. сч — ьх В Ьм Ьм .. Ьн-ьз (46) се„сгв ... с„ ь ь „ ... ь„ (ЬО Ас1) = а;+ь; (сь Ь;) = а;.г,,;ь„ (Ьо Асг,) =(Ь;,, Ас1) =(со Ь;)=он (Ьг, Асу) =О при ~! — /~) 1, ) (48) где сы и Ь — соответственно компоненты векторов с; и Ьо В силу биортогональности будем иметь: а о ... о ВС О О...а„ где йг=(со Ь;), Следовательно, С '=с) 'В' и В ' =с) 'С'. Далее, так как 194 вычислении совстввнных анлчвний и ввктогов матгиц (гл.
3 то агава Ьг 0 ... 0 0 В~ аатзг Ьз ... 0 0 В'АС = О аа амва ... 0 0 (49) О О О...Ь вЂ” а.-а- Поэтому га «та 0 ... 00 ам ааг ... 0 0 С 'АС=О В'АС 1 а ...00 (50) 0 0 . ° 1 аа,а-г Таким образом, в рассматриваемом случае наш процесс эквивалентен приведению матрицы А к тридиагональной форме. Если производить процесс Ланцоша без указанных упрощений.
то он будет эквивалентен приведению матрицы А к верхней треугольной форме. В симметрическом случае всегда получим тридиагональную форму. Случай к ч, и — 1 потребует выбора новых начальных векторов, как это указывалось в начале параграфа, При этом матрица приводится к Аг: 0 . :Ай! (5! ) ( О !Аа! где клетки Аг имеют вид, указанный выше. Вернемся еще раз к вопросу о применении метода Ланцоша в случае симметрической матрицы А.
Этот случай особенно выгоден для этого метода. Прежде всего отметим, что для симметрической матрицы (Ас, с ) (г „Ас„,) (аь, с„) алана 1= ' = ' = ' )О, (52) (с,, с,,) (сь, с„) (а„г с,,) причем знак равенства будет достигаться лишь при сь = О. Далее, из условия Ра,(Л)=(Л вЂ” еачь«)Рь(Л) — качка ьРк-1(Л) (53) следует, что никакие два многочлена Ра (Л) и Р„,, (Л) (й=о, 1, ..., ш — 1) не могут обрашаться в нуль при одном и том же значении Л = Л'. Действительно, если бы Р„,(Л') = Ра (Л') = О, то из (52) и (53) следовало бы Ра,(Л') = О. Повторяя эти рассуждения для многочленов Рь(Л) и Ра,(Л), мы пришли бы к выводу, что Рь а(Л')=О.
Продолжая дальше, мы пришли бы в конце концов к заключению, что Ра(),') =О. Но это невозможно, так как Ре(Л)=1. метод ллнцошА 195 Изучим теперь взаимное расположение корней Р„(Л). Много- член Р,(Л) имеет единственный корень Л, =а)2. При этом Р,)Л)) = (1) / оп = — аюРз(О. Следовательно, квадратный многочлен Р,(Л), поло>кительный для достаточно больших по абсолютной величине значений Л, будет обращаться в нуль в точках Л> и Лз, Л, (Л, (Ла (2) (2) (2) (1) )2) для Р (Л) будем иметь: Р (Л))) = — 222>Р)(Л~> )) ) О, Р (ЛЗ22)) = М)1 — — ссз)Р)(Л2 ) < О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
