1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 40
Текст из файла (страница 40)
Диагональные элементы полученной диагональной матрицы и будут искомыми собственными значениями. Но уничтожить все иедиагональные элементы за конечное число поворотов нельзя, ибо, в отличие от прямого метода вращений, здесь прн очередном повороте ранее уничтоженный элемент снова может стать ненулевым. Какой именно недиагональный элемент целесообразно аннулировать при очередном повороте? Конечно, если уничтожать максимальный по модулю внедиагональный элемент, то скорость убывания 5, будет наибольшей. При ручных расчетах это наилучший способ. Но на ЭВМ перебор элементов матрицы для определения максимального элемента требует неприемлемо большого числа действий.
А если аннулировать элементы в заранее определенном порядке — циклом, то сходимость будет очень медленной. Наиболее выгодным оказалось уничтожение так называемого оптимального элемента. Составим суммы квадратов модулей внедиагональных элементов строк: ь '=Х~ 1=! ! Ф~ Выберем из этих сумм наибольшую, а в ней выберем наибольший по модулю элемент; его называют оптимальным. Поиск оптимального элемента сводится к перебору двух строк (строки сумм го а в выбранной сумме — строки ~,ао~), т.
е. требует малого числа действий. Суммы (52) вычисляются тоже экономично, ибо при ' каждом вращении нз них меняются только две — гь Можно выбрать любой из четырех корней этого уравнения, тогда р определится однозначно. Для определенности положим 1ВО АлГеБРАическАя пРОБлемА соБстаенных знАчении (Гл. ш и гь причем их можно вычислять по таким формулам: гл = г, + пена — Лье — ааь г) =г,+г,— ге, (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) и' арифметических действий, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
