Численная устойчивость метода деления пополам

40. При точном вычислении метод § 39 мог бы быть использован для определения любого собственного значения с любой наперед заданной точностью. На практике ошибки округления будут ограничивать достижимую точность, но тем не менее, как мы установим, метод исключительно устойчив. Мы дадим анализ ошибок, соответствующий использованию стандартной арифметики с плавающей запятой.

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

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

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

где

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

откуда

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

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

41. Предположим для удобства, что удовлетворяют соотношениям

Тогда, согласно § 39, все значения которые используются в процессе деления пополам, лежат в интервале Следовательно,

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

центрами которых являются собственные значения матрицы С (гл. 2, § 44).

Теперь очень важным вопросом, на который должен быть дан ответ на каждом шаге процесса деления пополам при вычислении собственного значения, является следующий: «Меньше ли, чем , собственных значений матрицы С, которые больше средней точки текущего интервала?» Если каждый раз на этот вопрос дается правильный ответ, то всегда локализуется в точном интервале. Это верно независимо от того, правильно ли определяется действительный номер!

Покажем, что на практике мы должны получить правильный ответ, если находится вне интервала (41.3) с центром в как бы близко ни были собственные значения и даже тогда, когда некоторые из других собственных значений матрицы С лежат в -интервале. Если меньше, чем то наверняка первые к собственных значений матрицы должны быть больше, чем а возможно, что и некоторые другие. Вычисленная последовательность дает правильное число совпадений, соответствующее следовательно, на наш вопрос она должна дать правильный ответ «нет» даже тогда, когда получает неправильный действительный номер. Аналогично, если больше, чем то наверняка и все меньшие собственные значения матрицы должны быть меньше, чем Следовательно, мы должны получить на наш вопрос правильный ответ «да».

Итак, в этом процессе возможно следующее: или

(i) правильный ответ получается всегда, и в этом случае лежит в каждом из интервалов или

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

Рис. 3.

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

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

Итак, если мы останавливаемся на шаге, то центр последнего интервала таков, что