Алгоритм метода Пауэлла

Начальный этап. Выбрать x₁ - начальную точку, Dx - величину шага по оси x. Задать точность поиска по х и f(x) e₁=0,01 и e₂=0,1. Перейти к основному этапу.

Основной этап. Шаг 1. Вычислить x₂ = x₁ + Dx.

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

Шаг 3. Если f(x₁) > f(x₂), положить x₃ = x₁ + 2Dx. Если f(x₁) £ f(x₂), положить x₃ = x₁ - Dx.

Шаг 4. Вычислить f(x₃) и найти F_мин = min{f₁, f₂, f₃}.

X_мин = (×) x_i, которая соответствует F_мин.

Шаг 5. По трем точкам x₁, x₂, x₃ вычислить используя формулу для оценивания с помощью квадратичной аппроксимации.

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

- является ли разность X_мин - достаточно малой(/X_мин - /<e₁)?

- является ли разность F_мин - f( ) достаточно малой (/F_мин - f( )/<e₂)?

Если оба условия выполняются, закончить поиск. В противном случае перейти к шагу 7.

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

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

Пример расчета экстремума функции методом Пауэлла.

Постановка задачи. Рассчитать минимум функции f(x) = (3-x)² + 2x-1 методом Паулла. Выбираем начальную точку x₁=0 и Dx=1 - величину шага по оси x, а также точность поиска по х и f(x) e₁=0,01 и e₂=0,1.

Результаты расчета минимума функции f(x) = (3-x)² + 2x-1 представлены в таблице 2.8.

Таблица 2.8

Результаты расчета минимума функции f(x) = (3-x)² + 2x-1 методом Пауэлла

Из расчетов видно, что экстремум найден за одну итерацию, что говорит о высокой эффективности метода.

МЕТОДЫ С ИСПОЛЬЗОВАНИЕМ ПРОИЗВОДНЫХ

Рассмотренные в предыдущем разделе методы поиска основываются на предположениях об унимодальности и в ряде случаев о непрерывности исследуемой целевой функции. Целесообразно предположить, что если в дополнении к условию непрерывности ввести требование дифференцируемости функции, то эффективность поисковых процедур можно существенно повысить.

2.3.1. Метод Ньютона.

В рамках схемы Ньютона предполагается, что функция f дважды дифференцируема. Работа алгоритма начинается в точках x₁, которая представляет начальное приближение и строится по рекурентному соотношению x_k+1 = x_k - [f'(x_k)/f''(x_k)], где присутствуют первая и вторая производные. Однако, в зависимости от выбора начальной точки и вида функции алгоритм может как сходиться к истинной стационарной точке, так и расходиться. Несмотря на этот недостаток метод Ньютона требует наименьшего количества расчетов функции.