зациях приходится предусматривать возможность изменений в некоторых матрицах задачи (см. разд. 4.4.2),

Ясно, чго в случае знаконеопределеииой М решение системы (8.23) не обязательно будет направлением спуска. Надо помнить также, что из-за ошибок округления численное решение (8.23) может нарушать (8.22) и при положительно определенной, но очень плохо обусловленной М. В частности, такое случается в квазиньютоновских алгоритмах, если в качестве гарантии положительной определенности аппроксимации матрицы Гессе (илн обратной к ней матрицы) используются только условия типа (4.41). Чем это чревато, видно из примера 4.8.

Вместо (8.22) в хороших алгоритмах часто контролируется неравенство

(8.24)

где Eft-положительная величина. Оно может нарушаться даже для некоторых направлений спуска. Несоблюдение (8.24) обычно бывает связано с чрезмерно жесткими условиями нормального останова.

8.5. ОЦЕНКА точности ВЫЧИСЛЕНИЯ ФУНКЦИЙ ЗАДАЧИ 8-5.1. РОЛЬ ТОЧНОСТИ

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

Применять необоснованные оценки точности не следует. В то же время, если не используется дополнительная информация, для определения достаточно надежной оценки ошибки вычисления функции в точке, как правило, требуются значительные усилия. Имея это в виду, мы предлагаем следующий, хорошо зарекомендовавший себя на практике подход. Для рассматриваемой функции Ф строится хорошая оценка погрешности вьиисления в «характерной» точке (обычно в начальной точке поиска минимума); пригодные для этого процедуры описаны в разд. 8.5.2. Принимается некоторая модель поведения ошибки, и в соответствии с ней оценки для последующих точек получаются пересчетом по простой формуле (см. разд. 8.5.3).

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

Ф в точке X мы тюдразумеваем положительное число вл, такое, что

?/(Ф(1)) Ф(х)<е, (8.25)

где л: - машинное представление х. Таким образом, в включаются и ошибки подсчета Ф, и ошибки округ.пения х. (Далее будет предполагаться, что значения л: иФ далеки от границ переполнения и антипереполнения.) Заметим, что неравенство (8.25) ие определяет однозначно (будучи выполненньда при каком-то е, она сохранится и при всех больших Са), но нам это и не требуется. Даже в малой окрестности рассматриваемой точки действительная ошибка может принимать существенно разные значения; например, там могут найтись х, которые принадлежат представимому множеству машины и в которых Ф вычисляется без погрешности. Учитывать эти вариации нн к чему. Нам нужна величина е, которая была бы хорошей оценкой для ошибок подсчета Ф в любой точке вблизи х.

Мы хотим подчеркнуть, что определение (8.25) учитъшает только iwepeiuHocmu при вычислении Ф и никак не отражает точность, с которой математическая функция Ф отражает какую-то реальную зависимость. Если, к примеру, Ф согласуется с данными наблюдений только в трех старших десятичных разрядах, то это отнюдь не означает, что Сд должна быть порядка 10"". Само собой разумеется, ошибки моделирования тоже должны приниматься во внимание, ио уже на этапе содержательного анализа решения (этот момент подробнее обсуждается в разд. 7.3.1).

8.5.1.2. Роль оценок точности в оптимизационных алгоритмах.

Оценка погрешностей вычислений функций задачи может учитываться во многих модулях алгоритма оптимизации. В частности, она (i) встречается в критериях останова (разд. 8.2.3); (ii) определяет минимальное приемлемое расстояние между пробными точками в процедуре одномерного поиска (разд. 4.3.2.1 и 8.4,2); (iii) входит в формулы расчета конечно-разностных интервалов (разд. 4.6.1.1 и 8.6); (iv) используется прн выборе масштабирующих множителей (разд. 8.7).

В случаях (i) и (ii) рассматриваемая оценка нужна для определения момента, когда продолжение счета становится бессмысленным, поскольку вариации функции снизились до «уровня шума» (стали меньше, чем е). Таким образом, заниженное значение ел может привести к ненужным итерациям и остановке алгоритма с признаком отказа (см, разд, 8.4.3). С другой стороны, если взять неоправданно большой, появляется вероятность преждевременного прерывания счета (см. разд. 8.2.3.6).

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

зашш. По-настоящему ответственно к оценке ед приходится относиться тогда, когда рабочая точность машины низка.

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

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

(аорЬ)=(аорЬ) (Не), где IЕI не превосходит произведения ув, в котором у - число порядка единицы. Исходя из этого, можно оценгаать точность вычисления любой функции. Однако, поскольку больпщиство встречающихся в приложениях функций предполагает длинные цепочки вычислений, такой подход непрактичен.

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

e-ErIOWI. (8.26)

Однако это соотношение полезно только при шалыхъ er. Когда Ф-стандартная функция типа синуса, косинуса нли экспоненты. (8.26) обычно выполняется с Ед порядка еу.

к сожалению, при Ф, близких к нулю, e,j в (8.26), вообще говоря, не будет малой. Даже для очень простых функций относительная ошибка вычисляемого значения может оказаться очень большой. Возьмите, к примеру, Ф(л)=1-л; при х вблизи единицы (см. также разд. 2,1.5 и пример 8.3). Поэтому на практике разумно использовать в качестве нижней оценки е., величину

ед~Е„(1 + Ф). (8.27)

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

Функции с необычно малыми значениями е/,. Как уже было указано выше, для стандартных функций ф (д:) ошибка Сд может быть меньше, чем Ед. Другой важный класс функций, обладающих тем же свойством, образуют целевые функции задач о наименьших квадратах с малыми невязками. Это объясняется следующим образом. Рассмотрим

Ф(а;) = 2 Л(х).

считая, что для каждого «справедливо fl(h)~i i+i, где 6,.К е,.. Тогда, пренебрегая ошибками, возникающими при выполие-нии операций сложения и возведения в квадрат, получим

(8.28)

Отсюда видно, что при «ма.тх» е,. и /,. величина Bj, для Ф может оказаться намного меньше, чем вд. Мы подчеркиваем этот факт потому, что частое нспользова!не сумм квадратов с нулевыми невязками, в частности функции Розенброка (пример 4.2), в качестве тестовых функций иногда порождает заблуждение относительно точности, которая достижима для функтщй иного сорта.

8.5.2. ОЦЕНИВЛНИЕ ТОЧНОСТИ

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

Чтобы не писать громоздких формул, мы ограничимся изложением методов, которые позволяют оценивать точность вычисления дважды непрерывно дифференцируемых функций f(x) скалярного аргумента. (Эти методы можно использовать и в /г-мериом случае, если рассматривать поведение функции вдоле-некоторого направления р. II р II = 1.)

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

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

8.5.2.1. Оценивание точности, когда можно увеличивать длину машинного слова. Очень простой и эффективный метод оценки Вд доступен при условии, что имеется возможность вычислений с повышенной точностью. Она существует, например, если используемый ФОРТРАН-компилятор допускает спецификации типов переменных операторами REALmi.

Предположим, что минимизация будет проводиться с одинарной точностью, и пусть fl„ и ftb - результаты арифметических операций, выполняемых машиной в режимах «короткого» и «длинного» представлений чисел соответственно. Тогда для Определения можно вычнс1ить f в X и нескольких соседних точках в обоих режимах и найти максимум модуля полученных разностей значений, т. е. взять

tA~tnax\fl,,(fiXi))-fts(f(X;))\.

Просмотр нескольких (скажем, трех-четырех) точек необходим для повышения надежности (оценка по одной точке могла бы оказаться слишком оптимистичной: представьте, что / - относительно простая функция и X записывается в «короткое» слово без ошибки округления).

8.5.2.2. Оценивание точности с использованием производных.

Мегоды оценки Ед, описанные в этом разделе, предполагают доступность первой производной f.

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

Обозначим минимальную ощутимую вариацию х через Л„,„. Если \х\ есть число порядка единицы или больше, обычно задают формулой ft„i„ = e„x. При малых \х\ величина будет зависеть от задачи. Скажем, при е„=10-» и л-= Ю"" изменение X на 10-" для одних задач будет ощутимым, а для других нет. Во многих случаях минимальная ощутимая вариация х имеет порядок Вд,.

Точное значение f в возмущенной точке связано с / (л:) тейлоровским разложением f в окрестности х:

( + Л„д=(л;) + й„,„Г(1),

где Е-некое число нз диапазона х<?<хЧ-Л„1„. Если /(1)» ~ Г i"), то при сформулированном выше предположении двумя оценками вд будут

A~\f(x+h„,,)~f(x)\ (8.29)

Е.4~Л„,„Г(х). (8.30)

Использование ошибки конечно-разностной аппроксимации. При

очень малых значениях конечно-разностного интервала ошибка численного дифференцирования в основном определяется составляющей (ошибкой условий), которая отражает точность вычисления / (см. разд. 4.С. 1.1 и 8.6). Следовательно, зная эту ошибку, можно воспользоваться ею для оценивания Вд.

(8.32)

Рассмотрим конечно-разностное приближение ф производной /, вычисленное для интервала Л, который настолько мал, что ошибкой отбрасывания можно пренебречь. Коль скоро при этом ошибка условий окажется близкой к Вд/Л, получим

ч>(Л)-/(х)~Ед/Л (8.31)

п соответственно

ед~Лч>(Л)-Г(х).

Оценка (8.32) хороша только при условии, что выполнено (8.31), а (8.31) будет нарушено, если погрешности вычислений / в х и x+h близки по модулю и имеют одинаковый знак. Поэтому предлагается считать ф тремя способами (по правой, левой и центральной формулам; см. разд. 8.6.1) и по найденным ф, фв п определять Вд следующим образом:

Ед- шах Лф(Л)-Г(х)1. (8.33)

Фг. Фв. Фс

Ради повышения надежности оценки советуем вычислять (8.33) по меньшей мере для двух (малых) конечно-разностных интервалов. Подчеркнем еще раз: эти интервалы надо выбрать так, чтобы погрешности конечно-разностных аппроксимаций производной почти целиком определялись ошибками условий. Интересно отметить, что при ф=0 фюрмулы (8.33) и (8.30), по существу, совпадают.

Проиллюстрируем применение (8.32) на простом примере. Допустим, что используется машина с двенадцатиразрядной десятичной мантиссой и что 1д:, \f(x)\, /(х), Г(х) - величины порядка единицы, а Ед~10-". Тогда мантиссы вычнс.ттснных значений f(x), f(x+h) и &f=f(x+h) - f(x), получающихся при Л=10 будут

txaiiimcca. Af

Р«с. 8j. Схематическое изображение 12-разрядных маитисс операндов лроцедуры конечно-разностного оценивания точности вычисления /.

выглядеть так, как показано на рис. 8j. Ненадежные разряды помечены крестиками. По предположению относительно модулей f н ее производных в х восемь старших разрядов вычисленных значений /(X) и f(x+h) совпадут. Этн разряды помечены точками. После вычитания }(х) из f(x+h) останутся только четыре значащих разряда. Два младших будут ненадежными из-за неточности представления f, таким образом, в мантиссе hf будут только две правильные цифры (десять младших разрядов Д/, помеченные крестиками ненадежны).