Несимметричные ленточные матрицы

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

Особенно интересен случай трехдиагональной матрицы А. Сравним две последовательности трехдиагональных матриц полученных следующим образом. В первой начнем с и используем -разложение (без перестановок), в котором каждая единичная нижняя треугольная. Во второй начнем с некоторая диагональная матрица, и используем любой другой тип -разложения (без перестановок). Доказательство § 52 показывает, что на соответствующих стадиях мы имеем

с некоторой диагональной матрицей Если

то из (66.1) найдем

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

и затем использовать -разложение с единичной нижней треугольной на каждой стадии. Если

то

и, следовательно,

Эти уравнения показывают, что после вычисления остальные могут быть определены без вычисления В самом деле, если мы рассматриваем как нуль при всех то имеем схему

в которой каждая наклонная линия с верхним индексом 5 может быть получена по выше лежащей наклонной линии, если использовать уравнения (66.7), причем связанные элементы размещаются по вершинам ромбов того типа, какой мы отметили. Читатель, знакомый с -алгорифмом, заметит, что это Рутисхаузера. Алгорифм играет значительно большую роль в общей проблеме вычисления нулей мероморфных функций, и полное обсуждение его выходит за рамки этой книги.

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

то в этом случае наш анализ показывает, что это точно те же величины, что и полученные при использовании формы (66.3). Кажется, что более удобно работать в терминах На самом деле это означает, что мы можем получить все преимущества LR Холецкого без вычисления квадратных корней. Вероятно, проще всего переходить прямо от и если мы используем на каждой стадии сдвиг и не восстанавливающий метод, то уравнения будут иметь вид

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