Сходимость в целом

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

Если известно, что все собственные значения вещественны, то ситуация вполне удовлетворительна. В отношении метода Лагерра мы знаем, что сходимость к соседним корням обеспечена при любом начальном приближении. Простейший способ — использовать в качестве исходного значения каждого корня и применить метод удаления, описанный в § 55. Сходимость в целом столь замечательна, что этот простой процесс вполне удовлетворителен, если только А не имеет кратных или патологически близких корней. Для таких корней (28.12) дает, что

и

откуда

Положив получим

Парлетт (1964) считает, что сходимость к простому корню обычно настолько быстра, что если с какого-то момента

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

Если применяется метод Ньютона с в качестве исходного приближения к каждому корню с методом удаления, описанным в § 55, то собственные значения получаются в монотонно убывающем порядке. Наконец, если мы применим последовательную линейную интерполяцию с исходными приближениями, например мы снова получим собственные значения в убывающем порядке. Сходимость в целом последних двух методов не настолько удовлетворительна, как сходимость метода Лагерра, и здесь следует пытаться определить лучше исходные значения. Так как собственные значения определяются в убывающем порядке, последний вычисленный корень есть верхняя граница для оставшихся корней, однако метод удаления не позволяет ее использовать. Вместо этого можно использовать — для всех шагов после второго для метода Ньютона и и для метода последовательной интерполяции. Если равно то вместо него нужно взять первое из большее, чем или, если такого нет, взять Заметим, что вместо можно использовать любую известную верхнюю границу для собственных значений. Если А была получена из исходной матрицы преобразованием подобия, вполне может случиться, что и в таком случае лучше использовать В каждом из последних двух методов не только корни вычисляются в монотонно убывающем порядке, но и сходимость к каждому корню монотонна.

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

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

Обозначим корни через так что

Покажем, что Так как ясно, что при все производные неотрицательны. Следовательно,

и потому

Так как числитель и знаменатель состоят лишь из неотрицательных членов, откуда следует Заметим, что мы требовали только, чтобы были вещественными и чтобы все производные были неотрицательными при Поэтому доказательство приложимо, например, для

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

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

Если А — симметричная или квазисимметричная трехдиагональная матрица, то можно получить информацию о распределении нулей из свойства последовательности Штурма и деления отрезка (гл. 5, § 39). Поэтому можно комбинировать методы этой главы с методом деления. Особенно изящная комбинация метода деления и последовательной линейной интерполяции была предложена Деккером (1962). Этот метод может использоваться для локализации вещественного корня любой вещественной функции после того, как определен интервал, содержащий этот корень.