1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 72
Текст из файла (страница 72)
Но у матрицы A + I3.18. Численные методы для несимметричной проблемысобственных значенийэти собственные значения перейдут в −1 и 3, второе собственное числостанет наибольшим по модулю, и теперь уже единственным. Соответственно, степенной метод сделается применимым к новой матрице.Пример 3.18.5 Для матрицы (3.15)1 2,−3 4как было отмечено в Примере 3.18.1, простейший степенной метод расходится из-за существования двух наибольших по абсолютной величине собственных значений.Но если сдвинуть эту матрицу на 2i, то её спектр (см. Рис. 3.24)поднимется «вверх», абсолютные величины собственных значений перестанут совпадать, и степенной метод окажется применимым.Степенные итерации для «сдвинутой» матрицы1 + 2i2(3.157)−34 + 2iдовольно быстро сходятсяк наибольшему по модулю собственному зна√чению 25 + (2 + 12 15) i ≈ 2.5 + 3.9364917 i .
Детальная картина сходимости при вычислениях с двойной точностью и начальным векторомx(0) = (1, 1)⊤ показана в следующей табличке:Номеритерации1351020Приближениек собственному значению2.0 + 2.0 i2.0413223 + 4.3140496 i2.7022202 + 3.9372711 i2.5004558 + 3.945456 i2.4999928 + 3.9364755 iВ данном случае для матрицы (3.157) имеем |λ2 /λ1 | ≈ 0.536.Ещё большее ускорение сходимости степенного метода можно получить при сдвиге исходной матрицы на (−2 + 2i), когда отношениемодулей собственных значений становится равным всего 0.127.Поскольку спектр симметричной (эрмитовой) матрицы лежит навещественной оси, то к таким матрицам имеет смысл применять ве-4423.
Численные методы линейной алгебрыщественные сдвиги. В частности, при этом для симметричных вещественных матриц алгоритмы будут реализовываться в более простойвещественной арифметике.Im0ReРис. 3.25. С помощью подходящих сдвигов любую крайнююточку спектра можно сделать наибольшей по модулю.С помощью сдвигов матрицы можно любое её собственное значение,которое является крайней точкой выпуклой оболочки спектра, сделатьнаибольшим по модулю, обеспечив, таким образом, сходимость к немуитераций степенного метода (см. Рис. 3.25). Но как добиться сходимости к другим собственным значениям, которые лежат «внутри» спектра, а не «с краю»? Здесь на помощь приходят обратные степенныеитерации.Обратные степенные итерации сходятся к ближайшей к нулю точке спектра матрицы, и такой точкой с помощью подходящего сдвигаможет быть сделано любое собственное число.
В этом — важное преимущество сдвигов для обратных степенных итераций.Другое важное следствие сдвигов — изменение отношения |λ2 /λ1 |,величина которого влияет на скорость сходимости степенного метода.Обычно с помощью подходящего выбора величины сдвига ϑ можнодобиться того, чтобыλ + ϑ 2λ1 + ϑбыло меньшим, чем |λ2 /λ1 |, ускорив тем самым степенные итерации.Совершенно аналогичный эффект оказывает удачный выбор сдвига на3.18. Численные методы для несимметричной проблемысобственных значенийотношение |λn /λn−1 |, которое определяет скорость сходимости обратных степенных итераций.3.18гБазовый QR-алгоритмQR-алгоритм, изложению которого посвящён этот параграф, является одним из наиболее эффективных численных методов для решенияполной проблемы собственных значений. Он был изобретён независимоВ.Н.
Кублановской (1960 год) и Дж. Фрэнсисом (1961 год). Публикация В.Н. Кублановской появилась раньше32 , а Дж. Фрэнсис более полно развил практичную версию QR-алгоритма.QR-алгоритм является наиболее успешным представителем большого семейства родственных методов решения полной проблемы собственных значений, основанных на разложении исходной матрицы напростейшие. QR-алгоритму предшествовал LR-алгоритм Рутисхаузера.
На практике применяются также ортогональный степенной метод,предложенный В.В. Воеводиным, и различные другие близкие вычислительные процессы.Вспомним теорему о QR-разложении (Теорема 3.7.1, стр. 314): всякая квадратная матрица представима в виде произведения ортогональной и правой (верхней) треугольной матриц. Ранее в нашем курсе мыуже обсуждали конструктивные способы выполнения этого разложения — с помощью матриц отражения Хаусхолдера, а также с помощью матриц вращений. Следовательно, далее можно считать, что QRразложение выполнимо и основывать на этом факте свои построения.Вычислительная схема базового QR-алгоритма для решения проблемы собственных значений представлена в Табл.
3.14: мы разлагаемматрицу A(k) , полученную на k-м шаге алгоритма, k = 0, 1, 2, . . . , наортогональный Q(k) и правый треугольный R(k) сомножители и далее,поменяв их местами, умножаем друг на друга, образуя следующее приближение A(k+1) .Прежде всего отметим, что посколькуA(k+1) = R(k) Q(k) = Q(k)⊤⊤Q(k) R(k) Q(k) = Q(k) A(k) Q(k) ,32 Упоминая о вкладе В.Н. Кублановской в изобретение QR-алгоритма, обычноссылаются на её статью 1961 года в «Журнале вычислительной математики и математической физики» [75]. Но первое сообщение о QR-алгоритме было опубликованоею раньше — в Дополнении к изданию 1960 года книги [44].4443. Численные методы линейной алгебрыТаблица 3.14.
QR-алгоритм для нахождениясобственных значений матрицы Ak ← 0;A(0) ← A;DO WHILE ( метод не сошёлся )вычислить QR-разложение A(k) = Q(k) R(k) ;A(k+1) ← R(k) Q(k) ;k ← k + 1;END DOто все матрицы A(k) , k = 0, 1, 2, . . . , ортогонально подобны друг другу иисходной матрице A. Как следствие, собственные значения всех матрицA(k) совпадают с собственными значениями A. Результат о сходимости QR-алгоритма неформальным образом может быть резюмирован вследующем виде: если A — неособенная вещественная матрица, то последовательность порождаемых QR-алгоритмом матриц A(k) сходится«по форме» к верхней блочно-треугольной матрице.Это означает, что предельная матрица, к которой сходится QRалгоритм, является верхней треугольной либо верхней блочно-треугольной, причём размеры диагональных блоков зависят, во-первых, оттипа собственных значений матрицы (кратности и принадлежности вещественной оси R), и, во-вторых, от того, в вещественной или комплексной арифметике выполняется QR-алгоритм.Если алгоритм выполняется в вещественной (комплексной) арифметике и все собственные значения матрицы вещественны (комплексны)и различны по модулю, то предельная матрица — верхняя треугольная.
Если алгоритм выполняется в вещественной (комплексной) арифметике и некоторое собственное значение матрицы вещественно (комплексно) и имеет кратность p, то в предельной матрице ему соответствует диагональный блок размера p × p. Если алгоритм выполняетсядля вещественной матрицы в вещественной арифметике, то простымкомплексно-сопряжённым собственным значениям (они имеют равные3.18. Численные методы для несимметричной проблемысобственных значениймодули) отвечают диагональные 2×2-блоки в предельной матрице.
Наконец, если некоторое комплексное собственное значение вещественнойматрицы имеет кратность p, так что ему соответствует ещё такое жекомплексно-сопряжённое собственое значение кратности p, то при выполнении QR-алгоритма в вещественной арифметике предельная матрица получит диагональный блок размера 2p × 2p.Пример 3.18.6 Проиллюстрируем работу QR-алгоритма на примерематрицы1 −235 −6 ,(3.158) 4−789имеющей собственные значения2.75841486.1207926 ± 8.0478897 iЧитатель может провести на компьютере этот увлекательный эксперимент самостоятельно, воспользовавшись системами Scilab, Matlabили им подобными: все они имеют встроенную процедуру для QRразложения матриц.33Пример 3.18.7 Для ортогональной матрицы0 11 0,(3.159)QR-разложением является произведение её самой на единичную матрицу.
Поэтому в результате одного шага QR-алгоритма мы снова получим исходную матрицу, которая, следовательно, и будет пределомитераций. В то же время, матрица (3.159) имеет собственные значения, равные ±1, так что в данном случае QR-алгоритм не работает.33 ВScilab’е, Matlab’е и Octave она так и называется — qr.4463.18д3. Численные методы линейной алгебрыМодификации QR-алгоритмаПредставленная в Табл. 3.14 версия QR-алгоритма на практике обычно снабжается рядом модификаций, которые существенно повышают еёэффективность. Главными из этих модификаций являются1) сдвиги матрицы, рассмотренные нами в §3.18в, и2) предварительное приведение матрицы к специальнойверхней почти треугольной форме.Можно показать (см.
теорию в книгах [13, 41]), что, аналогично степенному методу, сдвиги также помогают ускорению QR-алгоритма. Нов QR-алгоритме их традиционно организуют способом, представленным в Табл. 3.15.Таблица 3.15. QR-алгоритм со сдвигами для нахождениясобственных значений матрицы Ak ← 0;A(0) ← A;DO WHILE ( метод не сошёлся )выбрать сдвиг ϑk , приближённо равныйсобственному значению A ;вычислить QR-разложение сдвинутойматрицы A(k) − ϑk I = Q(k) R(k) ;A(k+1) ← R(k) Q(k) + ϑk I;k ← k + 1;END DOОсобенность организации сдвигов в этом псевдокоде — присутствиеобратных сдвигов (в строке 6 алгоритма) сразу же вслед за прямыми (в5-й строке).
Из-за этого в получающемся алгоритме последовательновычисляемые матрицы A(k) и A(k+1) ортогонально подобны, совершен-3.18. Численные методы для несимметричной проблемысобственных значенийно так же, как и в исходной версии QR-алгоритма:⊤⊤A(k+1) = R(k) Q(k) + ϑk I = Q(k) Q(k) R(k) Q(k) + ϑk Q(k) Q(k)⊤ (k) (k)⊤= Q(k)Q R + ϑk I Q(k) = Q(k) A(k) Q(k) .Представленная организация сдвигов позволяет сделать их в одно и тоже время локальными и динамическими по характеру, т. е.
изменяющимися от шага к шагу. По этой причине их можно корректировать наоснове результатов промежуточных вычислений.Пример 3.18.8 Проиллюстрируем работу QR-алгоритма со сдвигамина знакомой нам матрице (3.158)1 −235 −6 4−789из предыдущего примераПредложение 3.18.1 Матрица, имеющая хессенбергову форму, сохраняет эту форму при выполнении с ней QR-алгоритма.Доказательство. При QR-разложении хессенберговой матрицы в качестве ортогонального сомножителя Q для матрицы (A(k) − ϑI) получается также хессенбергова матрица, так как j-ый столбец в Q естьлинейная комбинация первых j столбцов матрицы (A(k) − ϑI). В своюочередь, матрица RQ — произведение после перестановки сомножителей — также получается хессенберговой.
Добавление диагональногослагаемого ϑI не изменяет верхней почти треугольной формы матрицы.Смысл предварительного приведения к хессенберговой форме заключается в следующем. Хотя это приведение матрицы требует O(n3 )операций, дальнейшее выполнение одной итерации QR-алгоритма с хессенберговой формой будет теперь стоить всего O(n2 ) операций, так чтообщая трудоёмкость QR-алгоритма составит O(n3 ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
