Метод золотого сечения. Алгоритм поисковой процедуры

Метод последовательного оценивания с использованием квадратичной аппроксимации (метод Пауэлла)

Метод основан на последовательном применении процедуры оценивания с использованием квадратичной аппроксимации.

Стратегия поиска

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

Алгоритм поисковой процедуры

Дано: х₁, Dх, TOL₁, TOL₂

Шаг 1. Вычислить х₂ = х₁ + Dх.

Шаг 2. Вычислить f(х₁) и f(х₂).

Шаг 3. Если f(х₁) > f(х₂), положить х₃ = х₁ + 2Dх. Если f(х₁) £ f(х₂), положить х₃ = х₁ — Dх. Вычислить f(х₃)

Шаг 4. Проиндексировать точки по порядку. Найти «наилучшую» точку

,

X_min = точка х_i, которая соответствует F_min.

Шаг 5. По трем точкам х₁, х₂, х₃ построить аппроксимирующий полином (найти коэффициенты а₀, а₁, а₂).

Шаг 6. Вычислить , используя формулу для оценивания с помощью квадратичной аппроксимации.

Шаг 7. Проверка на окончание поиска.

(а) Если [F_min– f()] / f()≤TOL₁,

(б) и если [Х_min — ]/  ≤TOL₂  ®end: x*=

Иначе  ® Шаг 8.

Шаг 8. Выбрать “наилучшую” точку (Х_min или ) и две точки по обе стороны от нее. Обозначить (проиндексировать) эти точки в естественном порядке и перейти к шагу 5.

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

Задание: f(x) = (100-x)²; x₁ = 92; Dх = 7, TOL₁ = TOL₂ = 0,01.

Практическая работа 7

Методы с использованием производных

Требования к функции: унимодальность, непрерывность, дифференцируемость

7.1. Метод Ньютона — Рафсона

Врамках схемы Ньютона – Рафсона предполагается, что функция f дважды дифференцируема. Работа алгоритма начинается в точке х₁, которая представляет начальное приближение (или начальную оценку) координаты стационарной точки, или корня уравнения f‘(х) = 0. Затем строится линейная аппроксимация функции f‘(х) в точке х₁,и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения.

Алгоритм

Дано: f(x); x₀, TOL

Шаг 1:  f’(x); f”(x)

Шаг 2:

Шаг 3: f’(x_k+1); f”(x_k+1)

Шаг 4: Если |f’(x_k+1) | ≤ TOL ® end: x*≈x_k+1

Иначе ® Шаг 2.

Задание:

f(x) - своя; x₀ = а, TOL=0,01

7.2. Метод средней точки (Больцано)

Определим две точки L и R таким образом, что f‘(L) < 0 и f’(R) > 0. Стационарная точка расположена между L и R. Вычислим значение производной функции в средней точке рассматриваемого интервала z = (L+R)/2. Если f’(z) > 0, то интервал (z, R) можно исключить из интервала поиска. С другой стороны, если f‘(z) < 0, то можно исключить интервал (L, z). Ниже дается формализованное описание шагов алгоритма.

Алгоритм

Дано: f(x); (a;b), TOL

Шаг 1. f’(x)

Шаг 2.R = b, L = a; при этом f‘(а) < 0 и f’(b) > 0.

Шаг 3.z = (R + L)/2 и f’(z).

Шаг 4. Если |f’(z)’| £TOL® end: x*≈ z.

Иначе ® Шаг 5.

Шаг 5. Если f’(z) < 0 ®L = z ® шаг 3

Если f’(z) > 0® R=z ® шаг 3.

Задание:

f(x) - своя; (a; b), TOL=5

Метод секущих

Метод секущих,являющийся комбинацией метода Ньютона и общей схемы исключения интервалов, ориентирован на нахождение корня уравнения f’(х) = 0 в интервале (а, b), если, разумеется, такой корень существует.

Предположим, что в процессе поиска стационарной точки функции f(х) в интервале (а, b) обнаружены две точки L и R, в которых знаки производной различны. В этом случае алгоритм метода секущих позволяет аппроксимировать функцию f‘(х) “секущей прямой” (прямой линией, соединяющей две точки) и найти точку, в которой секущая графика f‘(х) пересекает ось абсцисс (рис. 2.16). Таким образом, следующее приближение к стационарной очке х*определяется по формуле

.

Если |f’(z)| £e,поиск следует закончить. В противном случае необходимо выбрать одну из точек Lили R таким образом, чтобы знаки производной в этой точке и точке z были различны, а затем повторить основной шаг алгоритма.

Алгоритм

Дано: f(x); x₀, TOL

Шаг 1:  L:=a; R:=b

Шаг 2: f’(L); f’(R)

Шаг 3:

Шаг 4: Если |f’(x_k+1) | ≤ TOL ® end: x*≈x_k+1

Иначе ® оставляем z в качестве одной из границ, а второй границей