Министерство путей сообщения РФ
Дальневосточный государственный университет путей сообщения
Кафедра «Прикладная математика»
Курсовая работа
по численным методам
«Минимизация функций нескольких переменных.
Метод спуска.»
Выполнили: Косолапов А.Г. Терехов А.А.
Проверил: Смагин С.И.
Хабаровск 2003
Содержание:
I. Методы спуска (Общая схема) _________________________ 3
II. Метод покоординатного спуска._____________________ 4
Метод градиентного спуска.________________________________ 7
III. Метод наискорейшего спуска.______________________________ 9
IV. Описание программы._____________________________________10
Общая блок схема.________________________________________ 11
Руководство для пользования.______________________________12
Приложение А (Листинг программы)__________________________13
IX. Приложение B
(Исследование функции U=A*x1^3+B*x2^2-C*x1-D*x2 (изменение шага))_____
25
Методы спуска
Общая схема
Все методы спуска решения задачи безусловной минимизации различаются
либо выбором направления спуска, либо способом движения вдоль направления
спуска. Это позволяет написать общую схему методов спуска.
Решается задача минимизации функции ((x) на всём пространстве En.
Методы спуска состоят в следующей процедуре построения последовательности
{xk}. В качестве начального приближения выбирается любая точка x0(En.
Последовательные приближения x1, x2, … строятся по следующей схеме:
1) в точке xk выбирают направление спуска - Sk;
2) находят (k+1)-е приближение по формуле xk+1=xk-hkSk.
Направление Sk выбирают таким образом, чтобы обеспечить неравенство
f(xk+1)’f(M2).
Проведем такую же минимизацию целевой функции по переменным x3, x4, . . . ,xn. Дойдя до переменной xn, снова вернемся к x1 и
продолжим процесс. Эта процедура вполне оправдывает название метода. С ее
помощью мы построим последовательность точек М0,М1,М2, . . . , которой
соответствует монотонная последовательность значений функции
f(M0) >’ f (M1)>’ f(M2) >’ Обрывая ее на некотором шаге k можно
приближенно принять значение функции f(Mk) за ее наименьшее значение в
рассматриваемой области.
Проведем такую же минимизацию целевой функции по переменным x3, x4,
. . . ,xn. Дойдя до переменной xn, снова вернемся к x1 и продолжим процесс.
Эта процедура вполне оправдывает название метода. С ее помощью мы построим
последовательность точек М0,М1,М2, . . . , которой соответствует монотонная
последовательность значений функции f(M0)>’ f(M1)>’ f(M2) >’ ... Обрывая ее на некотором шаге k можно
приближенно принять значение функции f(Mk) за ее наименьшее значение в
рассматриваемой области. Отметим , что данный метод сводит задачу поиска
наименьшего значения функции нескольких переменных к многократному решению
одномерных задач оптимизации. Если целевая функция f(x1, x2, ... ,xn) задана явной формулой и является дифференцируемой, то мы можем вычислить ее
частные производные и использовать их для определения направления убывания
функции по каждой переменной и поиска соответствующих одномерных минимумов.
В противном случае, когда явной формулы для целевой функции нет, одномерные
задачи следует решать с помощью одномерных методов
На рис.изображены линии уровня некоторой функции двух
переменных u= f (х, у). Вдоль этих линий функция сохраняет
постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее
наименьшего значения, которое достигается в точке О, с помощью метода
покоординатного спуска. При этом нужно ясно понимать, что рисунок служит
только для иллюстрации метода.
Пусть требуется решить задачу (2): f(x) [pic] min, х ?Rn. (2)
В двумерном пространстве R2. Решение задачи (2) методом покоординатного
спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей
общей схеме.
Выбирают произвольно начальную точку х(0) из области определения
функции f(х). Приближения х(k) определяются соотношениями
(3): x(k+1)=x(k)+t(k)S(k) (k=0,1,2, ...), где вектор направления спуска s(k)- это единичный вектор, совпадающий с
каким-либо координатным направлением (например, если S(k) параллелен х1,
то S(k)= {1,0,0,...,0}, если он параллелен x2, то S(k)={0, 1, 0, . . . ,0}
и т.д.) ; величина t(k) является решением задачи одномерной минимизации:
f(x(k)+ts(k)) [pic] min, t ?R1, (k=0,1,2, ...),
и может определяться, в частности, методом сканирования.
Детальная реализация общей схемы в двумерном случае R2 дает траекторий
приближения к точке х* методом покоординатного спуска, состоящую из звеньев
ломаной, соединяющих точки х(k), x1~(k) x(k+1) (k=0, 1, 2,) . При
k=0, исходя из начальной точки х(0)=(x1(0),x2(0)), находят точку х~(0)=
(x1~(0),x2(0)), минимума функции одной переменной f(x1,x2(0)); при этом
f(x~(0))