§ 9.2. Обусловленность задачи минимизации

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

Рис. 9.7

Интервал будем называть интервалом неопределенности точки х локального минимума.

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

Оценим минимальное расстояние между точками начиная с которого заведомо будет выполнено неравенство т. е. точка х перестанет попадать в интервал неопределенности. Имеем

Следовательно, и неравенство выполнено, если Таким образом,

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

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

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

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

Предположим теперь, что для отыскания точки локального минимума можно использовать вычисляемые каким-либо образом приближенные значения производной функции Как уже отмечалось в § 9.1, в рассматриваемом случае задача минимизации эквивалентна задаче отыскания корня х нелинейного уравнения Из результатов § 4.2 вытекает, что последняя задача обладает значительно

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

Сравнение (9.4) с оценкой (9 3) показывает, что алгоритмы, использующие для отыскания решения х уравнения (9.1) вычисление значений производной, могут достигать более высокой точности, чем алгоритмы, использующие для минимизации функции только вычисление ее значений.

Пример 9.5. Оценим радиус интервала неопределенности для каждой из точек и локального минимума функции в случае, когда вычисление функции производится на -разрядной десятичной ЭВМ.

Заметим, что и 0.14. Так как для используемой ЭВМ , то в малой окрестности точки верхняя граница абсолютной погрешности вычисления приближенно равна . Аналогично,

Вычисляя значения второй производной при получаем силу формулы (9.2) радиусы интервалов неопределенности оцениваются следующим образом:

Следовательно, точку можно найти с большей точностью, чем точку если использовать сравнение вычисляемых на -разрядной десятичной ЭВМ

значений функции При этом каждую из точек можно найти с точностью но вряд ли удастся найти с точностью

Пример 9.6. Пусть теперь точки и локального минимума функции ищутся как решения нелинейного уравнения

Оценим в этом случае радиус интервала неопределенности для каждой из точек если вычисления ведутся на той же ЭВМ, что и в предыдущем примере.

Оценим сначала границу абсолютной погрешности вычисления производной исходя из приближенного равенства

Тогда

На основании формулы (9.4) имеем

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