§ 4.2. Обусловленность задачи вычисления корня

Пусть корень уравнения (4.1), подлежащий определению. Будем считать, что входными данными для задачи вычисления корня являются значения функции в малой окрестности корня. Так как значения будут вычисляться на ЭВМ по некоторой программе, то в действительности задаваемые значения являются приближенными и их следует обозначать через Ошибки в могут быть связаны не только с неизбежными ошибками округления, но и с использованием для вычисления значений функции приближенных методов. К сожалению, нельзя ожидать, что в окрестности корня относительная погрешность окажется малой. Достаточно обратиться к примерам 2.11 и 3.11, чтобы установить, что для чрезвычайно простых функций окрестности корней к значения этих функций не могут быть найдены с малой относительной погрешностью. Реально рассчитывать можно лишь на то, что малой окажется абсолютная погрешность вычисления значений функции.

Будем предполагать, что в достаточно малой окрестности корня выполняется неравенство где граница абсолютной погрешности. Сама погрешность корня ведет себя крайне нерегулярно и в первом приближении может восприниматься пользователем как некоторая случайная величина. На рис. 4.3, а представлена идеальная ситуация, отвечающая исходной математической постановке задачи, а на рис. 4.3, б — реальная ситуация, соответствующая вычислениям значений функции на ЭВМ.

Рис. 4.3

Если функция непрерывна, то найдется такая малая окрестность корня х, имеющая радиус в которой выполняется неравенство

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

Будем называть этот интервал интервалом неопределенности корня х. Найдем оценку величины Пусть корень простой. Для близких к х значений х справедливо приближенное равенство

Поэтому неравенство (4.9) примет вид откуда получаем

Следовательно,

Рис. 44

Здесь число которое в рассматриваемой задаче играет роль абсолютного числа обусловленности. Действительно, если корень уравнения то и тогда выполнено неравенство

Заметим, что радиус интервала неопределенности прямо пропорционален погрешности вычисления значения Кроме того, возрастает (обусловленность задачи ухудшается) с уменьшением т. е. с уменьшением модуля тангенса угла наклона, под которым график функции пересекает ось (рис. 4.4, а, б).

Если же (т. е. корень кратный), то формула (4.10) уже не верна. Пусть кратность корня равна Тогда в силу формулы Тейлора справедливо приближенное равенство

в правой части которого все слагаемые, кроме последнего, равны нулю. Следовательно, неравенство (4.9) имеет вид

Решая его, получаем аналогично (4.10) оценку радиуса интервала неопределенности:

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

Отметим, что не может быть меньше величины погрешности представления корня х в ЭВМ.

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

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

обычно бывает меньше единицы то появление при некотором значения свидетельствует, скорее всего, о начале "разболтки" — хаотического поведения итерационной последовательности. В этой ситуации вычисления имеет смысл прервать, чтобы выяснить причину явления и принять правильное

решение. Лучшим из полученных приближений к решению следует считать, конечно, Использование для контроля вычислений величины (4.12) называют часто правилом Гарвика.