Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [ 73 ] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

Деление А/ на h внесет дополнительную ошибку лишь в последний разряд. Следовательно, (рр будет отличаться от / (х) на величину порядка 10". Так как ft=10-", в соотвегствии с (8.32) получим (правильную) оценку

eA~Aqv - / (X) I = 10-qO-==10-».

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

Допустим, что f подсчитана для ряда точек {х,-[, сгенерированных по правилу Xi = x + ih, причем -малая величина. По определению вычисленные значения, буАУТ связаны с f (х,.) следующим образом:

?;=/(х.)--6,/(х,) + е,.ед, (8.34)

где I в, К 1. Можно составить таблицу разностей (см. разд. 2.3.5), образовав ее первый столбец из чисел а каждый последующий из разностей элементов предыдущего. В силу линейности разностного оператора в (А4 1)-м столбце получим Д*/,. = Д*Д.--Д*г,.

Как было указано в разд. 2.3.5. справедливо приближенное равенство Д"/»/i*f">. При этом, если величина h достаточно близка к нулю и у.довлетворяет необременительным требова-ния,м, модуль I ft*p становится очень малым уже при умеренных k (скажем, А 4). Следовательно, высшие разности вычисляемых значений / почти целиком будут определяться ошибками 6,-.

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

(8.35)

Ik!)

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

8.5.2.4. Численные примеры. В этом разделе представлены результаты применения вышеизложенных методов в конкретном случае.

Пример 8.3. Для тестирования была выбрана функция

/(x)=e+x»-Зх-1.1.

Вычисления проводились с одинарной точностью на IBM 370 (ew= 16-?ж9.537х 10"»). Рассматривались две точки: Xi=10, в которой / (х,) = 2.29954 x 10, f (Xi) = 2.23235x 10*, и х, = 1.115, в которой (х,) = -9.23681x 10-,Г(х,) = 3.77924 (все значения

I округлены до шести значащих цифр). Вторая точка специально подобрана так, чтобы значение функции было близким к нулю, -

1 хотелось продемонстрировать работу методов в ситуации, когда Ер в (8.26) существенно превосходит ед}-

Начнем с результатов применения методов разд. 8.5.2.2 (производные f счэтались с одинарной точностью). В х истинное значение ошибки подсчета f равно 2.5 х Ю"». Оно меньше «стандартной» нижней границы е (8.27) (ел = 2.2х Ю"), но это не должно удивлять-ведь известно, что действительные оишбки могут сильно различаться даже для очень близких точек. Когда в качестве конечно-разностного интервала было :задано число 1.049x10"?, опенка е, полученная по формуле (8.3.Ч), составила 3.7x10-; при конечно-разностном интервале 1.049x 10- та же формула дала оценку Сд, равную 6.1x10-. Формулы (8.29) и (8.30) дали 2.13x10- и 2.11 х Ю-соответственно; эти оценки явно завышены, что объясняется большим значением производной / (X,).

Для Xj действительным значением ошибки вычисления f является 1.4x10"; оно превосходит «стандартную» нижнюю границу Ед (eJ = 9.6x 10-). Относительная ошибка в х, равна 1.5x10-. Прн конечно-разностном интервале 2.017x10-" формула (8.33) дает в Xj оценку е, равную 2.9x10". Если же судить только по (рр (т. е. воспользоваться (8.32)), то получится величина порядка 10"; это подтверждает целесообразность операции взятия максимума по результатам применения трех ко-нечно-разностиых формул. При интервале/i = 2.017x №" опенка е, получающаяся по формуле (8.33), составила 2.7x10"". Формулы (8.29) и (8.30) дали 4.02 х Ю"» и 3.81 ;: 10" соотвегственно; в данно.м случае большого отличия от е из (8.33) нет.

Перейдем теперь к методу из разд. 8.5.2.3. Столбцы разностей, генерируемые для опорной точки х, при h=U1, частично показаны в табл. 8d. В четвертом и пято.м столбцах наблюдается ожидаемое чередование знаков. Оценки е, вычисленные

по формуле (8.35) при ft = 4.....7, равны 1.02 х lOS 6.40 х 10"»,

6.30x10" и 5.93x10-. При этом максима пная из действительных ошибок в значениях J,, по которым строилась таблица.



2 J00 X 10

2.2-1 X 10=

2-вг X10"

-1.66 X 10-=

+5.08 X 10~

-я.авх 10-=

2.322 X 10*

2.27 X 10

2.25 X 10"

+3.52 X 10-3

-1J0 X 10=

-J-1.21 X Ю-

2.3-i5 X 10

2.29 X 10"

2.28 X 10"

~7Ш X 10-3

+7.В1 X 10-

-Ы5Х10-

2.368 X Ю-"

2Л1 X 10="

2Л7 X 10"

+7ЛЗ X

-e.fii X10-"

-г8.Э) X 10-*

2.301 X 10

2.33 X 10

2.34 X Ю*

+3.91 X 10

-1-1.50 X 10-5

3.52 X 10-2

2.4UX 10

2.36 X Ю-*

2.35 X 10°

+1.05 X Ю-"

-I.B5X10-*

+9.Т7 X 10-=

2.«РХ 10

2.38 X 10-

2.37 X 10"

+7.81 X 10-=

-1 fif 10"

составила 2.5x10-, а средняя ошибка равна 8.1x10 Таким образом, полученные оценки можно признать вполне удовлетворительными. Интересно отметить, что в данном примере значения в,- из (8.34) не были равномерно распреде.чены на отрезке [-1, 1], так как ошибки вычисления f во всех точках вблизи X, положительны. Однако этого и не требуется-нужно только, чтобы ошибки не коррелировали и имели одинаковые вариации.

Метод из разд. 8.5.2.3 был опробован н в точке х. Разности, подсчитанные при /1=10-=, сведены в та6л.8е. Здесь мы видим.

Таблица 8е. Таблица разностей для примера 8.3 в Хг при Л =10"

д-/.-

X 10"

3.78 X 10-3

1.24 X 10-

-4.77 X 10-е

+9.51 X

-2.00 X 10-"

-5.456 X 10-3

3.80 X 10-

7.83 X 10-е

+4.77 X 10-*

-1Л5 X 10-

+2.1П X 10-

-i.eai X10"

3.80 X 10-3

1.24 X 10-S

-5.72 X 10-е

+1.14 X 10-6

-1.SI X 10"»

2,1 И X 10-3

3.82 X 10-3

6.68 X 10-"

+5.72 X 10-е

-7.63 X 10-е

+5.78 X 10-е

5.956 X 10-

3.82 X 10-3

1.24 X 10-=

-1.91 X 10-е

-1.В1 X 10-е

+1.14 X 10-"

9.-77 X 10-3

3.63 X 10-3

J.05 X Ш-"

-3.82 X 10-и

+9.51 X 10-е

X 10-5

1.361 X ю-

3.8-1 X Ю-Э

6.68 X 10-*

+5-72 X 10-е

-1.05 X 1D-S

+2Л0 X 10-"

что, хотя элементы в столбцах 4 и 5 близки между собой по модулю, чередование знаков наблюдается только в группах из четырех-пяти элементов, но не в столбце в целом; такая картина типична. Для ft = 4, 7 значения еЙ (вычисленные по формуле (8.35)) таковы; 1.03x10-, 1.08x10-». 1.10x10-» н 1.07х 10"". Максимальная среди действительных ошибок в равна 5.1x10-, а средняя действительная ошибка составила 4.1х10-«; таким образом, оценка е, снова получилась достаточно точной. Как и X,, точка х, характерна тем, что вблизи нее вычисленные значения f всегда превышают истинные.

Наконец, для х, ставился эксперимент, когда все величины считались с двойной точностью и лишь значения f вычислялись с одинарной. (На IBM 370 двойной точности соответствует Ед,= 16-1= «2.22x10-».) Цель состояла в том, чтобы показать, как сработает метод из разд. 8.5.2.3, если намного больше

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

(8.35) дала для А = 4..... 7 оценки в, равные 1.14x10-"

1.20x 10-, 1.25х10-« и 1.29x10-. Как и ожидалось, они практически те же, что и при реализации метода с одинарной точностью.

8.5.3. ПЕРЕОЦЕНИВАНИЕ ТОЧНОСТИ

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

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

Первое, что приходит на ум,- принять гипотезу постоянства относительной ошибки и, оценив вд в л:„, впоследствии пользоваться формулой

ей = (%).

Однако в общем случае этот подход неправомерен: при очень малых I /1 соответствующие оценки е, могут оказываться сильно заниженными. Здесь уместно напомнить, что для многих функций величина вд не бывает меньше стандартной нижней границы е\ (см. разд. 8.5.1)

Мы рекомендуем модель поведения Вд, в основе которой лежит предположение о том, что для всех х «число правильных цифр» в значении f будет одинаковым, причем при малых \1\ предлаеаетхя учитывать старшие нули после десятичной запятой. Считается также, что это число не может превосходить количества разрядов, выделяемых в машинном слове для записи мантиссы. Соответствующая формула расчета оценок такова:

ед (X) = (1 И-1 f (X) I) max (е„. j ) (8.36)

Проиллюстрируем работу (8.36) на функции из примера 8.3. Прн Х,= 10 стандартная нижняя граница Вд больше, чем вычисляемые обычными способами оценки е, и поэтому для х по формуле (8.36) получим Вд (х,) = e„ (1(х) ) = 9.6х 10".



Если же взять = 1.115 и положить (х„) = 1.2 х Ю"» (примерно такое значение дает метод из разд. 8.5.2.3), то для формула (8.36) дает оценку е, равную 2.7 х Ю".

Замечания и избранная библиография к разделу 8.5

Тема оценивания точности обсуждалась Стюартом (1967), Брен-том (1973а), Кертисом и Райдом (1974). Прием, описанный в разд. 8.5.2.3, соответствует методу Хэмминга (1962, 1973). Подробнее этот метод разобран Лайнессом (1977а).

8.6. ВЫБОР КОНЕЧНЫХ РАЗНОСТЕЙ

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

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

Ради простоты изложения мы ограничимся разбором проблемы выбора интервала для расчета оценки производной функции f(x) одной переменной; многомерный случай кратко обсуждался в разд. 4.6.1.3. Будет предполагаться, что точность вычисления f известна (см. разд. 8.5).

8.6.1. ОШИБКИ КОНЕЧНО-РАЗНОСТНЫХ ПРИБЛИЖЕНИЙ; ХОРОШО ОТМАСШТАБИРОВАННЫЕ ФУНКЦИИ

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

8.6.1.1, Аппроксимация по правым разностям. Просуммируем результаты разд. 4.6.1.1, касающиеся ошибок аппроксимации f (х) по правой конечно-разностной формуле

4f(/, h).

fix+h)-f{x) h

где Л>0. Отличие вычисляемого значения фг от f (х) в основном определится суммой ошибки отбрасывания (игнорируются слагаемые тейлоровского разложения порядков выше первого) и оишбки условий (значения / вычисляются с погрешностями). Эта сумма не превосходит

-Г(Е)-1-е„

(8.37)

где Е - некоторое число из отрезка [х, х-ЬЛ], а Ва - верхняя граница погрешностей вычисления / в х и в х+Л (см. разд.8.5.1). Минимум (8.37) достигается при Л, равном

(8.38)

причем минимальным значением (8.37) будет 2(/e f" (е) . К сожалению, ни производная /", ни точка % не известны, и поэтому для оценки hp на основе (8.38) нужны дополнительные предположения.

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

(8.39)

Если к тому же для всех точек отрезка [х, x-\-h\ справедливо соотношение О(\f\) = 0i\f"\), то из (8.38) будет следовать

Наконец, при 0(/)=0(/) можно утверждать, что «минимальная» относительная ошибка аппроксимации / (х) имеет порядок Ve-n- Это утверждение согласуется с бытующим среди программистов мнением, что при оптимальном конечио-разностном интервале количество правильных цифр в ц>р оказывается вдвое меньше, чем в /.

Мы подчеркиваем, что предьщущее высказывание справедливо только при сделанных предположениях относительно значений / и ее производных. Отметим также, что если модуль f мал по сравнению с 1/1 и \f"\ (как обычно бывает вблизи локального минимума /), то относительное уклонение qj от f может оказаться большим, даже когда конечно-разностный интервал выбран наилучшим образом.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [ 73 ] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0011