Будем далее считать, что целевая функция является унимодальной, т.е. у нее существует единственная точка минимума x*є[a,b], причем при xє[a,x*) f(x) строго (монотонно) убывает, а при xє(x*,b] строго возрастает. При этом к целевой функции не предъявляются требования непрерывности и дифференцируемости.
К основным прямым методам поиска минимума унимодальных функций относятся: метод перебора, метод исключения отрезков, метод парабол.
Метод перебора. Простейшим из прямых методов является метод перебора, который применяется в двух вариантах: метод равномерного (перебора) поиска и метод поразрядного поиска.
В случаи равномерного поиска отрезок разбиваем на равных частей с точками деления xi=a+i((b-a)/n), i=0,1,…, n. Вычислив значения f(x) в точках xi путем сравнения найдем точку xm 0≤m≤n для которой f(xm) = min f(xi), 0≤i≤n. Далее положим x*=xm, f*=f(xm). Для того, чтобы обеспечить необходимую точность ε определение точки x* необходимо выбрать число точек дробления из условия n ≥ (b-a)/ε.
Метод поразрядного поиска является усовершенствованием метода прямого поиска с учетом того, что если оказалось f(xi) ≤ f(xi+1), то необходимость вычислять f(x) в точках xi+2, xi+3 и т.д. отпадает, т.к. в x* ≤ xi+1 вследствие унимодальности целевой функции. Кроме того в методе поразрядного поиска сначала отрезок, содержащий x*, определяется с небольшой точностью, а затем точка ищется на этом отрезке с меньшим шагом и повышенной точностью.
Метод исключения отрезков. В отличии от метода перебора, в котором вычисление значений функции f(x) осуществляется в заранее выбранных точках xi, в методе исключения отрезков для выбора очередной точки используется информация, содержащаяся в уже найденных значениях функции f(x). В этом случае поиск точки минимума является более эффективным.
В методе исключения отрезков используется следующее свойство унимодальности функции f(x): если x* точка минимума функции f(x) на [a,b] и a ≤ x1 < x2 ≤ b, то:
при f(x1) ≤ f(x2) x*є[a,x2]
при f(x1) > f(x2) x*є[x1,b]
Сравнив значения f(x) в пробных точках x1 и x2 можно сократить отрезок поиска точки x*, перейдя к отрезку [a,x2] если f(x1) ≤ f(x2) или к отрезку [x1,b], если f(x1) > f(x2).
Данную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку минимума. Когда длинна последнего из найденных отрезков станет достаточно малой, следует положитьx* ≈ x^, где x^ - одна из точек этого отрезка, например, его середина. Методы, основанные на этом принципе называются методами исключения отрезков. Для того, чтобы относительное уменьшение отрезка на каждой итерации не зависело от того, какая из его частей исключается из дальнейшего рассмотрения, пробные точки следует располагать симметрично относительно середины исходного отрезка. В зависимости от способа выбора пробных точек используются различные методы исключения отрезка. К основным относится метод деления отрезка пополам (дихотомии) и метод золотого сечения.
Метод деления отрезка пополам (дихотомии). Пробные точки x1 и x2 в этом методе рассмотрены близко к середине очередного отрезка [a,b], т.е.
|
||||
|
||||
|
является близким к 1/2. Для любых x1, x2 и δ > 1/2 выбор точек обеспечивает максимально возможное уменьшение отрезка на каждой итерации. В конце, убедившись, что (b-a)/2 ≤ ε, за приближенное значение берут середину последнего найденного отрезка [a,b].
Число δ выбирается из интервала 0 < δ < 2ε с учетом того, что чем меньше ε, тем быстрее сходимость метода, т.е. тем больше относительное уменьшение длины отрезка на каждой итерации, но при очень малом δ трудно сравнивать значения функции в точках x1 и x2.
При достаточно малом δчисло итераций, необходимое для определения точки x*с точностью ε, приближенно определяется из условия:
n ≥ log 2 (b-a)/2ε
При числе итераций n = N/2 производится Nвычислений и достигается точность определения точки минимума x*
ε(N) ≈ (b – a)/2N/2 +1
Метод золотого сечения. В методе золотого сечения выбрано такое расположение точек x1 и x2 на отрезке [a,b], при котором одна из них становится пробной точкой и на новом отрезке, полученном в результате исключения части отрезка. Это позволяет уменьшить количество вычислений, т. к. на каждой итерации, кроме первой, вычисляется одно значение функции f(x), а другое уже известно из предыдущей итерации.
Золотым сечением называют деление отрезка на две части таким образом, чтобы отношение длины всего отрезка к длине большей части было равно отношению длины большей части к меньшей. Золотое сечение отрезка [a,b]производят две симметрично расположенные точки x1 и x2:
x1=a+(1-τ)(b-a); x2=a+τ(b-a), где τ = (√5 – 1) /2 ≈0.618
τ(b-a)
(1-τ)(b-a) (1-τ)(b-a) τ(b-a)
 |
|||
 |
|||
ax2′x1x2bax1x2x1′b
Точка x1 в свою очередь производит золотое сечение отрезка [a,x2], а точка x2– золотое сечение отрезка [x1,b]. Т.о. на каждой итерации исключения отрезков с пробными точками x1=a+(1-τ)(b-a) и x2=a+τ(b-a)одна из них переходит на следующий отрезок и значение в этой точке вычислять не следует. Если новым отрезком становится [a,x2] (f(x2) < f(x2)), то на него переходит пробная точка x=x2исходного отрезка, становясь его второй пробной точкой отрезка [x1,b] (x=x1′).
В конце вычислений в качестве приближенного значения x* можно взять середину из полученных отрезков x=(a+b)/2. На каждой итерации отрезок поиска точки минимума уменьшается в τ = (√5 – 1) /2 раз, поэтому в
результате итераций его длина становиться равной ∆n=τn(b-a). Точность εопределения точки x*после nитераций определяется из соотношения:
ε = =1/2τn(b-a) (2.7)
Условия окончания поиска точки x* с точностью ε имеет вид:
εn ≤ ε
Число итераций, необходимое для достижения заданной точности ε:
n ≥ ln 2ε/(b-a) 1 /ln τ ≈ - 2.1ln[2 ε/(b – a)] (2.8)
Достигнутая точность ε(N) вычисления минимума функции f(x) при N вычислениях составляет:
ε(N)=1/2τN -1(b-a). (2.9)
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.