Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Схема алгоритма






Алгоритм равномерного блочного поиска

Шаг 1. Задаются исходный отрезок неопределенности [ a, b ], e - точность приближенного решения , число экспериментов в блоке – n (нечетное, n= 2 k- 1). Проводим эксперимент в середине отрезка [ a, b ], т.е. вычисляем yk=f (xk), где xk =(a+b)/2.

Шаг 2. Проводим эксперименты в остальных точках блока: yi=f (xi), где xi=a+i* (b-a)/(n+ 1), i= 1, 2,.., n, i¹ k. Находим точку xj, в которой достигается минимум среди вычисленных значений: f(xj)=min f(xi), следовательно, точное значение минимума x* содержится на отрезке [ xj-1, xj+1 ].

Шаг 3. Полагаем a=xj -1, b=xj+ 1, xk=xj, yk=yj. Если b-a£ 2 e, то , и поиск заканчивается. Иначе перейти к шагу 2. Если заданная точность e достигнута после т итераций, т.е. после экспериментов в m блоках, то длина отрезка неопределенности после всех N вычислений (N=n+ (m- 1)(n- 1) = (n- 1) m +1) будет:

и

Алгоритм деления интервала пополам

Это вариант предыдущего алгоритма при n= 3.

Схема алгоритма.

Шаг 1. Задаются a, b, e. Производим эксперимент в точке x2 =(a+b)/2, т.е. вычисляем y2=f (x2).

Шаг 2. Проводим эксперименты в остальных точках блока: x1 =(a + x2)/2, y1 = f (x1), x3 =(x2 + b)/2, y3 = f (x3).

Находим xj такую, что f (xj)= min { f (xi)}.

1 ≤ i ≤ 3Тогда точное решение x* содержится на отрезке [ xj -1, xj +1]. Предполагается .

Шаг 3. Полагаем a = xj -1, b = xj +1, x2=xj, y2=yj. Если b-a £ 2 e, то и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число проведенных экспериментов равно N= 2 к+ 1, а длина получившегося отрезка неопределенности будет , где [ z ] – целая часть числа z. Следовательно, достигнутая точность будет , e=1/2LN.

Метод дихотомии

Это алгоритм блочного поиска для ni=n= 2, т.е. когда в блоке два эксперимента. Так как пассивная составляющая алгоритма, т.е. блок, содержит четное число экспериментов, то оптимальный выбор точек xij, в которых необходимо провести эксперименты, будет неравномерным, в отличие от предыдущих алгоритмов, где число экспериментов в блоке было нечетным и, соответственно, расположение точек равномерным. Если блок содержит два эксперимента, то оптимальное (дельта оптимальное) расположение точек, в которых будут проводится эксперименты, это как можно ближе к середине отрезка. Такое расположение точек позволяет получить наименьший отрезок неопределенностей после экспериментов в блоке.

Схема алгоритма.

Шаг 1. Задаются a, b, e и d - малое положительное число, значительно меньшее чем e.

Шаг 2. Определяется середина отрезка x =(a + b)/2. Производятся эксперименты в двух точках близких середине: y1 = f (x - d), y2 = f (x + d).

Шаг 3. Определяется следующий отрезок локализации, т.е. определяется какой из отрезков [ a, x+d ] или [ x-d, b ] содержит точное решение x*. Если y1£ y2, то это отрезок [ a, x+d ] и b=x+d, иначе это отрезок [ x-d, b ] и a=x-d, т.е. выбранный отрезок локализации мы снова обозначили как [ a, b ].

Шаг 4. Если b-a £ 2 e, то x= (a+b)/2, и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число экспериментов будет N =2 к, а длина получившегося отрезка неопределенности . Следовательно,


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал