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

[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]

Все сказанное выше можно было бы повторить применительно к ошибкам аппроксимации f (х) по левой конечно-разностной формуле

с тем единственным отличием, что Е 6 U - Л, х].

8.6.1.2. Аппроксимация по центральным разностям. Первую производную можно аппроксимировать и по центральной конечно-разностной формуле

4>с(/. 0

= 5Й

(8.40)

1,п R vroM случае ошибка отбрасывания составит ГлЧГ"(и)1 rnul\xXx+hlaouiu6, условий будет огра-

достигается при Л, равном

1Л"(м)1

Если выполнено (8.39) и для всех точек нз Ix-h, x+h] справедливо отношение 0{\f\)=0(\f"\), то получим

hc~V- (8-41)

Важно подчеркнуть, что (8.41) реализуется только прн сделанных предположениях.

8.6.1.3. Разность второго порядка. Для аппроксимации /" обычно используют следующую формулу;

Ф (f, Л) =-

(8.42)

°ГаЖ-?ГвХк=я

-™ Г р= н.г внс+:е:г:иа.=ф

Гьш:, ?ем~+(/42)ГгЧг1)1. Минимум этой суммы дости-гается при Л, равном

(8.43)

Если f удовлетворяет (8.39) н 0 ( f ) = 0 ( Г" I) Д™ чек из [x-h, x+h], то е.

8.6.2. ПРОЦЕДУРА АВТОМАТИЧЕСКОГО ОЦЕНИВАНИЯ КОНЕЧНО-РАЗНОСТНЫХ ИНТЕРВАЛОВ

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

8.6.2.1. Исходные соображения. В основе алгоритма лежит оценка (6.37), но поскольку f° и I неизвестны, предполагается аппроксимация f" (У с использованием формулы (8.42). Это в свою очередь означает, что должен быть найдет интервал Лф, позволяющий получить разумную оценку Ф. Затем в качестве искомого приближения «оптимального» h для правой конечно-разностной формулы берется

Лг=2 /

(8.44)

Такой способ выбора hp оправдан, если (1) между f"(x) н Г (У нет большой разницы (т. е. вторая производная меняется вблизи х не слишком быстро) и (и)Ф достаточно хорошо приближает/"(х). Имея в виду назначение Ф, можно довольствоваться совпадением у Ф и Г{х) лишь старшего разряда.

При поиске Лф учитывается, что ошибка отбрасывания в (8.42) ограничена сверху величиной, которая с ростом h, вообще говоря, возрастает, а ошибка условий при увеличении Л имеет тенденцию убывать. Формально поиск выглядит как перебор пробных значений {hj). Качество соответствующих Ф определяется по вычисляемым оценкам относительных ошибок условий:

С(Ф).

, 4ед

8.45)

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

Критерием приемлемости Ф считается принадлежность С(Ф)отрезку [0.001, 0.11. Зачем нужно ограничивать С(Ф) сверху, понятно без пояснений. Что же касается требования, чтобы величина С (Ф) была не меньше, чем 0.001, то его надо трактовать как неявный способ ограничить ошибку отбрасывания (напомним, что ошибки отбрасывания и условий, грубо говоря, связаны обратной пропорцией).



Если оценка С(Ф), отвечающая очередному Л;, оказывается неудовлетворительной, следующий пробный интервал берется больше илн меньше, чем Л, в зависимости от того, какая граница нарушена. При (?(Ф)>0.1 интервал увелич1шаегся, а прн С(Ф)<0.001 уменьшается. Выбрана простейшая схема, в которой hi либо умножается, либо делится на 10. Можно было бы предложить и более хитроумные правила пересчета hi, учитывающие конкретный вид зависимости (8.45). Однако подобные правила всегда опираются на какие-то дополнительные предположения (например, о постоянстве порядка Ф при изменениях /z), а они могут не выполняться.

В двух сгггуациях алгоритм не сумеет обеспечить подходящего значения С(Ф). Во-первых, ему ие удастся добиться неравенства С(Ф)0,1, если Ф при всех h будут почти нулевыми. Так случается, когда функция / почти постоянна, почти линейна или f (у-л) нечетна по у. Во-вторых, не исключено, что из-за слишком больших Ф даже при очень близких к нулю Л не будет выполняться неравенство С (ф) 0.001. Это возможно, когда х похожа на точку излома первой пропзво.аной.

Для контроля пригодности результатов применения алгоритма предусмотрено сравнение оценок f (х) по правой и центральной конечно-разностным формулам с интервалами и ha, соответственно. Если эти оценки получаются совсем разными, ни той ни другой доверять нельзя.

Начальный пробный интервал Ло определяется в предположении, что модули значений х, Цх), и f"(x) связаны следукяцим образом:

о(,Г1)оГ).

(8.46)

где ш>0 и г1>0. Параметр ш введен в числитель правой части (8.46), чтобы не было необходимости сггдельно рассматривать случай, когда модуль Щ очень мал; из аналогичных соображений в знаменатель введен параметр i\. В остальном вид правой части (8.46) согласован с характером зависимости второй производной от выбора масштабов функции и аргумента. Поскольку гипотеза о существовании связи (8.46) используется только при вычислении Ло, на значении окончательного интервала /to она практически не отражается; однако эффективность алгоритма при разных m и т] может быть разной. На основании своего опыта мы рекомендуем oj-1 и ti=l.

Подстановкой (8.46) в (8.38) получается интервал h =• - 2 (II-fix 1) (Гд/(а-1-П)- Если (8.46) действительно имеет место, отвечающая Л ошибка условий в чр будет блпзка к «оптимальной». В то же время формула (8.42) с Л = Л даст относительную ошибку С (ф) порядка единицы (т. е. у Ф не будет ни одной правильной цифры). Исходя из этого предлагается брать Л„=10Л, что позволяет рассчитывать на С(Ф) порядка 0.01

(поскольку С(Ф) обратно пропорциональна Л"). Для хорошо отмасштабированной (в смысле разд. 8.6.1.1) функции f значение С (Ф), отвечающее Л, попадет в требуемый диапазон, так что другие интервалы рассматривать не придется.

8.6.2.2. Формулировка алгоритма. Описанный ниже алгоритм FD вьтчнслнет интервал hp, который должен обеспечивать хорошее качество аппрокспмацпн f по правой конечно-разностной формуле, а также величины ч (оценку f (х)), Ф (оценку f"(x)) и £р (верхнюю границу погрешностн оценки (р). Число итераций ограничивается параметром К. На тот случай, когда после просмотра К пробных интервалов подходящего Лф пачучено не будет, организуется хранение Л - минимального из тех Л;, для которых оценки относительных ошибок условий в приближениях [(х) по правой и левой консч-но-разностиы.м формулам имеют приемлемые значения (ие превосходят 0.1). Таким образом, при каждом Л,- вычисляются

C(<ff).

(Если qг пли ср оказывается нулем, в качестве соответствующей С берется произвольное большое число.) Формально алгоритм определяется так:

Алгоритм FD (автоматическое, оценивание hp, f и (") FD1. [Инициализация] Зафиксировать ю, i\ и К- Вычислить f(x) и Л„=10Л, где

Л = 2(,1 + 1х) (8.47)

Присвоить ftf-о, Л-.--1. Вычислить f(x+h„), f (х-h„),

ff(h„), Фв(Л„), Ф(Л„), C((Pf). СШ, С(Ф).

FD2. [Проверка пригодности начального интервала.] Если тах{С(ф,,), С((ре)}<0.1, присвоить h, - h„. Еслп0.001< С(Ф)0.1, присвоить ho*-h„ и перейти к шагу FD5. Если С(Ф)<0.001, перейти к шагу FD4; иначе перейти к шагу FD3.

FD3. [Увеличение Л.] Присвоить k-k+l, Л10Л ,. Вычислить соответствующие конечно-разностные оценки и связанные с ннмн относительные ошибки условий. Если Л < О и тах{С(ф;,), С(ф5)}<0.1, присвоить Л-с-Лц. Если С(ФХ0.1 присвоить Лф--и перейти к шагу FD5. Если k = K, перейти к шагу FD6; в противном случае, повторить шаг FD3.

FD4. [Уменьшение Л.] Присвоить kk+l и Лt-Л.,/10. Вычислить соответствующие конечно-разностные оценки и



связанные с ними относительные ошибки условий. Если С (Ф) > 0.1, присвоить Лф Л , и перейти к шагу FD5. Если max (C((pf), С(ф8)} <0.1, присвоить i-Л,;. Еслн 0.001 < <С(ФХ0.1, присвоить Лф*-Ли и перейти к шагу FD5. Если kK, перейти к шагу FD6; в противном случае повторить шаг FD4. FD5. [Расчет оценки оптимального интервала.] Определить hp по формуле (8.44) и вычислить ip<pp{hf), ttihc),

(8.48)

и модуль £ = ч1-ф,, (Лф) . Если max 0.5, выдать

сообщение об успешном завершении счета; иначе выдать сообщение об Отказе. Foe. [Разбор ситуации, когда искомого Лф получить не удалось]. Если Л., < О (т. е. для всех h,, выполнялось неравенство тах{С(срр), С(<fg)\ > 0.1), то похоже, что f почти постоянна, и тогда присвоить hfh (8.47), ф О, Ф<-О и Если С(Ф)>0.1 и h,>0, то похоже, чго f

нечетна или почти линейна, и тогда присвоить hf-h, Ч>Ч>(М, Ф-0, а Ер вычислить по формуле (8.48). Иначе похоже, что /" быстро растет с уменьшением Л (поскольку С (Ф) < 0.001 для всех Н, и тогда присвоить hp.i-hK, tf4f{hf), ф<-Ф(Лр) а Ер вычислить по формуле (8.48). Во всех трех случаях выдать сообщение об отказе.

8.6.2.3. Численные примеры. Описанные ниже эксперименты с алгоритмом FD проводились на IBM 370, прпчем вычисления осуществлялись с одинарной точностью (Е;„л;.9375х Ю"). Параметры алгоритма во всех случаях были таковы: Л = 6, ш=1, ц=\. Значения определялись процедурой, обсуждавшейся в разд. 8.5.2.3.

Пример 8.4. Когда алгоритм FD применялся к функции из примера 4.9 (разд. 4.6) при х= \ и e = .4х 10"?, относительная ошибка С(Ф), отвечающая интервалу Л„ (.398x10-), составила .416x10"=, т. е. оказалась меньше установленной нижней границы. После деления Л„ на 10 значение С {Ф) стало равным .424x10" и, соответственно, был зафиксирован интервал ha,--=K. Подстановка Лф в (8.42) дала ©=.238294x10» и это - хорошая оценка f" (х) = .242661 х Ю». По Ф были вычислены /!f=.819x10-» и фр(Af) = .955636X 10". Относительная погрешность полученной оценки ifp{hp) равна .807x10-". Заметим, что выбранное значение hp вполне согласуется с данными табл. 4а н что достигнута максимальная точность, на которую можно надеяться при использовании шестиразрядной арифметики.

Пример 8.5. Второй тестовой функцией послужила f (х) = (X-100)» + 10-» (X-300)=.

Рассматривалась точка х=0, где е, = .9х10-. Истинными значениями f(x) и Г(х) являкл-ся .997300x10 и .199820x10, так что связь (8.46) отсутствует. Поскольку начальный интервал Л„ оказался слишком малым, алгоритму пришлось дважды увеличить Л прежде, чем получилась приемлемая относительная ошибка С(Ф). В результате были зафиксированы Ф = . 199567 х 10, Л;,= .134 и фр=-.199632X 10". В тоже время, точное значение /(X) равно -.199730x10». Таким образом, относительная погрешность оценки составила .49x10"».

Пример 8.6. Как уже отмечалось в разд. 8.6.при близких к нулю I f I правая конечно-разностная формула дает плохую относительную точность приближения f, даже если ft выбирается наилучшим образом. Чтобы проиллюстрировать это, мы применили алгоритм FD к f{x)=x + 3x-10х в точке х= .99999, где Ед = 7х10-5 и f(x) = -.180244x10-». Требования к С (Ф) удовлетворились при Л = Л„ и соответствующая оценка ф = . 180008 х Ю» оказалась вполне приемлемой (/" (х) = .179999 х 10"). Отвечающее ей значение hp равно .125x10"". При этом ф,(Лp) - .913х ю"», т, е. отличается от (х) почти на два порядка (хотя Л,,-хорошее приближение оптимального интервала). Центральная конечно-разностная формула с hha, тоже определила неудовлетворительную оценку: ф (Лф) = -.357 х 10"=. Поскольку ф {hp) и фс (Лф) оказались совершенно разными, алгоритм остановился с признаком Отказа.

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

Основываясь на высказанных положениях, мы рекомендуем обращаться к процедуре пз разд. 8.6.2.2 один раз, в «типичной» точке (как правило, в xj, и сохранять полученные интервалы неизменными на всех последующих итерациях. Возьмем, к примеру.



[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.0008