Доказательство сходимости последовательности As

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

то, вообще говоря, результат (3.4) справедлив. Прежде чем давать формальное доказательство, рассмотрим простой пример матрицы третьего порядка. Если для простоты матрицу X правых собственных векторов записать в виде

и ее обратную в виде

то

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

Очевидно, что если то

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

при условии, что

Из (5.8) мы видим, что предельное значение равно соответствующему элементу, полученному при разложении X в произведение треугольных. Поэтому мы установили, что если

при

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

то из явных выражений для элементов треугольных сомножителей матрицы, полученных в гл. 4, § 19, имеем

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

имеем

Согласно теореме Вине — Коши (гл. 1, § 15) равен сумме произведений соответствующих -строчных миноров двух матриц из правой части (6.4). Следовательно, можно написать

где это -строчный минор, состоящий из строк и столбцов матрицы X, а это -строчный минор, состоящий из строк и столбцов матрицы У.

Главные члены в числителе и знаменателе (6.5) определяются множителем при условии, что соответствующие коэффициенты не равны нулю. Этот член в знаменателе равен

где главные ведущие подматрицы порядка Предполагая, что не нуль, имеем

что показывает, что где

Из (4.3) и (4.4) имеем

откуда следует, что предельная матрица для есть верхняя треугольная с диагональными элементами

Используя соотношение и уравнение (6.5), можно элементарным, но весьма утомительным способом доказать, что

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

Следовательно, если некоторые собственные значения плохо разделены, то сходимость к треугольной матрице может быть медленной. Другое (и более простое) доказательство дано в § 33, но метод доказательства, используемый здесь, более поучителен.

7. При получении этих результатов явно или неявно были сделаны следующие предположения:

(i) Все собственные значения различны по абсолютной величине. Заметим, что А может быть комплексной, но не может быть вещественной матрицей, имеющей комплексно сопряженные собственные значения (последний случай обсуждается в § 9).

(ii) Разложение в произведение треугольных матриц существует на каждом этапе. Легко построить матрицы, которые не являются исключительными в других отношениях, для которых это условие не удовлетворяется, например

Эта матрица имеет собственные значения 1 и 3, но не может быть разложена в произведение треугольных. Однако заметим, что, например, может быть разложена в произведение треугольных, и мы можем работать с этой модифицированной матрицей.

(iii) Ведущие главные миноры не равны нулю. Существуют очень простые матрицы, для которых это требование не выполнено. Наиболее очевидными примерами таких матриц являются матрицы вида

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

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

Ясно, что в этом примере две половины матрицы полностью «не связаны» при и введение малых приводит к появлению

«слабой связи». В более сложных примерах мы первоначально можем иметь полную «несвязанность», т. е. при некотором иметь

но ошибки округления в LR-процессе могут внести эффект слабой связи.