Уточнение системы собственных значений

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

В гл. 3, §§ 59—64 мы обсуждали проблему уточнения полной системы собственных значений и собственных векторов с теоретической точки зрения. Сейчас опишем детально практическую процедуру, использующую описанные там идеи. Эта процедура была запрограммирована на с использованием фиксированной запятой, и мы будем описывать ее в этой форме. Изменения, необходимые для вычислений с плавающей запятой, очевидны.

Предположим, что каким-то образом мы определили приближенную систему собственных значений и собственных векторов. Обозначим вычисленные собственные значения и собственные векторы через и а матрицу собственных векторов через и определим матрицу невязки

соотношением

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

До сих пор не появилось никаких ошибок округления. Далее, мы хотим вычислить так точно, как это возможно. На это производилось с использованием итерационного метода, описанного в гл. 4, § 69. Матрица X сначала разлагается в произведение треугольных с использованием перестановок, а затем каждое уравнение решается с помощью итераций. Заметим, что метод, описанный в главе 4, использует одинарную точность вычислений с накоплением скалярных произведений, но, как мы указывали, можно использовать правые части с двойной точностью. В предположении, что процесс сходится и дает решения уравнений верные с рабочей точностью. Если положим то будем иметь

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

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

64. Теперь мы можем для локализации собственных значений использовать теорему Гершгорина (гл. 2, § 13). Так как В масштабирована по столбцам, то на удобнее применять обычные результаты Гершгорина к а не к В, однако мы использовали здесь обычные круги, так что можно сделать прямую ссылку на предыдущее. Непосредственное приложение теоремы Гершгорина показывает, что собственные значения А лежат в кругах с центрами и радиусами но, вообще говоря, это очень слабый результат. На более точная локализация получалась следующим образом.

Предположим, что круг, связанный с изолирован. Умножим первый столбец В на и первую строку на где k — наибольшее целое число такое, что первый круг Гершгорина остается изолированным. В силу наших предположений . При таком значении к теорема Гершгорина утверждает, что одно собственное значение находится в круге с центром и радиусом а значит, и в круге с центром и радиусом Мы можем заменить их верхней границей, так как в любом случае они меньше, в 21 раз.

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

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