Н.Н. Калиткин - Численные методы (1133437), страница 39
Текст из файла (страница 39)
ш и гь причем их можно вычислять по таким формулам: гл = г, + пена — Лье — ааь г) =г,+г,— ге, (53) штрихи относятся к значениям после вращения. Доказательство сходимости. Оптимальный элемент составляет не менее 1!(л — 1) части суммы (52) своей строки, а эта сумма — не менее !гав части 5в. Следовательно, за одно вращение недиагональная часть сферической нормы уменьшается 2 не менее чем на , долю своей величины (ибо уничтожаются л (и — 1) два симметричных элемента). Значит, за У вращений Зз убывает не медленнее, чем (1 —, ~ — ехр ( — 2Ж/л'), 2 м *) Циклом будем называть процесс с последовательным перебором всех подниагональпых элементов, илн условно — л(л — !)~2 последовательных поворотов при другом способе выбора аннулируемых элементов.
и тем самым стремится к нулю при Ж- оо. Следовательно, процесс Якоби с выбором оптимального (и тем более максимального) элемента всегда сходится. Исследуем сходимость вблизи решения, считая собственные значения простыми. Пусть все внедиагональные элементы уже малы, ац Б. Тогда из формул (51) следует, что угол поворота имеет тот же порядок малости: р -Б, сс-1 — 0(ее). Подстановка в формулы (43) —.(44) показывает, что при этом неуничтожаемые внедиагональные элементы меняются на 0 (е').
Значит, за один цикл вращений*) все внедиагональные элементы станут е', что означает квадратичную сходимость. Итак, вдали от решения сходимость не хуже линейной, а вблизи решения квадратичная, т. е. быстрая. Зто позволяет получать все собственные значения с высокой точностью. Обычно процесс сходится за 6 — 8 циклов вращений, или за (3 —:-4) п' элементарных вращений. Интересно, что чем больше кратных собственных значений, тем быстрей сходится метод.
Поскольку собственные векторы диагональной матрицы суть ео то собственными векторами матрицы А будут столбцы матрицы (г=п(гы. Заметим, что если внедиагоиальные элементы аг = = 0 (Б), то Зз = 0 (е'), так что диагональные элементы отличаются от собственных значений на 0(е'). Поэтому для нахождения собственных значений достаточно положить е 10 ', чтобы получить правильно !О знаков. Ио чтобы получить с той же точностью 181 НЕЭРМИТОВЫ МАТРИЦЫ $ 3] собственные векторы, надо или вычислять их по формулам «' =(П (Уег) Уг У~ = (Уп) (34) нп — 1 н рг ' пРи 1~1 ап — лп или делать еще один цикл вращений.
Хотя теоретически в методе Якоби'могут накапливаться ошибки, фактически устойчивость и точность очень высоки. Кратные собственные значения получаются столь же точно, как и простые, а собственные векторы практически ортого- ° ° нальны друг другу. Метод Якоби с выбором оптимального элемента требует обычно около 30п' арифметических действий и и' ячеек памяти для нахождения всех собственных значений.
Для нахождения всех собственных векторов требуется еще около 20п' действий. Таким образом, этот метод раз в 10 медленнее ме- (Т) ° ° О ° ° ° 02 ° ° ° Оу тода отражении. Основное его достоинство— надежность и единообразность вычислений, Рис. 34. что позволяет легко запрограммировать метод. Итерационный метод вращений применяется там, где важна точность, надежность и простота расчета и менее существен объем вычислений. 3 а м е ч а н и е. Этот метод можно ускорить в 1,б — 2 раза; не теряя его достоинств.
У произвольных матриц недиагональная часть сферической нормы в среднем многа большедиагональной,5э/5г л,а утрехдиагональных в сред. нем 5з/5г 2. Значит, трехдиагональная матрица является выгодным начальным приближением для итерационного метода Якоби, Поэтому целесообразно прсдварительно привести исходную эрмитову матрицу к трехдиагональной форме при помощи прямого метода вращений и затем первым ходом метода Якоби аннулировать все нечетные или все четные подкиагональные элементы (рис.
34). Г1осле этого можно переходить на обычный вариант итерационного метода вращений с выбором оптимального элемента. й 3. Неэрмитовы матрицы 1. Метод элементарных преобразований. В принципе можно привести преобразованием подобия неэрмитову матрицу к почти треугольной форме при помощи отражений нли вращений. Для матриц такой формы задача на собственные значения решается сравнительно быстро и устойчиво способом, описанным в 3 1. Однако существует втрое более быстрый (хотя несколько менее устойчивый) метод элементарных преобразований; он позволяет привести произвольную матрицу к трехдиагональной форме всего за 2п' арифметических действий.
Для неэрмитовых матриц это самый быстрый из известных методов, 1зз ллгнвэличвскхя пеовлвмл совствннных значении игл, щ Метод является двухходовым. Первым ходом матрица приводится к верхней почти треугольной форме, а вторым — к трех- диагональной форме. Каждый ход состоит нз последовательности элементарных преобразований подобия, напоминающих отражения; преобразования первого хода поочередно обращают в нуль столбцы в нижней части матрицы, а преобразования второго хода — сгроки в верхней части матрицы.
Первый ход. На его д-м шаге для преобразования подобия используется матрица следующего вида: оо.„о ггз 1 0 ... 0 Л~ йгд (о) од о 1 . о (55) о о Исследуем свойства этой матрицы. Нетрудно проверить, что й("У ~ Е, так что эта матрица не унитарна (именно поэтому элементарные преобразования менее устойчивы по отношению к ошибкам округления). Изменим знаки всех компонент оь т. е, возьмем матрицу Ф ( — о); непосредственным перемножением легко убеждаемся, что )У (о) ЬГ( — о) =Е. Следовательно, обратная к (55) матрица определяется просто: йг-' (о) = Ж ( — о).
(56) Аналогично методу отражений, матрицы (55) применяются для обращения в нуль нижней части д-го столбца, если уже аннулированы предыдущие столбцы (рис. 32). Разобьем матрицу А на клетки тех же размеров, что и в (55), и запишем преобразование подобия на данном шаге Ьм=аг — оаэеь при 9+2~((п. (58) Ье,эсае г, Поэтому, чтобы обратить в нуль все элементы клетки В„кроме углового элемента Ь,е,, надо положить о; = — ы- прн д+2(((п.
(59) Последняя формула определяет матрицу искомого элементарного У клетки А,, а следовательно, и у клетки В, =У ( — о) А, только последний столбец является ненулевым; элементй этого столбца результирующей матрицы получаются позлементным перемноже- нием клеток; гвз неэРмитовы мАтРицы й зу преобразования. Она существенно проще, чем формулы для нахождения нужной матрицы отражения в п. 2. Само преобразование (57) очень несложно.
Благодаря специальной структуре матрицы Ж умножение на нее выполняется так же быстро, как умножение на вектор. Например, поэлементно перемножая матрицы, найдем клетку В,=Азу (и): Ьц =агу пРи г)+2~У(п, 1~(~г), (60) Ььдьд — — аг ьх+ ~ айсг при 1 =г =-'д; /=а+2 при умножении справа на Л' меняется только первый столбец клетки А„а остальные столбцы клетки В, равны соответствующим столбцам клетки А,. Произведение Са — — Ааааа(с) вычисляется также по формулам (60), только с одним отличйем: первый индекс элементов принимает значения г)+1.
1«=. п. Умножение слева на Жд приводит к другим выражениям; так, для четвертой клетки В,=У ( — и) С, поэлементное перемножение дает Ьд.'сдь'пРиг)+1~)~п (61) Ьц =си — с се,, г прн г)+1 =)~п, г)+2~э -и, т. е. меняются почти все элементы клетки. Формулы (58) — (61) полностью определяют очередной шаг первого хода. Они экономичны, так что метод элементарных преобразований позволяет привести произвольную матрицу к почти треугольной форме всего за (5/3) и' арифметических действий, т. е.
вдвое быстрей, чем в методе отражений. Ыо для эрмитовых матриц метод элементарных преобразований невыгоден, ибо при неупитарных преобразованиях эрмитовость не сохраняется. Тем самым результирующая матрица будет почти треугольной, а не трехднагональной, как в методе отражеаий; вдобавок выигрыша в скорости по сравнению с методом отражений в этом случае нет. Однако расчет по полученным формулам еще недостаточно устойчив.
Если в ходе расчета на очередном шаге возникает малый ведущий элемент адэз, д, то согласно формулам (59) компоненты пг будут велики. При вычислении остальных клеток матрицы элементы умножаются на эти компоненты, и погрешность сильно возрастает. Чтобы сделать метод устойчивым, выбирают главный (т. е. наибольший по модулю) элемент аннулируемого столбца )а, )=-гпах)агд( пРи г7+2~г, г -и (62) г н перестановкой (г)-)-1)-й н г-й строк делают его ведущим. Тогда будет выполняться неравенство газ~==1, и погрешность практически не будет нарастать.
Формально перестановку двух строк 184 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИИ 1ГЛ. щ можно записать как умножение слева на матрицу перестановки Р: Я+1 г о+1 (63) А'=Р А,,А, Р ~з,= (все элементы, стоящие вне главной диагонали, кроме отмеченных здесь, равны нулю). Непосредственным перемножением легко убедиться, что Р =-Р'= Р", так что свойствй матрицы перестановки похожи на свойства матрицы отражения.
Но перестановка строк меняет собственные значения матрицы. Чтобы собственные значения не менялись, надо сделать преобразование подобия А"=Р-'АР. Используя свойства матриц перестановок и ассоциативность умножения, получим А" = Р-'АР = РА Р = (РА) Р = А'Р. Отсюда видно, что после перестановки строк надо умножить полученную матрицу справа иа Р. Поэлементным перемножением легко убедиться, что умножение справа на Р есть просто перестановка соответствующих столбцов матрицы А' (перестановка выполняется на ЭВМ быстрее, чем арифметические действия).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
