Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 86
Текст из файла (страница 86)
Тем самым доказано, что в условиях сходимости треугольного степенного метода диагональные элементы матриц Йа сходятся к собственным значениям матрицы А. Ллгорифм ь)с по своей вычислительной схеме несколько проще, чем степенной треугольный метод. Однако он не является само- исправляющимся алгорифмом. Кроме того, он менее приспособлен к определению собственных векторов матрицы, ибо для решения этой задачи требуется восстановить матрицу Сл, что сводится к перемножению большого числа треугольных матриц и может сопровождаться нарастанием ошибок округления. Следует отметить связь алгорифма ЕЯ с алгорифмом )',)О. Именно, соотношения 532 итеглционные методы для вешания полной пвозлвмы [гл, чш так что алгорифм Яь) можно рассматривать как Ей-алгорифм, при- мененный к некоторой начальной матрице рн) О ) О а()) 1 1 1= 1(й, = а(~) ! ч-1 О О Р -з (!) е(д 1 1 Сокращение числа операций в этом случае происходит за счет того, что все последующие матрицы Лай» будут оставаться ленточными того же строения.
где а,, = р(0) + е('), р. = р((),а(г). Напомним, что в алгорифме Я0 в качестве исходных, значений р(()) и а(') берутся коэффициенты двучленных соотношений биортогонального алгорифма. Тем самым числа а( и р), определяющие матрицу l, являются коэффициентами трехчленных соотношений биортогонального алгорифма. Как мы видели, матрица У получается из матрицы А преобразованием подобия, вызываемым переходом к базису, состоящему из векторов рз, ..., р„,. Поэтому собственные значения матрицы У, а следовательно, и матрицы ( совпадают с собственными значениями матрицы А.
Применение алгорифма '!т к матрицам общего вида требует очень большого числа вычислительных операций. Число операций знзчительно сокращается, если исходная матрица является ленточной, т. е. такой, для элементов аи которой выполняются равенства а(,= О .~ при (( — у'!) т, где т некоторое число, значительно меньшее. чем порядок и матрицы.
Иными словами, ленточная матрица имеет внд 533 ЛР-Алгорнем и 80) Е)с-алгорифм допускает модификацию со сдвигами, равносильную соответствующей модификации степенного треугольного метода при Сэ= Е. В этой модификации процесс происходит по следующему предписанию: (А — Е,Е) = Е,)г, й~Е~ — (1~ — (д Е = ЕФк (6) (эк-1Ед-~ — (Га (а-г) Е= Екав где Ек и Йд матрицы прежнего строения. Обозначим ЕгЕк .
Ед — Сд и убедимся в том, что (А — (аЕ) С», = Сайд. Для (к= 1 это верно при С,=Е. Пусть утверждение верно для инлексов, меньших (г. Докажем, что оно верно и для индекса Й. Действительно, (А — 1кЕ) Са 1 — (А 1к- Е) Ск- (Уд 1а-1) Сд=(А — Гд,Е)Сд-кЕк-г (~а — ~а г)Са-т= = С,,Л,,Е,, — ((к — (к,) Са, = = Се-гйа-гЕк-г (Уа (а-к) Е)— = Ск,Едок = СРк. Тем самым мы убедились в том, что матрицы Ск и Яа совпадают с одноименными матрицами треугольного степенного метода со сдвигами (м 1к, ... Так же как и в й 78, можно подобрать сдвиги так, чтобы соответствующий метод ЕЯ со сдвигами имел квадратичную схолнмость. Именно, при этом следует брать — 1 = г1а> дчт а е ' где г1к) — последний диагональный элемент матрицы Йа. 9 80. ЛР-алгорифм Вычислительная схема ЛР-алгорифма ') близка к вычислительной 'схеме Етт-алгорифма, но несколько более трулоемка на каждом шагу.
Сходимость же процесса, в условиях сходимости треугольного степенного метода, является квадратичной. к) Рутисхауаер и Бауэр 11). 534 итвглционныи методы для гашения полной пгозлвмы (гл. чш Алгорифм позволяет последовательно вычислять матрицы С» треугольного степенного метода с номерами К ивляющимися степенями двойки (при С,=Е). Положим А' =Л Е,„, где Л,„ — левая треугольная матрица с единичной главной диагональю, Š†прав треугольная матрица. Ясно, что Л„, = С,м в обозначениях треугольного степенного метода при Се= Е'..
Возводя равенство (1) в квадрат, получим (2) разложим теперь матрицу ЕмЛм в произведение левой треугольной матрицы Е с единичной главной диагональю и правой треугольной матрицы й,„ (3) Тогда получим откуда Лт+г Лт1.т ут+г = )~лз~аю. (4) Эти формулы позволяют последовательно вычислять матрицы Лм и Ем при т= О, 1, 2, ..., начиная с матриц Ле и Еы которые находятся разложением исходной матрицы А в произведение двух треугольных.
Матрицы Лм, в условиях сходимости треугольного степенного метода, будут схолиться к предельной матрице С, причем сходи- Л, мм мость будет порядка 0(~ — '~ ), т. е. сходимость будет квадра- ~,,~ ) тичной. Найдя матрицу С, строим затем матрицу )г = С 'АС, что не представляет труда, нбо С треугольная матрица с единичной главной диагональю. Матрица )г будет правой треугольной матрицей, той самой, которая появлялась как предельная для матриц Й„ в треугольном степенном методе. Собственные значения матрицы А равны диагональным элементам матрицы )с, собственные же векторы определяются при помощи матриц С и И, как в треугольном степенном методе.
Недостатком толыго что 'описанной вычислительной схемы является стремительный рост (или стремительное исчезновение) элементов матриц Х с возрастанием пг. Это явление частично устраняется посредством нормировки на каждом шагу правых треугольных матриц Е к единичной главной диагонали. Под ЛР-алгорифмом и ЛР-Алгпгием 535 $ 80! подразумевают процесс с такой нормировкой. Выведем расчетные формулы алгорифма ЛР. Положим Хт — ЛтР (5) где Ьт диагональная матрица, Рт правая треугольная матрица с еди- ничной главной диагональю.
Тогда Возводя в квадрат это равенство, получим Разложим теперь матрицу Р Лт в произведение левой треугольной с единичной главной лнагональю ьт, диагональной О, и правой треугольной с единичной главной диагональЮ ььст РтАа = ) тОтОьв' (6) Тогда А + = ьтьвбьпттОтКпбтРпь = Лт (Лпьт пьбт ) ЛтОтбт (Лт ЙтЛт) Рпь. Лт+1 — ~ьа (Лть-т'ьт ) Рьа+ь (Лт Йтбт) Рт Ь~„= Ь,'„И, (ь) где РьвЛт ~'тОпьрт Последние формулы и являются предписанием для алгорифма ЛР. Начало процесса определяется разложением данной матрицы А в произведение ЛеЬеРе.
Заметим, что каждый из множителей Лтбтйт и Ь,„ььсь„Ь стремится к единичной матрице. Алгорифм ЛР заканчивается стабилизацией матриц Л . По предельной матрице С определяется матрица ьс = С 'АС. Ее диагональные элементы дают собственные значения матрицы А, собственные же векторы матрицы А суть и,=а~,, ..., и„=си где Уы ..., Рв собственные векторы матрицы гс. Ясно, что Ьтб Л„,ь есть леваЯ тРеУго~ьнаа матРица с единичной главной диагональю, матрица Л Й Ь есть правая треугольная матрица с единичной главной диагональю, а матрица Ь 0 амтв Ь~,О диагональная, Поз гому 536 итаглционныа методы для вешания полной паовламы 1гл.
тш й 81. Итерационные процессы, основанные на применении вращений Вращения, уже рассматривавшиеся нами в $ 5! в связи с преобразованием симметричной матрицы к трехдиагональной. можно использовать для нос~роения итерационных процессов, решающих полную проблему собственных значений. Эти процессы для симметричных матриц состоят в цепочке преобразований подобия, в результате которых в пределе получается диагональчая матрица, так что ее собственные значения определяются непосредственно. Впервые такой процесс был предложен Якоби [11 в 1846 г.
Однако практическое применение его стало возможным лишь с развитием быстродействующих счетных устройств. В настоящее время имеется целый ряд модификаций метода Якоби. Элементарный шаг каждого якобиева процесса заключается в преобразовании подобия посредством матрицы 11~Я при се+за=1.
Как мы видели в й 51, матрица ТН есть .матрица вращения плоскости, натянутой на 1-й и /-й координатные векторы, на угол 0 такой, что сова=с, з1п0 =а. Матрица ТН ортогональна, так / что Тг1=Т7,. Процесс в целом состоит в построении последовательности матриц А=А ~, А ~. А ...., каждая из которых получается из предыдущей при помощи злементарного шага. Эти влементарные шаги должны быть подобраны так, чтобы матрицы А~ 1 безгранично приближались к диагональной матрице при л-+со.
Близость симметричной матрицы А к диагональной мы будем характеризовать числом Р(А). равным сумме квадратов всех цедиасоиаль-. $'811 пвоцвссы, основанные на пгимвнвнии вгащвний ' 88у ных злементов матрицы А. Эта близость может быть, также охарактеризована любой нормой матрицы А — В, где О диагональная матрица, составленная из диагональных злементов матрицы А. Якобиев процесс будем называть релаксационным или монотонным, если 1 (А ) уменьшается на каждом шагу.
Выяснии, как надо выбирать матрицу Тг~ при фиксированных индексах 1 и Г', чтобы Р(Т' АТ ) было меньше, чем Р(А). Обозначим Т,'. АТ = С = (с ). Напомним (0 51), что злементы матрицы С совпадают с элементами матрицы А за исключением элеиентов, находящихся в строках с номерами 1 и г' илн в столбцах с номерами ( и г'. В частности, саа — — ааа при й + г, (г + )'. Пусть л'(А) = ~~1а а'.
= Бр А'А = 8р А'. Я 1.г Легко видеть, что л'(А) = л'(С). Действительно, и (С)=БрС =Бр(Т," АТ,) =БрА"= л (А). Далее пусть 1 си сы с=~ саг са~ Тогла С= Т'АТ, где Т=— , и следовательно, и'(С) =- и'(А). с Ясно, что Р (С) — Р (А) = и' (С) †.~ с'-' „— л' (А) + а 1 + ~'„ а' = аа + а' — с'-. — с', за и м Й ~р' нбо па (С) = и' (А) н са„= аы при (г + 1, й + /. Следовательно. Р(С) — Р(А) = л'(А) — 2а,' — пз(С) + 2с,'. = — 2(с, "'— а', '), так как ла(А) = и'(С).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
