Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
шпоры МО готовые!.docx
Скачиваний:
15
Добавлен:
24.09.2019
Размер:
2.33 Mб
Скачать

27. Основные определения в задаче одномерной минимизации. Примеры.

f(x)→min,

Предп., что f(x) принимает на X конечные значения. ,

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

.

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

Опр. Посл-ть {xk} сходится к Х, если .

Замеч. Если мн-во Х* не явл. пустым, то всегда min-щая посл-ть, сходящаяся к Х*.

Пример . Множ-во решений задачи min-ции f(X)

Х*={0}, f* =0. Посл-ть xk=k явл. минимизир. для f(x):

Опр. Функция f(x) наз. унимодальной на [a;b], если она непр. на этом отрезке и такие числа α, β, a≤αβ≤b, что ф-ция f(x) строго монотонно убывает при a≤x≤α, если a<α;

строго монотонно возрастает при βx≤b, если β<b. f(x)=f* при αxβ

Случаи, когда один или два из отрезков , , вырожд. в точку не исключ.

Если α=β, функция наз. строго унимодальной.

28.Метод деления отрезка пополам решения задачи одномерной минимизации.

Пусть f(x)-унимодальна на [a;b]. Решим задачу f(x)min.

Выберем 2 точки: , , δ>0.

точки x1 и x2 располагаются симметрично относительно середины отрезка [a;b]

если f(x1)≤ f(x2), то полагаем a1=a, b1=x2

если f(x1)>f(x2), то полагаем a1=x1, b1=b

В силу унимодальности f(x) [a1;b1]X*≠Ø

Пусть найден отрезок [ak-1;bk-1], длина кот. , который имеет непустое пересечение с множеством X*

,

если f(x2k-1)≤f(x2k) полагаем ak=ak-1, bk=x2k.

если f(x2k-1)>f (x2k) полагаем ak=x2k-1, bk=bk-1

Получим отрезок [ak;bk],

и который имеет непустое пересеч с X*

Процесс деления отрезка пополам продолж. до тех пор, пока не будет достигнута заданная точность ε>0, т.е. пока не будет выполнено условие

Чтобы достигнуть зад. точность необх. выполнить k делений отрезка пополам. Т.к. на каждом шаге знач. фнкции вычисл. дважды, то кол-во вычислений функции будет равно

В качестве решения берут точку x2k+1, если f(x2k+1)≤f(x2k+2) и точку x2k+2, если

f(x2k+1)>f(x2k+2)

Если нет необходимости вычисл. приближ. значение min-ма именно в точке, кот. выбрана в качестве решения, то за решение задачи можно взять середину

29.Метод золотого сечения.

МЗС позволяет решить задачу с требуемой точностью при меньшем кол-ве вычислений значения функции.

Опр, Золотым сечением отрезка наз деление отрезка на 2 неравные части так, что отношение длины меньшей части к длине большей равно отношению длины большей части к длине всего отрезка.

Из опр =>, что отрезок [a;b] делиться точками:

Точка х1 дает золотое сечение отрезка [a;x2], а х2 – отрезка [x1;b].

Описание МЗС

Решаем задачу . Положим а1=а, b1=b и найдем точки х1 и х2, котор делят [a1;b1] в золотом сечении. Вычислим и . Если , то положим а2=а1, b2=x2, .

Если , то а2=х1, b2=b1, . Длина построенного отрезка [a2;b2] равна и точка минимума функции принадлежит [a2;b2]. Пусть на некотор этапе найдены х1, х2,…,х[n-1] и найден отр-к в золотом сечении, его длина . Определим т по правилу . Возможны 2 случая: и Рассмотрим первый: вычисляем значения в обеих точках, Если , то . Иначе, . Получаем отрезок и . И найдем точку , кот делит в золотом сечении. Процесс повторяется до тех пор пока выполняется неравенство . В качестве решения задачи берут точку и с вычесленным значением функции в этой точке.

Замечание. Погрешность этого метода не превышает значение

Замечание. В МЗС сильно возрастает погрешность при вычислении по формуле из-за приблизительности вычислений , Поэтому на каждом шаге метода надо выполнять непосредственное деление отрезка в золотом сечении. И выбирать в качестве ту точку, которая дальше от .

Замечание. МЗС можно применять для нахождения минимума функций не явл-ся унимодальными. Но в этом случае решение может находиться далеко от глобального минимума.