Порядок выполнения лабораторной работы. 1. Кратко описать изучаемые методы покоординатного поиска минимума функций многих переменных.

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

2. Составить алгоритм метода циклического покоординатного поиска.

3. Дать графическую иллюстрацию задачи индивидуального задания и выполнить вручную по две итерации циклического покоординатного поиска и Зейделя.

4. Выполнить с использованием компьютерного комплекса расчеты индивидуальной задачи по каждому из рассмотренных алгоритмов.

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

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

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

1. Минимизировать функцию f(X)=5x₁²+5x₂²+6x₁x₂из начальной точки X⁰=(2;4)^T.

2. Минимизировать функцию f(X)=5x₁²+5x₂²-6x₁x₂из начальной точки X⁰=(-4;3).

3. Минимизировать функцию f(X)=5x₁²+5x₂²+8x₁x₂из начальной точки X⁰=(3;5)^T.

4. Минимизировать функцию f(X)=5x₁²+5x₂²-8x₁x₂из начальной точки X⁰=(-3;4)^T.

5. Минимизировать функцию f(X)=2x₁²+x₂²-x₁x₂из начальной точки X⁰=(-1;2)^T.

6. Минимизировать функцию f(X)=2x₁²+2x₂²+2x₁x₂-14x₁-12x₂+29 из начальной точки X⁰=(-1;4)^T.

7. Минимизировать функцию f(X)=2x₁²+2x₂²-2x₁x₂-4x₁-2x₂+5 из начальной точки X⁰=(-1;3)^T.

8. Минимизировать функцию f(X)=100(x₂-x₁²)²+(1- x₁)² из начальной точки X⁰=(-1;0)^T.

ГРАДИЕНТНЫЕ МЕТОДЫ

Рассмотрим задачу безусловной минимизации (2.1) предполагая, что функция f(X) непрерывно дифференцируема на Eⁿ. Для численного решения задачи применим простейшую итерационную процедуру вида

X^k⁺¹= X^k+ a_kS^k, k=0,1,2,..., (2.21) позволяющую при определенных условиях построить минимизирующую последовательность для функции f(X), т.е. такую последовательность точек Х^kÎEⁿ, что f*.

От того, как выбирается направление поиска S^k и как определяется величина шага a_k,зависят свойства итерационной процедуры (2.21) такие, как поведение функции f(X) на элементах последовательности {X^k}, сходимость к решению, скорость сходимости, объем требуемых вычислений.

Известно, что направление наибыстрейшего возрастания функции f(X) в точке X совпадает с направлением градиента функции f(X), то есть вектора

(X)= ,

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

Метод градиентного спуска

В соответствии с основной идеей градиентного метода будем строить элементы минимизирующей последовательности {X^k} с помощью рекуррентной формулы (2.21), где в качестве направления S^k выбирается направление антиградиента, как направление наискорейшего убывания функции f(X) в малой окрестности точки X^k. То есть, вычислительная схема метода градиентного спуска такова:

X^k⁺¹= x^k- a_k · (X^k), k=0,1,2,… (2.22)

Величина шага выбирается так, чтобы выполнялось условие

f(X^k⁺¹) < f(X^k), k=0,1,2,... (2.23)

В качестве критерия окончания счета на практике используют условия

| f(X^k⁺¹) - f(X^k) | £ e₁, (2.24)

|| X^k⁺¹ - X^k || £ e₂, (2.25)

|| (X^k) || £ e₃, (2.26)

где e_i - заданные параметры точности.

Опишем алгоритм рассмотренного метода градиентного спуска.

Шаг 0. Задать параметр точности e>0, начальный шаг a>0, параметр алгоритма lÎ(0;1), выбрать X⁰ÎEⁿ, вычислить значение f(X⁰), положить k=0.

Шаг 1. Найти градиент (X^k) и проверить условие достижения заданной точности || (X^k) || £ e. Если оно выполняется, то перейти к шагу 4, иначе - к шагу 2.

Шаг 2. Найти новую точку в направлении антиградиента X= X^k- a· (X^k) и вычислить f(X). Если f(X) < f(X^k), то положить X^k⁺¹=X^k, f(X^k⁺¹)=f(X^k), k=k+1, и перейти к шагу 1, иначе - перейти к шагу 3.

Шаг 3. Положить a=a·l, где 0<l<1 и перейти к шагу 2.

Шаг 4. Завершить вычисления, положив X^*= X^k, f ^*= f(X^k).