Ленточные матрицы

59. Объем работы для произвольных симметричных матриц очень велик, но это не так для ленточных матриц, т. е. матриц таких, что

Рассмотрим сначала -алгорифм Холецкого. Очевидно, что он сохраняет ленточную форму (для несимметричных матриц ср. § 66), и на каждом шаге матрица такая, что

Следовательно, хотя имеет отличных от нуля элементов в типичной строке, имеет только элементов.

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

Для того чтобы получить все преимущества от ленточной формы и симметрии, удобно обозначить элементы А следующим образом, проиллюстрированным для случая

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

60. Элементы получаются строка за строкой, причем элементы строки вычисляются следующим образом: (i) Определяем

Затем для всех от до выполняем шаги (ii) и (iii).

(ii) Определяем

(iii) Вычисляем где сумма равна нулю, если

Если то (Если отрицательно, то слишком велик.)

Если

В качестве примера при имеем

Величины введены для того, чтобы учесть эффекты окончания.

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

(i) Определяем

Затем для всех от до выполняем шаги (ii) и (iii).

(ii) Определяем

(iii) Вычисляем

Если

Если то Например, если то

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

61. Если используется техника Рутисхаузера § 56, то мы должны исследовать каждый срыв. Если срыв произошел, когда то текущее значение х является следующим сдвигом. Если срыв произошел, когда мы должны вычислить матрицу X второго порядка из уравнения (56.3). Имеем

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

Требуется примерно умножений для выполнения разложения и столько же для переумножения. Если это значительно меньше, чем для полной матрицы. Мы видели в гл. 4, § 40, что ошибки при разложении очень малы. Например, при использовании арифметики с фиксированной запятой с накоплением скалярных произведений имеем

где имеет ту же ленточную форму. Аналогично

где снова имеет ленточную форму. Из этих результатов легко видеть, что максимальная ошибка, введенная в любое собственное значение полным преобразованием, равна Если нормирована так, что то все элементы всех ограничены единицей. Заметим, что если мы сравним вычисленную с точной нам может неправильно показаться, что собственные значения имеют значительно меньшую точность (см., например, Рутисхаузер (1958, стр. 80)).