Срыв факторизации Холецкого

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

то

Предположим, что мы достигли такой стадии, когда уже определены, но при попытке определить первый элемент нужно извлекать квадратный корень из отрицательной величины. Из (56.2) имеем

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

Очевидно, что так как отрицательно, мы сможем достичь по крайней мере той же стадии, что раньше, и соответствующая теперь определяется соотношением

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

определенная. Пусть такая ортогональная матрица, что

Так как мы считаем, что имеет факторизацию, то Следовательно, имеем

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

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