Главная > Математика > Алгебраическая проблема собственныx значений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Кратные собственные значения

48. Вернемся к случаю кратных собственных значений. Соображения § 32 показывают, что кратные собственные значения, которым соответствуют линейные элементарные делители, не влияют неблагоприятно на скорость сходимости. Это иногда вызывает недоумение и дает основание для аргументов следующего типа.

Пусть матрица имеет элементарные делители и где приблизительно 1 и 3, и предположим, что на некотором этапе

Можно проверить, что один шаг LR даст

-алгорифм даст в основном то же самое). Очевидно, что элемент сходится неудовлетворительно.

Ошибка состоит в том, что если имеет линейные элементарные делители, то мы не можем получить таких Ранг должен быть равен единице, и следовательно, например, элемент должен удовлетворять соотношению так что должен быть приблизительно равным Если учесть соотношения, которые должны быть между элементами то видно, что каждый поддиагональный элемент уменьшается на каждом шаге приблизительно в три раза. Использование сдвигов значительно увеличивает скорость сходимости (ср. § 54 для симметричных матриц).

Если имеет нелинейные элементарные делители, то -алгорифм, вообще говоря, не дает сходимости к матрице в верхней треугольной форме. Так, например, матрица

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

Тем не менее -алгорифм сходится. На самом деле мы можем доказать сходимость для любых матриц, имеющих жорданову форму из (48.3). Действительно, имеем

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

Если мы теперь положим

то из формы очевидно, что Следовательно,

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

то

и поскольку

то стремится к верхней треугольной матрице.

Очевидно, что это доказательство можно распространить на случай элементарных делителей любой степени, и затем, как в §§ 30—32, перенести на случай, когда имеет сложную жорданову форму.

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

которая имеет кубический элементарный делитель. При работе с 12 десятичными знаками, при использовании -алгорифма с двойным сдвигом, требуется только одиннадцать итераций. Конечно, эта матрица плохо обусловлена. Изменение порядка 8 в элементах вызывает изменения порядка в собственных значениях. Кратные собственные значения имеют погрешность порядка а простое собственное значение порядка Мы должны рассматривать этот результат как «наилучший возможный» при данной точности вычислений. Для больших матриц с нелинейными элементарными делителями способ двойного сдвига может значительно медленнее давать правильное значение сдвига, и сходимость может быть с самого начала очень медленной.

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление