Главная > Математика > Алгебраическая проблема собственныx значений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Элементарные устойчивые преобразования

8. Преимущества использования ортогональных преобразований для симметричных матриц настолько велики, что мы не рассматривали использования более простых элементарных устойчивых матриц. Теперь обстоятельства сильно изменились.

Рассмотрим приведение к верхней форме Хессенберга при помощи устойчивых элементарных матриц типа (гл. 3, § 47). Приведение состоит из основных шагов. Перед началом шага матрица приведена к которая для имеет вид

Мы увидим, что последующие шаги не меняют элементов, обозначенных Основной шаг состоит в следующем:

(i) определяем наибольшую из величин (Если элементов с наибольшим модулем несколько, то берем первый из них.) Если этот элемент есть то переставляем строки т. е. умножаем слева на (Элемент можно рассматривать как «ведущий элемент» по отношению к нашему преобразованию);

(ii) для всех значений от до вычисляем так что и вычитаем из строки (строка Операции в (ii) означают умножение слева на матрицу типа С их помощью получаются нули в позициях ;

(iii) переставляем столбцы т. е. умножаем справа на

(iv) для всех значений от до прибавляем к столбцу столбец). Операции в (iv) означают умножение справа на Если ведущий элемент равен нулю, то произвольны и наиболее просто взять

Заметим, что столбцы от первого до не меняются при преобразовании, которое само определяется элементами столбца в позициях от до Перестановки включены для того, чтобы избежать численной неустойчивости. Элементы столбца от 1 до также не меняются. Имеются величин и их можно записать в позициях, которые раньше занимали аннулированные

9. Кажется, что описание, данное в § 8, является наиболее естественным путем введения алгорифма. Но сейчас мы опишем две различные

модификации основного шага, которые дадут возможность получать преимущества от накопления скалярных произведений. Мы снова будем использовать верхний индекс так как такие, обозначения будут нужны при анализе ошибок в этих модификациях. Перестановки и множители определяются так же, как и раньше, и преобразованные элементы определяются из следующих соотношений. Модификация I:

Модификация II:

Единственная ошибка округления делается тогда, когда заканчивается накопление соответствующих скалярных произведений. Эти два процесса математически идентичны, но различны на практике. Так как ведущий элемент следующего шага выбирается из элементов мы можем определять сразу, как только эти элементы вычислены.

Приблизительное число умножений в шаге равно при умножении слева и — при умножении справа, независимо от того, используем ли мы исходную формулировку или модификации. Общее число умножений в полном приведении приблизительно равно

что равно половине числа умножений при приведении по методу Хаусхолдера и четверти — по методу Гйвенса.

<< Предыдущий параграф Следующий параграф >>
Оглавление