Оптимизация Интегрирование

оптимизации

Выбор оптимального решения производится с помощью некоторой зависимой от параметров x1, x2, …, xn функции y=f(x1, x2, …, xn), которая называется целевой функцией.

Задачи оптимизации делятся на:
а) безусловные, когда необходимо найти max/min целевой функции
б) условные, при постановке которых задаются некоторые условия (ограничения) в виде уравнений и неравенств.

σ и найти величину x ∈ σ, соответствующую max/min значению функции.

Одномерная оптимизация

Теорема Вейерштрасса: Всякая функция f(x), непрерывная на отрезке [a,b], принимает на этом отрезке наибольшее и наименьшее значение, т.е. на отрезке [a,b] существуют такие x1 и x2, что
f(x1) ≤ f(x) ≤ f(x2)

Не доказывает единственности решения – на [a,b] может быть несколько min и max;
Это может быть точка локального max/min.

количество вычислений функции.
3. Метод золотого сечения.
Наиболее распространенный метод.
4. Метод перебора.
Часто используется.

Основные методы задачи

CB называется такое деление отрезка, при котором отношение его бóльшей части ко всей длине отрезка равно отношению его меньшей части к бóльшей:

Определение золотого сечения

[a,b];

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

2. Функция f(x) имеет одну точку экстремума (min или max) на интервале [a,b], т.е. функция УНИМОДАЛЬНА.

3. Задана точность нахождения точки экстремума ε, например ε = 10-3.

Найти: Минимальное значение функции на [a,b].

точки y и z по формулам:

Алгоритм метода золотого сечения

y = b – (b-a)*s = b – bs + as = as + (1-s)b =>
y = 0,618a + 0,382b

z = a + (b-a)*s = a – as + bs = (1-s)a + sb =>
z = 0,382a + 0,618b

f(y) и f(z).

Алгоритм метода золотого сечения

3. Проверяем условие f(y) < f(z) (1):

a) Если условие выполняется, то переопределяем интервал [a,b] <= [a,z], т.е. сокращаем интервал до [a,z] и называем новый интервал [a,b].

б) Если условие не выполняется, то переопределяем интервал [a,b] <= [y,b], т.е. сокращаем интервал до [y,b] и называем новый интервал [a,b].

< ε (2).

Алгоритм метода золотого сечения

а) Если точность достигнута (условие (2) выполняется), то решение найдено и равно:

и

б) Если точность не достигнута (условие (2) не выполняется), то перейти к п 1. (к следующей итерации).

уменьшается:
в начале его длина равна b – a, а к концу становится меньше заданной точности ε.

Вывод:

Если искать максимум функции f(x), то в методе золотого сечения меняется только условие (1) на противоположное:
f(y) > f(z)

пределами интегрирования [a,b].

Численное интегрирование

Решение: Разбиваем интервал [a,b] на равные по длине интервалы (N интервалов) и заменяем площадь каждой i-той трапеции площадями прямоугольников:

Si – площадь i-того прямоугольника, R – погрешность вычисления.

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

1. Первообразная функции F(x) (т.е. F´(x) = f(x) ) не может быть найдена.

2. Функция f(x) задана таблично.

интеграла:

Постановка задачи: Пусть функция f(x) непрерывна и дифференцируема на интервале [a,b]. Дана точность ε = 10-4 нахождения интеграла.

Найти: значение интеграла
с заданной точностью ε.

Найдем h – длину каждого i-того интервала h = (b – a)/N.

3. Найдем площадь каждого i-того прямоугольника, принимая за его длину значение функции в середине каждого i-того интервала, а за ширину – длину интервала h. Т.е.

i-той прямолинейной трапеции (соединяя точки в начале и конце i-того интервала прямой линией). Тогда

Метод трапеций