72677

Программная реализация метода последовательного перебора

Курсовая

Информатика, кибернетика и программирование

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

Русский

2014-11-26

1.55 MB

23 чел.

Содержание

Введение

3

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

6

1.1. Постановка задачи

6

1.2. Локальный минимум и максимум. Унимодальные функции. Связь между задачами максимизации и минимизацию.

10

1.3. Метод равномерного перебора. Условие Липшица.

14

1.4. Метод последовательного перебора

17

1.5. Классический метод решения задач минимизации функции одной переменной

19

1.6. Метод половинного деления

20

1.7. Метод парабол

22

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

24

1.9. Применение и особенности численных методов минимизации функций одной переменной

25

Глава 2. Реализация методов равномерного перебора, последовательного перебора.

27

2.1. Реализация методов равномерного перебора и последовательного перебора

27

2.2. Тестирование программ.

28

Заключение

31

Список литературы

32

Приложение 1. Текст программы, реализующей метод равномерного перебора.

33

Приложение 2. Текст программы, реализующей метод последовательного перебора.

36


Введение

Первые задачи, связанные с отысканием наименьших и наибольших величин появились еще в древние времена. Развитие промышленности в XVII-XVIII веках привело к необходимости исследования более сложных задач на экстремум и появлению вариационного исчисления. Однако лишь в XX веке при огромном размахе производства и осознании ограниченности ресурсов Земли встала задача оптимального использования энергии, материалов, рабочего времени, большую активность приобрели вопросы наилучшего в том или ином смысле управления различными процессами физики, техники, экономики и других. Сюда относится, например, задача организации производства с целью получения максимальной прибыли при заданных затратах ресурсов, задача управления системой гидростанций и водохранилищ с целью получения максимального количества электроэнергии, задача о космическом перелете из одной точки пространства в другую наибыстрейшим образом или с наименьшей затратой энергии, задача о быстрейшем нагреве или остывании металла до заданного температурного режима, задача о наилучшем гашении вибраций и многие другие задачи [2].

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

С задачами минимизации функций одной переменной мы впервые сталкиваемся при изучении начальных глав математического анализа и решаем их методами дифференциального исчисления. Может показаться, что эти задачи относятся к достаточно простым и методы их решения хорошо разработаны и изучены. Однако это не совсем так. Методы дифференциального исчисления находят ограниченное применение и далеко не всегда удобны для реализации на современных ЭВМ. Хотя в последние десятилетия появились другие методы, более удобные для использования на ЭВМ, требующие меньшего объема вычислительного труда, но тем не менее эту область экстремальных задач никак нельзя считать завершенной. Работы, посвященные новым методам минимизации функций одной переменной, продолжают появляться на страницах математических книг и журналов [2]. К сожалению, не существует общепринятого универсального численного метода, который позволял бы получать оптимальное решение для любой задачи нелинейной оптимизации. При решении каждой задачи минимизации, может требоваться применение нескольких методов, поэтому эффективное решение задачи минимизации зависит от набора алгоритмов минимизации, которыми владеет исследователь. В данной работе представлены методы минимизации функций одной переменной.

Сложные вычислительные задачи, возникающие при исследовании физических и технических проблем, можно разбить на ряд элементарных — таких как вычисление интеграла, решение дифференциального уравнения и т. п. Многие элементарные задачи являются несложными и хорошо изучены. Для этих задач уже разработаны методы численного решения, и нередко имеются стандартные программы решения их на ЭВМ. Есть и достаточно сложные элементарные задачи; методы решения таких задач сейчас интенсивно разрабатываются (например, решение уравнений бесстолкновительной плазмы). [4]

Именно поэтому задача минимизации функций одной переменной в наше время является актуальной.

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

Для достижения цели требуется решить конкретные задачи:

  1.  создание обзора метода последовательного перебора;
  2.  программная реализация метода последовательного перебора.

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

Данная программа имеет подробное описание и является новой. Она может быть использована студентами, аспирантами, преподавателями в учебных целях.


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

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

1.1. Постановка задачи

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

Определение 1.1.

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

В зависимости от свойств множества и функции множество может содержать одну, несколько или даже бесконечно много точек, а также возможны случаи, когда пусто.

Определение 1.2.

Функция называется ограниченной снизу на множестве , если существует такое число , что для всех . Функция не ограничена снизу на , если существует последовательность , для которой .

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

Определение 1.3.

Пусть функция ограничена снизу на множестве . Тогда число называют нижней гранью на , если: 1) при всех ; 2) для любого сколь угодно малого числа найдется точка , для которой . Если функция не ограничена снизу на , то в качестве нижней грани на принимается. Нижнюю грань на обозначают через .

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

Определение 1.4.

Последовательность называется минимизирующей для функции на множестве , если .

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

Определение 1.5.

Скажем, что последовательность сходится к непустому множеству , если , где — расстояние от точки до множества .

Заметим, что если то всегда существует минимизирующая последовательность, сходящаяся к; например, можно взять стационарную последовательность, где — какая-либо точка из . Однако не следует думать, что при любая минимизирующая последовательность будет сходиться к .

Определение 1.6.

Пусть - погрешность решения рассматриваемой задачи минимизации для функции cпомощью метода . -гарантированная точность метода на классе функции . Метод - оптимальный метод на классе , если , а величину - наилучшей гарантированной точностью методов на классе. Если для некоторого метода выполняется неравенство , то назовем - оптимальным на классе.

Определение 1.7.

Пусть - унимодальная функция на отрезке , и пусть вычислены значения в точках . Тройка точек локализует минимум функции на отрезке по точкам, если:

  1.  точка совпадает с одной из точек ;
  2.  ;
  3.  , причем - ближайшие к точки среди точек .

Определение 1.8.

Пусть - класс унимодальных функций на отрезке . На задан последовательный метод , если:

  1.  задано правило выбора первой порции точек , , по которым определяется тройка точек , локализующая минимум на;
  2.  при на отрезке по заданному правилу выбирается вторая порция точек , и по точкам определяется тройка , локализующая минимум на;
  3.  прина отрезке по известному правилу выбирается следующая порция точек и по точкам находится тройка , локализующая минимум на и т.д. Этот процесс выбора точек отдельными порциями продолжается до тех пор, пока не будет выбрана последняя -я точка и определена соответствующая локализующая тройка .

Определение 1.9.

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

1.2. Локальный минимум и максимум. Унимодальные функции. Связь между задачами максимизации и минимизации.

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

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

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

Теорема 2.1. (Вейерштрасса)

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

Возможна и более широкая постановка задач минимизации второго типа — когда ищутся не только точки минимума в смысле определения 1, но и точки так называемого локального минимума.

Определение 2.1.

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

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

рис. 2.1.

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

Выделим класс функций, у которых все точки локального минимума являются точками глобального минимума.

Определение 2.2.

Функцию назовемунимодальной на отрезке, если она непрерывна на и существуют числа такие, что: 1) строго монотонно убывает при (если ); 2) строго монотонно возрастает при (если); 3) при , так что. Случаи, когда один пли два из отрезков , , вырождаются в точку, здесь не исключаются. В частности, если , то назовем строго унимодальной на отрезке .

Нетрудно видеть, что если функция унимодальна на , то она остается унимодальной и на любом отрезке .

В заключение кратко остановимся на задаче максимизации функции.

Определение 2.3.

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

Определение 2.4.

Если функция ограничена сверху на, то число называется верхней граньюнав том случае, когда: 1) для всех; 2) для любого числа найдется такая точка , что . Если не ограничена сверху на , то по определению принимается . Последовательность называется максимизирующей для на , если . Если существует такая точка, что, то называется точкой максимума на , а величина наибольшим или максимальным значением на . Множество точек максимума на будем обозначать через , верхнюю грань — через .

Заметим, что верхняя грань и максимизирующаяпоследовательность всегда существуют, а максимальное значение может не существовать. Если выполнены условия теоремы 1, то , и и любая максимизирующая последовательность сходится к .

В задачах максимизации также можно различать задачи двух типов: в задачах первого типа ищется величина , а в задачах второго типа ищется и какая-либо точка . Нетрудно видеть, что

,

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

Наконец, немного о точках локального максимума.

Определение 2.5.

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

Для функции, график которой изображен на рис., точки являются точками строгого локального максимума, а в точках, удовлетворяющих неравенствам и , реализуется нестрогий локальный максимум; —точка глобального максимума.

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

1.3. Метод равномерного перебора. Условие Липшица.

При обосновании этого численного метода минимизации используется условие Липшица.

Определение 3.1.

Говорят, что функция удовлетворяет условию Липшица на с константой , если для любых и из выполняется

    (1)

Величина при этом называется константой Липшица.

рис. 3.1.

Геометрический смысл условия Липшица состоит в том, что модуль тангенса угла наклона () любой секущей графика функции , проходящей через точки и , не превышает (рис. 3.1.).

Теорема 3.1.

Если функция удовлетворяет условию Липшица на , то она непрерывна на.

Следствие 3.1.

Если функция удовлетворяет условию Липшица на , то существует хотя бы одна точка минимума функции на.

Теорема 3.2.

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

Описание метода

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

Для решения поставленной задачи разобьем на равных по длине отрезков .

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

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

Теорема 3.3.

Пусть функция удовлетворяет условию Липшица нас известной константой . Если , то .

Теорема 3.4.

Пусть функция удовлетворяет условию Липшица нас известной константой . Если и , то , и , и .

1.4. Метод последовательного перебора

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

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

  (2)

удается решить за меньшее количество вычислений значений функции. Положим

  (3)

где , , , а число определяется условием .

Теорема4.1.

Метод последовательного перебора (3) решает задачу (2) на классе .

Заметим, что метод (2) выгодно отличается простотой реализации и не требует большой машинной памяти. Недостатком метода (2), как и метода ломаных, является необходимость априорного знания константы Lиз условия Липшица.

Метод последовательного перебора, аналогичный методу (2), можно предложить и для некоторых других классов функций. Остановимся на классе функций, дважды .дифференцируемых на отрезке, у которых , где - некоторая фиксированная константа. Обозначим этот класс функций через . Заметим, что если , то , и следовательно, монотонно убывает на . Это значит, что тогда функция достигает своей нижней грани при  или . Таким образом, задача минимизации функций из класса в случае решается просто. Поэтому имеет смысл рассматривать класс при .

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

  (4)

где, , , а число определяется условием .

Теорема4.2.

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

(5)

В худшем случае (например, если ) может оказаться, что , , и тогда метод (4) переходит в метод равномерного перебора с шагом . Если же при некоторых  (например, для ), то методом (4) удается получить неравенство (5), вообще говоря, при меньшем , чем методом равномерного перебора. Недостатком метода (4) является требование знания константы .

1.5. Классический метод решения задач минимизации функции одной переменной

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

Алгоритмическая схема классического метода решения задач минимизации и максимизации функции на:

  1.  Определить все точки подозрительные на экстремум.
  2.  Для каждой точки подозрительной на экстремум установить, действительно ли в этой точке функция имеет локальный экстремум или нет. Если да, то определить вид экстремума (локальный минимум или локальный максимум).
  3.  Вычислить значения функции во всех подозрительных точках (или во всех точках локального экстремума, если они найдены). Наименьшее и наибольшее из этих значений будут равны и соответственно, а точки экстремума, в которых достигаются эти значения, будут представлять собой точки глобального минимума и максимума функции на.

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

1.6. Метод половинного деления

Если функция дифференцируема, то в точках локального и глобального минимума и максимума производная обращается в 0. Таким образом, точки локального и глобального минимума и максимума в этом случае находятся среди корней уравнения. Это обстоятельство позволяет решать некоторые задачи минимизации и максимизации, используя известные численные методы решения уравнений с одним неизвестным (половинного деления, касательных и т.п.). Следующие два метода минимизации получены именно таким способом и являются аналогами методов половинного деления и касательных. Условия применения этих методов должны обеспечить существование и единственность корня уравнения на , выполнение условий применимости соответствующего метода решения уравнений, а также то, что указанный корень уравнения совпадает именно с точкой минимума функции на,а не с точкой максимума или стационарной точкой (что тоже может быть) [8].

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

Легко видеть, что выполняются все условия применимости метода половинного деления, применительно к решению уравнения на (насуществует единственный корень  уравнения, непрерывна и имеет на концах отрезка значения разных знаков).

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

Дляопределенияприближенного значения точки минимума строится последовательность приближений.

рис. 6.1.

Разделим пополам точкой и выберем из двух половин , ту половину отрезка, на концах которой функция имеет значения разных знаков. Обозначим эту половину (рис. 6.1).

Разделим пополам точкой и выберем из двух половин , ту половину отрезка, на концах которой функция имеет значения разных знаков. Обозначим эту половину (рис. 6.1) и т. д. Продолжая этот процесс будем получать остальные члены последовательностей и  последовательности приближений . Вычисления членов этих последовательностей продолжают до тех пор, пока не будет выполнено условие окончания итераций:

.

После этого вычисляется приближенное значение точки минимума

.

1.7.Метод парабол

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

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

Легко видеть, что выполняются все условия применимости метода касательных, применительно к решению уравненияна (на существует единственный корень уравнения,и непрерывны и не обращаются в на ). Этот метод позволяет определить приближенное значение точки минимума с погрешностью, не превышающей заданного положительного числа.

Для решения уравнения на строится последовательность приближений. В начале задается начальное приближение , , еслина. В противном случае, когда на ,. Остальные члены последовательности вычисляются по рекуррентной формуле:

,    (6)

Так строится последовательность приближений к точке минимума в методе парабол. Вычисления по формуле (6) продолжают до тех пор, пока не будет выполнено условие окончания итераций:

     (7)

Здесь - положительное число такое, что на . После выполнения условия (7) вычисляется приближенное значение точки минимума

    (8)

Замечание

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

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

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

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

рис. 8.1.

Шаг 1.Разобьем на три, вообще говоря,неравные части точками()так, чтобы первый и третий отрезки разбиения имелиодинаковую длину, а отношение их длин к длине всего отрезка имело заданное значение (см. первую числовую ось рисунка 8.1):

    (9)

Найдем наименьшее из значений функции в точках()и точки, в которых это значение достигается.

Если это значение достигается функцией в точках или , то отбросим отрезок , а в противном случае – отрезок .

Шаг 2.С выбранной оставшейся после отбрасывания частью мы поступим так же как со всем отрезком на первом шаге, то есть разобьём её на три подобных части. Для координат точек разбиения оставим старые обозначения (). Таким образом, при каждом новом разбиениивыбранной части последнего отрезка, значения переменных будут соответствующим образом меняться. На второй и третьей числовой оси рисунка 8.1 показаны два таких разбиения выбранной части отрезка. Потребуем также, чтобы для каждого нового разбиения выбранной части отрезка выполнялось условие (9) при постоянном значении величины .

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

Шаги метода продолжаются до тех пор, пока не будет выполнено условие:

     (10)

После этого, в качестве приближенного значения координаты точки глобального минимума выбирается середина последнего отрезка разбиения:

     (11)

1.9. Применение и особенности численных методов минимизации функций одной переменной

Среди рассмотренных в работе численных методов решения задач минимизации наиболее широкую сферу применения имеют методы равномерного перебора и золотого сечения. Их можно использовать для минимизации непрерывных функций. Чтобы применять метод половинного деления требуется наличие и непрерывность производной у минимизируемой функции. А чтобы использовать метод парабол необходимо наличие трех непрерывных производных. Поэтому метод парабол имеет наиболее узкую сферу применения [8]. Для применения метода последовательного перебора необходимо знать константу Липшица. В результате рассмотрения этого метода было получено:

  1.  Если функция монотонно убывает на , то шаг разбиения остается постоянным и равным ;
  2.  Если функция монотонно убывает, а затем монотонно возрастает на , то шаг разбиения в первом случае (см. 1) остается постоянным, а во втором случае начинает расти в следствии роста величины (см. метод последовательного перебора).

Если же сравнивать методы по скорости получения результата при фиксированной точности, то получается обратная картина. Метод равномерного перебора - самый медленный, он требует вычисления наибольшего количества значений минимизируемой функции. За ним идут методы последовательного перебора, золотого сечения и половинного деления. Самый же быстрый -метод парабол. Это связано с тем, что его аналог, метод касательных, может при определенных условиях иметь квадратичную сходимость (в то время как метод половинного деления имеет только линейную сходимость). Этим же свойством, очевидно, будет обладать и метод парабол [8].

Несмотря на некоторые недостатки, рассмотренные методы являются наиболее эффективными при решении нелинейных задач.

Глава 2. Реализация методов равномерного перебора, последовательного перебора.

В данной главе представлено описание программ, реализующих такие методы, как: метод равномерного перебора, метод последовательного перебора. Также рассмотрен пример решения задачи минимизации аналитическим методом и программно, рассмотренными численными методами. За основу была взята книга [8] из списка литературы.

2.1. Реализация методов

Описанные методы минимизации функций одной переменной были реализованы в виде функций программы minimum в приложении.

Метод Равномерного перебора

Описание и назначение этого метода было представлено выше (см. гл. 1.4), а сам метод был реализован в функции Ravnom_perebor в программе minimum.

Исходные данные:

– концы отрезка на котором решается задача;

– заранее найденная константа Липшица, равная;

– заданная точность искомого приближенного значения точки минимума;

– функция.

Результаты:

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

Метод последовательного перебора.

Описание метода:

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

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

Сам метод был реализован в среде Borland Delphi 6.

Исходные данные:

– концы отрезка на котором решается задача;

– константа Липшица, равная ;

– заданная точность искомого приближенного значения точки минимума;

– функция.

Результаты:

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

- значение функции в точке .

2.2. Тестирование программы

Проиллюстрируем работу программы на примере.

Требуется найти точку минимума функции с точностью на отрезке .

Решим данную задачу аналитически.

Найдем стационарные точки функции. Для этого решим уравнение, где первая производная функции. Решая уравнение, находим единственный корень. Выясним, является ли данная точка точкой минимума. Для этого найдем значения производной в точках и, ,. Таким образом, функция убывает на отрезке , и возрастает на полуинтервале . Следовательно, точка минимума функции. Зная искомую точку минимума функции, сравним её с полученными результатами в программе minimum и в программе (см. приложение). Для этого в функцию запишем, в функцию запишем первую производную, а в функцию запишем вторую производную. Также внесем исходные данные, , , , , . После выполнения двух программ получаем результаты, представленные на рисунках:

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


Заключение

К основным результатам курсовой работы можно отнести:

  1.  Обзор литературы, связанной с методами минимизации функции одной переменной.
  2.  Программная реализация методов минимизации функции одной переменной, а именно метода равномерного перебора и метода последовательного перебора.


Список литературы

  1.  Васильев Ф.П. Численные методы решения экстремальных задач. М.: изд. «Наука», 1988.
  2.  Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука 1980.
  3. Зуев Е.А. «Язык программирования TurboPascal 6.0, 7.0» Изд-во: Веста, Радио и связь, 1993.
  4.  Калиткин Н.Н. Численные методы. М.: изд. «Наука», 1978.
  5. Пантелеев А.В. Методы оптимизации в примерах и задачах. 2003.
  6.  Полак Э. Численные методы оптимизации. М.: изд. «Мир», 1974.
  7.  Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: изд. «Наука», 1978.
  8.  Трубников С.В. Численные методы минимизации. Электронное учебное пособие. 2005.
  9. Трубников С.В.Компьютерное моделирование: Учебное пособие для студентов вузов.- Брянск, Изд-во БГУ. 2004.


Приложение 1.

Текст программы, реализующей метод равномерного перебора.

{Программа реализуют различные методы оптимизации заданной функции}

program Test;

uses

Crt;

type

TFunc = function(x: real): real;

var

c:char;

x, x0, a, b, L, q, eps: real;

function Ravnom_Perebor(f: TFunc; a, b, L, eps: real): real;

{Реализует метод равномерного перебора}

var

N, i:  LongInt;

 h, fk, xk, x: real;

begin

N:=Trunc(L*(b-a)/(2*eps))+1;  {Находение числа отрезков             разбиения}

h:=(b-a)/N;   {Находение длины отрезков разбиения}

x:=a+h/2; {Нахождение середины первого отрезка разбиения}

fk:=f(x);   {Вычисляем значение функции в середи         первого отрезка разбиения}

 for i:=1 to N-1 do

begin

 xk:=a+(2*i+l)*h/2;   {Нахождение середины          следующего отрезка}

   if f(xk)<fk then  {Сравнение значений функции в следующем   отрезкес минимальным значением функции на предыдушем шаге}

 begin

  x:=xk;{Назначение новой точки минимума функции}

  fk:=f(xk) ;  {Назначение нового минимального          значения функции}

 end;

end;

Ravnom_Perebor:=x;

end;

{$F+}

{Описание заданной функции}

function f(x:  real):  real;

begin

f:=x*x+2*x;

end;

{Описание первой производной заданной функции}

function df(x:  real): real;

begin

df:=2*x+2;

end;

{Описание второй производной заданной функции}

function d2f(x:  real):  real;

begin

d2f:=2;

end;

{$F-}

begin

clrscr;

 a:=-3 ;    {Задание левого конца отрезка}

b:=1;     {Задание правого конца отрезка}

L:=4; {Задание константы для метода равномерного перебора}

q:=1;    {Задание константы для метода парабол}

x0:=-3; {Задание начального приближения для метода парабол}

eps:=0.01;     {Задание точности вычисления}

{Нахождение точки минимума методом равномерного перебора}

 x:=Ravnom_Perebor(f, a, b, L, eps);

writeln('x=', x:10:8, '    Ravnom_Perebor');

 c:=readkey;     {Выход по нажатию клавиши}

end.


Приложение 2.

Текст программы, реализующей метод последовательного перебора.

unit Unit1;

interface

uses

 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

 Dialogs, StdCtrls, ExtCtrls, jpeg, ComCtrls, TeeProcs, TeEngine, Chart,

 Series;

type

 TForm1 = class(TForm)

 GroupBox1: TGroupBox;

 Label1: TLabel;

 Image1: TImage;

 Label2: TLabel;

 Edit1: TEdit;

 Label3: TLabel;

 Edit2: TEdit;

 Label4: TLabel;

 Edit3: TEdit;

 Label5: TLabel;

 Edit4: TEdit;

 Label7: TLabel;

 Label8: TLabel;

 Label9: TLabel;

 Button1: TButton;

 GroupBox2: TGroupBox;

 Memo1: TMemo;

 PageControl1: TPageControl;

 TabSheet2: TTabSheet;

 Chart1: TChart;

 Series1: TLineSeries;

 Series2: TLineSeries;

 Series3: TLineSeries;

 Series4: TLineSeries;

 Series5: TLineSeries;

 Series6: TLineSeries;

 procedure Edit4Change(Sender: TObject);

 procedure Edit3Change(Sender: TObject);

 procedure Edit1Change(Sender: TObject);

 procedure Edit2Change(Sender: TObject);

 procedure FormShow(Sender: TObject);

 procedure Button1Click(Sender: TObject);

 procedure Edit1KeyPress(Sender: TObject; var Key: Char);

 private

 { Private declarations }

 public

 { Public declarations }

 end;

var

 Form1: TForm1;

 a,b,c,d,e,h,j,n,Fmin,Jx,fuct:real;  L,i,nn,k,m,x:integer;

 u:array[1..1000] of real;

 Ju:array[1..1000] of real;

 F:array[1..1000] of real;

 Kmin:string;

implementation

{$R *.dfm}

procedure TForm1.Edit4Change(Sender: TObject);

begin

if (length(Edit4.Text) = 0) then

begin

label9.Visible:=true;

end

else

begin

label9.Visible:=false;

end;

end; //выводит восклицательный знак если в поле не задано значение

procedure TForm1.Edit3Change(Sender: TObject);

begin

if (length(Edit3.Text) = 0) then

begin

Label8.Visible:=true;

end

else

begin

Label8.Visible:=false;

end;

end; //выводит восклицательный знак если в поле не задано значение

procedure TForm1.Edit1Change(Sender: TObject);

begin

if (Length(Edit1.Text) = 0) or (Length(Edit2.Text) = 0) or (Length(Edit1.Text) = 0) and (Length(Edit2.Text) = 0) then

begin

Label7.Visible:=true;

end

else

begin

Label7.Visible:=false;

end;

end; //выводит восклицательный знак если в поле не задано значение

procedure TForm1.Edit2Change(Sender: TObject);

begin

if (Length(Edit1.Text) = 0) or (Length(Edit2.Text) = 0) or (Length(Edit1.Text) = 0) and (Length(Edit2.Text) = 0) then

begin

Label7.Visible:=true;

end

else

begin

Label7.Visible:=false;

end;

end; //выводит восклицательный знак если в поле не задано значение

procedure TForm1.FormShow(Sender: TObject);

begin

if (Length(Edit1.Text) = 0) or (Length(Edit2.Text) = 0) or (Length(Edit1.Text) = 0) and (Length(Edit2.Text) = 0) then

begin

Label7.Visible:=true;

end

else

begin

Label7.Visible:=false;

end;

if (length(Edit3.Text) = 0) then

begin

Label8.Visible:=true;

end

else

begin

Label8.Visible:=false;

end;

if (length(Edit4.Text) = 0) then

begin

label9.Visible:=true;

end

else

begin

label9.Visible:=false;

end;

end;    //выводит восклицательный знак если в поле не      задано значение при открытии формы

procedure TForm1.Button1Click(Sender: TObject);

begin

//=========Очистка поля мемо1 и очистка графика=============//

Memo1.Clear;

Form1.Chart1.Series[0].Clear;

Form1.Chart1.Series[1].Clear;

Form1.Chart1.Series[2].Clear;

Form1.Chart1.Series[3].Clear;

Form1.Chart1.Series[4].Clear;

Form1.Chart1.Series[5].Clear;

//==========Проверка на введеные данные в поля=============//

if (Label7.Visible=true) or (Label8.Visible=true) or (Label9.Visible=true) then

begin

MessageBox(handle, 'Извините вы что-то забыли ввести!!', 'Ошибка данных!!', 0);

end

else

begin

//==================Значения с формы======//

// отрезок

a:=StrToFloat(Edit1.Text); // отрезок от а {c формы значение от}

b:=StrToFloat(Edit2.Text); // отрезок до б {с формы значение до}

// искомая погрешность

e:=StrToFloat(Edit3.Text); // значение искомой погрешности.

// Константа Липшица

L:=StrToInt(Edit4.Text); //Значение константы Липшица.

//===============Построение графика по формуле============//

for x:=-10 to 10 do

 begin

 Jx:=sqr(x)+2*x;

 form1.Chart1.Series[0].AddXY(x,Jx);

 form1.Chart1.Series[1].AddXY(x,0);

 form1.Chart1.Series[2].AddXY(0,x);

 form1.Chart1.Series[3].AddXY(a,x);

 form1.Chart1.Series[4].AddXY(b,x);

 form1.Chart1.Series[5].AddXY(x,L);

end;

//==================Начало================//

d:=(2*e)/L; // первое значение для шага разбития

c:=b-a; // второе значение для шага раазбития

 //Шаг разбития

 if d>c then

begin

 h:=c;   //если первоезначение больше второго то       минимум равен второму значению

end

else

begin

 h:=d; //иначе обратная процедура, минимум равен первому

end;        // шаг разбития

//значение n отрезков

n:=(abs(a)+abs(b))/h; // кол-во отрезков

 nn:=StrToInt(FloatToStr(n));

//==================Пред шаговая================//

u[1]:=a+(h/2); //первое значение u1

///////////////////////////////////////////////////

Ju[1]:=sqr(u[1])+2*u[1]; //J(u1) по формеле c формы

///////////////////////////////////////////////////

Fmin:=Ju[1];    // функция, для нахождения          следующей точки разбиения

///////////////////////////////////////////////////

//==================Шаги================//

// Заполняет Fmin из F[1..n] и Ju[i]

 for i:=2 to nn do

 begin

 if u[i-1]<(b-(h/2)) then

  begin

   u[i]:=u[i-1]+h+((Ju[i-1]-Fmin)/L);

   Ju[i]:=sqr(u[i])+2*(u[i]);

   for k:=1 to i do

   begin

    if Fmin>=Ju[k] then

    begin

     Fmin:=Ju[k];

    end

    else

    begin

     Fmin:=Fmin;

    end;

   end;

  end  // Шаги и их заполнением и выполнение

 else

 begin

 u[nn]:=u[nn-1]+h+((Ju[nn-1]-Fmin)/L);

 if u[nn]>b then

  begin

   Fmin:=b;

  end

  else

   begin

    Fmin:=u[nn];

   end;

  end;

end;

//проверка минимума в минимальном значении

 F[1]:=u[1];

 for i:=1 to nn do

   begin

 if Fmin = Ju[i] then

 begin

 if F[1] > u[i] then

  begin

   F[1]:=F[1];

  end

 else

  begin

   F[1]:=u[i];

  end;

 end;

 end;

 //вывод результата на форму в поле мемо1

 Memo1.Lines.Add('Минимум функции : '+FloatToStr(Fmin));

 Memo1.Lines.Add('Значение функции в минимуме: '+FloatToStr(F[1]));

 Memo1.Lines.Add('Данные, полученные в ходе решения поставленной задачи,'+#13+'являются не точными и предполагают наличие погрешности связанной с выбором e  и  L');

end;

end;

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);

begin

if key in ['a'..'z','A'..'Z','а'..'я','А'..'Я' ,'ё',' ','.','+','*','/','=',')','(','&','^','%','$','#','@','!',';',':','?','"','[',']','{','}','\','|','/','_','<','>','¦','№'] then key:=#0;

end;         //защита от ввода букв

end.


 

А также другие работы, которые могут Вас заинтересовать

28043. Промышленное лесопользование, его виды. Приемы возобновления лесов 10.97 KB
  Способы возобновления леса. Изменение старого поколения леса новым называется возобновлениям леса. При естественном семенном возобновлении леса молодое поколение генетически и экологически лучше отвечает конкретным условиям выращивания: климату почве. Благополучно обстоит дело только в лесах третьей группы.
28045. Рациональное использование и охрана климатических ресурсов. Источники загрязнения атмосферы и последствий 17.63 KB
  В нем содержится азота Ng 783 кислорода 0^ 2095 диоксида углерода СО^ 003 аргона Ar 093 от объема сухого воздуха небольшое количество других инертных газов. Однако изза огромного количества азота в атмосфере проблема его баланса не так серьезна как баланс кислорода и углекислого газа. лет назад содержание кислорода в атмосфере было в тысячу раз меньше чем сейчас так как не было основных продуцентов кислорода зеленых растений. Жизнедеятельность живых организмов поддерживается...
28046. Регулирование природопользования: задачи регулирования. Система природоохранных норм и нормативов 7.63 KB
  Механизм управления природопользованием объединяет методы функции и организационные структуры органы управления. Методы управления природопользованием это способы воздействия на поведение и деятельность управляемых объектов с целью обеспечения рационального природопользования и охраны окружающей среды. Основные методы управления:  административные команднораспорядительные обусловлены возможностью государственного принуждения;  экономические создают непосредственную материальную заинтересованность...
28047. Регулирование природопользования. лицензирование 5.76 KB
  лицензия выдается на каждый вид деятельности. природоресурсоваяя лицензияразрешение на ведение определенного вида деятельности связанной с использованием какого либо прир. лицензия выдается уполномоченным гос.МПР России его территориальноотраслевые департаменты в республиках краях городах районах Лицензия на использование земельвыдается администрацией района города в виде земельноотводного акта.