Вычисление собственных значений в арифметике с фиксированной запятой

47. Для метода деления пополам, который мы описали в §§ 37—39, почти необходимо вычисление с плавающей запятой. Если используется фиксированная запятая, то имеет место так много нормировок, что в этом случае вычисление по существу осуществляется с плавающей запятой. Но так как основным требованием является вычисление главных миноров матрицы для различных значений мы можем использовать метод, описанный в гл. 4, § 49. Так как имеет трехдиагональный вид, находим, что данный метод идентичен методу Гаусса с выбором главного элемента по столбцу. Поскольку этот процесс снова потребуется, когда мы будем рассматривать задачу определения собственных векторов, опишем его подробно.

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

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

(i) Если то переставляем строки Обозначим элементы полученной строки через и строки через так что, если имела место перестановка, то

и в противном случае

Схема, соответствующая (47.1), теперь будет такой:

где или или равно нулю.

(ii) Вычисляем и сохр аняем его. Заменяем нулем

(iii) Вычисляем и записываем их соответственно на места Теперь схема такова:

Заметим, что Простое доказательство по индукции показывает, что если С нормирована так, что

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

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

то видим, что имеют один и тот же знак, если правая часть (47.4) положительна.

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

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

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

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