1.3. Сравнительный анализ методов одномерного поиска

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

Поскольку при реализации методов одномерного поиска определение значений функции f(х) требует несравненно больших затрат, чем выполнение таких вспомогательных операций, как вычисление точек перебора, сравнение значений функции и т.п., то объем вычислений можно оценить количеством N вычислений значений функции f(х).

Метод считается тем эффективнее, чем меньше N, гарантирующее заданную точность определения точки х* минимума функции f(х). Для сравнения рассматриваемых методов по этому признаку рекомендуется составить таблицу значений N(e) в зависимости от требуемой точности определения х*.

При сравнении методов по точности более эффективным считается тот из рассматриваемых методов, который обеспечивает достижение меньшего значения e(N) при одинаковом объеме вычислений. Для получения вывода о точности рекомендуется составить таблицу значений достигнутой точности e(N) в зависимости от количества N найденных значений функции f(х) для указанных методов.

1.4. Порядок выполнения лабораторной работы

1. Кратко описать изучаемые методы одномерного поиска.

2. Решить задачу (1.1) классическим методом.

3. Выполнить программную реализацию каждого алгоритма.

4. Провести расчеты указанной в индивидуальном задании (см. пункт 1.5) задачи при различных значениях параметров алгоритмов с целью получения результатов, достаточных для сравнения изучаемых методов.

5. Выполнить сравнительный анализ (см. пункт 1.3) изучаемых методов, составив для этого таблицы значений N(e) и e_n(N).

1. Сформулировать вывод о сравнительной эффективности изучаемых методов. Содержание работы отразить в отчете.

1.5. Задания для лабораторной работы.

1. Минимизировать функцию f(х)= на отрезке [-1;2].

2. Минимизировать функцию f(х)= x на отрезке [0,1;3].

3. Минимизировать функцию f(х)= на отрезке [0;2].

4. Минимизировать функцию f(х)= x  ln(x+1) на отрезке [-0,3;2].

5. Минимизировать функцию f(х)= на отрезке [0;3].

6. Минимизировать функцию f(x)= x³  3 sin x на отрезке [0;1].

7. Минимизировать функцию f(x)= на отрезке [0,5;2].

8. Минимизировать функцию f(x)= x⁴+x²+x+1 на отрезке [-1;0].

2. Методы безусловной оптимизации

Задачи безусловной оптимизации сводятся к поиску точек минимума функции многих переменных на всём пространстве соответствующей размерности. Функции многих переменных f(X)=f(x₁,x₂,...,x_n) будем рассматривать как функции, заданные в точках Х n-мерного евклидова пространства Eⁿ. Изучим основные методы решения задач безусловной минимизации вида

min{f(X) | XÎ Eⁿ }. (2.1)

Если функция f(x) дважды дифференцируема, то задачу (2.1) можно решить классическим методом с помощью необходимых и достаточных условий безусловного экстремума. При этом из необходимого условия

или (2.2)

находим все стационарные точки функции f(x). Среди них, используя достаточные условия, находим точки локального минимума, в которых матрица вторых производных положительно определена. Сравнивая значения функции в этих точках, определяем точку глобального минимума.

Однако, аналитически решить систему уравнений (2.2) не всегда возможно. Кроме того, функция f(x) может быть не только недифференцируемой, но даже не аналитически заданной. Поэтому классический метод имеет ограниченное применение и для решения задачи (2.1) на практике разрабатывают приближённые численные методы. Простейшие из них, называемые прямыми методами, предполагают лишь возможность вычисления или измерения значений функции и не требуют вычисления её производных.

Рассмотрим основные из этих прямых методов, использующие итерационные процедуры вида

X^k+1=F(X^k, X^k-1,…, X⁰), X⁰Î Eⁿ, (2.3)

в которых выбор нового приближения к точке минимума определяется сравнением значений функции f(X) в нескольких точках пространства Eⁿ.