5.2Блок-схема метода золотого сечения

Входные параметры: a; b; " Выходные параметры: v ; f(v ); n

6Симметричные методы

Метод золотого сечения относится к классу симметричных методов. Общее описание произвольного симметричного метода минимизации ф-и f(x) на интервале [a; b] выглядит так:

1. на интервале [a; b] задается точка x1 такая, что a < x1 < b

a1 = a b1 = b x1 = x1

ивычисляется f(x1)

2.пусть уже сделано n 1 шагов и найдены отрезок [an 1; bn 1], а так же точкаxn 1 an 1 < xn 1 < bn 1

изначение ф-и f(xn 1)

3.тогда на следующем n-ом шаге вычисляется точка

xn = an 1 bn 1 xn 1

10

расположенная внутри отрезка [an 1; bn 1], симметрично точке xn 1 относительно середины этого отрезка. Именно отсюда происходит название симметричные методы

4. затем вычисляется значение f(xn) и сравнивается с f(xn 1). Пусть для определенности

xn 1 6 xn

Тогда при

f(xn 1) 6 f(xn)

полагают

an = an 1 bn = xn xn = xn 1

иначе, если

xn 1 > xn

то

an = xn 1 bn = bn 1 xn = xn

Все симметричные методы имеют тот же недостаток, что и метод золотого сечения: погрешность, допущенная в задании первой точки x1 приводит к быстрому накоплению погрешности на дальнейших шагах, поэтому симметричные методы лучше использовать в модифицированном виде. Чтобы избежать быстрого роста погрешности на каждом отрезке [an; bn], содержащем точку xn c предыдущего шага, следующую точку xn+1 нужно определять не по формуле

xn+1 = an bn xn

алучше непосредственно произвести разбиение отрезка [an; bn] точками в соответствии с методом.

6.1Постановка задачи об оптимальных методах

Предположим, что задано некоторое множество P и класс функций Q и зафиксирована какая-либо постановка задачи минимизации (например, задача первого или второго типа). Пусть (f; p) погрешность решения рассматриваемой задачи минимизации для функции f(x) принадлежащей Q с помощью конкретного метода p. Ясно, что если минимизировать одним и тем же методом P различные ф-и из множества Q,то будут получаться различные погрешности. Считают, что метод p1 лучше метода p2 если погрешность метода p1 даже для самых ¾плохих¿ для p1 функций из Q будет меньше погрешности метода p2 даже для самых ¾плохих¿ для p2 функций из Q.

Для характеристики метода вводят величину

(p) = sup(f; p)

f2Q

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

(p1) < (p2)

Определение. Метод p называют оптимальным методом на классе Q, если

(p ) = inf sup (f; p ) =

p2P f2Q

Величину называют наилучшей гарантированной точностью методов P на классе ф-ий Q. При рассмотрении конкретных оптимальных методов будем предполагать, что

решается задача минимизации второго типа на классе ф-ий Q, состоящем из всех унимодальных ф-ий на отрезке [a; b]

11

методы минимизации используют лишь значения ф-и и не используют значений ее производных

число n вычислений значений минимизируемой ф-ий задано заранее. При выборе точек x1; x2; :::; xn

вкоторых будут вычисляться значения ф-и выделяют два принципиально различных способа:

–Последовательный. Точки x1; x2; :::; xn выбираются последовательно, отдельными порциями, причем при выборе каждой очередной порции учитываются результаты предыдущих вычислений. Рассмотренные ранее методы детом деления отрезка пополам и метод золотого сечения является последовательными способами.

–Пассивный. Все точки x1; x2; :::; xn выбираются сразу до начала вычислений и в дальнейшем уже не меняются.

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

1.Задача А. С помощью n вычислений значений f(x) найти такую точку !n, которая удалена от X на возможно меньшее расстояние и соблюсти условие, чтобы приближением к f служило значение f(!n)

2.Задача Б. С помощью n вычислений значений f(x) найти такую точку !n, которая удалена от X на возможно меньшее расстояние, но в отличие от задачи А не требовать, чтобы значение ф-и принимаемое за приближение f было обязательно вычислено в точке !n.

6.2Оптимальный пассивный метод для задачи А (метод равномерного перебора)

Для задачи А при всех n > 1 существует и при том единственный оптимальный пассивный метод pAn на классе Q унимодальных ф-ий. В этом методе точки x1; x2; :::; xn определяются по формуле

xi = a + nb+1a i i = 1; 2; :::; n

Наилучшая гарантированная точность на классе Q равна

= b a n+1

6.3Оптимальный последовательный метод для задачи А (метод Фибоначчи)

Связан с числами Фибоначчи

pp

Относится к классу симметричных методов.

a1 = a b1 = b

Производят деление отрезка [a; b] = [a1; b1] двумя точками

(

x1 = a1 + (b1 a1)FFn (4)

n+2

x2 = a1 + (b1 a1)FFn+1

n+2

Алгоритм вычислений совпадает с общим алгоритмом произвольного симметричного метода. Чтобы избежать быстрого роста погрешности метод применяют в модифицированном виде. На некотором k-ом шаге не используют формулу

xk = ak bk xk 1

а непосредственно производят деление отрезка двумя точками

12