VII. Нахождение минимума функций одной переменной

1. Основные определения. Задача нахождения минимума функции f(x), xÎ[a,b] состоит в нахождении такой точки Î[a,b], что

(7.1)

Пусть задана функция f(x) на отрезке [a,b]. Точка Î[a,b] называется точкой глобального минимума, если для всех xÎ[a,b] выполняется условие:

(7.2)

Точка называется точкой локального минимума, если существует d - окрестность этой точки, что выполняется условие:

(7.3)

Если и выполняется условие то говорят, что является точкой строгого локального минимума.

Унимодальные функции. Если на отрезке [a,b] определена функция f(x) с одной точкой локального минимума и при этом для всех < функция строго убывает, , а для всех > функция строго возрастает , то такая функция называется унимодальной.

Этапы поиска минимума. Так же, как и в задаче поиска корня, задача поиска минимума разделяется на два этапа: этап локализации и этап итерационного уточнения. На этапе локализации выделяется отрезок минимальной длины, содержащий одну точку локального минимума, на котором функция является унимодальной. На втором этапе используется один из методов поиска точки минимума.

2. Методы прямого поиска:

а) оптимальный пассивный поиск. На отрезке [a,b] задается последовательность точек x₀,x₁,...,x_n, таких, что x_k=x₀+kh, k=1,...,n; x₀=a, x_n=b. В этих точках вычисляется значение функции f(x_k). За точку минимума принимается та точка x_k, для которой выполняется соотношение: . Следовательно: Отсюда предельная относительная погрещность равна

б) метод деления отрезка пополам. На отрезке локализации выбирается две точки: (обычно , где e-заданная точностья)и вычисляются значения и Если то точка минимума находится на отрезке если то точка минимума находится на отрезке , т.к. функция является унимодальной. Отрезок с точкой минимума принимается за новый отрезок локализации на котором опять выбираются две точки и т.д., до отрезка длина которого . После этого полагаем . Следовательно, для абсолютной предельной погрешности нахождения минимума можем записать: .

в) метод золотого сечения. Золотым сечением отрезка называется деление отрезка на две части, так что отношение длины всего отрезка к длине большей части равно отношению большей части lк длине меньшей (принцип подобия): . (Рис.4). Золотое сечение отрезка можно произвести двумя симметрично расположенными двумя точками:

(7.4)

где

Сечение называется золотым, потому, что точка x₁ в свою очередь производит золотое сечение отрезка [a,x₂], а точка x₂-золотое сечение отрезка [x₁,b].

В методе золотого сечения отрезок локализации делится золотым сечением на три части двумя точками x₁ и x₂. Вычисляются значения и . Если то точка минимума находится на отрезке , если , то точка минимума находится на отрезке , т.к. функция является унимодальной. Отрезок с точкой минимума принимается за новый отрезок локализации и т.д. до отрезка , длина которого . Полагаем . Следовательно: .

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

Варианты задания №10

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

1. 2.