Приближенные методы поиска экстремальных значений функций одной переменной

Тема  7.   Приближенные  методы  поиска  экстремальных  значений  функций  одной  переменной.

                            Функция  y = f(x)  имеет  в  некоторой  окрестности  точки  x^*  локальный  минимум,  если  для  любой  точки  x,  отстоящей  от  нее  не  более  чем  на  некоторую  величину  e  (т.е.  | x - x^*| < e),  справедливо  неравенство  f(x) < f(x^*).  Функция  y = f(x)  имеет  в  некоторой  окрестности  точки  x^**  глобальный  минимум  на  некотором  интервале  [a, b],  если  для  любой  точки  x  из  этого  интервала  (т.е.  x Î [a, b]),  справедливо  неравенство  f(x) < f(x^**).  Точку  достижения  функцией  глобального  минимума  можно  определить  посредством  выбора  из  всех  точек  локальных  минимумов  или  одной  из  границ  интервала  той,  в  которой  значение  функции  будет  минимальным.  Аналогично  можно  опредилить  локальный  и  глобальный  максимум  функции  одной  независимой  переменной.   Точки  минимума  и  максимума  функции  имеют  общее  название  -  точки  экстремума  функции.  Ограничимся  рассмотрением  только  дифференцируемых  функций.

Необходимым  условием  наличия  в  некоторой  точке  локального  экстремума  функции  является  равенство  нулю  ее  производной.  Это  условие  не  является  достаточным,  поэтому  такие  точки  являются  только  подозрительными  на  наличие  локального  экстремума.  Достаточным  условием  наличия  в  них  экстремума  является  тот  факт,  что  этой  точке  вторая  производная  функции  будет  отличной  от  нуля  (или  при  переходе  через  эту  точку  ее  первая  производная  меняет  знак).  При  этом 

· функция  имеет  минимум,  если  ее  вторая  производная  в  подозрительной  на  экстремум  точке  положительна  (или  в  этой  точке  ее  первая  производная  меняет  знак  с  “+”  на  “-“)

· функция  имеет  максимум,  если  ее  вторая производная  в  подозрительной  на  экстремум  точке  отрицательна  (или  в  этой  точке  ее  первая  производная  меняет  знак  с  “-”  на  “+“).

Если  вторая  производная  в  подозрительной  на  экстремум  точке  равна  нулю  (или  в  этой  точке  ее  первая  производная  не  меняет  знак)  -  для  решения  вопроса  о  наличии  в  ней  экстемума  необходимы  более  сложные  исследования.

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

· для  поска  локального  минимума  необходимо  выбирать  интервал,  на  котором  вторая  производная  функции  знакопостоянная  и  положительная

Рекомендуемые материалы

· для  поска  локального  максимума  необходимо  выбирать  интервал,  на  котором  вторая  производная  функции  знакопостоянная  и  отрицательная.

В  противных  случаях  -  достаточно  проверять  конечные  точки  интервала.

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

Метод  сетки   предназначен  для  поиска  глобального  экстремума  функции  на  заданном  интервале.  Суть  метода  состоит  в  том,  что  весь  интервал  [a, b]  покрывается  “сеткой”  -  множеством  точек,  удаленных  друг  от  друге  на  более  чем  на  величину  заданной  точности  (e>0),  а  затем  в  каждой  из  этих  точек  производится  расчет  значений  функции.  Далее  из  них  выбирается  минимальное  (или  максимальное),  которое  (вместе  с  соответствующей  ей  абсциссой  (т.е.  значением  переменной  x) и  будет  найденным  значением  глобального  экстремума  заданной  функции  на  заданном  интервале.  Выбор  шага  разбивки  интервала  производится    так,  чтобы  выполнялось  неравенство    а  это  возможно  при  .

Метод  равномерного  поиска  предназначен  для  поиска  локального  экстремума  функции  на  заданном  интервале.  Суть  метода  состоит  в  том,  что  весь  интервал  [a, b]  аналогичо  предыдущему  методу  покрывается  “сеткой”  -  множеством  точек,  удаленных  друг  от  друге  на  более  чем  на  величину  заданной  точности  (e>0),  а  затем  начиная  с  левого  конца  заданного  интервала  (точки  x=a)  последовательно  в  каждой  из  этих  точек  производится  расчет  значений  функции  и  сравнение  его  с  расчитанным  на  предыдущем  шаге.   Если  значения  не убывают  (при  поиске  максимума)  или  не  возрастают  (при  поиске  минимума)  процесс  вычислений  повторяют  до  достижения  конца  интерваая.  Если  же  тенденция  изменения  значений  нарушается  -  процесс  перебора  точек  прекращают  и  предыдущую  точку  принимают  в  качестве  решения  задачи.

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

· шаг  поиска  (приближения)  не  является  постоянным,  а  изменяется  от  некоторого  начального  значения  до  значения,  меньшего  заданной  точности  (по  абсолютной  величине)  по  мере  приближения  к  искомому  значению  x.  Начальное  значение  шага  выбирается  равным  ,   где   значение  k  выбирается  таким,   чтобы  было  выполнено  двойное  неравенство  5 £ k £ 10.   В  процессе  приближения  к  точке  экстремума  как  знак  шага,  так  и  его  величина  будут  изменяться

· начиная  с  левого  конца  заданного  интервала  (точки  x=a)  последовательно  в  каждой  из  этих  точек  производится  расчет  значений  функции  и  сравнение  его  с  расчитанным  на  предыдущем  шаге.   Если  значения  не убывают  (при  поиске  максимума)  или  не  возрастают  (при  поиске  минимума)  процесс  вычислений  повторяют  до  достижения  конца  интервала.  Если  же  тенденция  изменения  значений  нарушается  -  производят  изменение  величины  и  знака  шага,  полагая

                                                          ,

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

Процес  поиска  значения  экстремума  этим  методом  удобно  проводить  с  занесением  результатов  расчетов  в  таблицу  следующего  вида

Подробный  алгоритм  поиска  экстремума  по  этому  методу  приведен  в  на  рис.  7.1.

 

Пример 1.  Найти  минимум  функции     на  интервале  [0, 5]  методом  равномерного  приближения  с  точностью  0.025.

Имеем    ,   .  Следовательно,  данная  функция  во  всей  области  ее  определения  имеет  только  один  локальный  (он  же  и  глобальный)  минимум.   Примем  k=5.  Тогда  h₀=1.  Дальнейшие  вычисления  будем  проводить  в  Excel  и  результаты  вычислений  представим  в  виде  таблицы.

Так  как  на  19-м  шаге  при  очередной  смене  величины  шага  его  абсолютное  значение  оказалось  меньше  заданной  точности  -  процесс  приближения  прекращен  и  получены  следующие  результаты

                                             x_min =  3.000,     f_min = -14.000.

            Метод  дихотомии   (другое  название  -  метод  половинного  деления) предназначен  для  поиска  локального  экстремума  функции  на  заданном  интервале.  Способ  достижения  цели  -  в  некотором  смысле  аналогичен  ранее  описанному  методу  половинного  деления  при  поиске  корней  нелинейных  уравнений.   Исходный  отрезок   [a, b]   делят  пополам  точкой  с  с  координатой  .  После  этого  находят  значения  функции  в  двух  пробных  точках,  находящихся  справа  и  слева  от  точки  с  на  расстоянии  e/2,  После  этого  из  двух  образовавшихся  половинок  отрезка  одну  отбрасывают,  а  имеено  ту,   в  которой  содержится  та  пробная  точка,  значение  функции в  которой  меньше  (при  поиске  максимума)  или  больше  (при  поиске  минимума).  Для  этого  находят  значения  функции  в  точках    и ,   сравнивают  их  между  собой  и  определяют  “отбрасываемую”  половину  отрезка.   Отбрасывание  производят  посредством  переноса  в  среднюю  точку  отрезка  (точку с)  другого  конца  отбрасываемого  отрезка  (т.е.  точки  a  или  b).  Так  производят  до  тех  пор,  пока  длина  оставшегося  отрезка  станет  меньшей  заданной  точности.  В  таком  случае  за  найденное  приближенное  значение  точки  достижения  функцией   экстремума  принимают  средину  этого  (последнего)  отрезка.

Процес  поиска  значения  экстремума  этим  методом  удобно  проводить  с  занесением  результатов  расчетов  в  таблицу  следующего  вида

,

Подробный  алгоритм  поиска  экстремума  по  этому  методу  приведен  на  рис.  7.2.

Пример 2.  Найти  минимум  функции     методом  половинного  деления  с  точностью  0.02.

Определение  интервала  поиска  обосновано  в  примере  1,  но  мы  его  несколько  увеличим  для  наглядности  метода.  Решение  примера  приведем  в  таблице.

Ответ  -  x_min =  3.00,     f_min = -14.000.

 

         Метод  золотого  сечения   предназначен  для  поиска  локального  экстремума  функции  на  заданном  интервале.  Способ  достижения  цели  -  в  некотором  смысле  аналогичен  ранее  описанному  методу  дихотомии.   Исходный  отрезок   [a, b]   делят  на  три  части  точками     и  ,  где  l=0.382.  Очевидно,  что  x₁ < x₂.  После  этого  находят  значения  функции  в  крайних  точках  интервала  и  в  точках  x₁  и x₂.  Из  четырех  полученных  значений  функции  выбирают  минимальное  (при  поиске  минимума)  или  максимальное  (при  поиске  максимума).  Дальше  производят  “отбрасывание”  той  части  интервала  (одной  из  имеющихся  трех  частей),  которая  находится  наиболее  далеко  от  точки  экстремума. Это  достигается  переносом  точки  a  в  точку  x₁  или  точки  b  в  точку  x₂.  В  результате  проделанных  операций  длина  интервала  [a, b]  уменьшиться.  Теперь  к  оставшится  трем  точкам  (a,  b  и  x₁  или  x₂)   добавим  четвертую  (недостающий  x)  по  формуле a + b - <имеющийся  x >  и  дальше  все  повторяем.  Так  продолжаем  до  тех  пор,  пока  длина  интервала  [a, b]  не  станет  меньше  заданной  точности.   В  этом  случае  за  точку  экстремума  примем  значение  одного  из  x.

Процес  поиска  значения  экстремума  этим  методом  удобно  проводить  с  занесением  результатов  расчетов  в  таблицу  следующего  вида

Подробный  алгоритм  поиска  экстремума  по  этому  методу  приведен  на  рис. 7.3.

Пример 3.  Найти  минимум  функции     методом  половинного  деления  с  точностью  0.05.

Определение  интервала  поиска  обосновано  в  примере  1.  Решение  примера  приведем  в  таблце.

Ответ  -  x_min =  2.99,     f_min = -13.999.

 

                 Рис. 7.3.  Блок-схема  алгоритма  поиска  экстремума  функции  методом 

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