Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление




Скачать 184.13 Kb.
НазваниеЧисленные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление
Дата публикации06.09.2013
Размер184.13 Kb.
ТипДокументы
zadocs.ru > Информатика > Документы
Глава 4. Численные методы (процедуры) минимизации функции одной переменной
В связи с тем, что градиент функции многих переменных указывает направление наискорейшего возрастания функции в окрестности точки, в которой вычисляется градиент, то поиск минимума функции многих переменных по существу сводится к минимизации функции одной переменной.
4.1. Постановка задачи.
Пусть R={x:- 
Определение 1: Точку x*X называют точкой минимума функции f(x) на множестве X, если f(x*)f(x) для всех xX; величину f(x*) называют наименьшим или минимальным значением f(x) на X и обозначают . Множество всех точек минимума f(x) на X будем обозначать через X* .

В зависимости от свойств множества X и функции f(x) множество X* может содержать одну, несколько или даже бесконечно много точек, а также возможны случаи, когда X* пусто.

Пример 1: Пусть при x0 и f(0)=0. На множестве X={x: 1 x  2} минимальное значение F(x) равно нулю, множество X* содержит одну точку x* =1. Если X={x: 1/3  x 1}, то множество X* содержит три точки: 1/3, 1/2, 1; если X={x: 0  x  1}, то X* = {x: x =1/n, n=1,2,…} - счётное множество. В случае, когда X={x: 2 x < } функция f(x) не имеет наименьшего значения на X. В самом деле, какую бы точку xX ни взять, найдётся точка yX (например, y = k при достаточно большом k), такая что f(x)>f(y). Это значит, что X* = .
Пример 2: Функция на X={x: x1} принимает своё наименьшее значение, равное нулю, во всех точках отрезка X* ={x: 0 x1}. Если X={x: 1  x  2}, то X* содержит одну точку x*=1; если X={x: 1 < x  2}, то X* = .




Пример 3: Пусть f(x)=x при x0 и f(0)=1. На множествах X={x: 0  x  1} или X={x: 0 < x  1} эта функция не имеет наименьшего значения, т.е. X* =.

Пример 4: Пусть f(x) = ln(u), X={x: 0 < x  1}. Здесь X* =, так как во всех точках из X функция принимает конечные значения, а для последовательности xk =1/k, (k=1,2,…) имеем .


Определение 2: Функция f(x) называется ограниченной снизу на множестве X, если существует такое число М, что f(x)М для всех xX. Функция F(x) не ограничена снизу на X, если существует последовательность {xk}X, для которой .

В примерах 1-3 функции ограничены снизу на рассматриваемых множествах, а в примере 4 функция не ограничена.

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

Определение 3: Пусть функция f(x) ограничена снизу на множестве X. Тогда число f* называют нижней гранью f(x) на X, если

  1. f*  f(x) при всех xX;

  2. для любого сколь угодно малого числа >0 найдётся точка xX, для которой f(x)* + . Если функция f(x) не ограничена снизу на X, то в качестве нижней грани F(x) на X принимается f* =-. Нижнюю грань f(x) на X обозначают через .

В примерах 1-3 нижняя грань J* =0, а в примере 4 f* =-.

Если X* , то очевидно, нижняя грань f(x) на X совпадает с наименьшим значением этой функции на X, т.е. В этом случае говорят, что функция f(x) на X достигает своей нижней грани. Подчеркнём, что всегда существует, а , как мы видели из примеров 1-4, не всегда имеет смысл. Введём ещё два определения.

Определение 4: Последовательность {xk}X называется минимизирующей для функции f(x) на множестве X, если

.

Из определения и существования нижней грани следует, что минимизирующая последовательность всегда существует.

Определение 5: : Скажем, что последовательность {xk} сходится к непустому множеству X, если , где - расстояние от точки xk до множества X.

Теорема К. Вейерштрасса. Всякая непрерывная функция на замкнутом ограниченном множестве достигает экстремума (минимума, максимума).

4.2. Метод золотого сечения.
Определение 1: Функцию f(x) назовем унимодальной на отрезке [a, b], если она непрерывна на отрезке [a, b] и существуют такие числа , (a ≤  ≤ ≤ b) такие, что

1) f(x) строго монотонно убывает при a ≤ x ≤  (если a < );

2) f(x) строго монотонно возрастает при  ≤ x ≤ b (если < b);

3) f(x) = при  ≤ x ≤ , так что X* = [, ]

Случаи, когда один или два из отрезков [a, ], [, ], [, b] вырождаются в точку, здесь не исключаются.

В частности, если =, то функцию f(x) называют строго унимодальной на отрезке [a, b].

Перейдём к описанию метода минимизации унимодальной функции на отрезке, основанном на отношении золотого сечения.

Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, что отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Если взять за единицу длину всего отрезка, а за t обозначить длину большего отрезка, тогда (1-t) – будет длиной малого отрезка. Тогда это отношение (золотое сечение) находится из следующего уравнения

,

Таким образом, t2 + t - 1 = 0, откуда t1 = (-1 + 5)/2 = 0,618033989. Отрицательный корень t2 = (-1 - 5)/2 этого уравнения не подходит в качестве золотого сечения.

Легко проверить, что золотое сечение отрезка [a, b] производится двумя точками x1 = a+(3-5)*(b-a)/2 = a+(b-a)*0,381966011 и x2 = a+(-1+5)*(b-a)/2 = a+(b-a)*0,61803989, расположенными симметрично относительно середины отрезка, причём a12
В результате анализа двух рассмотренных значений функции будет определен тот интервал, который должен исследоваться в дальнейшем. Этот интервал будет содержать одну из предыдущих точек и следующую точку, помещаемую симметрично ей. Первая точка находится на расстоянии (b-a)0,381966011 от одного конца интервала, вторая — на таком же расстоянии от другого. Далее х1 и х2 будем обозначать через u1 и u2, соответственно.

Замечательно здесь то, что точка u1 в свою очередь производит золотое сечение отрезка [а, u2], так как u2 - u1 < u1 - а = b - u2 и (u2 - а)/(u1 - a) = (u1 - а)/(u2 – u1). Аналогично точка u2 производит золотое сечение отрезка [u1, b]. Опираясь на это свойство золотого сечения, можно предложить следующий метод минимизации унимодальной функции f(u) на отрезке [a, b].

Положим a1 = a, b1 = b. На отрезке [а1, b1] возьмем точки u1, u2, производящие золотое сечение, и вычислим значения f(u1), f(u2). Далее, если f(u1)≤f(u2), то примем a2= u1, b2 = u2, = u1; если же f(u1)>f(u2), то примем а2=u1, b2 = b1, = u2. Поскольку функция f(u) унимодальна на [а, b], то отрезок [а2, b2] имеет хотя бы одну общую точку с множеством U* точек минимума f(u) на [a, b]. Кроме того, b22 = (5- 1) (b-а)/2 и весьма важно то, что внутри [a2, b2] содержится точка с вычисленным значением f() = min{f(u1); f(u2)}, которая производит золотое сечение отрезка [a2, b2].

Пусть уже определены точки u1, ..., un-1, вычислены значения f(u1), ..., f(un-1), и найден отрезок [аn-1, bn-1] такой, что

n-1, bn-1]U* ≠, bn-1-an-1=((5-l)/2)n-2*(b-a), и известна точка , производящая золотое сечение отрезка [аn-1, bn-1] и такая, что f() = (n2). Тогда в качестве следующей точки возьмем точку un = аn + bn-1 - , также производящую золотое сечение отрезка [an-1, bn-1], вычислим значение f(un).

Пусть для определенности an-1 n< < bn-1 (случай < un рассматривается аналогично). Если f(un)f(), то полагаем an = an-1, bn = , = un, если же f(un) >f(), то полагаем an = un, bn = bn-1, =. Новый отрезок [an, bn] таков, что [an, bn]U* ≠ , bn-an = ((5 -1)/2)n-1*(b-а), точка производит золотое сечение [an, bn]„| и f() = min{f(un); f()}= .

Если число вычислений значений f(x) заранее не ограничено, то описанный процесс можно продолжать, например, до тех пор, пока не выполнится неравенство bnn<, гдо  — заданная точность. Если же число вычислений значений функции f(x) заранее жестко задано и равно n, то процесс на этом заканчивается и в качестве решения задачи второго типа можно принять пару (f(),), где f() является приближением для f* = , а точка служит приближенном для множества U* с некоторой погрешностью.
Алгоритм поиска точки минимума по методу золотого сечения.

Шаг 1. Полагаем k=0, ak = a0 = 0, bk = b0 = 10,  = 0,1.

Шаг 2. Полагаем k = bk – ak.

Шаг 3. Если k <, то перейти в шагу 6, иначе перейти к следующему шагу 4.

Шаг 4. Положим

u1 = ak + (bk - ak)0,381966011,

u2 = ak + (bk - ak)0,61803989.

Вычислим f(u1) и f(u2).

Шаг 5. Если f(u1)
ak+1 = ak, bk+1 = u2, а также полагаем k:=k+1 и перейдем к шагу 2,

в противном случае (иначе) полагаем

ak+1 = u1, bk+1 = bk,

а также полагаем k:=k+1 и переходим к шагу 2.

Примечание 1. Отметим, что k = bk – ak.= (0,61803989)k0.

Шаг 6. Положим f(x*) = min{f(u1), f(u2)} и x* = arg min{f(u1), f(u2)}.

Примечание 2. Можно показать, что в случае если f(u1)
Задание к лабораторной работе №3 по теме «Минимизация функции одной переменной».
Задание 4.1. Возьмем в качестве а0=0, b0=10 и =0,1. Применить метод золотого сечения к функции

f(x) = N2(x-N3)2 + N1,

где N3 - последняя цифра номера вашей личной зачетной книжки студента (или студенческого билета);

N2 – предпоследняя цифра номера вашей личной зачетной книжки студента (или студенческого билета)и соответственно

N1 – третья с конца цифра номера вашей личной зачетной книжки студента (или студенческого билета).

Если какая-либо цифра равна нулю, то возьмите в качестве этой цифры единицу.

Задание 4.2. Взять в качестве а0=0, в качестве b0=10 и =0,1. Применить метод золотого сечения к функции из своего варианта из задания №1 в направлении антиградиента.

Начальная точка .

4.3. Поиск отрезка, содержащего точку минимума. Метод удвоения шага.

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

Шаг 1 (нестандартный). Выбирают точку x0 и определяют направление убывания функции f(x). Для этого выбирают число h и вычисляют f(x0+h). Если f(x0 + h) < f(x0), то полагают х1 = x0+ h и переходят к шагу 2 при k=1. Если f(x0+ h)  f(x0), то полагают h = -h и вычисляют f(x0+h). Если f(x0 + h) < f(x0), то полагают х1 = х0 + h и переходят к шагу 2 при k = 1. Если f(x0+ h)  f(x0), то полагают h = h/2 и повторяют процедуру предварительного шага. В результате шага 1 получают число h и точки x0, x1= x0 + h такие, что f(x1) < f(x0).

Шаг 2. Удваивают h и вычисляют хk+1 = xk + h.

Шаг 3. Вычисляют f(xk+1). Если f(xk+1) < f(xk), то полагают k=k+1 и переходят к шагу 2. Если f(xk+1)  f(xk), то поиск останавливают и в качестве отрезка, содержащего точку минимума, выбирают [xk-1, xk+1].
Пример 1: y = (x2-9)(x-4), x0 = -1, h=1.
Прежде чем применять данный метод необходимо убедиться, что мы не последуем в ложном направлении. А именно – можно двигаться в сторону минус бесконечности целую бесконечность времени.

Для этого реализуем метод удвоения для функции из примера 1 с начальным приближением x0 = -2. Вычисления согласно методу удвоения показаны в таблице 1.
Таблица 1







xk

f(xk)

Шаг 1.

x0 =

-2

30




h=

1







x0+h=

-1

40
















h=-h

-1







x0+h=

-3

0
















x1 = x0 +h

-3







k=1







Шаг 2.

h=2h

-2



















x2 = x1 +h

-5

-144




k=k+1 = 2







Шаг 2.

h=2h

-4







x3 = x2 +h

-9

-936


Из этих вычислений видно, что мы долго можем двигаться в сторону минус бесконечности. Поэтому желательно вначале построить график функции, чтобы правильно выбрать начальную точку.
Задание к лабораторной работе №4 по теме «Поиск отрезка, содержащего точку минимума».
Задание 4.1.. Применить метод удвоения к функции

f(x) = (x2-N2)(x-N3) + N1, x0 = -1, h=1.

где N3 - последняя цифра номера вашей личной зачетной книжки студента (или студенческого билета);

N2 – предпоследняя цифра номера вашей личной зачетной книжки студента (или студенческого билета) и соответственно

N1 – третья с конца цифра номера вашей личной зачетной книжки студента (или студенческого билета).

Если какая-либо цифра равна нулю, то возьмите в качестве этой цифры единицу. Желательно вначале построить график функции, чтобы правильно выбрать начальную точку x0.
Литература к главе 4.
1. Васильев Ф.П. Численные методы решения экстремальных задач: Учебное пособие для вузов. – М.: Наука, 1988. – 552 с.

2. Карманов В.Г. Математическое программирование: Учебное пособие. – М.: Наука, Гл. ред. физ.-мат. лит., 1986. – 288 с.

3. Математические методы в экономике: Учебник. 2-е изд./Замков О.О., Толстопятенко А.В., Черемных Ю.Н. -М.: МГУ им. М.В. Ломоносова, "Дело и Сервис", 1999. –368 с.





Добавить документ в свой блог или на сайт

Похожие:

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconЛабораторная работа №7
Цель работы: изучить численные методы поиска минимума функции одной переменной. Ознакомиться с методами решения задач условной оптимизации...

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconРешение систем линейных уравнений методом Крамера
Понятие функции одной переменной, способы задания. Элементарные функции и их графики

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconЛекция. Процедуры и функции
Цель: ознакомиться со средой программирования Visual Basic for Applications, изучить процедуры и функции vba

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление icon16. Функции двух переменных. Понятие о множестве (линии) уровня функции...
...

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconФункции нескольких переменных
При рассмотрении функций нескольких переменных ограничимся подробным описанием функций двух переменных, т к все полученные результаты...

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconЭкзаменационные вопросы. Понятие функции. Способы задания функций. Элементарные функции
Предел функции. Непрерывность функции в точке. Точки разрыва функции и их классификация

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconОдной переменной
Пусть определена на и некоторая фиксированная точка; приращение аргумента в точке; соответствующее приращение функции; отношение...

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconИсследование дифференциальных уравнений широкое поле в чистой и прикладной математики
Дифференциальное уравнение является математическое уравнение для неизвестной функции одного или нескольких переменных, что касается...

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconПрограмма коллоквиума по теории пределов, дифференциальному исчислению...
Понятие функции (отображения). Область определения функции и множество её значений. График функции. Способы задания функции

Численные методы (процедуры) минимизации функции одной переменной в связи с тем, что градиент функции многих переменных указывает направление iconИ нтенсивная т ехнология м одульного о бучения приложения определённого...
Приложения определённого интеграла. Функции нескольких переменных: Методические указания и индивидуальные задания к модулю 9 системы...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов