Уменьшение ширины ленточной матрицы

68. Техника §§ 59—64 весьма эффективна, если требуется найти только несколько собственных значений общей ленточной матрицы. Для вычисления большого числа собственных значений, может быть, лучше сначала привести матрицу к трехдиагональному виду при помощи предварительного преобразования. Это можно сделать при помощи методов Гивенса или Хаусхолдера, но ширина матрицы на промежуточных стадиях приведения увеличивается.

Рутисхаузер (1963) описал два интересных приведения, использующих соответственно плоские вращения и матрицы отражения, в которых ленточная симметричная форма сохраняется на всех стадиях. Мы дадим только приведение, основанное на плоских вращениях, и в нашем описании используем только элементы верхнего треугольника.

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

(см. скан)

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

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