Последовательная линейная интерполяция

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

С другой стороны, если использовать последовательную линейную интерполяцию, то

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

так как

Соотношение (38.2) может быть записано в виде

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

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

в табл. 2 § 7, где первые пять значений лежат в области неопределенности, окружающей Несмотря на то, что расстояние пятого значения от корня в 219 раз больше подобного расстояния для первого, все вычисленные значения имеют один порядок величины. Из уравнения (38.1) видно, что поправка при одной итерации равна

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

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

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

Так, в табл. 2 значение при дано приблизительно с 15 значащими двоичными цифрами. Если мы возьмем это значение и выполним один шаг линейной интерполяции, используя в качестве второй точки интерполяции, интерполированное значение будет иметь 43 правильных двоичных цифры, т. е.