Ступенчатые итерации

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

где каждая есть единичная нижняя треугольная, а каждая верхняя треугольная. Если то

Следовательно, суть матрицы, полученные при разложении в произведение треугольных, так что (гл. 8, § 4) равны произведению первых 5 нижних треугольных матриц, полученных при помощи -алгорифма, совпадают с верхними треугольными матрицами этого алгорифма. Мы знаем, следовательно (гл. 8, § 6), что если, например, модули всех собственных значений различны, то где матрица, полученная при разложении в произведение треугольных матрицы правых собственных векторов А. Не надо предполагать, что это формальное сходство с -алгорифмом означает, что этот алгорифм столь же распространен на практике, как и LR-алгорифм.

Успех -алгорифма по существу зависит от ряда факторов. Среди них наиболее важными являются инвариантность верхней формы Хессенберга (даже при использовании перестановок), эффективность сдвига и устойчивость процесса исчерпывания. При ступенчатых итерациях, если верхняя матрица Хессенберга, и есть то, хотя имеет только ненулевых поддиагональных элементов, число ненулевых элементов в последовательных прогрессивно растет, и уже полная нижняя треугольная матрица; с этого момента и являются полными матрицами.

С другой стороны, если А — нижняя матрица Хессенберга, также сохраняет эту форму на каждом этапе. Хотя разложение в произведение треугольных требует лишь умножений, вычисление AL

требует уже умножений. Введение перестановок строк при разложении AL разрушает преимущества формы Хессенберга, а перестановки столбцов — нет, хотя применение перестановок, как и в -алгорифме, не имеет теоретического обоснования. Ускорения сходимости можно достигнуть, применяя вместо А, и можно менять от итерации к итерации, но отсутствие действительно эффективной техники исчерпывания делает это менее удовлетворительным, чем в LR-алгорифме. Когда малое собственное значение определено, мы не можем свободно выбирать так как это может сделать доминирующим собственным значением А.

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

где верхние треугольные матрицы порядка. Если доминирующие собственных значений А имеют различные модули, где получена приведением матрицы из доминирующих собственных векторов к верхней трапециевидной форме. Более общо: если

то матрицы не обязательно стремятся к пределу, но подпространства, натянутые на их столбцы, стремятся к инвариантному подпространству (гл. 8, §§ 32, 34). Этот процесс впервые был описан Ф. Л. Бауэром, который назвал его ступенчатыми итерациями.

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

где состоит из первых к векторов, которые уже стабилизировались, а из остальных векторов, которые еще не стабилизировались. Определим соотношением

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

Надо заметить, что не обязательно первые столбцы будут стабилизироваться первыми. Например, если четыре доминирующие собственные значения равны первые два столбца скоро будут порождать подпространство, соответствующее собственным векторам следовательно, столбцы 3 и 4 будут сходиться. Разделение столбцов 1 и 2 в соответствующие собственные векторы будет происходить значительно медленнее. Если доминирующее собственное значение соответствует нелинейному элементарному делителю, то этот эффект может быть еще более заметным. Численный пример дан в § 41.