Учебные материалы


Рассмотрим математическую постановку одномерной задачи оптимизации на конкретном примере



Карта сайта leproprice.ru Р А З Д Е Л Ы К У Р С А

  • Назначение методов одномерной оптимизации.пример постановки оптимизационной задачи.
  • Классификация методов.область применения аналитических и численных методов.
  • Численные методы оптимизации при отсутствии априорной информации. Метод сканирования.
  • Методы оптимизации унимодальных функций (методы исключения интервалов). Общие сведения.
  • Установление границ начального интервала неопределенности для методов исключения интервалов.
  • Метод дихотомии.
  • Метод золотого сечения.
  • Сравнение эффективности методов.
  • Методы точечного оценивания (метод Пауэлла).
  • Назначение методов одномерной оптимизации. Пример постановки оптимизационной задачи.одномерные задачи относятся к наиболее простому типу оптимизационных задач. Однако знать методы одномерной оптимизации очень важно ,поскольку они применяются :
  • Для решения практических задач с одним управляемым параметром ; входят в ряд методов многомерной оптимизации
  • Для нахождения экстремума функции многих переменных В заданном направлении. Оптимизируемой переменной в этом случае является величина шага в заданном направлении . Таковы ,например ,методы наискорейшего спуска ,сопряженных направлений ,переменной метрики и другие . Рассмотрим математическую постановку одномерной задачи оптимизации на конкретном примере. Задача " окно имеет прямоугольную форму. Периметр окна равен 8 м. Каковы должны быть размеры окна (длина и ширина), чтобы оно пропускало наибольшее количество света? " Очевидно, что количество света, пропускаемое окном, однозначно связано с площадью окна. Следовательно, в задаче требуется найти такие размеры окна - его длину и ширину - при которых площадь окна будет максимальной при заданном периметре. Математическая постановка задачи включает в себя:
  • Выбор переменных задачи;
  • Запись в виде функции этих переменных критерия оптималь-ности;
  • Запись в виде функции этих переменных ограничений задачи. Выберем в качестве переменных задачи длину окна и ширину окна b. Тогда критерий оптимальности можно записать как функцию этих переменных следующим образом: s = a*b Ограничение на периметр окна можно записать следующим образом: p = (a+b)*2 Из полученной математической постановки задачи следует, что данную задачу надо рассматривать как двумерную задачу условной оптимизации при одном ограничении-равенстве. Решить такую задачу методами одномерной оптимизации Не представляется возможным. Однако ее можно сформулирвать как одномерную оптимизационную задачу , если выбрать в качестве переменной задачи Только длину окна a, а ширину выразить через длину, используя заданный периметр . Ширина окна b выражается через его длину a и периметр p следующим образом: B = (8 - 2*a)/2 = 4 - a Теперь площадь окна, являющаяся попрежнему целевой функцией, будет представлять собой функцию одной переменной a: S = a*(4 -a) Ограничения в задаче отсутствуют. Задачу в такой математической постановке можно решить методами одномерной оптимизации ! Надо отметить, что задачи и более высокой размерности, чем 2, тоже могут быть сведены к одномерным, если число уравнений-ограничений задачи на 1 меньше, чем число переменных. Попробуйте самостоятельно сделать математическую постановку следующей задачи как одномерной задачи оптимизации, обозначив переменную через x, а критерий оптимальности через f(x). Теперь можно перейти к изучению следующего раздела курса - рассмотрению методов решения одномерных оптимизационных задач. При этом будем считать, что критерий оптимизации задан, т.е. Математическая постановка задачи уже выполнена. Физическим смыслом как самого критерия, так и переменной задачи интересоваться не будем. Если хотите выйти на перечень разделов курса - введите 0.
  • Классификация методов. Область примененияаналитических и численных методов. На следующем кадре вам будет предложена классификация методов одномерной оптимизации. Запишите ее в тетрадь и постарайтесь запомнить названия методов . Классификация Методов Одномерной Оптимизации 1. Аналитические 2. Численные 2.1метод равномерного поиска 2.2 методы исключения интервалов 2.2.1метод дихотомии 2.2.2метод золотого сечения 2.2.3метод фибоначчи 2.3 методы точечного оценивания 2.3.1методы, использующие квадратичнуюаппроксимацию (метод пауэлла) 2.3.2методы, использующие кубическуюаппроксимацию Личных классов целевых функций. Рассмотрим, какие методы оптимизации применимы для разпростейшим является случай, когда целевая функция задана в виде аналитической зависимости: y=f(x),непрерывна и может быть найдено явное выражение для ее производной: df/dx. Нахождение экстремумов таких функций можно проводить известными из курса высшей математики методами дифференциального исчисления (будем называть их в дальнейшем аналитическими методами). Напомним вкратце этот путь. При нахождении экстремума аналитическими методами находится значение переменной x, обращающее в нуль первую производную функции: df/dx = 0. Отсюда вытекает требование непрерывности и дифференцируемости самой функции. Это так называемое 'необходимое условие' экстремума. Характер экстремума - максимум или минимум функцииопределяется по знаку второй производной: d(df/dx)/dx. Отсюда вытекает требование непрерывности и дифференцируемости первой производной функции. Если функция задана на конечном интервале , то она может достигать своего наибольшего и наименьшего значения либо в граничных точках интервала, либо в точках максимума и минимума. Последние точки обязательно должны быть критическими, т.е. Производная функции: df/dx в этих точках должна обращаться в нуль. Это - необходимое условие экстремума! Следовательно, для определения наименьшего или наибольшего значения функции f(x) на заданном интервале нужно вычислить ее значения во всех критических точках данного интервала и в его граничных точках и сравнить полученные значения между собой. Наибольшее или наименьшее из них и будет искомым значением. П Р И М Е Р " Найти наименьшее значение функции: на интервале [ 1,3 ]". РЕШЕНИЕ Вычислим производную функции по переменной x: Приравнивая ее нулю, найдем критические точки: X = 0 и X = 2 Точка x = 0 лежит вне заданного интервала, поэтомудля анализа оставляем три точки: X = 1 X = 2 X = 3 ВЫЧИСЛЯЕМ ЗНАЧЕНИЯ ФУНКЦИИ В ЭТИХ ТОЧКАХ: F(1) = -2/3 F(2) = -4/3 F(3) = 0 Сравнивая их, заключаем, что наименьшего значения функция достигает в точке: x = 2. Это значение: F(2) = -4/3. Следуеи иметь в виду, что если функция f(x) является непрерывной дифференцируемой функцией с непрерывной производной, то для отыскания экстремума наряду с аналитическими,могут быть применены и численные методы оптимизациитоже. Это чаще всего целесообразно в том случае, когда df/dx = 0 является сложным нелинейным уравнением, аналитическое решение которого не представляется возможным. А если целевая функция не является дифференцируемой? Еcли она не задана аналитически, а есть только возможность смоделировать ее или измерить экспериментально ? Такие задачи можно решить только численнми методами оптимизации ! Если функция не является дифференцируемой во всех точках области определения, то даже необходимое условие наличия оптимума, позволяющее идентифицировать стационарные точки, может не выполняться в точке оптимума. Поясним это на примере. Задана кусочно-линейная функция Эта функция непрерывна во всех точках действительной оси (то есть не имеет разрывов), но недифференцируема при x=2. Функция достигает максимума в точке x=2, которая не является стационарной. Напомним, что стационарной называется точка, в которой 1-ая производная функции f(x) обращается в ноль.
  • Численные методы оптимизации при отсутствии априорной информации. Метод сканирования. Будем считать, что с аналитическими методами решения задач одномерной оптимизации вы знакомы из курса математического анализа. Остановимся на численных методах. Для определенности будем исследовать задачу минимизации , поскольку, как известно, max f(x) = min (-f(x)). Существует множество численных методов одномерной оптимизации. Среди них есть более простые и более сложные. Сложность метода зависит от априорной информации о показателе качества f(x). Если о функции f(x) известно только то, что она имеет экстремальный характер, и никакой другой априорной информации нет, то при отыскании экстремума единственным разумным действием в такой ситуации будет последовательное нахождение значения критерия при всех допустимых значениях x. Поскольку таких значений на интервале [a,b] бесконечное множество, то практически перед решением задачи задаются точностью определения оптимального значения переменной x. Обозначим заданную точность через е . Тогда для отыскания экстремума следует определить f(x) в n равноотстоящих друг от друга на величину "е" точках, где целое число n задается округлением значения до ближайшего большего целого значения. При этом значение реализуемой точности решения е определяется как : Значения аргумента x в точках расчета определяются по следующей формуле: , где i =1,N Крайние точки отрезка получаются при i=1 и i=N. Из полученных значений функции выбирается наименьшее значение. Номер наименьшего значения и определяет оценку положения экстремума с точностью не хуже, чем заданная величина "e". Рассмотренный метод поиска называется сканированием. Рассмотрим пример , иллюстрирующий работу метода сканирования . Пуссть: Найти Хopt с точностью E = 0,55 Рассчитаем необходимое число точек 'n' . Для этого вычислим выыражение : (b-a)/E+1 = 8,27(27) округлив до ближайшего большего целого числа, получим N = 9. Реализуемая точность равна : Er = (b-a)/(N-1)=0,5, что лучше заданной точности E = 0,55 РАССЧИТАЕМ ЗНАЧЕНИЕ АРГУМЕНТА В 9 ТОЧКАХ ПО ФОРМУЛЕ : Рассчитаем значения функции в каждой точке : СРАВНИВАЯ ЗНАЧЕНИЯ ФУНКЦИИ В 9 ТОЧКАХ , НАХОДИМ :
  • Численные методы оптимизации унимодальных функций. Методы исключения интервалов. Общие сведения. Учет дополнительной информации о функции может сделать поиск экстремума более эффективным. Например, о функции может быть известно, что она имеет только один экстремум, или что она монотонна, или что ее вторая производная всюду сохраняет свой знак и т.п. Среди возможных дополнительных сведений о функции f(x) наиболее ценным и наименее обременительным является сведение о ее унимодальности (одноэкстремальности). Функция f(x) является унимодальной на отрезке [a,b] в том и только том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки x*. Иначе говоря, если x*—единственная точка минимума f(x) на отрезке a<=x<=b , то f(x) оказывается унимодальной на этом интервале тогда и только тогда, когда для точек x1 и x2 : Из x*<=x1<=x2 следует,что F(x*)<=F(x1)<=F(x2) Из x*>=x1>=x2 следует,что F(x*)<=F(x1)<=F(x2) Надо отметить, что унимодальная функция не обязательно должна быть непрерывной. Определить интервал, содержащий экстремум, на основании двух измерений функции позволяет правило исключения интервалов: пусть F(x) - унимодальна на замкнутом интервале a <= X <= b, а ее минимум достигается в точке X*. Рассмотрим точки X1 и X2, расположенные в интервале таким образом, что: a Если F(X1)>F(X2), то точка минимума F(x) не лежит в интервале (a,X1), t.e. X1 <= X* <= b
  • Если F(X1) Если F(X1)=F(X2), то можно исключить оба крайних интервала (a,X1) и (X2,b). при этом точка минимума должна располагаться в интервале (X1,X2), т.е. X1 < X* < X2. Замечание: правило исключения интервалов устраняет необходимость полного перебора всех допустимых точек! Методы поиска, которые позволяют определить оптимум функции одной переменной путем последовательного исключения подинтервалов и, следовательно,путем сокращения интервала поиска, носят название методов исключения интервалов. В процессе применения методов исключения интервалов можно выделить два этапа:
  • Этап установления границ интервала, на котором реализуется процедура поиска экстремума. это могут быть границы достаточно широкого интервала,содержащего заведомо точку оптимума. в поисковых задачах оптимизации отрезок, на котором располагается точка минимума, называют интервалом неопределенности
  • Этап уменьшения интервала, на котором реализуется конечная последовательность преобразований исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины e, определяющей точность поиска экстремума.
  • Установление границ начального интервала неопределенности для методов исключения интервалов. Если начальный интервал , содержащий точку минимума, неизвестен ,его можно получить . Поиск граничных точек начального интервала производится обычно с помощью эвристических методов. Рассмотрим один из них . Алгоритм получения начального интервала неопределенности состоит из двух этапов:
  • Выбор "удачного" направления
  • Движение в этом направлении до получения точки минимума. Исходными данными для алгоритма являются начальная точка x1 и величина шага d. Рассмотрим шаги первого этапа.
  • Вычислить значение функции в начальной точке: f1=f(x1)
  • Вычислить значения аргумента и функции после шага (-d): x4 = x1-d f4=f(x4)
  • Вычислить значения аргумента и функции после шага d: x5 = x1+d f5=f(x5)
  • Сравнить значения функции в точках х4,х1,х5:
  • Если F4>=F1>=F5 , шаг d удачного направления, оставляем его. Х2=х5, f2=f5
  • Если F4<=F1<=F5 , шаг d неудачный, надо изменить его знак на противоположный. d=-d х2=х4 f2=f4
  • Если F4>=F1<=F5 , то начальный интервал уже найден - точка минимума лежит между х4 и х5
  • Если F4=F5 , то функция f(x) не является унимодальной. Проиллюстрируем Возможные Варианты Окончания 1 Этапа а) * шаг d ведет к б) * * функция F(x) не унимо- | * уменьшению F(x), * | дальна, поскольку, кроме | | * то есть соотве- | | | минимума,она имеет еще и | | | тствует удачному | | | максимум. x4 x1 x5 направлению поиска. x4 x1 x5 Согласно предпо- ложению об унимодальности, точка минимума должна распола- гаться правее точки x1. в * * начальный г) * знак d надо | | интервал * | изменить. | * | { x4 , x5 } * | | | | | | | | x4 x1 x5 x4 x1 x5 На втором этапе - движения в выбранном направлении до получения интервала, содержащего точку минимума – делается ряд шагов увеличивающейся длины. Рассмотрим алгоритм второго этапа. Запишите название этапа и шаги алгоритма.
  • Переприсвоение: х0 присваивается значение х1, F0=F1 х1 присваивается значение х2, F1=F2
  • Расчет новой длины шага : d = d*2
  • Расчет аргумента и функции в третьей точке : х2 = х1 + d F2=F(x2)
  • Сравнение F2 и F1. Если F2 F1=10 > f5=8.9 функция в направлении шага d убывает, следовательно направление шага выбрано правильно. Принимаем:x2=x5=2.5 F2=F5=8.9 Выполним этап 2 алгоритма - движение в выбранном направлении до получения отрезка, содержащего точку минимума. итерация 1 - шаг 1: выполняем переприсвоение X0=X1=2 F0=F1=10 X1=X2=2.5 F1=F2=8.9 Шаг 2: Рассчитываем Новую Длину Щага d = 0.5*2=1 Шаг 3: рассчитываем аргумент и функцию в третьей точке : X2=2.5+1=3.5 F2=3.5+16/3.5=8.1 Шаг 4: сравниваем f2 и f1 : F2=8.1 < F1=8.9 . Следовательно, идем на шаг 1. Итерация 2 - Шаг 1:Выполняем Переприсвоение X0=X1=2.5 F0=F1=8.9 X1=X2=3.5 F1=F2=8.1 Шаг 2: Рассчитываем Новую Длину Шага: D=2*1=2 Шаг 3: рассчитаем аргумент и функцию в третьей точке : X2=X1+d=3.5+2=5.5 F2=5.5+16/5.5=8.5 Поскольку F2=8.5 > F1=8.1 , процедуру поиска границ начального интервала, содержащего точку минимума, заканчиваем.начальный интервал: [ 2.5, 5.5 ] Теперь попробуйте свои силы в самостоятельном решении аналогичной задачи: " найдите начальный интервал неопределенности для функции вида: F(X)= (3*X*X + X + 5)^ 2 Заданы начальная точка x=2 и величина шага d=0.5 "
  • Метод Дихотомии Величина подинтервала, исключаемого на каждом шаге, зависит от расположения пробных точек x1 и x2 внутри интервала поиска. Поскольку местонахождение точки оптимума заранее неизвестно ,целесообразно предположить ,что размещение пробных точек должно обеспечивать уменьшение интервала в одном и том же отношении на каждом шаге . В методе дихотомии это отношение равно 1:2, т.е. Интервал неопределенности делится на каждом шаге пополам и отбрасывается часть, где минимум заведомо быть не может. Кстати, само слово ' дихотомия ' означает последовательное деление на две равные части. На следующем кадре приведен рисунок , иллюстрирующий работу метода . а +-----------*-----------+----------*-----------+ в I итерация ' X1 ' ' ' Xm X2 а +-----*-----+-----*-----+ в II итерация X1 Xm ' X2 ' ' а +--*--+--*--+ в III итерация X1 Xm X2 а +--+--+ в IV итерация Xm На следующих кадрах приводится описание основных шагов поисковой процедуры , ориентированной на нахождение точки минимума функции F(x) в интервале [ a ; b ]
  • Положить хm = ( a + b )/2; l = b – a вычислить значение f(xm)
  • Положить х1 = a + l / 4; x2 = b - l / 4 заметим ,что точки х1 ,хm ,х2 делят интервал [ a ; b ] на 4 равныечасти . Вычислить значения F(x1) и F(x2) .
  • Сравнить f(x1) и f(xm) .
  • Если f(x1) < f(xm) ,исключить интервал [ xm ; b ] , положив b = xm .средней точкой нового интервала поиска становится точка х1 .следовательно , необходимо положить хm = x1.перейти к шагу 5 .
  • Если f(x1) >= f(xm) , перейти к шагу 4 .
  • Сравнить f(x2) и f(xm) .
  • Если f(x2) < f(xm) , исключить интервал [ a ; xm ] , положив a = xm. Так как средней точкой нового интервала становится точка х2 , положить хm = х2. Перейти к шагу 5 .
  • Если f(x2) >= f(xm) ,исключить интервалы [ a ; x1 ] , [ x2 ; b ] , положив a = x1 , b = x2. Заметим ,что хm продолжает оставаться средней точкой нового интервала. Перейти к шагу 5 .
  • Вычислить l = b - a . Рассмотрим пример , иллюстрирующий метод дихотомии . Минимизировать Функцию : F( X ) = ( 2 - X ) ^ 2 На Интервале 0 <= Х <= 8 , То Есть При A = 0; B = 8 Точность Поиска Е = 0,1 Выполняем итерацию 1. В соответствии с методом делаем шаг 1. Xm = ( a + b ) / 2 = 4 L = b - a = 8 F( Xm ) = 4 Переходим ко второму шагу. Делаем шаг 2 . X1 = a + L / 4 = 2 X2 = b - L / 4 = 6 F( X1 ) = 0 F( X2 ) = 16 Шаг 3. F( x1 ) = 0 < F( xm ) = 4 следовательно , исключается интервал [ xm ; b ] = [4 ;8 ] . Поэтому новое значение b = Xm = 4 Xm = X1 = 2 F(Xm) = F(2) = 0 Переходим к шагу 5 . Шаг 5 . L = b - a = 4 - 0 = 4 L = 4 > E = 0,1 СЛЕДОВАТЕЛЬНО ,ПОИСК НАДО ПРОДОЛЖАТЬ , Т.Е. ПЕРЕЙТИ К СЛЕДУЮЩЕЙ ИТЕРАЦИИ НА ШАГЕ 2 С ОТРЕЗКОМ [ 0 ; 4 ] . ПРИ ЭТОМ Xm = 2 , F( Xm ) = 0 . Итерация 2 . Шаг 2 . Х1 = a + L / 4 = 1 X2 = b - L / 4 = 3 F( X1 ) = 1 Шаг 3 . F( X1 ) = 1 > F( Xm ) = 0 Следовательно ,переходим к шагу 4 . Шаг 4 . F( X2 ) = 1 > F( Xm ) = 0 Следовательно , Исключаются Интервалы [ A ; X1 ] = [0; 1] [ X2 ; b ] = [3; 4] поэтому новое значение a = x1 = 1 b = X2 = 3 Старые Значения Сохраняются Для Xm = 2 F( Xm ) = 0 Переходим к шагу 5 . Шаг 5 . L = b - a = 3 - 1 = 2 L = 2 > E = 0,1 Следовательно ,поиск надо продолжать ,т.е. Перейти к следующей итерации на шаге 2 с отрезком [ 1; 3] при этом xm = 2 F( Xm ) = 0 Итерация 3 . Шаг 2 . X1 = a + L / 4 = 1,5 X2 = b - L / 4 = 2,5 F( X1 ) = 0,25 F( X2 ) = 0,25 Шаг 3 . F( X1 ) = 0,25 > F( Xm ) = 0 Следовательно, переходим к шагу 4 . Шаг 4 . F( X2 ) = 0,25 > F( Xm ) = 0 Следовательно Исключаются Интервалы [ A ; X1 ] = [ 1; 1,5 ] [ X2 ; b ] = [ 2,5 ; 3 ] Поэтому новое значение a = x1 = 1,5 b = X2 = 2,5 Старые значения сохраняются для xm = 2 f( xm ) = 0 Переходим к шагу 5 . ШАГ 5 . L = b - a = 2,5 - 1,5 = 1 L = 1 > E = 0,1 Следовательно, Поиск Надо Продолжать , Перейдя К Следующей Итерации На Шаге 2 С Отрезком [ 1,5 ; 2,5 ] L = 1 Последующие итерации аналогичны проделанным и далее не рассматриваются . Окончание процедуры происходит при выполнении условия l < e на шаге 5 . В нашем примере за 3 итерации ( т.е. При шести вычислениях функции f( x ) ) исходный интервал поиска длины 8 уменьшился до величины 1 ,т.е. 2^3 раз ! Как видим , метод дихотомии позволяет довольно быстро попасть в область экстремума . Так , для определения положения экстремума с точностью 1% от длины начального интервала надо сделать всего 14 измерений показателя качества ( это 7 итераций дихотомии ) ,т.к. L / ( 2 ^7 ) = l / 128 < 0.01*l . Это во много раз лучше ,чем метод перебора (сканирования), требующий, как вы помните,101 измерение !!! Итак ,в методе дихотомии интервал неопределенности уменьшается на каждые 2 вычисления значения функции (в точках х1 и x2 ) в два раза ,т.е. Длина отрезка на ( к + 1 ) итерации равна : L(k+1) = Lk/2^0,5 Где к - число измерений показателя качества .для дихотомии физический смысл имеют лишь четные 'к' . Попробуйте свои силы в самостоятельном решении аналогичной задачи. ЗАДАЧА " СДЕЛАТЬ 2 ИТЕРАЦИИ ПО МЕТОДУ ДИХОТОМИИ ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМУМА ФУНКЦИИ: F( X ) = X*X + 2*X ЗАДАННОЙ НА ИНТЕРВАЛЕ a=-2, b=4."
  • Метод Золотого Сечения Метод золотого сечения состоит в построении последовательности отрезков [a0,b0], [a1,b1], ..., Стягивающихся к точке минимума функции f(x). На каждом шаге, за исключением первого, вычисление значения функции производится лишь в одной точке. Эта точка, называемая "золотым сечением", выбирается следующим образом. Пусть длина исходного интервала неопределенности равна l, а точка делит его на две части: l1 и l2 , причем l1 > l2 и L1 + l2 = l. "золотое сечение" интервала неопределенности выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка: l1/l = l2/l1 ...(*). Из этого соотношения найдем точку деления. Обозначим отношение l2/l1 через t. Подставим его в уравнение (*). Получим: L1/(L1 + T*L1) = T Сократив Дробь На L1 , Получим: T*T + T - 1 = 0 Решение этого уравнения дает : T = 0.5 *(-1 + SQR(5)) = 0.61804... Таким образом, при золотом сечении длина большего отрезка l1 оказалась равной l*t, а длина меньшего отрезка : l*(1-t), где (1 - t) = 0.38196... Поскольку заранее неизвестно, в какой последовательности: l1 и l2 или l2 и l1 надо делить интервал, рассматривают точки, соответствующие двум способам деления. На следующем кадре вам будет предложен алгоритм метода. Он состоит из ряда шагов. Запишите шаги алгоритма. Алгоритм метода "золотого сечения"
  • Вычислить l=b-a
  • Положить x1=a + l*t1, x2=b-l*t1, где t1=0.38196 вычислить значения f(x1) и f(x2).
  • Сравнить значения функции в двух точках.
  • Если f(x1) Если f(x1)>=f(x2), то исключается интервал [a,x1). Полагаем a=x1, x1=x2.
  • Вычислить l=b-a. Если величина l мала, закончить поиск. В противном случае вернуться к шагу 2 на расчет недостающей точки. В качестве оптимального значения x можно принять x=a (либо x=b, либо x=0.5(a+b) ). Как видим, только на первой итерации вычисляются две промежуточные точки. На всех остальных - одна, поскольку другая переносится с предыдущей итерации. Однако следует иметь в виду, что для большей точности на каждой итерации лучше определять две новые точки, а не одну, поскольку значение t1 не является точным. При оперировании только с одной новой точкой ошибки округления при вычислении могут привести к потере интервала, содержащего миминум. Геометрическая иллюстрация метода "золотого сечения" . . | . . | | * . | | |. .* | | | . . | | | | . .* | | | | * | | | | | | | | | $---------|-----$--|-----$-------------$ 1-ая итерация a1 | | x1 | | x2| b1 | | | | | a2 $---------$-----$--|-----$ 2-ая итерация x1| x2| | b2| | | | | $-----$--$-----$ 3-ья итерация a2 x1 x2 b3 Проиллюстрируем работу метода золотого сечения, решив вместе с вами следующую задачу. Задача:" реализуйте процедуру одномерного поиска точки минимума функции F(x)=(2-x)^2 на интервале a<=x<=b, где a=0, b=8, Используя метод золотого сечения, выполните 3 итерации. Как изменится длина интервала в результате каждой итерации? " Ответы на эти вопросы мы получим, решая эту задачу на следующих кадрах. Итерация1
  • Вычисляем длину исходного интервала неопределенности: l = b - a = 8 - 0 = 8
  • Вычисляем значения аргумента и функции в двух точках: X1 = a + L*T1 = 3.06 X2 = b - L*T1 = 4.94 F(X1) = 1.13 F(X2) = 8.65
  • Сравниваем значения функции в двух точках. F(x1)=1.13 вычисляем длину интервала, полученного после 1-ой итерации l = b - a = 4.94 - 0 = 4.94. в результате выполнения 1-ой итерации длина интервала, содержащего минимум,уменьшилась в (8/4.94)=1.51 раза . иначе говоря, длина полученного интервала составляет (4.94/8)=0.62 от длины исходного интервала. Итерация 2 В соответствии с алгоритмом итерация 2 начинается с
  • Вычислим значения x и f(x) в новой точке. X1=a+l*(1-t)=0+(4.94*0.38196)=1.87 F(x1)=f(1.879)=0.0169 Ранее получили: x2=3.06 f(x2)=1.13 Переходим к шагу 3.
  • Сравним значения аргумента и функции В двух точках: F(x1)=0.0169 < F(x2)=1.13 Вновь интервал [x2,b] = [3.06,4.94] исключается. Поэтому новые значения: b=x2=3.06 x2=x1=1.87 F(x2)=F(1.87)=0.0169 Переходим к шагу 4 .
  • Вычислим длину интервала на второй итерации : L = b - a = 3.06 - 0 = 3.06 Длина интервала неопределенности после второй итерации уменьшилась по сравнению с исходной в 8/3.06 = 2.61 раза. При этом нам потребовалось вычислять значения функции в трех точках. Переходим к третьей итерации. Теперь вы познакомились с пошаговым решением задачи на 1 и 2 итерациях. Третья итерация дается без пояснений. Итерация 3
  • X1 = a + L * T1= 0 + 3.06 * 0.38196 = 1.17 X2 = 1.87 F(X1) = 0.69 F(X2) = 0.0169
  • F(X1) = 0.69 > F(X2) = 0.0169 ИСКЛЮЧАЕТСЯ ИНТЕРВАЛ [A,X1)= [0,1.17) НОВЫЕ ЗНАЧЕНИЯ ТОЧЕК: a = X1 = 1.17 b = 3.06 X1 = X2 = 1.87 F(X1) = F(1.87) = 0.0169
  • L = b - a = 3.06 - 1.17 = 1.89 Если интервал l = 1.89 велик ( больше заданной точности ), можно продолжить итерации аналогичным образом. По трем итерациям можно сделать следующие выводы: За три итерации ( 4 вычисления значения функции ) по методу золотого сечения исходный интервал длины 8 уменьшился до величины 1.89 для сравнения напомним, что в методе дихотомии при тех же условиях уменьшение интервала было до 2 -х !
  • Сравнение Эффективности Рассмотренных Методов Эффективность методов исключения интервалов можно оценить отношением интервала неопределенности после n вычислений целевой функции к начальному интервалу неопределенности. Такая функция эффективности предложена д.дж.уайлдом.обозначим ее через E. На следующем кадре представлена таблица, содержащая значения е ,соответствующие различным количествам вычислений целевой функции n для трех методов поиска. Запишите ее и постарайтесь запомнить для n = 10. Метод Поиска E 2 5 10 20 метод дихотомии 1/2 0.5 0.177 0.031 0.0009 метод сканиронирования 2/(N+1) 0.667 0.333 0.182 0.095 Из таблицы следует, что наиболее эффективным является метод золотого сечения. Он эффективнее метода сканирования в 950 !!! Раз ( при n = 20 ) Проведем также сравнение методов по количеству вычислений значений функции, требуемому для достижения заданной величины относительного уменьшения интервала неопределенности, или заданной степени точности. Если величина e задана, то значение n вычисляется По следующим формулам. Метод дихотомии : N = 2 Ln ( E ) / Ln 0.5 Метод Золотого Сечения: N = 1 + ( Ln ( E ) / Ln ( 0.618 )) Метод Сканирования: N = ( 2 / E ) - 1 В таблице приведены количества вычислений f(x) необходимых для определения координаты точки минимума с заданной точностью: Заданная Точность Е 0.1 0.05 0.01 0.001 Метод дихо томии 7 9 14 20 метод ска нирования 19 39 199 1999
  • Методы точечного оценивания. Метод пауэлла. Сейчас мы познакомимся с группой численных методов одномерной оптимизации,требующих от функции, кроме унимодальности, еще и непрерывность. Введение дополнительного требования делает методы этой группы более эффективными, чем методы исключения интервалов. Основная идея рассматриваемого метода связана с возможностью аппроксимации гладкой функции полиномом и последующего использования аппроксимирующего полинома для оценивания координаты точки оптимума. Согласно теореме вейерштрасса об аппроксимации, если функция непрерывна в некотором интервале, то ее можно с любой степенью точности аппроксимировать полиномом достаточно высокого порядка. Качество оценок координаты точки оптимума, получачаемых с помощью аппроксимирующего полинома, можно повысить:
  • использованием полинома более высокого порядка;
  • уменьшением интервала. Второй способ является более предпочтительным, поскольку построение аппроксимирующего полинома порядка выше 3-его становится весьма сложной процедурой, тогда как уменьшение интервала в условиях, когда выполняется предположение об унимодальности функции, особой сложности не представляет. Один из методов этой группы- метод пауэлла, основан на последовательном изменении процедуры оценивания с использованием квадратичной аппроксимации. Если задана последовательность точек: x1, x2, x3 и известны соответствующие этим точкам значения функции F1, F2, F3, то можно опредилить постоянные величины a0, a1, a2 таким образом, что значение квадратичного полинома: g(x)=a0+a1*(x-x1)+a2*(x-x1)*(x-x2) совпадают со значением F(x) в 3-х указаных точках. Рассчитаем коэффициенты полинома f(x). F1=F(X1)=a0+a1*(X1-X1)+a2*(X1-X1)*(X1-X2)=a0 ОТСЮДА: a0=F1 ...... (1) F2=F(X2)=a0+a1*(X2-X1)+(X2-X1)*(X2-X2)*a2 =a0+a1*(X2-X1) ОТСЮДА: a1=(F2-F1)/(X2-X1) .... (2) F3=F(X3)=a0+a1*(X3-X1)+a2*(X3-X1)*(X3-X2)=F1+(F2-F1)*(X3-X1)/(X2-X1)+a2*(X3-X1)*(X3-X2) ОТСЮДА: a2=((F3-F1)/(X3-X1)-a1)/(X3-X2)... (3) Зная коэффициенты a0, a1, a2 апроксимирующего полинома F(x), можно вычислить координату точки экстремума x путем приравнивания нулю 1-ой производной и последующего нахождения корней полученного таким образом уравнения: dF/dX=a1+a2*(X-X2)+a2*(X-x1)=0 X=(a2*(X1+X2)-a1)/(2*a2)=(X1+X2)/2-a1/(2*a2)... (4) Поскольку функция f(x) на рассматриваемом интервале и аппроксимирующий квадратичный полином унимодальны , то то можно ожидать , что экстремум полинома окажется вполне приемлемой оценкой точки истинного экстремума функции . Рассмотрим пример:"оценить координату x точки минимума функции f(x)=x*x+8/x на интервале 1<=x<=5 с помощью квадратичной апроксимации." Для получения коэффициентов квадратичного полинома необходимо знать значение функции в 3-х точках. Расположим точки на отрезке следующм образом: Первую и третью - на концах отрезка, а вторую -посередине. Получим: X1 = 1 X2 = 3 X3 = 5 Вычислим соответствующие значения функции: F1=F(1)=9 F2=F(3)=(9+8/3)=11.67 F3=F(5)=25+8/3=26.6 Для того, чтобы оценить x, необходимо найти значение параметров a1 и a2 апроксимирующей функции, обратившись к формулам (2), (3): a1=(11.67-9)/(3-1)=4/3 a2=(1/(5-3))*((26.6-9)/(5-1)-(11.67-9)/83-1))=23/15 Подставим найденные значения в формулу (4) для расчета экстремума аппроксимирующего полинома. Получим: X = (1+3)/2 -4*15/(3*2*23)= 1.565 Для сравнения заметим, что точный минимум функции достигается в точке : x* = 1.5874 как видим, значения x и x* оказались достаточно близки. Значение функции в точке экстремума аппроксимирующего полинома будет: F(X) = 1.565^2 + 8/1.565 = 7.561 Задача: " f(x)=x+4/x задана на отрезке [1,3]. Найти x -точку экстремума квадратичного аппроксимирующего полинома ".


  • edu 2018 год. Все права принадлежат их авторам! Главная