Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Бабенка К.И. -> "Основы численного анализа" -> 206

Основы численного анализа - Бабенка К.И.

Бабенка К.И. Основы численного анализа — НИЦ «Регулярная и хаотическая динамика», 2002. — 848 c.
ISBN 5-93972-162-1
Скачать (прямая ссылка): osnovichislenogo2002.djv
Предыдущая << 1 .. 200 201 202 203 204 205 < 206 > 207 208 209 210 211 212 .. 324 >> Следующая

В случаях кратных собственных значений картина будет сложнее. Мы описали одну из тактик проведения якобиевых итераций. Применяются и другие тактики (см. [110, 114]).
Собственные векторы матрицы А находятся после того, как мы получили матрицу
Ат = ЦО'а1А1[[Ог,]1
I I
с малыми элементами вне диагонали. Определим компоненты вектора ? = (?ь ..., &_ь 1, ..., с помощью формул
(то)
С, - ак1 и I А
^к ~ (то) _ (то) ' Л 7= 1-акк а11
Тогда вектор
будет приближенным собственным вектором матрицы А, причем, как следует из формул (12), (13), его компоненты определены с точностью е2.
3. Ы1 и <ЗД алгоритмы. Несмотря на численную устойчивость метода Якоби, в практической деятельности он вытеснен другими итерационными методами, обладающими большей скоростью сходимости и пригодными для произвольных комплексных матриц. Опишем один из таких методов — так называемый ЬЯ-алгоритм. В § 2 мы установили, что при выполнении определенных условий матрица А может быть представлена в виде
А = ЬН7 (15)
где Ь — нижняя треугольная матрица с диагональными элементами, равными единице, Я — верхняя треугольная матрица. Это разложение единственно.
В итерационном процессе, на основании которого строится ЬЯ-ал-горитм, в качестве группы матриц преобразований берутся нижние треугольные матрицы с диагональными элементами, равными единице. Из (15) получаем
Ь~гАЬ = ЯЬ = Аг
544 Глава 8. Теория итераций и методы решения некоторых задач
и далее полагаем А\ = ЬгКг, Ь^А\Ь\ = И\Т\ = А2, а в общем случае
Ат — ВтВтч Вш АтВт ВщВт — Ат+1- (1^)
Если указанное построение возможно, то мы получаем последовательность подобных матриц, которые будут сходиться к верхней треугольной матрице в случае различных собственных значений. В самом деле, пусть собственные значения матрицы А удовлетворяют неравенствам
|А1| > ... > |А„| >0. (17)
Заметим, что из соотношений (16) следует, что Ат = Ьт1_1... Ь^гАдЬ° ... ... Ьт—1, где Ьо = Ь, Ао = А; поэтому
Во ¦ ¦ ¦ Ьт-\Ат = АоЬо ... Ьт-1-
с другой стороны, Ь0 ... ЬтЯт ... Во = Ь0 ... Вт_\АтВт-\ • • • -Ко; откуда в силу предыдущего соотношения
Во ¦ . . ЬтВт . . . До = АоЬо . . . Т>т-\Вт-\ ¦ ¦ • Во.
Следовательно, полагая ?}т = Ьо ... Ьт, Бт = Нт ... Но, получим
(<дтЗт = А0 ~*~ . (18)
Преобразуем Ао1. Пусть А0ХКХ~г, где Л = diag (Аг)™_г Предположим,
что матрицы X и Х~1 допускают представление X = ?91, Х~1 = -С].?!!, где ?, ?1 и 91, 911 принадлежат тем же группам треугольных матриц, что и!и]? соответственно. Заметим, что
А™ = ХАтХ-г = ?9ит?15К1 = ?<К(Лт?1Л-т)Лт1К1.
Если ?1 = (/^)™^=1, 1ц = 0 (г < ]), 1ц = 1 (г = 1,2,..., п), то легко видеть, что Лт?1Л~т = (2^(Аг/А^)т)™ а поскольку при г > ] по предположению (Аг/А^)"1 = 0(ат) (0 < д < 1), то
Лт?1Л-т =1 + §т^
где / — единичная матрица, а матрица ёт имеет элементы порядка 0(ат). Далее, легко видеть, что
41 + ёт) = (1 + Вт)Ж = ?т<Кт<К,
где ?т — нижняя треугольная матрица, 91т — верхняя треугольная матрица, причем ?т = I + 0{ат). Поэтому А™ = ??т(<Кт91Лт911), где в скобках стоит верхняя треугольная матрица. В силу единственности используемого разложения на основании (18) имеем С^т-1 = ??т- Следовательно, Цт = ? + 0{ат+1), и поэтому
[? + 0(дт+1)] Ат = А0 [? + 0{ат+1)}.
§ 7. Методы решения алгебраической проблемы собственных значений 545
Отсюда следует, что
Ат=Ж№-1 + 0(дт),
причем матрица верхняя треугольная. Таким образом, доказана
сходимость ЬИ-алгоритма в случае собственных значений, удовлетворяющих неравенствам (17).
Но эти неравенства заведомо не выполняются для вещественных матриц, имеющих комплексные собственные значения. Можно доказать, что если |А&| > |Ад,+1|, за исключением комплексно-сопряженной пары А;, А;+1 (Аг+1 = А;), и если разложение на произведение треугольных матриц не встречает препятствий в процессе итераций, то все элемен-
(т) л
ты а- матрицы Ат стремятся к пределу, за исключением элементов
(т) (т)
Ні а1,1+-
(т) (т)
Заметим, что собственные значения этой матрицы стремятся к А;, Аг+д; а[™') —> 0, если г > ], (г, ]) ф (1 + 1, I); а>™^ —> Аг, если г ф I, I + 1, и е^™' стремятся к пределу, если г < ], (г, ]) ф (1,1 + 1).
Хотя случай комплексно-сопряженных значений включается в сферу действия ?Д-алгоритма, тем не менее против него можно выдвинуть много существенных возражений. Прежде всего, разложение матрицы в произведение треугольных не всегда возможно, как это мы видели при изучении алгоритма Гаусса, а требуются перестановки строк. Но даже если такое разложение возможно, оно может быть численно неустойчивым, хотя сама проблема собственных значений будет хорошо обусловлена. Далее, ХД-алгоритм на каждом шаге итерационного процесса требует х 2п3/3 умножений, из которых половина приходится на процесс разложения матрицы в произведение треугольных, и к тому же итерации могут медленно сходиться, когда собственные значения плохо отделены друг от друга. Оказывается, что все эти недостатки ХД-алгоритма можно устранить.
Прежде всего покажем, как можно уменьшить число операций на шаге итерационного процесса. Для этого целесообразно преобразовать исходную матрицу А к такой форме, которая инвариантна относительно преобразований, используемых на итерационном шаге ХД-алгоритма, и имеет максимальное число нулевых элементов. В частности, такой формой матрицы будет обобщенная трехдиагональная форма, когда матрица А = (яу)™^=1 имеет нулевые элементы во всех позициях (г, ]), для которых г > 2 + 1- В частности, если А — еще и симметрическая матрица, то она будет трехдиагональной. Иногда такую форму матрицы называют верхней формой Хессенберга. Выше мы установили, что произвольную симметрическую матрицу с помощью (п — 2)(п— 1)/2 элементарных преобразований подобия можно привести к трехдиагональному виду. Но если те же выкладки применить к произвольной матрице, то с помощью тех же (п-2)(п- 1)/2 элементарных преобразований подобия можно привести матрицу к верхней форме Хессенберга. Для этого потребуется
Предыдущая << 1 .. 200 201 202 203 204 205 < 206 > 207 208 209 210 211 212 .. 324 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100