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

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

оказываются тесно связанными (хотя и неэквивалентными). Во многом близки н пути их решения, причем мето;1В1 поиска нуля несколько проще. С них мы и начнем. Точнее говоря, речь пойдет о задаче отьгскания на конечном отрезке такой точки х*, в которой некоторая нелинейная функция f(x) принимает нулевое значение и меняет знак.

Первый вопрос, возникающий в связи с рассматриваемой задачей,-это вопрос о том, что называть ее численным решением. Машина считает с ограниченной точностью и оперирует конечным набором представимых значений аргумента х. В этом наборе скорее всего не найдется такого х, для которого вычисляемое значение ft(f(x)) величины f(х) было бы нулевым, т.е. рассчитывать иа точный нуль бессмысленно. Значит, надо довольствоваться тем, что найден отрезок [а, Ь], удовлетворяющий условиям

f(a)f(b)<0. a-i<6,

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

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

4.1.1.1. Метод деления пополам. Этот метод состоит в последовательном сокращении интервала неопределенности на основе сопостаеления знаков функции. Допустим, каким-то образом выявлен исходный интервал la, Ы, в крайних точках которого знаки f различны, т. е. f(a)/(b)<0. Вычислим значение f в середине этого интервала. Еслн оно окажется нулевым, задача решена; в противном случае заменим а или b средней точкой в зависимости от того, совпадает ли знак функции в ней со знаком f (а) или f (b) соответственно. Тем самым интервал неопределенности будет уменьшен вдвое. После этого вычисляется значение f в новой средней точке и т. д. Работа описанного алгоритма проиллюстрирована на рис. 4а. ч

Деление пополам обеспечивает локализацию х* с любым допус- 1 ком 6, если только точности вычиаения f будет достаточно для правильного определения ее знаков. При этом .чокалнзация корня иа отрезке длины, не превосходящей 6, достигается вычислением около logs ((Ь-а)/6) значений функции / в разных точках. Теоретически деление пополам является «оптимальным» алгоритмом поиска нуля для функций, меняющих знак на \а, Ы. Точнее говоря, ему отвечает минимальная гарантированная оценка длины интервала неопреде.

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

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


Рис, 4а. Первые три точки последовательности, генерируемой методом деления пополам.

вательносги интервалов неопределенности. При делении пополам эта последовательность сходится линейно, причем асимптотический параметр ошибки равен Vj.

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

Если f дифференцируема, первым претендентом на роль модельной функции / для (А+1)-й итерации будет прямая, касательная к f в текущей точке Xj. Если производная / (х) не равна нулю, эта прямая пересечет ось абсшкс в точке

iW. (4.1)

Итеративную процедуру, заданную формулой (4.1), принято называть мсетодом Ньютона для поиска нуля. Ее геометрическая интерпретация ясна из рис. 4Ь, В отличие от деления пополам, где результатом каждого шага является новый интервал неопределенности, итерация метода Ньютона дает новую оценку корня. Что же каса-




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

Некоторые популярные и на первый взгляд не имеющие ничего общего с методом Ньютона вычислительные процедуры в действительности оказываются его Цх) реализациями. Например, формулал:й+,=/2(д:ь+а/лГй) правила «подели и осред-ни», с помощью которого школьников учат вычислять Ка, есть не что иное, как преобра.зоваиная формула ньютоновской итерации для поиска нуля функции f (х)=х-а.

Метод Ньютона фактн-Рис- 4Ь. Итерация метода Ньютона для по- чески ИСХОДИТ из предполо-иска нуля функЩ1и /М; очередная точка жения о ТОМ. Что при оцени-

"с"ат=к7(Г:ГГоГк>ТГсс."" вании корня фунГ<цни f ее

можно считать «похожей на линейную». Поэтому естественно ожидать, что, если такое «сходство» действительно имеет место, он будет работать хорошо. И в самом деле, когда производная f (х*) не равна нулю и начальная точка х «достаточно близка» к X* (т. е. Хо находится в той окрестности х*, где f хорошо аппроксимируется линейной зависимостью), метод Ньютона сойдется к X* квадратично (см. разд. 2.3.6).

Пример 4.1. При вычислении по методу Ньютона величины 14 с нача.пьиым приближением х,, = 2.5 получаются ошибки {4-4}, ft = 0, .... 4, равные 2.25,. 2025, 2.439х Ю"», 3.717x10" и 8.0x10-1" (расчеты проводились с шестнадцатиразрядной точностью).

Основные трудности с методом Ньютона возникают из-за того, что его образцовая скорость сходимости локальна, т. е. реализуется лишь в малой окрестности искомого корня. Если же точка Хд недостаточно близка к X*, этот метод может безнадежно ра.зойтись. Например, в изображенном на рис. 4с случае ньютоновское приближение оказывается абсолютно бессмысленным. Кроме того, поскольку ньютоновский шаг ие определен, когда производная f (Xi,) равна нулю, его реализация при «малых» f(x) всегда будет связана с численными трудностями. Таким образом, метод Ньютона следует применять с осторожностью: далеко не .пюбую задачу на поиск нуля удастся решить с его помощью.

4.1.1.3. Методы секущих и ложного положения. В числе недостатков метода Ньютона помимо прочего называют необходимость

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


Рис. 4с. Случаи расходимости метода НьЕотоиа.

можно каждый раз брать прямую, проходящую через точки, полученные на двух предыдущих итерациях. По существу это означает замену в ньютоновской формуле производной f (х,,) ее конечно-разностной аппроксимацией (f-fk-i)Hk-xi), г.де через обозначено f(x,,). Тем самым мы приходим к процедуре поиска нуля, которая задается формулой вида

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

Если производная f (х) не равна нулю и точки х„, х достаточно близки к X*, метод секущих сойдется сверхлинейно со скоростью 1.6180. Таким образом, он может работать весьма эффективно. Так, применение его в примере 4.1 с Хп=1. Xj = 2.5

дает для ft = 2.....7 ошибки \х1-Ц, равные -5.51x10-,

-6.53x10-% 2.44x10-», -I.OOxlO- -1.53x10-" (расчеты проведены с шестнадцатиразрядной точностью).

К сожалению, метод секущих нередко расходится, и это возможно из-за того, что при совпадении знаков и f j i его очередная точка попадает вне отрезка, соединяющего две предыдущих. Если бы



знаки fk и ff. i всегда различались, текущая оценка корня обязательно ложилась бы между предыдущими, и тогда сходимость была бы гарантирована. Данное условие можно обеспечить ценой несложной модификации метода - достаточно слегка изменить правило выбора из тройки ЛГ4+,, Xft, Xj.i пары точек для построения следующей линейной аппроксимации. Вместо того чтобы из двух точек


Рис. 4d. Пример медленной сходимости метода ложного ноложения.

Хл, х,, 1 всегда оставлять первую, надо оставлять ту их них, в которой знак функции f отличен от знака /л ц. Соответствующую процедуру называют методом ложного положения. Этот метод начинает работать с точек x„KXi, удовлетворяющих неравенству fj,<0. Для него ограниченность и сходимость последовательности оценок искомого корня обеспечены. Однако эти гарантии достигаются ценой потери быстродействия. Сходимость метода ложного положения всего лишь линейна, причем асимптотический параметр ошибки может быть сколь угодно близким к единице. Ситуация, в которой метод сходится очень медленно, изображена на рис. 4<1 (в этом примере ff<0 для всех 11 и потому далекая от корня точка Xt, никогда не будет отброшена). Как правило, деление пополам оказывается намного эффективнее метода ложного положения, хоть и получен он из значительно более быстродействующей схемы. Последнее говорит о том, что, модифицируя какой-либо алгоритм с целью расширить его область сходимости, никогда не лишне подумать о последствиях такой модификации в отношении скоростных качеств.

* 4.1.1.4. Дробная интерполяция и методы высоких порядков.

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

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

Вопрос о выборе корня не возникнет, если интерполировать / дробной функцией вида

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

4.1.1.5. Регуляризоваиные алгоритмы поиска нуля. Рассмотренную ранее процедуру деления пополам можно интерпретировать как один из способов реализации общей схемы поиска нуля путем генерирования последовательности вложенных интервалов {/;}, каждый из которых содержит искомый корень х*. Точнее говоря, общий подход состоит в том, чтобы при заданном интервале /о, содержащем X*, строить систему {/,-}, /=1, .... удовлетворяющую условиям и х*€ /у- Вчастности, имея интерва.п можно определять по знакам / на границах и в какой-нибудь внутренней точке и этого интервала. Так работают многие методы и в том числе метод деления пополам.

В методе деления пополам в качестве и выбирается середина Однако ничто не мешает определять и по методу Ньютона или, скажем, с помощью дробной аппроксимации. При этом не обязательно строить аппроксимирующую функцию по значениям / на границах ннтерва.па неопределенности. Можно, например, испапьзовать для этого «лучшие» из точек, известных к началу очередной итерации. Так, в примере, изображенном на рис. 4d, линейную модель для второго шага эффективнее построить по точкам л:, и х,, хотя интервалом неопределенности будет [лгв, 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.0011