Анализ ошибок при обратных итерациях

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

На практике матрицу разлагают в произведение двух треугольных, используя выбор главного элемента по столбцу, причем записываются элементы и позиции главных элементов (гл. 4, § 39). Это означает, что с точностью до ошибок округления,

где некоторая матрица перестановок, С сохраненной информацией мы можем решить уравнение решая две треугольные системы уравнений

Перестановки здесь играют малую роль, за исключением обеспечения численной стабильности. Эффект ошибок округления таков, что мы имеем

и вычисленный вектор х удовлетворяет соотношениям

где суть матрицы с малыми элементами, зависящими от способа округления (гл. 4, § 63). Очевидно, что матрица не зависит от может зависеть.

Следовательно, зная разложение в произведение треугольных, мы можем вычислить последовательности вида

где для удобства анализа мы нормировали при помощи -нормы. Если бы матрицы были нулевыми, то мы бы итерировали точно с следовательно, стремились бы к собственному вектору соответствующему ближайшему к собственному значению. Точность вычисленного вектора была бы высока, если бы было мало и собственный вектор был неплохо обусловлен. Как мы уже замечали, вычисленные решения треугольной системы уравнений обычно исключительно точны (гл. 4, §§ 61, 62), так что на практике обычно очень близко к решению уравнения на каждом шаге, и итерированные векторы действительно будут сходиться к собственным векторам

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

и предположим без существенной потери общности, что Следовательно, можем написать

Покажем, что для установления нашего результата достаточно убедиться, что велик. Из (49.2) имеем:

где

Это показывает, что если велика, а малы, то дают малую невязку, и следовательно, если неплохо обусловлен, — хороший собственный вектор. Действительно, положив

и предположив, что получаем из уравнения (49.2) умножением на слева

Следовательно,

что дает

Подставив в (49.5), получим

Следовательно, предполагая, что ни ни не малы, получаем, что вектор невязки г) мал.