Оптимальный поиск

Рассмотрим класс функций одного аргумента, которые называются унимодальными. Определим унимодальную функцию y = f(X) следующим образом:

1. f(X) задана на отрезке [a,b]. 2. пусть X₁ и X₂ ε [a,b], причем X₁ < X₂

пусть X⁰ – точка, в которой f(X) достигает минимума (максимума); тогда из X₁ > X⁰ следует f(X₂) > f(X₁), а из X₂ < X⁰ следует f(X₁) > f(X₂).

Примеры унимодальных функций приведены на рис.7. Заметим, что определение унимодальности исключает возможность участков f(X) с постоянным значением

рис. 7

минимум f(X) может находится во внутренней точке [a,b] или на границе. Первоначально о положении X⁰ ничего не известно, кроме того, что, X⁰ ε [a,b]. [a,b] можно назвать отрезком неопределенности.

Выбор Xi и вычисление F(Xi) называется экспериментом. Во всех случаях после выполнения заданных экспериментов отрезок неопределенности становится уже. Последовательное повторение экспериментов позволит достигнуть величины отрезка неопределенности меньшей, чем любое наперед заданное ε > 0. правило выбора Xi называется стратегией. Оптимальной называется стратегия, которая приводит к X⁰ (с точностью до ε) за минимальное число шагов (экспериментов).

Обозначим длину отрезка неопределенности L_n(X₁, X₂, . . ., Xn), где n – число экспериментов;

f (X_k) = min f(X_i), 1≤ i ≤ n, где K – номер эксперимента, которому соответствует минимальное значение f(X_i). Тогда получим:

X₂ – X₁, k=1;

L_n(X₁, X₂, . . ., X_n, к) = X_k+1 – X_k-1, 1≤ k ≤ n;

X_n – X_n-1, k=n.

Т.о., L_n зависит как от выбора способа разбиения [a,b], так и от поведения f(X).

Пассивный поиск

В пассивном поиске все эксперименты проводятся одновременно. Без ограничения общности положим X₁ = a = 0; X_n = b = 1;

Рассмотрим n = 4; 0 < X₂ < X₃ < 1

Тогда L_n = max { X₂ – 0, X₃ – 0, 1 - X₂, 1 – X₃}= max { X₃, 1 - X₂}

1≤ k ≤ 4

L_n = min max { X₃, 1 - X₂}

0 < X₂ < X₃ < 1 k= 2,3

Так как X₂ < X₃, то оптимальной стратегией будет X₂ = ½ - Δ /2, X₃ = ½ + Δ /2, а соответствующее L_n = ½ + Δ /2 (рис.8,а ).

Под Δ > 0 понимают минимальное число, которое делает 2 эксперимента X₂ и X₃ различными.

При рассмотрении n = 5 получаем (рис 8,б), что L_n улучшилось на Δ /2, что заставляет отказаться от нечетного числа экспериментов.

При произвольном четном n наилучшая стратегия составляется парами Δ - экспериментов (Xi разнесены на расстояние Δ).

В общем случае L_n ≈ 2/n + Δ /2.

рис.8

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

Существует довольно очевидная теорема: "Если непрерывная функция на концах некоторого интервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но м.б. и несколько)". Вот на базе этой теоремы и построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется "дихотомией", т.е. "делением отрезка на две части". Обобщенный алгоритм выглядит так:

задать начальный интервал [a;b];

убедиться, что на концах функция имеет разный знак  < 0.;

Начальное приближение x0 =  .

повторять

выбрать внутри интервала точку X;

сравнить знак функции в точке X со знаком функции в одном из концов;

если совпадает, то переместить этот конец интервала в точку X,

иначе переместить в точку X другой конец интервала;

После каждой итерации отрезок, содержащий корень уменьшается вдвое;

пока не будет достигнута нужная точность.

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

Метод выбора точки деления - ключевой для скорости работы метода. Хорошо, если функция, чей корень находится, проста и быстро вычисляется; но внутри функции могут быть и матричные операции, и численное интегрирование, и все что угодно; так что главным критерием оптимизации является минимизация числа делений (естественно, без ухудшения точности метода).

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