Дж. Деммель - Вычислительная линейная алгебра, страница 40

А,ты — — ВЯ; + о;1 = Сг19гВ1Щ + оЯЯ; = 9~Я;В; + ,.1) ~ 4~тАД Если матрица В; невырожденна, то верна и запись Авы = ВД, + о 1 = Влсг,В,В, ' + и;В;В,. ' = ВЯьВ; + а,1)В, ' = В,А;В, '. Мы утверждаем, что если сг; — точное собственное значение матрицы А„то 14В;итерация сойдется в один шаг. Действительно, матрица А, — о;1 вырожденна, раз о, является собственным значением, поэтому вырожденна матрица В; и, значит, какой-то из ее диагональных элементов равен нулю. Предположим, что В;(п, и) = О.

Тогда последняя строка матрицы ВЯ, будет нулевой, а последняя строка матрицы А;ч, = ВЯ;+ о,1 совпадет с оге~, где е„— последний столбец единичной матрицы порядка и. Иными словами, последняя строка в Аиы — нулевая с тем исключением, что в позиции (и, п) находится собственное значение о;. Это означает, что алгоритм сошелся: матрица Аг ы имеет верхний 174 Глава 4. Несимметричиаи проблема собственных значений блочно-треугольный вид, нижним диагональным 1 х 1-блоком которого является число сгс. Ведущая главная подматрица А' порядка п — 1 определяет новую, меньшую спектральную задачу, которая может быть решена ЯВ;итерацией без (А' а какого-либо изменения собственного значения сг;: Аьы — — ~ ос Если о, не является точным собственным значением, то элемент Ас гг(п, п) считается сошедшимся, если левый нижний блок Ас+г(п, 1: и — 1) достаточно мал.

Из нашего предыдущего анализа следует, что этот блок должен сходиться к нУлю со скоРостью, опРеделЯемой отношением ~Ль — ос~/пппб~э ~Лг — ос), где (Ль — сг,! = шш (Лд — ос). Поэтому можно ожидать быстрой сходимости, если сгс — очень хорошее приближение к собственному значению Ль. Имеется и другой способ обоснования ожидаемой быстрой сходимости: нужно распознать в ЯВ;итерации неявно выполняемую обратную итерацию. Если ос — точное собственное значение, то последний столбец о, матрицы цс является левым собственным вектором матрицы А, для собственного значения а;.

В самом деле, г?*Ас = с1'. ЯсВс + сгс1) = е г В, + асгХ'. = осг?',. Если число сг, близкб к некоторому собственному значению, то мы ожидаем, что о. будет близок к соответствующему собственному вектору, поскольку с1. параллелен вектору ((А, — сгс1)') ге„(ниже мы объясним, почему). Иными словами, г?. совпадает с вектором, который был бы получен в обратной итерации, примененной к матрице (Ас — асХ)' (и вектору е„). Поэтому мы рассчитываем, что он будет близок к некоторому левому собственному вектору. Приведем доказательство параллельности д.

и вектора ((А, — сгсХ)') 'е„. Из соотношения А, — ос1 = Я,В, следует, что (Ас — о,1)В, ~ = Я,. Обратим матрицы в обеих частях этого равенства, а затем возьмем сопряженные к ним. Правая часть Яс при этом не изменится. В левой же части будет теперь стоять матрица ((Ас — ас1)*) 'В;. Ее последний столбец равен вектору ((А, — о;1)') [О,..., О, В,(п, п)]г, лишь множителем отличающемуся от последнего столбца матрицы ((А, — сгсХ)') Откуда же взять хорошее приближение ас к собственному значению, если именно собственные значения мы и желаем вычислить? Мы вернемся к этому вопросу позднее.

Пока же отметим, что если процесс уже почти сошелся к вещественному собственному значению, то элемент Ас(п,п) должен быть близок к этому собственному значению и число ос = Ас(п, п) будет хорошим сдвигом. В действительности, такой выбор обеспечивает локальную квадратичную сходимостсч означающую, что на каждом шаге число верных разрядов приближения удваивается. Вот наше объяснение факта квадратичной сходимости. Пусть на шаге 1 имеем ()Ас(п,1: п — 1)!)/йА() = гг «1. Если заменить А;(п,1: п — 1) нулевым блоком, то А, станет верхней блочнотреугольной матрицей, а точное собственное значение Ль возмутится и станет равным элементу Ас(п,п).

Если Ль далеко от других собственных значений, то оно не будет плохо обусловленным, а потому возмущение в нем будет величиной порядка О(г1()А)0. Иначе говоря, (Ль — Ас(п, п)! = ОЩА(!). Если положить сгс = Ас(п, п), то можно ожидать, что на следующей итерации Аьы(п, 1: п — 1) уменьшится в (Ль — сгс(/шгп ~ь(Лг — ос) = 0(г1) раз. Как следствие, ()А,гг(п, 1: и — 1)() = 0(г1зйА(0, или )/Ас~ы(п,1: п — 1)йДА)) = 0(гуз).

4.4. Алгоритмы для несимметричной проблемы собственных значений 175 Такой характер убывания — от г1 к О(з1г), — и означает квадратичную сходи- мость. Пример 4.7. В таблице показаны ЯВ-итерации со сдвигом для той же 4 х 4- матрицы Ао, что и в примере 4.5. Сдвиги выбираются по правилу лз = Аз(4, 4). Поначалу поведение метода несколько хаотичное, но ближе к концу сходимость становится квадратичной, так что на каждом из последних трех шагов величина 9Ас(4,1: 3)9 — )Аз(4,3)( как бы возводится в квадрат.

Кроме того, на каждом из шагов с четвертого по девятый число верных разрядов в Аз(4,4) удваивается. К моменту, когда получена матрица Аго, не только последняя строка, но и остальная часть матрицы проделала значительный путь к своей предельной форме. Поэтому последующие собственные значения будут вычисляться очень быстро: для каждого будет достаточно одного или двух шагов. Приведем эту матрицу: 30.000 — 32.557 — 70.844 14.985 6.1548 10 в 6.0000 1.8143 †,55754 2 5531, 10-зз 2 0120 10-в 2 0000 †.25894 1 4692, 10-зв 7 4289 10 — зг 6 0040, 10-гв 1 0000 Аго= 4.4.5. Квк сделать Язв-итерацито практичной Вот вопросы, которые остается решить, чтобы сделать алгоритм более практичным: 1.

Метод слишком трудоемок. Стоимость ЯВ;разложения составляет 0(пз) флопов. Поэтому даже в благоприятном случае, когда на вычисление каждого собственного значения требуется в среднем только одна итерация, общая стоимость метода составит О(пз) флопов. Мы же хотели бы найти алгоритм, стоящий лишь 0(п ) операций. 2.

Как следует выбирать сз, для ускорения сходимости к комплексному собственному значению? Если взять комплексное вы то и вся последующая арифметика должна быть комплексной. Для вещественной матрицы А это означает увеличение общей стоимости процесса приблизительно в 4 раза. Мы же хотели бы найти алгоритм, который в случае вещественной матрицы Ао(4,:) = Аз(4,:) = Аг(4,:) = Аз(4,:) = А4(4,:) = Аз(4,;) = Ав(4,:) = Ат(4,:) = Ав(4,:) = Ад(4,;) = Азо(4,:) = +1.9 —.85 +.35 1 2 10 — г — 1.5.

10 — 30 10 — 1,4 ° 10 в — 1.4. 10 +28 10 — 34 10-гз +1.5 10 +56. — 4.9 +.86 —,17 — 1.8 10 — 22 10 — 63 10 з — 3.6 10 +4.2 10 — 3.0 10 +7.4 10 +40. +2.2 10 +.30 —.70 —.38 —.50 — 7,8 10 — 2.3 10 +1 4 10-в 4 8. 10 — 'з +6.0. 10 — 10.558 — 6.6068 0.74894 1.4672 1.4045 1.1403 1.0272 0.99941 0.9999996468853453 0.9999999999998767 1,000000000000001 176 Глава 4.

Несимметричная проблеме собственных значений А использует только вещественную арифметику и сходится к вещественной форме Шура. 3. Как распознать факт сходимости метода? Ответы на эти вопросы будут подробно обсуждаться позже. Вкратце же они состоят в следующем; 1.

Матрица вначале будет приведена к верхней форме Хессенберга, т.е. элементы в А, находящиеся ниже первой поддиагонвли, станут нулями (а,, = О, если з > у+1) (см. разд. 4.4.6). Далее 14В;итерация будет применяться неявно, что означает: на каждом шаге матрица Я не будет вычисляться в явном виде, так же как явно не будет производиться умножение на с„(см. равд. 4.4.8).

Это снизит стоимость одного шага ь4В;итерации с 0(пз) до 0(пз), а общую стоимость — с 0(и«) до 0(пз), что и было нашей целью. Если А — симметричная матрица, то она будет приведена к трехдиагональной форме, в результате чего стоимость одного шага 14В;итерации снизится еще больше, а именно до 0(п) операций. Этот случай обсуждается в равд. 4.4.7 н гл. 5. 2. Поскольку комплексные собственные значения вещественных матрийчзстречаются сопряженными парами, сдвиги на а; и а; можно производить совместно. Оказывается, что это позволяет весь процесс вести в вещественной арифметике (см. равд. 4.4.8). Для симметричной матрицы А все собственные значения вещественны н подобной проблемы не возникает.