Анализ ошибок

55. В главе 9 мы обсудим обратную итерацию в более общем плане; кроме того, случай симметричной трехдиагональной матрицы уже был подробно изучен Уилкинсоном (1963b, стр. 143—147). По этой причине мы довольствуемся здесь менее формальным исследованием.

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

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

Предположим для удобства, что С нормирована, и выполним такие итерации:

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

где

Если обозначим

то (55.2) может быть записано в виде

Из членов справа первый мал, так как X по предположению близко к собственному значению, второй мал согласно (55.3). Третий будет мал, если велика. Следовательно, чем больше мы получим значение для тем меньше будет наша оценка для правой части (55.5), и это есть вектор-невязка, соответствующий Уилкинсоном (1963b, стр. 139—147), показано, что должна быть большой, если разложение содержит не очень малую часть вектора

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

и затем выполняем еще один шаг.

На практике это никогда не приводило более чем к трем итерациям, и обычно было достаточно двух. (Заметим, что первая итерация включает лишь обратную подстановку.) Множитель не имеет глубокого смысла, а только обеспечивает то, что мы будем редко выполнять необязательную дополнительную итерацию. Можно было бы думать, что нормированный вектор должен стремиться к пределу в рамках ошибки округления и что некоторое условие, основанное на этом, должно быть более естественным критерием окончания, чем (55.6). Однако это не так; если С имеет более чем одно собственное значение, патологически близкое к X, то в конечном счете будет лежать в подпространстве, натянутом на соответствующие собственные векторы. Иногда случается, что при последовательных итерациях мы получаем совсем разные векторы, лежащие в этом подпространстве. Тогда последовательные не «сходятся» совсем.