Главная | Обратная связь | Поможем написать вашу работу!

43.Метод касательных. 44.Метод наискорейшего спуска.. 45.Метод покоординатного спуска.

43. Метод касательных.

Определение минимума функции методом касательных.

Определение. Множество X n-мерного евклидового пространства En называется выпуклым, если вместе с любыми двумя точками и ему принадлежит и соединяющий их отрезок .

Выпуклость множества X означает, что из следует для всех .

Определение. Скалярная функция называется выпуклой на выпуклом множестве X, если для любых и выполняется неравенство
(1)
Если же
(2)
то функция называется вогнутой. Если для неравенство (1) – строгое, то называют строго выпуклой (соответственно для (2) – строго вогнутой). Сумма выпуклых (вогнутых) функций является выпуклой (вогнутой) функцией.

Пусть в интервале [a; b] задана выпуклая функция . Требуется с заданной точностью методом касательных найти точку минимума этой функции (x*) и значение функции в этой точке ( ).

Алгоритм решения задачи:

1-й шаг (нестандартный). Полагаем .

k-й шаг ( ). Если , то точность достигнута. Возьмем и найдем . Если , то определяем абсциссу xk точки пересечения прямых

Затем вычисляем . Если , то минимум найден: x*=xk. Процесс заканчивается. Если , то полагаем ak+1 = xk, bk+1 = bk. Если , то полагаем , и k-й шаг закончен.

44. Метод наискорейшего спуска.

Метод применяется для нахождения минимума некоторой функции = f(x1, x2, ..., xn), заданной в евклидовом пространстве, где = (x1, x2, ..., xn) — вектор. Численные методы отыскания экстремума функции состоят в построении последовательности векторов { }, удовлетворяющих условию: f( ) > f( (1)) > ... > f( (n)). Методы построения таких последовательностей называются методами спуска. В этих методах элементы последовательности { } вычисляются по формуле

(k = 0, 1, 2,... …),

где вектор (k) определяет направление спуска; — длина шага в данном направлении.

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

(k = 0, 1, 2,... ),

где в точке .

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

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

|| grad f( (k+1)) || < e, где || grad f || = . В этом случае полагаем .

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

Метод применяется для отыскания минимума функции n перемен- ных. Выбирается некоторое начальное приближение х(0) точки минимума функции. Затем выбирается направление спуска параллельно оси 0х1 и решается задача одномерной минимизации функции. Величина a0 определяется из условия

Затем определяется первое приближение точки минимума а все остальные координаты остаются без измене- ния. При следующем уточнении точки минимума спуск производится вдоль линии, параллельной оси 0х2. Величина a1 определяется из условия

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