Дальнейшее уточнение собственных векторов

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

вычислений. Из нашего анализа ясно, что, работая с фиксированным разложением в произведение двух треугольных, мы не можем ожидать результатов лучших, чем точный собственный вектор матрицы из уравнения (48.3). Мы знаем, что матрица весьма мала, но если существуют другие собственные значения, близкие к А, то вычисленный собственный вектор обязательно будет иметь составляющие по соответствующим собственным векторам, которыми нельзя пренебречь. Например, если а другие собственные значения хорошо отделены от этих двух, вычисленный собственный вектор и будет в основном иметь вид

где может быть порядка порядка (гл. 2, § 10).

Интересно обсудить вопрос, можем ли мы получить более точный собственный вектор, чем и, используя то же самое разложение в произведение треугольных и ту же точность вычислений. Рассмотрим точное решение уравнения

Очевидно, мы имеем

и следовательно, если ближе к единице, чем к то нормированный х будет иметь значительно меньшую компоненту по чем и. В гл. 4, §§ 68, 69 мы обсуждали проблему точного решения системы уравнений и показали, что (51.1) может быть решена достаточно точно, если накапливать скалярные произведения и если не слишком плохо обусловлена.

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

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

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

стать настолько плохо обусловленной, что хорошее решение вообще не может быть получено, если не работать с большей точностью.

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

где

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

На первой стадии компонента по уменьшается по сравнению с компонентой по на множитель, меньший чем

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

На первой стадии компонента по уменьшается по сравнению с компонентой по на множитель, меньший чем

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

и, следовательно, после нормирования

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

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

На основе этой техники было разработано несколько программ для DEUCE. Наиболее усложненная из них была предназначена для определения собственных векторов комплексных матриц с двойной точностью, начиная с приближенных собственных значений. При этом использовалось разложение в произведение треугольных лишь с обычной точностью! Используя технику, описанную в гл. 4, § 69, возможно определить вектор с двойной точностью, потому что, как установлено в пункте (i) настоящего параграфа, мы можем использовать правую часть в уравнении с двойной точностью без применения двойного количества знаков. Программа для DEUCE была весьма замысловатой, и на вычислительных машинах с большой оперативной памятью, наверно, было бы более экономно использовать обычные вычисления с двойной точностью. Однако программа существенно помогла понять природу обратных итераций. Она также дала очень надежный критерий точности вычисленных векторов. Интересно, что эти надежные оценки могут быть получены для с использованием лишь грубых оценок остальных собственных значений.