Метод деления отрезка пополам

Простейшим методом минимизации функции одной перемен­ной, не требующим вычисления производной, является метод деления отрезка пополам. Опишем его, предполагая, что мини­мизируемая функция J(и) унимодальна на отрезке [a, b]. Поиск минимума J(и) на [а, b] начинается с выбора двух точек и , где — постоянная, являю­щаяся параметром метода, 0 < < b – a. Величина выбирается вычислителем и может определяться целесообразным количе­ством верных десятичных знаков при задании аргумента . В частности, ясно, что не может быть меньше машинного нуля ЭВМ, используемой при решении рассматриваемой задачи. Точ­ки расположены симметрично на отрезке [ a, b ] относи­тельно его середины и при малых делят его почти пополам — этим и объясняется название метода.

После выбора точек вычисляются значения J(), J() и сравниваются между собой. Если J()≤ J(), то полагают = a, = u₂; если же J()>J() то полагают = , =b. Поскольку J(и) унимодальна на [a, b], то ясно, что отрезок [ , имеет общую точку с множеством точек минимума J(u) на [a, b] и его длина равна

.

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

Длина получившегося отрезка равна и [

Если количество вычислений значений минимизируемой функции ничем не ограничено, то описанный процесс деления отрезка пополам можно продолжать до тех пор, пока не полу­чится отрезок длины , где — заданная точ­ность, . Отсюда имеем, что к > log₂ (()). Поскольку каждое деление пополам требует двух вычислений значений функции, то для достижения точности тре­буется всего таких вы­числений.

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

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

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

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

§ 4. Метод золотого сечения. Симметричные методы

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

1. Как известно, золотым сечением отрезка называется деле­ние отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению дли­ны большей части к длине меньшей части отрезка.

Нетрудно проверить, что золотое сечение отрезка про­изводится двумя точками и ,расположенными симметрично относи­тельно середины отрезка, причем

Замечательно здесь то, что точка в свою очередь произво­дит золотое сечение отрезка , так как и . Аналогично точ­ка производит золотое сечение отрезка . Опираясь на это свойство золотого сечения, можно предложить следующий метод минимизации унимодальной функции на отрез­ке .

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

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

Пусть для определенности (случай рассматривается аналогично). Если , то полагаем если же , то полагаем . Новый отрезок таков, что точка производит золотое сечение и .

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

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

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

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

Как известно линейно независимые частные решения этого уравнения имеют вид и (п = 1, 2,...), где — корни характеристического урав­нения , а любое решение уравнения (1) представи­мо в виде (2) где постоянные A и B однозначно определяются начальными ус­ловиями из линейной системы . (3)

При из (3) имеем и понятно, что формула (2) в этом случае дает уже из­вестное нам решение . Однако точка задана с погрешностью, поэтому в системе (3) вместо точного значе­ния придется взять приближенное . Тогда постоян­ные A, B из (3) определятся с соответствующими погрешностя­ми: , и вместо (2) с точными A, B будем иметь (п = 1, 2,...). Поскольку , то погрешность с возрастанием будет расти очень быстро. Это зна­чит, что уже при не очень больших отрезок и точки будут сильно отличаться от тех, которые по­лучились бы при работе с точными данными. Численные экспе­рименты на ЭВМ также подтверждают, что метод золотого се­чения в описанном выше виде практически неприменим уже при небольших .

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

3. Метод золотого сечения относится к классу так называемых сим- метричных методов. Дадим краткое описание произвольного симметрично­го метода минимизации функции на отрезке .

Первый шаг: на задается точка , полагается и вычисляется . Пусть уже сделано шагов и найдены отрезок и точка с вычисленным значением , причем . Тогда на следующем n-м шаге берется точка расположенная внутри [ , симметрично точке относительно середины этого отрезка — отсюда происходит название методов. Затем вычисляется значе­ние и сравнивается с . Пусть для определенности (случай рассматривается аналогично). Тогда при полагается если же , то . Если , то процесс может быть продолжен дальше. Может оказаться, что ,— в этом случае процесс заканчивается; при необходимости на можно продолжать поиск минимума аналогичным методом, начиная с выбора новой начальной точки .

Из описания симметричного метода видно, что всякий симметричный метод полностью определяется заданием отрезка и первой точки . Отсюда следует, что в качестве другой характеристики сим­метричного метода можно взять длины отрезков (п = 1, 2,...), где . Очевидно, при всех . Как видим, симметричные методы весьма просты и, пожалуй, даже изящны. Однако все эти методы страдают тем же недостатком, что и метод золотого сечения: погрешность, допущенная в задании первой точки приводит к быстрому накапливанию погрешностей на дальнейших шагах, и уже при не очень больших п результаты будут сильно отличаться от тех, которые могли бы получиться при точной реализации симметричного ме­тода с точными исходными данными.

Если симметричный метод таков, что для выполнено условие

, (4)

при некотором N > 1, то будут удовлетворять конечно-разностному урав­нению (1) при , и исследование поведения погрешностей в этом случае может быть проведено так же, как это было сделано выше для ме­тода золотого сечения. Чтобы избежать слишком быстрого роста погреш­ностей в симметричных методах со свойством (4), на каждом отрезке (, содержащем точку с предыдущего шага, следующую точку нужно определять не по формуле , а лучше принять за ту из точек , которая наиболее удалена от