35. Метод одномерного поиска. Деление интервала пополам

Главная задача м-дов одномерного поиска: нахождение extr за как можно меньше кол-во попыток. К прямым методам поиска относят методы, в которых для отыскания экстремума не используются производные первого и высших порядков. В этих методах направления поиска определяются на основе последовательных вычислений значений функции f(x). Если вычислять значения ЦФ в под интервалом неодинаковое число раз, можно повысить эффективность оптимума. Вычислить номер ЦФ на i сужаемых интервалах получим коэффициент дробления f=(2/(N+1))^i. В м-де пол. дел. принимают N=3, при этом на каждом интервале получается коэффициент дробления 0.5. При этом первое же вычисление 3ех значений позволяет сузить интервал неопределенности в 2раза. Последние вычисление требует выделения ф-ции в 2ух точках. В общем случае N >= 3 f =(1/(2^(N+1/2)). Отличие: требуется меньше вычислений, чем в м-де общего поиска.

36. Метод одномерного поиска. Метод Дихотомии

Главная задача м-дов одномерного поиска: нахождение extr за как можно меньше кол-во попыток. К прямым методам поиска относят методы, в которых для отыскания экстремума не используются производные первого и высших порядков. В этих методах направления поиска определяются на основе последовательных вычислений значений функции f(x). Вычислить Ц. функции в 2х точках на заданном интервале позволяет сузить интервал. Задача состоит в том, чтобы выбрать эти 2 точки, чтобы сужаемый интервал был минимальным. (рис). Если значение ЦФ при x1> чем при x2, по СИН: z=z1+z2. Зад: Одновременно минимизировать z1 и z2 при этом должны выполняться условия: 1) общий интервал не меняется z=z1+z2+z3; 2) z1>0, z2>0, z3>0. Исключим z2,тогда z-z1=min (1)

z-z3=min(2)

поскольку z задано, то правые части уравнений (1), (2) будут тем меньше, чем больше z1 и z3, то есть оптимальное значение будет достигаться в точке, когда z1=z3=0,5z, но эта опт. значение не может быть, так как наруш. условие. Тогда ] z2=ε. Вычитаем по ε/2. В результате после перв. пары вычисл. знач. : f=0,5+ ε/2

37. Методы одномерного поиска. Золотого сечения

Главная задача м-дов одномерного поиска: нахождение extr за как можно меньше кол-во попыток. К прямым методам поиска относят методы, в которых для отыскания экстремума не используются производные первого и высших порядков. В этих методах направления поиска определяются на основе последовательных вычислений значений функции f(x). Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки  и  такие, что:

, где  —пропорция золотого сечения. Таким образом:

То есть точка  делит отрезок  в отношении золотого сечения. Аналогично  делит отрезок  в той же пропорции. Это свойство и используется для построения итеративного процесса.