Общие замечания о методе деления пополам

43. Если мы реализуем шагов метода деления пополам, то из (41.4) следует, что оценка ошибки в вычисленном собственном значении равна и из анализа видно, что, как правило, она будет завышена. Наиболее замечательным в этом результате является то, что оценка не зависит от

По существу при каждом вычислении последовательности необходимо выполнить умножений и вычитаний могут быть вычислены один раз), так что если независимо находятся все собственных значений, используя шагов метода деления пополам, то всего требуется умножений и вычитаний. Для больших время определения собственных значений будет порядка тогда как время, необходимое для выполнения как метода Гивенса, так и метода Хаусхолдера,

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

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

Метод деления пополам обладает очень большой гибкостью. Мы можем использовать его для нахождения специально выделенных собственных значений собственных значений в заданном интервале или для нахождения предписанного чцсла собственных значений слева или справа от заданного значения. Мы не обязаны определять все требующиеся собственные значения с одной и той же точностью и можем очень просто изменять точность изменением числа шагов деления пополам. Если нас интересует лишь общее распределение собственных значений, а не их точное определение, то метод особенно эффективен. Он был использован Дином (1960) для нахождения распределения собственных Значений трехдиагональных матриц до 32 000-го порядка.

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