Автор работы: Пользователь скрыл имя, 22 Марта 2014 в 16:57, курсовая работа
Построение последовательности заканчивается в точке , для которой , где – заданное малое положительное число, или при ( – предельное число итераций), или при двукратном одновременном выполнении двух неравенств , где – малое положительное число. Вопрос о том, может ли точка рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования.
Содержание
Пусть дана функция , ограниченная снизу на множестве и имеющая непрерывные частные производные во всех его точках.
Требуется найти локальный минимум функции на множестве допустимых решений , т.е. найти такую точку , что
Стратегия метода Ньютона состоит в построении последовательности точек , , таких, что ,
Точки последовательности вычисляются по правилу
где точка задается пользователем, а направление спуска определяется для каждого значения по формуле
Выбор по формуле (2) гарантирует выполнение требования при условии, что . Формула (2) получена из следующих соображений:
1. Функция аппроксимируется в каждой точке последовательности квадратичной функцией .
2. Направление определяется из необходимого условия экстремума первого порядка: . Таким образом, при выполнении требования последовательность является последовательностью точек минимумов квадратичных функций . Чтобы обеспечить выполнение требования , даже в тех случаях, когда для каких-либо значений матрица Гессе не окажется положительно определенной, рекомендуется для соответствующих значений вычислить точку по методу градиентного спуска с выбором величины шага из условия .
Построение последовательности заканчивается в точке , для которой , где – заданное малое положительное число, или при ( – предельное число итераций), или при двукратном одновременном выполнении двух неравенств , где – малое положительное число. Вопрос о том, может ли точка рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования.
Шаг 1. Задать , , , – предельное число итераций, найти градиент и матрицу Гессе .
Шаг 2. Положить .
Шаг 3. Вычислить .
Шаг 4. Проверить выполнение критерия окончания :
а) если неравенство выполнено, то расчет окончен, ;
б) если нет, то перейти к шагу 5.
Шаг 5. Проверить выполнение неравенства :
а) если неравенство выполнено, то расчет окончен: ;
б) если нет, то перейти к шагу 6.
Шаг 6. Вычислить матрицу .
Шаг 7. Вычислить .
Шаг 8. Проверить выполнение условия :
а) если , то перейти к шагу 9;
б) если нет, то перейти к шагу 10, положив .
Шаг 9. Определить .
Шаг 10. Найти точку ,
положив , если ,
или выбрав из условия , если .
Шаг 11. Проверить выполнение условий:
а) если оба условия выполнены при текущем значении и , то расчет окончен, ;
б) в противном случае положить
Стратегия метода Ньютона – Рафсона состоит в построении последовательности точек , , таких, что ,
Точки последовательности вычисляются по правилу
где точка задается пользователем, а величина шага определяется из условия
Задача (4) может решаться либо аналитически с использованием необходимого условия минимума с последующей проверкой достаточного условия , либо численно как задача
где интервал задается пользователем.
Если функция достаточно сложна, то возможна ее замена полиномом второй или третьей степени и тогда шаг может быть определен из условия при выполнении условия .
При численном решении задачи определения величины шага степень близости найденного значения к оптимальному значению , удовлетворяющему условиям , , зависит от задания интервала и точности методов одномерной минимизации.
Построение последовательности заканчивается в точке , для которой , где – заданное число, или при (М – предельное число итераций), или при двукратном одновременном выполнении двух неравенств , – малое положительное число.
Вопрос о том, может ли точка рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования.
Шаг 1. Задать , , , – предельное число итераций, найти градиент и матрицу Гессе .
Шаг 2. Положить .
Шаг 3. Вычислить .
Шаг 4. Проверить выполнение критерия окончания :
а) если неравенство выполнено, то расчет окончен, ;
б) если нет, то перейти к шагу 5.
Шаг 5. Проверить выполнение неравенства :
а) если неравенство выполнено, то расчет окончен: ;
б) если нет, то перейти к шагу 6.
Шаг 6. Вычислить матрицу .
Шаг 7. Вычислить .
Шаг 8. Проверить выполнение условия :
а) если условие выполняется, то найти ;
б) если нет, то положить .
Шаг 9. Определить .
Шаг 10. Найти шаг из условия .
Шаг 11. Вычислить .
Шаг 12. Проверить выполнение неравенств:
а) если оба условия выполнены при текущем значении и , то расчет окончен, ;
б) в противном случае положить и перейти к шагу 3.
Стратегия решения задачи состоит в построении последовательности точек , , таких, что , Точки последовательности вычисляются по правилу
где точка задается пользователем; величина шага определяется для каждого значения из условия
Решение задачи (3) может осуществляться с использованием необходимого условия минимума с последующей проверкой достаточного условия минимума . Такой путь может быть использован либо при достаточно простой минимизируемой функции , либо при предварительной аппроксимации достаточно сложной функции полиномом (как правило, второй или третьей степени), и тогда условие замещается условием , а условие – условием .
Другой путь решения задачи (3) связан с использованием численных методов, когда ищется . Границы интервала задаются пользователем. При этом степень близости найденного значения к оптимальному значению , удовлетворяющему условиям , зависит от задания интервала и точности методов одномерной минимизации.
Построение последовательности заканчивается в точке , для которой , где – заданное малое положительное число, или , где М – предельное число итераций, или при двукратном одновременном выполнении двух неравенств , где – малое положительное число. Вопрос о том, может ли точка рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования.
Шаг 1. Задать , , , , – предельное число итераций.
Найти градиент функции в произвольной точке .
Шаг 2. Положить .
Шаг 3. Вычислить .
Шаг 4. Проверить выполнение критерия окончания :
а) если критерий выполнен, расчет закончен, ;
б) если критерий не выполнен, то перейти к шагу 5.
Шаг 5. Проверить выполнение неравенства :
а) если неравенство выполнено, то расчет окончен: ;
б) если нет, то перейти к шагу 6.
Шаг 6. Вычислить величину шага из условия
Шаг 7. Вычислить .
Шаг 8. Проверить выполнение условий
а) если оба условия выполнены при текущем значении и , то расчет окончен, ;
б) если хотя бы одно из условий не выполнено, положить и перейти к шагу 3.
Исследовать численный метод поиска минимума функции многих переменных.
Функция: .
Тестовая функция: Химмельблау
Использовать методы:
а) Ньютона;
б) Ньютона-Рафсона с использованием дихотомии и «золотого сечения»;
г) Градиентного спуска с дроблением шага.
Точность вычислений: , , .
На основе выше изложенной теории, составляем блок-схемы поиска безусловного минимума функции многих переменных методом Ньютона.
Блок – схемы методов одномерной минимизации
а) метод дихотомии (diho(xk,dk)); б) метод золотого сечения (zoloto(xk,dk))
Блок – схема метода Ньютона
Блок – схема метода Ньютона - Рафсона
Блок – схема метода наискорейшего градиентного спуска
Выполняем задачу для тестовой функции Химмельблау.
Результаты выполнения программ согласуются с теоретическими результатами для тестовой функции за исключением метода Ньютона – он расходится.
Выполняем задачу для заданной функции.
Изменяем значение .
Вывод: полученные результаты говорят о том, что при уменьшении решение уточняется.