Кратные и патологически близкие собственные значения

40. Метод деления неприменим для локализации кратных нулей четного порядка, но использовать последовательную линейную интерполяцию все еще можно. Можно подумать, что точность, достижимая в этом случае для кратного корня, сильно ограничена, но это не так. Хотя сходимость медленная, окончательная достижимая точность зависит только от размеров области неопределенности. Ситуация теперь значительно хуже, чем в случае простого нуля. Для двойного нуля, например, соотношение (38.2) становится таким:

но мы не можем утверждать, что значительно меньше, чем

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

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

где границы для порядка Такие возмущения коэффициентов иногда вызывают в корнях возмущения порядка (гл. 2, § 3). Поэтому область неопределенности имеет ширину где к порядка единицы. Соответственно линейная интерполяция перестает давать постоянное улучшение, как только мы достигли z, имеющего ошибку порядка Однако если мы вычисляем определитель матрицы

рассматривая ее как трехдиагональную, то область неопределенности, содержащая порядка и корень при может быть определен точно. (Об определении кратности см. § 57).

41, Этот пример может показаться слегка искусственным. К сожалению, трехдиагональная матрица с линейными элементарными делителями и собственным значением кратности должна иметь нулевых наддиагональных элементов; это следует просто из подсчета ранга. Однако если мы хотим рассмотреть собственные значения, которые в действительности не кратные, но равны с рабочей точностью, то мы можем дать значительно более интересные примеры. Хорошую иллюстрацию дает матрица из главы 5. Используя мантиссу с 30 двоичными знаками, доминирующий нуль был найден правильно до последней цифры, причем использовалась последовательная линейная интерполяция, несмотря на то, что второе собственное значение совпадает с первым с рабочей точностью. Рассматривались аналогичные примеры матриц, собственные значения которых с рабочей точностью были высокой кратности, и несмотря на то, что сходимость была чрезвычайно медленной, окончательная достижимая точность была очень высокой.