12.Теорема об оптимальности пассивного поиска.

Т. 1)Если N=2k-1, то предлагаемый алгоритм является оптимальным. 

2)Если N=2k то оптимального алгоритма не существует. 

13.Последовательные методы поиска экстремума.

В алгоритмах последовательного поиска очередная точка, в которой производится эксперимент, выбирается с учетом информации, полученной в предыдущих опытах. Рассмотрение этих алгоритмов начинается с блочного поиска, которые сочетают в себе пассивные и последовательные стратегии поиска. При этом вычисления в точках объединены в блоки, в каждом из которых проводится одновременно ni экспериментов), общее число экспериментов будет ), т.е. блок - это совокупность из нескольких экспериментов, которые проводятся одновременно (пассивный поиск). Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {xij (j=1,2,…,ni}(последовательный поиск). Если размеры блоков равны единице, т.е. ni=1, то мы имеем обычный последовательный алгоритм поиска. К методу активного поиска относятся также: алгоритм деления интервала пополам(алгоритм блочного поиска, но n-число экспериментов в блоке=3), метод дихотомии(Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента.), симметричные методы-метод зол сечения и чисел Фибоначчи(т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка.)

14. Метод поразрядного поиска.

• представляет собой усовершенствованный метод перебора;

• поиск точки минимума осуществляется с переменным шагом.

Краткое описание алгоритма:

1. Вводится начало и конец отрезка a, b и точность E.

Выбор начального шага h = b-a4;

2. Задаем x0= a. Вычисляем F(x0), N=1;

2. Предположим, что мы идем вправо +h. x1=x0+h . Вычисляем значение F(x1), N=N+1;

2. Сравнить F(x0) и F(x1). Если F(x0) >F(x1), переходим к шагу 5, иначе к шагу 6;

2. x0= x1, F(x0)=F(x1). Проверка на то, не вышли ли мы на границу a<x0<b?

Если да: идем на шаг 3;

Если нет: идем на шаг 7. 

6. Функция начала расти, переходим шаг 7.

6. |h|<=E? 

Если да: “точность достигнута” x~ = x0, y~= F(x0), Eгар = h. И выводим рез-ты;

Если нет: “точность не достигнута - меняем направление” 

x0=x1, F(x0)=F(x1), h = -h/4 и идем на шаг 3.

15. Метод дихотомий

• Этот метод является методом прямого поиска;

• В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Краткое описание алгоритма:

1. Вводится a, b, E, sigma. Причем sigma << E. N= 0;

2. x = (a+b)/2; y1=f(x-sigma); y2=f(x+sigma); N=N+2;

3. y1<y2?

Если да: b = x+sigma;

Нет: a = x - sigma;

4. Проверка условия достижения заданной точности: b-a > 2E?

Если да: возвращаемся к шагу 2;

Нет: x~ = (a+b)/2;  y~ = f(x~0);  Eгар = (b-a)/2. Вывод x~, y~, Eгар, N.

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

• последовательный метод;

• Суть метода деления отрезка пополам состоит в разбиении отрезка [a, b] (при условии f(a)f(b) < 0) на два отрезка, определении знака функции f(x) через производную в середине отрезка (a + b)/2 и выборе отрезка, на котором функция непрерывна, меняет знак и содержит решение;

• Далее применяем алгоритм решения.

Краткое описание алгоритма:

Входные данные: f(x), a, b, ε.

1. x = (a + b)/2

2. Если f(a)·f(x) < 0, то b = x, иначе если f(x)·f(b) < 0, то a = x.

3. Если |b - a| > 2ε, то идти к 1.

4. x = (a + b)/2.

Выходные данные: x.

Значение x является решением с заданной точностью ε нелинейного уравнения вида f(x) = 0.

Если f(x) = 0, то x — точное решение.

!!! Дополнить рисунком (пометка самому себе)