Численное нахождение экстремумов функции

Тран Зуй

Численное нахождение экстремумов функции

01.03.02 Прикладная математика и информатика

Математика

Дипломы

Вуз: Белгородский государственный университет - национальный исследовательский университет (НИУ «БелГУ»)

ID: 5c1a82ac7966e104f6f85b89

UUID: 2c0377f0-e5e3-0136-05d1-525400005860

Язык: Русский

Опубликовано: около 6 лет назад

Просмотры: 759

Тран Зуй

Источник: Федеральное государственное автономное образовательное учреждение высшего образования «Белгородский государственный национальный исследовательский университет»

Комментировать 0

Рецензировать 0

Скачать - 1,1 МБ

Поделиться работой

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» (НИУ «БелГУ») ИНСТИТУТ ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ И ЕСТЕСТВЕННЫХ НАУК КАФЕДРА ОБЩЕЙ МАТЕМАТИКИ ЧИСЛЕННОЕ НАХОЖДЕНИЕ ЭКСТРЕМУМОВ ФУНКЦИИ Выпускная квалификационная работа обучающегося по направлению подготовки 01.03.02 Прикладная математика и информатика очной формы обучения, группы 07001406 Трана Зуя Научный руководитель: к.ф.-м.н., доцент, Флоринский В.В. БЕЛГОРОД 2018

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ .......................................................................................................... 3 1. ОБЗОР СОСТОЯНИЯ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЯ ........... 5 1.1 Общая постановка задачи ........................................................................... 5 1.2 Существующие методы нахождения экстремумов функций ................... 7 1.3 Выбор среды разработки ПО .................................................................... 11 2. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ ........ 15 2.1. Метод половинного деления ................................................................... 15 2.2. Программная реализация метода половинного деления ........................ 17 2.3. Метод золотого сечения ........................................................................... 18 2.4. Программная реализация метода золотого сечения ............................... 21 3. МЕТОДЫ МИНИМИЗАЦИИ ДЛЯ ФУНКЦИЙ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ.................................................................................................. 23 3.1. Градиентный метод. ................................................................................. 23 3.2. Программная реализация градиентного метода ..................................... 28 3.3. Метод Ньютона ........................................................................................ 30 3.4. Программная реализация метода Ньютона ............................................ 32 4. ТЕСТИРОВАНИЕ ПО И ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ........................................................................................... 35 ЗАКЛЮЧЕНИЕ .................................................................................................. 43 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ............................................ 44 ПРИЛОЖЕНИЕ .................................................................................................. 46 2

ВВЕДЕНИЕ В настоящий время, в различных областях науки и техники, существует большое количество экстремальных задач. Задачи по нахождению экстремумов функций, часто встречаются в науке, экономике и технике. Умение переходить от содержательной постановки задачи к математической, даёт возможность для применения математических методов их анализа и решения. С помощью численных методов можно получить приближенной решение. В зависимости от метода, с помощью числа итерационных исчислений можно определить минимальное значение функции и точность расчета точки минимума. Актуальность темы данной работы состоит в том, что использование численных методов упрощает алгоритм решения многомерных задач, а также дает возможность найти решение абсолютно всех классов экстремальных задач, появившихся в последнее десятилетие. Целью данной работы является разработка программ некоторых методов нахождения численных значений экстремумов функций. В процессе работы будут решены следущие задачи:  Изучить и исследовать общую задачу;  проанализировать характеристики различных численных методов, а также дать подробное описание метода половинного деления, метода золотого сечения, градиентного метода, метода Ньютона;  осуществить программные реализации алгоритмов;  изучить возможности пакета программирования Matlab по решению экстремальных задач;  разработать программы в среде пакета программирования Matlab для нахождения экстремумов функции. Объект исследования – задачи на нахождение экстремумов функции. Предмет исследования – численные методы решения (а именно метод половинного деления, метод золотого сечения, градиентный метод, метод 3

Ньютона) экстремальных задач, то есть задач на нахождение минимума и максимума функции. Практическая значимость данной работы заключается в разработке программ в среде пакета программирования Matlab по нахождению экстремумов функции. Для того чтобы достичь поставленной цели, разбираются некоторые мелкие задачи, которые решаются в процессе написания одной из глав. В первой главе работы рассматривается теоретический обзор по обзоре состояния вопроса и задачи исследования, включаются в следующие:  Общая постановка задачи.  Существующие методы нахождения экстремумов функций.  Выбор среды разработки ПО. В второй главе работы рассматривается описание методов минимизации функций одной переменной, включаются в следующие:  Метод половинного деления.  Программная реализация метода половинного деления.  Метод золотого сечения.  Программная реализация метода золотого сечения. В третьей минимизации для главе работы рассматривается функций нескольких описание методов переменных, включаются в следующие:  Градиентный метод.  Программная реализация градиентного метода.  Метод Ньютона.  Программная реализация метода Ньютона. В четвертой главе представляет собой практическая часть, которая содержит:  Создание ПО.  Тестирование созданного ПО. 4

1. ОБЗОР СОСТОЯНИЯ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЯ 1.1 Общая постановка задачи При постановке задачи поиска минимума функций необходимо следущие данные:  функция 𝑓(𝑥), где 𝑥 = (𝑥1 , 𝑥2 , . . . , 𝑥𝑛 )𝑇 , определенную на n – мерном евклидовом пространстве 𝑅𝑛 , которая называется целевой. Степень достижения цели, которая решается задача, определяется значениями этой функции;  множество векторов 𝑋 ⊆ 𝑅𝑛 , среди элементов которых осуществляется поиск допустимых решений. Данное множество будем называть областью допустимых решений [1]. Задача нахождения минимума целевой функции на области допустимых решений заключается в нахождении вектора 𝑥 ∗ из множества векторов 𝑋 ⊆ 𝑅𝑛 , для которого целевая функция 𝑓(𝑥) достигает минимального значения на этом множестве: 𝑓(𝑥 ∗ ) = 𝑚𝑖𝑛𝑓(𝑥) 𝑥∈𝑋 Чтобы решить задачу на максимума функции 𝑓(𝑥), необходимо рассмотреть задачу нахождения минимума функции −𝑓(𝑥), т.е. заменить знак функции на противоположный (рис. 1.1). 5

Рис. 1.1 Задача поиска минимума или максимума целевой функции 𝑓(𝑥) составляет задачу поиска экстремума: 𝑓(𝑥 ∗ ) = 𝑒𝑥𝑡𝑟 𝑓(𝑥). 𝑥∈𝑋 Мы получим задачу условного экстремума, если на множество допустимых решений 𝑋 наложим ограничения (условия). Таким образом, если 𝑋 = 𝑅𝑛 , т.е. ограничения (условия) на множество допустимых решений 𝑋 отсутствуют, то переходим к решению задачи поиска безусловного экстремума – пара (𝑥 ∗ , 𝑓(𝑥 ∗ )), включающая точку 𝑥 ∗ и значение целевой функции 𝑓(𝑥 ∗ ) в этой точке. Обозначим через 𝑋 ∗ множество точек минимума (максимума) целевой функции 𝑓(𝑥) на множестве 𝑋. 𝑋 ∗ может содержить конечное количество точек, бесконечное количество точек или быть пустым. Точка 𝑥 ∗ ∈ 𝑋 называется точкой глобального (абсолютного) минимума функции 𝑓(𝑥) на множестве 𝑋, если функция достигает в этой точке своего наименьшего значения, т.е. 𝑓(𝑥 ∗ ) ≤ 𝑓(𝑥) ∀ 𝑥 ∈ 𝑋. 6

Точка 𝑥∗ ∈ 𝑋 называется точкой локального (относительного) минимума функции 𝑓(𝑥) на множестве 𝑋, если существует 𝜀 > 0, такое, что если 𝑥∈𝑋 и ‖𝑥 − 𝑥 ∗ ‖ < 𝜀, то 𝑓(𝑥 ∗ ) ≤ 𝑓(𝑥). Здесь ‖𝑥‖=√𝑥12 + 𝑥22 + 𝑥32 + ⋯ + 𝑥𝑛2 −евклидова норма вектора 𝑥. Точка 𝑥 ∗ глобального минимума сравнивается по величине функции со всеми точками из множества допустимых решений 𝑋, а точка 𝑥 ∗ локального минимума только с принадлежащими её 𝜀 − окрестности (рис. 1.2)[1]. Рис. 1.2 1.2 Существующие методы нахождения экстремумов функций Под понятием экстремальных задач понимают задачи, которые ориентированы на поиск и нахождение максимального или минимального, т.е. экстремального некоторой определенной функции. Основным отличием численных методов нахождения экстремума функции от аналитических является то, что с их помощью можно получить только приближенное решение. Точность найденных точек минимума и максимума зависит от точности метода, числа итераций и др. Численные методы поиска и нахождения экстремумов функции одной переменной можно классифицировать следующим образом: 7

 методы нулевого порядка, которые используют для нахождения необходимых экстремумов только лишь значения функции и не требуют вычисления ни одной из ее производных;  методы первого и более высоких порядков, которые требуют для поиска и нахождения максимального и минимального значения функций использование производных. К главным достоинства нулевых (прямых) методов можно отнести следующее:  позволяют исследовать и находить решение даже недифференцируемых целевых функций;  имеют в своей основе достаточно простые алгоритмы и программы оптимизации, которые позволяют легко вычислить любую точку экстремума и значение функции в этой точке;  требуют относительно малого объема машинной памяти, что позволяет экономить пространство на электронном носителе. К недостаткам прямых методов относят:  требуют длительного времени работы компьютера, так как метод и стратегия поиска экстремума является не самой лучшей;  прямые методы дают очень низкую точность, , для получения высокой точности нужно совершить достаточно большое количество вычислений, в случае ограничения на число вычислений получить высокую точность вычисления становится практически невозможным. Говорят, что функция имеет локальный (т.е. местный) минимум или максимум в какой-либо известной точке 𝑥0 ; только при условии существования некоторого  такого, что для любого 𝑥 из неравенства |𝑥 − 𝑥0 | <  выполняется равенство: 𝑓(𝑥 ∗ ) ≤ 𝑓(𝑥) (𝑓(𝑥 ∗ ) ≥ 𝑓(𝑥)) 8

В большинстве случаев рассматривают такие задачи по нахождению и поиску условного экстремума, которые требуют дополнительных специфических ограничений. В частности, подобного рода задачами можно считать задачи математического программирования. Унимодальной на некотором отрезке является функция, для которой существует такая точка, делящая его на различные две части, что в одной части функция убывает, а в другой соответственно возрастает. Для корректного вычисления решения задач численными методами обязательно условие унимодальности данной функции на всем рассматриваемом отрезке. Стационарной точка 𝑥 называется только при выполнение следующего условия: 𝑓 ′ (𝑥 ∗ ) = 0 Стационарная точка является локальной минимальной точкой для дважды дифференцируемой функции при выполнении следующего неравенства: 𝑓 ′′ (𝑥 ∗ ) > 0 Ниже рассмотрим основные классы численных методов. Одним из основных является метод половинного деления (дихотомии). Основная идея метода дихотомии состоит в постепенном делении отрезка на две части, часть, не содержащая минимума или максимума функции, отбрасывается. Следует отметить, что для использования данного метода необходимо, чтобы функция была унимодальна на всей длине данного отрезка. Стоит отметить, что уменьшение длины данного отрезка должно проходить методом выбора двух точек 𝑥1 и 𝑥2 , которые располагаются симметрично по отношению к середине отрезка 9

𝑥= 𝑎+𝑏 2 Абсциссы этих точек находятся по формулам: 𝛿 𝛿 𝑥1 = 𝑥 − ; 𝑥2 = 𝑥 + 2 2 𝛿 – это величина различимости точек (δ < ε). Наиболее подробно данный метод рассматривается в следующем разделе [2]. Метод равномерного поиска (метод перебора) можно отнести к пассивным стратегиям. Для начала необходимо задать начальный интервал 𝐿0 = [𝑎0 , 𝑏0 ] неопределенности, а также число 𝑁 вычисляемых значений функции на этом отрезке. Потом разделим интервал 𝐿0 на 𝑁 + 1 равных отрезков 𝑁 точками. Далее происходит процесс сравнения величин, а затем находится искомая точка, в которой значение функции принимает экстремальное значение (как минимальное, так и максимальное). Метод деления пополам даёт возможность исключать в точности половину интервала на этапе абсолютно каждой итерации. В редких случаях этот метод называют трехточечным поиском на равных интервалах, так как его осуществление происходит на как можно более точном выборе трех пробных точек, которые относительно равномерно распределены в определенном интервале поиска. Наиболее подробно данный метод рассматривается в следующем разделе [3]. Метод поразрядного поиска Метод поразрядного поиска имеет вид усовершенствованного метода перебора. С помощью переменного шага, можно найти точку минимума функции. Изначально шаг предполагается очень большим и сложно найти отрезок, в котором присутствует точка минимума. Но с заданием высокой точности, возможно отыскать точку минимума на данном отрезке. 10

Данную идею возможно реализовать с помощью метода поразрядного поиска таким образом: выбор точек лежащих на отрезке осуществляется с шагом: ∆= 𝑥𝑖+1 − 𝑥𝑖 > 𝜀 до того момента, когда, начнет увеличиваться функция, то есть условие: 𝑓(𝑥𝑖+1 ) ≥ 𝑓(𝑥𝑖 ) не выполнится, или же нет совпадения первой точки с правым концом отрезка [a, b], на котором происходит поиск минимума функции. Затем шаг становится меньше, а выбор точек происходит справа налево, до того момента, когда значения функции не начнут увеличиваться. Процесс можно считать законченным только в том случае, если выбор точек по заданному направлению завершен, а значение шага ∆ не превышает значение точности 𝜀. 1.3 Выбор среды разработки ПО На сегодняшнее время язык программирования C# является самым мощным, быстро развивающимся и востребованным языком в ИТ–отрасли. В настоящее время на этом языке C# пишут многие приложения: от небольших десктопных программок до крупных веб-порталов и веб-сервисов, обслуживающих ежедневно миллионы пользователей [28]. C# язык подобен синтаксисом с C, близок к C++ и Java. Это облегчает работу с C#. Java и С++ дали возможность быть объектно-ориентированным C#. К примеру, C# поддерживает статическую типизацию, полиморфизм, перегрузку операторов, наследование. Объектно-ориентированные подходы позволяют решить задачи по построению крупных, но в тот же момент гибких, расширяемых и масштабируемых приложений. И язык C# активно развивается, и каждая новая версия имеет больше интересных возможностей и функций, таких как асинхронные методы, динамическое связывание, и т.д.[30]. 11

Язык С# имеет массу преимуществ: объектная ориентированность, простота, типовая защищенность, поддержка совместимости версий, «сборка мусора» и многое другое. Это всё дает возможность для быстроты и легкости разработки приложений. Учитывая достижения многих других языков программирования: C++, С, Java, Visual Basic авторы С# создали проще, удобнее и современнее язык, который не уступает C++, но при этом существенно повышает продуктивность разработок [28]. На С# программа содержит один или несколькие файлы. Каждый файл может состоить из одного или нескольких пространств имен. Каждое пространство имен может содержать вложенные пространства имени типы, такие как классы, структуры, интерфейсы, перечисления и делегаты - функциональные типы. На языке С# возможно создать приложения для Windows Forms. Windows Forms дает очень простые и в тоже время мощные механизмы для управления графикой. Форма имеет вид экранного объекта, обычно в прямоугольной форме, который позволяет предоставлять информацию пользователю и вводить информацию от пользователя. Формы представляют собой следующие виды: стандартное диалоговое окно, много документного интерфейса (MDI) или поверхности для отображения графической информации. Разместить компоненты управления на поверхности формы – самый простой способ задания поверхности [30]. Форма – это объект, который содежит свойство для определения их внешного вида, методы для определения их вида, событие для определения их взаимодействия с пользователем. Форма имеет два окна программы для процесса создания приложения: окно дизайнера форм для отображения графического, которого представляет визуальных компонента формы и окно кода программы, в котором все данные вашей программы хранятся [28]. Дальше будем рассматривать еще одно хорошее программное обеспечение, которое используется по всему миру. 12

Matlab – это системный пакет программ, использующийся в инженерии и в научных вычислениях. В нем присутствует программы, связанные с различными математическими вычислениями. В среде Matlab возможна визуализация процессов и объектов исследования, построение графиков различных функций. Данная среда служит для построения математических моделей различных процессов. Система Matlab может применятся в следующих научных областях:  математика и вычисления;  анализ данных, исследование и визуализация результатов;  вычислительный эксперимент, имитационное моделирование, макетирование;  разработка алгоритмов;  разработка приложений, включая графический интерфейс пользователя;  научная и инженерная графика. Программирование в среде Matlab осуществляется на основе векторов, представляющих собой массив данных различной размерности. Т.е. существует возможность решать вычислительные вычислительные задачи с данными, заданными в векторно-матричном виде. Система Matlab имеет 2 вида м–файлов:  скрипты – это последовательность команд (представляют собой процедуры);  Function –это функция с входными аргументами и выходными параметрами (значениями функции). При решении других проблем может быть сложно визуализировать процесс, то есть переменная динамически изменяется в процессе решения задачи. Все эти и другие трудности могут быть решены с помощью графического интерфейса пользователя. (GUI-GraphicalUserInterface). 13

При использовании GUI дает возможность для создания программы более универсальной. После создания интерфейса появляются два файла: fig-файл и m-файл. fig-файл – это «фигура» самого интерфейса и m-файл создается самим Matlab и содержит программный код всех элементов интерфейса. В составе MatLab имеет среда GUIDE, которая позволяет создать приложения с графическим интерфейсом пользователя. Работа в GUIDE достаточно проста – компоненты управления (кнопки, выпадающие списки и т. д.) размещаются с помощью мыши, а затем события программируются, которые возникают, когда пользователь обращается к этим элементам управления. Преимущество среды GUIDE заключается в том, что легко сделать простой графический интерфейс. Весь код для интерфейса создается самим Matlab. Для работы с частью программы GUI вам необходимо изучить принцип обмена данными при использовании команд setappdata и getappdata (который является стандартным методом обмена данными между различными элементами GUI). Процесс построения графического интерфейса пользователя представляет собой три этапы:  Постановка задачи.  Создание формы интерфейса и создание на неё компонентов управления.  Написание кода программы и кода обработки событий. Таким образом, для разработки программы пользовательского интерфейса, с которой решены назначенные задачи в этой работе, обе программы, описанные выше подходят [29]. 14

2. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 2.1. Метод половинного деления Метод половинного деления – это самый простой для нахождения решения нелинейных уравнений численный метод. Данный метод предполагает, что функция 𝐽(𝑢) непрерывна. Основа данного метода располагается на теореме о промежуточных значениях. Таким образом, если необходимо найти значение минимума или максимума, то необходимо, чтобы функция имела на концах заданного отрезка противоположные знаки. Разделив данный отрезок пополам и взяв ту из частей, на концах которой значение функции также имеет противоположный знак. Если значение функции в точке, которая находится в середине, является искомым экстремумом, то процесс можно считать завершенным [1]. Опишем этот метод, пусть минимизируемая функция 𝐽(𝑢) унимодальна на отрезке [a, b]. Нахождение минимума 𝐽(𝑢) на отрезке [a, b] начинается с выбора двух точек 𝑢1 = 𝑎+𝑏−𝛿 2 и 𝑢2 = 𝑎+𝑏+𝛿 2 , где 𝛿 − постоянный параметр метода, 0 < 𝛿 < 𝑏 − 𝑎. Значение параметра δ выбирается произвольно и может быть определено соответствующим числом правильных десятичных цифр при задании аргумента. Ясно, что 𝛿 всегда больше машинного нуля ЭВМ, используемой при решении рассматриваемой задачи. Точки 𝑢1 и 𝑢2 симметрично расположены на [a, b] относительно его середины и делят его почти пополам при малых 𝛿 − это объясняет название метода [4]. После выбора точек 𝑢1 и 𝑢2 , значения 𝐽(𝑢1 ), 𝐽(𝑢2 ) вычисляются и сравниваются друг с другом. Если 𝐽(𝑢1 ) ≤ 𝐽(𝑢2 ), то пусть 𝑎1 = 𝑎, 𝑏1 = 𝑢2 ; если 𝐽(𝑢1 ) > 𝐽(𝑢2 ), то предположим что 𝑎1 = 𝑢1 , 𝑏1 = 𝑏. Необходимо, что функция 𝐽(𝑢) была унимодальна на отрезке [a, b], то ясно, что отрезок [a, b] имеет общую точку с множеством 𝑈∗ точек минимума 𝐽(𝑢) на [a, b] и его длину равно 15

𝑏1 − 𝑎1 = 𝑏−𝑎−𝛿 2 + 𝛿. Предположим, что отрезок [𝑎𝑘−1 , 𝑏𝑘−1 ], имеет непустое пересечение с 𝑈∗ , уже известен, и пусть 𝑏𝑘−1 − 𝑎𝑘−1 = точки 𝑢2𝑘−1 = 𝑎𝑘−1 +𝑏𝑘−1 −𝛿 2 , 𝑢2𝑘 = 𝑏−𝑎−𝛿 2𝑘−1 + 𝛿 > 𝛿(𝑘 ≥ 2). Тогда возьмём 𝑎𝑘−1 +𝑏𝑘−1 +𝛿 2 , расположенные на отрезке [𝑎𝑘−1 , 𝑏𝑘−1 ], симметрично относительно его середины, и вычислим значения 𝐽(𝑢2𝑘−1 ), 𝐽(𝑢2𝑘 ). Если 𝐽(𝑢2𝑘−1 ) ≤ 𝐽(𝑢2𝑘 ) то полагаем 𝑎𝑘 = 𝑎𝑘−1 ,𝑏𝑘 = 𝑢2𝑘 , если же 𝐽(𝑢2𝑘−1 ) > 𝐽(𝑢2𝑘 ), то полагаем 𝑎𝑘 = 𝑢2𝑘−1 ,𝑏𝑘 = 𝑏𝑘−1 . Длина получившегося отрезка [𝑎𝑘 , 𝑏𝑘 ] равна 𝑏𝑘 − 𝑎𝑘 = 𝑏−𝑎−𝛿 2𝑘 + 𝛿 > 𝛿 и [𝑎𝑘 , 𝑏𝑘 ] ∩ 𝑈∗ ≠ ∅ [22]. Если число вычислений значений минимизированной функции не ограничено, то описанный процесс деления интервала пополам может быть продолжать до тех пор, что не будет получить интервал [𝑎𝑘 , 𝑏𝑘 ] длины 𝑏𝑘 − 𝑎𝑘 < 𝜀, где 𝜀 − заданная точность, 𝜀 > 𝛿. Отсюда имеем, что 𝑘 > 𝑙𝑜𝑔2 ( 𝑏−𝑎−𝛿 𝜀−𝛿 ). Так как каждое деление пополам требует двух вычислений значений функции, то для достижения точности 𝑏𝑘 − 𝑎𝑘 < 𝜀 нужно всего 𝑛 = 𝑏−𝑎−𝛿 2𝑘 > 2𝑙𝑜𝑔2 ( 𝜀−𝛿 ) таких вычислений [23]. После нахождения отрезка [𝑎𝑘 , 𝑏𝑘 ] в качестве приближения к множеству 𝑈∗ можно взять точку 𝑢̅𝑛 = 𝑢2𝑘−1 при 𝐽(𝑢2𝑘−1 ) ≤ 𝐽(𝑢2𝑘 )и 𝑢̅𝑛 = 𝑢2𝑘 при 𝐽(𝑢2𝑘−1 ) > 𝐽(𝑢2𝑘 ), а значение 𝐽(𝑢̅𝑛 ) может служить приближением для 𝐽∗ = inf 𝐽(𝑢). 𝑢 ∈ [𝑎, 𝑏] При этом выборе приближения для 𝑈∗ будет допущена погрешность 𝜌(𝑢̅𝑛 , 𝑈∗ ) ≤ max{𝑏𝑘 − 𝑢̅𝑛 ; 𝑢̅𝑛 − 𝑎𝑘 } = 𝑏−𝑎−𝛿 2𝑘 . Если не будем требовать того, чтобы значение функции, приниятой в качестве приближения к 𝐽∗ , вычислялось в той же точке, которая служит приближением к 𝑈∗ , то вместо 16

𝑢̅𝑛 можем взять точку 𝑣𝑛 = 𝑏𝑘 −𝑎𝑘 2 = 𝑏−𝑎−𝛿 2𝑘+1 𝛿 𝑛 2 2 𝑎𝑘 +𝑏𝑘 с меньшей погрешностью 𝜌(𝑢̅𝑛 , 𝑈∗ ) ≤ 2 + (𝑘 = и 𝛿 достаточно мало) [24]. 2.2. Программная реализация метода половинного деления Метод половинного деления относится к последовательным стратегиям. Задаются пользователем начальный интервал и точности. Алгоритм основан на анализ значений функции в двух точках. Чтобы найти их, необходимо делить данный интервал неопределенности пополам и по обе 𝜀 стороны от середины сохраняется в , где 𝜀 − небольшое положительное 2 число. Если длина установленного текущего величины, то интервала процесса неопределенности поиска стандартные: меньше поиск заканчивается [10]. Схема решения задачи методом половинного деления: Этап 1. Задается начальный интервал неопределенности 𝐿0 = [𝑎0 , 𝑏0 ], 𝜀 − малое число, 𝑙 > 0 −точность. Этап 2. Примем 𝑘 = 0. Этап 3. Вычислим 𝑦𝑘 = 𝑎𝑘 +𝑏𝑘 −𝜀 2 , 𝑓(𝑦𝑘 ), 𝑧𝑘 = 𝑎𝑘 +𝑏𝑘 +𝜀 2 , 𝑓(𝑧𝑘 ). Этап 4. Сравним 𝑓(𝑦𝑘 ) и 𝑓(𝑧𝑘 ): 1) если 𝑓(𝑦𝑘 ) ≤ 𝑓(𝑧𝑘 ), то положим 𝑎𝑘+1 = 𝑎𝑘 , 𝑏𝑘+1 = 𝑧𝑘 (рис. 2.1, а) и перейдём к этапу 5; 2) если 𝑓(𝑦𝑘 ) > 𝑓(𝑧𝑘 ), то положим 𝑎𝑘+1 = 𝑦𝑘 , 𝑏𝑘+1 = 𝑏𝑘 (рис. 2.1, б). Этап 5. Вычислим ∆ = |𝑏𝑘+1 − 𝑎𝑘+1 | и проверим условие окончания: а) если ∆ ≤ 𝑙, процесс поиска завершается. Точка минимума 𝑥 ∗ ∈ [𝑎𝑘+1 , 𝑏𝑘+1 ]. Значение приближенного решения определяется по формуле: 𝑥∗ ≅ 𝑎𝑘+1 +𝑏𝑘+1 2 ; б) если ∆ > 𝑙, положим 𝑘 = 𝑘 + 1 и перейдём к этапу 3[11]. 17

Рис. 2.1 2.3. Метод золотого сечения Идея метода с золотого сечения остоит в постепенном делении отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Известно, что золотое сечение интервала [a, b] производится двумя точками: 𝑢1 = 𝑎 + 3 − √5 (𝑏 − 𝑎) = 𝑎 + 0.3819 … (𝑏 − 𝑎); 2 √5 − 1 (𝑏 − 𝑎) = 𝑎 + 0.6180 … (𝑏 − 𝑎), 2 расположенными симметрично относительно от середины интервала, причем 𝑢2 = 𝑎 + 𝑎 < 𝑢1 < 𝑢2 < 𝑏, 𝑏−𝑎 𝑏−𝑢1 = 𝑏−𝑢1 𝑢1 −𝑎 = 𝑏−𝑎 𝑢2 −𝑎 = 𝑢2 −𝑎 𝑏−𝑢2 = √5+1 2 = 1.618033989 … Замечательно здесь то, что точка и, в свою очередь производит золотое сечение интервала [𝑎, 𝑢2 ], так как 𝑢2 − 𝑢1 < 𝑢1 − 𝑎 = 𝑏 − 𝑢2 и 𝑢2 −𝑎 𝑢1 −𝑎 = 𝑢1 −𝑎 𝑢2 −𝑢1 . Аналогично точка 𝑢2 производит золотое сечение отрезка [𝑢1 , 𝑏]. На 18

основании этого свойства золотого сечения, мы можем предложить следующий метод для минимизации функции унимодального 𝐽(𝑢) на интервале [а, b] [21]. Положить 𝑎1 = 𝑎, 𝑏1 = 𝑏. На интервале [𝑎1 , 𝑏1 ] взять точки 𝑢1 и 𝑢2 , которые производят золотое сечение, и вычислить значения 𝐽(𝑢1 ), 𝐽(𝑢2 ). Далее, если 𝐽(𝑢1 ) ≤ 𝐽(𝑢2 ), то положить 𝑎2 = 𝑎1 , 𝑏2 = 𝑢2 , 𝑢̅2 = 𝑢1 ; если 𝐽(𝑢1 ) > 𝐽(𝑢2 ), то положить 𝑎2 = 𝑢1 , 𝑏2 = 𝑏1 , 𝑢̅2 = 𝑢2 . Поскольку функция 𝐽(𝑢) унимодальна на интервале[а, b], то интервал [𝑎2 , 𝑏2 ] имеет по крайней мере одну общую точку с множеством 𝑈∗ точек минимума функции 𝐽(𝑢) на [а, b]. Кроме того, 𝑏2 − 𝑎2 = √5−1 (𝑏 2 − 𝑎) и важно то, что внутри [𝑎2 , 𝑏2 ] была точка 𝑢̅2 с вычисленным значением 𝐽(𝑢̅2 ) = min{ 𝐽(𝑢1 ), 𝐽(𝑢2 )}, которая производит золотое сечение отрезка [𝑎2 , 𝑏2 ] [18]. Пусть уже определены точки 𝑢1 , 𝑢2 , … , 𝑢𝑛−1 вычислены значения 𝐽(𝑢1 ), ..., 𝐽(𝑢𝑛−1 ), найден отрезок [𝑎𝑛−1 , 𝑏𝑛−1 ] такой, что [𝑎𝑛−1 , 𝑏𝑛−1 ]∩ 𝑈∗ ≠ ∅, 𝑏𝑛−1 − 𝑎𝑛−1 = 𝑛−2 √5−1 (𝑏 ( 2 ) − 𝑎), и известна точка 𝑢̅𝑛−1 , производящая золотое сечение отрезка [𝑎𝑛−1 , 𝑏𝑛−1 ] и такая, что 𝐽(𝑢̅𝑛−1 ) = min 𝐽(𝑢𝑖 )(𝑛 ≥ 1≤𝑖 ≤𝑛−1 2). Тогда в качестве следующей точки возьмем точку 𝑢𝑛 = 𝑎𝑛−1 + 𝑏𝑛−1 − 𝑢̅𝑛−1 , также производящую золотое сечение отрезка [𝑎𝑛−1 , 𝑏𝑛−1 ] вычислим значение 𝐽(𝑢𝑛 ). Предположим для определенности, что 𝑎𝑛−1 < 𝑢𝑛 < 𝑢̅𝑛−1 < 𝑏𝑛−1 (случай 𝑢̅𝑛−1 < 𝑢𝑛 рассматривается аналогично). Если 𝐽(𝑢𝑛 ) ≤ 𝐽(𝑢̅𝑛−1 ), то полагаем 𝑎𝑛 = 𝑎𝑛−1 , 𝑏𝑛 = 𝑢̅𝑛−1 , 𝑢̅𝑛 = 𝑢𝑛 ; если 𝐽(𝑢𝑛 ) > 𝐽(𝑢̅𝑛−1 ), то полагаем 𝑎𝑛 = 𝑢𝑛 , 𝑏𝑛 = 𝑏𝑛−1 , 𝑢̅𝑛 = 𝑢̅𝑛−1 . Новый отрезок [𝑎𝑛 , 𝑏𝑛 ] таков, что [𝑎𝑛 , 𝑏𝑛 ]∩ 𝑛−1 √5−1 (𝑏 ) 2 𝑈∗ ≠ ∅, 𝑏𝑛 − 𝑎𝑛 = ( − 𝑎), точка 𝑢̅𝑛 , производит золотое сечение [𝑎𝑛 , 𝑏𝑛 ] и 𝐽(𝑢̅𝑛−1 ) = min{𝐽(𝑢𝑛 ); 𝐽(𝑢̅𝑛−1 )}= min 𝐽(𝑢𝑖 ) (1 ≤ 𝑖 ≤ 𝑛 − 1) [16]. 19

Если количество вычислений значений 𝐽(𝑢) не ограничено заранее, то описанный процесс можно продолжить, например, до тех пор, пока не выполнено неравенство 𝑏𝑛 − 𝑎𝑛 < 𝜀, где 𝜀 − требуемая точность. Если количество вычислений значении функции 𝐽(𝑢) предварительно фиксировано и равно 𝑛, то процесс заканчивается и как решение проблемы второго типа, мы можем взять пару 𝐽(𝑢̅𝑛 ), 𝑢̅𝑛 , где 𝐽(𝑢̅𝑛 ) является приближением для 𝐽∗ = 𝑖𝑛𝑓 𝐽(𝑢)(𝑢 ∈ [𝑎, 𝑏]), а точка 𝑢̅𝑛 служит приближением для множества 𝑈∗ с погрешностью 1 𝜌(𝑢̅𝑛 , 𝑈∗ ) ≤ max{𝑏𝑛 − 𝑢̅𝑛 ; 𝑢̅𝑛 − 𝑎𝑛 } = (√5 − 1)(𝑏𝑛 − 𝑎𝑛 )= 2 𝑛 √5−1 ) 2 =( (𝑏 − 𝑎) = 𝐴𝑛 . Ранее было показано, с помощью метода половинного деления за 𝑛 = 2𝑘 вычислений значений функции 𝐽(𝑢) в аналогичном случае было получить точку 𝑢̅𝑛 с погрешностью 𝜌(𝑢̅𝑛 , 𝑈∗ ) ≤ 2−𝑛⁄2 (𝑏 − 𝑎 − 𝛿) < 2−𝑛⁄2 (𝑏 − 𝑎) = 𝐵𝑛 . Отсюда имеем 𝐴𝑛 ⁄𝐵𝑛 = ( 2√2 𝑛 ) √5+1 ≈ (0.87 … )𝑛 − видно, что уже при небольших 𝑛 преимущество метода золотого сечения перед методом деления отрезка пополам становится ощутимым [22]. Рассмотрим возможности численной реализации метода золотого сечения на компьютере. Заметим, что число √5 в компьютере неизбежно будет задаваться приближенно, поэтому первая точка 𝑢1 = 𝑎 + 3−√5 (𝑏 2 − 𝑎) будет найдена с некоторой погрешностью. Посмотрим, как повлияет эта погрешность на результаты последующих шагов метода золотого сечения. Обозначим ∆𝑛 = 𝑏𝑛 − 𝑎𝑛 = 𝑛−1 √5−1 ( 2 ) (𝑏 − 𝑎). Нетрудно проверим, что ∆𝑛 является решением конечно-разностного уравнения ∆𝑛−2 = ∆𝑛−1 + ∆𝑛 , или ∆𝑛 = ∆𝑛−2 − ∆𝑛−1 (𝑛 = 3, 4, …(1). с начальными условиями ∆1 = 𝑏 − 𝑎, ∆2 = 𝑏 − 𝑢1 . 20

Как известно, линейно независимые частные решения этого уравнения имеют 𝜏1𝑛 и 𝜏2𝑛 (𝑛 = 1, 2, ...), где 𝜏1 = √5−1 , 2 𝜏2 = √5+1 2 − корни (2) характеристического уравнения 𝜏 2 + 𝜏 − 1 = 0, а любое решение уравнения (1) представимо в виде ∆𝑛 =𝐴𝜏1𝑛 + 𝐵𝜏𝑛2 , 𝑛 = 1, 2, ... где постоянные А и В однозначно определяются начальными условиями из линейной системы [2] 𝐴𝜏1 + 𝐵𝜏2 = ∆1 , 𝐴𝜏12 + 𝐵𝜏22 = ∆2 . (3) 2.4. Программная реализация метода золотого сечения Метод относится к последовательным стратегиям. Задаются пользователем начальный интервал и точность. Алгоритм уменьшения интервала основан на анализе значения функции в двух точках. Точки золотого сечения выбираются в качестве точек вычисления функции Затем, принимая во внимание свойства золотого сечения на каждой итерации, кроме первой, требуется только один новый расчет значения функции. Условия окончания процесса поиска стандартные: поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины [1]. Схема решения задачи методом золотого сечения: Этап 1. Задается начальный интервал неопределенности 𝐿0 = [𝑎0 , 𝑏0 ], 𝜀 > 0 − точность. Этап 2. Примем 𝑘 = 0. Этап 3. Вычислим 𝑦0 = 𝑎0 + 3−√5 2 (𝑏0 − 𝑎0 ); 𝑧0 = 𝑎0 + 𝑏0 − 𝑦0 . Этап 4. Вычислим 𝑓(𝑦𝑘 ) , 𝑓(𝑧𝑘 ). Этап 5. Сравним 𝑓(𝑦𝑘 ) и 𝑓(𝑧𝑘 ): 21

а) если 𝑓(𝑦𝑘 ) ≤ 𝑓(𝑧𝑘 ), положим 𝑎𝑘+1 = 𝑎𝑘 , 𝑏𝑘+1 = 𝑧𝑘 и 𝑦𝑘+1 = 𝑎𝑘+1 + 𝑏𝑘+1 − 𝑦𝑘 , 𝑧𝑘+1 = 𝑦𝑘 (рис. 2.2, а) и перейдём к этапу 6; б) если 𝑓(𝑦𝑘 ) > 𝑓(𝑧𝑘 ), то положим 𝑎𝑘+1 = 𝑦𝑘 , 𝑏𝑘+1 = 𝑏𝑘 и 𝑦𝑘+1 = 𝑧𝑘 , 𝑧𝑘+1 = 𝑎𝑘+1 + 𝑏𝑘+1 − 𝑧𝑘 (рис. 2.2, б). Этап 6. Вычислим ∆ = |𝑏𝑘+1 − 𝑎𝑘+1 | и проверим условие окончания: 1) если ∆ ≤ 𝜀, процесс поиска завершается. Точка минимума 𝑥 ∗ ∈ [𝑎𝑘+1 , 𝑏𝑘+1 ]. Значение приближенного решения определяется по формуле: 𝑥∗ ≅ 𝑎𝑘+1 +𝑏𝑘+1 2 ; 2) если ∆ > 𝜀, то положим 𝑘 = 𝑘 + 1 и перейдем к этапу 4 [23]. Рис. 2.2 22

3. МЕТОДЫ МИНИМИЗАЦИИ ДЛЯ ФУНКЦИЙ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ 3.1. Градиентный метод. Рассматрим задачу 𝐽(𝑢) → 𝑖𝑛𝑓; 𝑢 ∈ 𝑈 ≡ 𝐸 𝑛 , предполагать, что функция J(u) непрерывно дифференцируема на E n , т. е. J(u) ∈ C1 (E n ). Согласно дифференцируемой фупкцни J(u + h)-J(u) = 〈J ' (u), h〉 + o(h; u), (1) где lim 𝑜(ℎ; 𝑢)|ℎ|−1 = 0. Если 𝐽′ (𝑢) ≠ 0, то при достаточно малых |ℎ| |ℎ| → 0 главная часть приращения (1) определяется дифференциалом функции 𝑑𝐽(𝑢) = 〈𝐽′ (𝑢), ℎ〉. Справедливо неравенство Коши − Буняковского −|𝐽′ (𝑢)|. |ℎ| ≤ 〈𝐽′ (𝑢), ℎ〉 ≤ |𝐽′ (𝑢)|. |ℎ|, причем если 𝐽′ (𝑢) ≠ 0, то правое неравенство превращается в равенство только при ℎ = 𝛼𝐽′ (𝑢), а левое неравенство − только при 𝐽′ (𝑢) ≠ 0, где 𝑎 = 𝑐𝑜𝑛𝑠𝑡 ≥ 0. Отсюда ясно, что при 𝐽′ (𝑢) ≠ 0 направление наибыстрейшего возрастания функции 𝐽(𝑢) в точке и совпадает с направлением градиента 𝐽′ (𝑢), а направление наибыстреншего убывания − с направлением антпградиента (−𝐽′ (𝑢)) [2]. Это свойство градиента, которое лежит в основе ряда итерационных методов минимизации функций. Один из этих методов называется градиентным методом. Этот метод, как и все итерационные методы, предполагают выбор начального приближения − некоторой точки 𝑢0 . Общих правил выбора точки 𝑢0 в методе градиента, как, к сожалению, другими методами. В тех случаях, когда априорная информация о местоположении точки (или точек) минимума может быть получена из геометрических, 23

физических или любых других соображений, начальное приближение 𝑢0 стараются выбрать поближе к этой области [15]. Предположим, что некоторая начальная точка 𝑢0 уже выбрана. Тогда метод градиента состоит в построении последовательности {𝑢𝑘 } по правилу 𝑢𝑘+1 = 𝑢𝑘 − 𝛼𝑘 𝐽′ (𝑢𝑘 ), 𝛼𝑘 > 0, 𝑘 = 0,1,2, … (2) Число 𝛼𝑘 из (2) часто называют длиной шага или просто шагом градиентного метода. Если 𝐽′ (𝑢𝑘 ) ≠ 0, то шаг 𝛼𝑘 > 0 можно выбрать так, чтобы 𝐽(𝑢𝑘+1 ) < 𝐽(𝑢𝑘 ). В самом деле, из равенства (1) имеем 𝐽(𝑢𝑘+1 ) − 𝐽(𝑢𝑘 ) = 𝛼𝑘 [−|𝐽′ (𝑢𝑘 )|2 + o(𝛼𝑘 )𝛼𝑘−1 ] < 0 при всех достаточно малых 𝛼𝑘 > 0. Если 𝐽′ (𝑢𝑘 ) = 0, то 𝑢𝑘 − стационарная точка. В этом случае процесс (2) прекращается, и при необходимости проводится дополнительное исследование поведения функции в окрестности точки ик для выяснения того, достигается ли в точке 𝑢𝑘 минимум функции 𝐽(𝑢) или не достигается. В частности, если 𝐽(𝑢) − выпуклая функция, то в стационарной точке всегда достигается минимум [7]. Существовать многие способы выбора величины 𝛼𝑘 в методе (2). В зависимости от способа выбора 𝛼𝑘 можно получить различные варианты градиентного метода. 1) На луче {𝑢 ∈ 𝐸 𝑛 : 𝑢 = 𝑢𝑘 − 𝛼𝑘 𝐽′ (𝑢𝑘 ), 𝛼 ≥ 0}, направленном по антиградиенту, введем функцию одной переменной 𝑓𝑘 (𝛼) = 𝐽(𝑢𝑘 − 𝛼𝑘 𝐽′ (𝑢𝑘 )) , 𝛼 ≥ 0, и определим 𝛼𝑘 из условий (3) 𝑓𝑘 (𝛼𝑘 ) = inf 𝑓𝑘 (𝛼) = 𝑓𝑘∗ , 𝛼𝑘 > 0 𝛼≥0 Метод (2), (3) принято называть методом скорейшего спуска. При 𝐽′ (𝑢𝑘 ) ≠ 0 согласно 𝑓𝑘′ (0) = −|𝐽′ (𝑢𝑘 )|2 < 0, поэтому нижняя грань в (3) может достигаться лишь при 𝛼𝑘 > 0 [14]. 24

2) На практике нередко довольствуются нахождением какого-либо 𝛼𝑘 > 0, обеспечивающего условие монотонности: (𝑢𝑘+1 ) < 𝐽(𝑢𝑘 ). С этой целью задаются какой-либо постоянной 𝛼 > 0 и в методе (2) на каждой итерации берут 𝛼𝑘 = 𝛼. При этом для каждого 𝑘 ≥ 0 проверяют условие монотонности, и в случае его нарушения 𝛼𝑘 = 𝛼 дробят до тех пор, пока не восстановится монотонность метода. Время от времени полезно пробовать увеличить 𝛼 с сохранением условия монотонности. 3) Если функция 𝐽(𝑢) ∈ 𝐶 1,1 (𝐸 𝑛 ), т. е. 𝐽(𝑢) ∈ 𝐶 1 (𝐸 𝑛 ), и градиент 𝐽′ (𝑢) удовлетворяет условию 𝐽′ (𝑢) − 𝐽′ (𝑣) ≤ 𝐿|𝑢 − 𝑣|, 𝑢, 𝑣 ∈ 𝐸 𝑛 причем константа 𝐿 известна, то в (2) в качестве 𝛼𝑘 может быть взято любое число, удовлетворяющее условиям 0 < 𝜀0 ≤ 𝛼𝑘 ≤ 2⁄(𝐿 + 2𝜀), (4) где 𝜀0 , 𝜀 − положительные числа, являющиеся параметрами метода. В частности, при 𝜀 = 𝐿/2, 𝜀0 = 1/𝐿 получим метод (2) с постоянным шагом 𝛼𝑘 = 1/𝐿. Отсюда ясно, что если константа 𝐿 большая или получена с помощью слишком грубых оценок, то шаг 𝛼𝑘 в (2) будет маленьким [13]. 4) Возможен выбор 𝛼𝑘 из условия 𝐽(𝑢𝑘 ) − 𝐽(𝑢𝑘 − 𝛼𝑘 𝐽′ (𝑢𝑘 )) ≥ 𝜀𝛼𝑘 |𝐽′ (𝑢𝑘 )|2 , 𝜀 > 0. (5) Для удовлетворения условия (5) сначала обычно берут некоторое число а 𝛼𝑘 = 𝛼 > 0 (одно и то жо на всех итерациях), а затем при необходимости дробят его, т. е. изменяют по закону 𝛼𝑘 = 𝜔𝑖 𝛼 (𝑖 = 0,1,2, … ,0 < 𝜔 < 1) до тех пор, пока впервые не выполнится условие (5). Из рис. 3.1 и 3.2 можно попять, что чем ближе линии уровня 𝐽(𝑢) = 𝑐𝑜𝑛𝑠𝑡 к окружности, тем лучше сходится метод скорейшего спуска. Это же явление можно усмотреть и чем ближе 𝜇⁄𝐿 к единице (для функции 𝐽(𝑢) = 25

|𝑢|2 , у которой линиями уровня являются окружности (сферы), как раз имеем 𝜇⁄𝐿 = 1, тем ближе 𝑞 к нулю и тем лучше сходимость [3]. Те же рис. 3.1 и 3.2 показывают, а теоретические исследования и численные эксперименты подтверждают, что метод скорейшего спуска и другие варианты градиентного метода медленно Рис. 3.1 Рис. 3.2 сходятся в тех случаях, когда поверхности уровня функции 𝐽(𝑢) сильно вытянуты и функция имеет так называемый «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений функции − эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно (на рис. 3.2 и 3.3 изображены линии уровня «овражной» функции двух переменных) [18]. 26

Рис. 3.3 Если точка лежит на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», и в результате аппроксимации {𝑢𝑘 }, полученной метод градиента, будет попеременно располагаться на одном «склоне оврага». Если «склоны оврага» достаточно круты, то такие скачки «со склона на склон» точек 𝑢𝑘 могут значительно замедлить сходимость метода градиента. Чтобы ускорить сближение этого метода при поиске минимума функции «овражной», мы можем предложить следующий эвристический метод, называемый методом оврага. Сначала мы опишем простейшую версию этого метода. В начале поиска задаются две точки 𝑣0 , 𝑣1 из которых производят спуск с помощью некоторого варианта метода градиента, и получить две точки 𝑢0 , 𝑢1 на «дне оврага». Затем полагают 𝑣2 = 𝑢1 − (𝑢1 − 𝑢0 )|𝑢1 − 𝑢0 |−1 ℎ sign(𝐽(𝑢1 ) − 𝐽( 𝑢0 )), где ℎ − положительная постоянная, называемая овражным шагом. Из точки 𝑣2 , которая, вообще говоря, находится на «склоно оврага», производят спуск с помощью градиентного метода и определяют следующую точку 𝑢2 на «дне оврага» [17]. Если уже известны точки 𝑢0 , 𝑢1 , … , 𝑢𝑘 (𝑘 ≥ 2), то из точки 27

𝑣𝑘+1 = 𝑢𝑘 − (𝑢𝑘 − 𝑢𝑘−1 )|𝑢𝑘 − 𝑢𝑘−1 |−1 ℎ sign(𝐽(𝑢𝑘 ) − 𝐽( 𝑢𝑘−1 )), совершают спуск с помощью градиентного метода и находят следующую точку 𝑢𝑘+1 на «дне оврага» (см. рис. 3.3; спуск из точки 𝑣𝑘 в точку 𝑢𝑘 , состоящий, быть может, из нескольких итерационных шагов градиентного метода, условно изображен отрезком прямой, соединяющей точки 𝑣𝑘 , 𝑢𝑘 , 𝑘 = 0, 1, 2, … ). 3.2. Программная реализация градиентного метода Стратегия решения задачи состоит в построении последовательности точек {𝑥 𝑘 } , 𝑘 = 0, 1, 2, …, таких, что 𝑓(𝑥 𝑘+1 ) < 𝑓(𝑥 𝑘 ), 𝑘 = 0, 1, 2, ….Точки последовательности {𝑥 𝑘 } вычисляются по правилу 𝑥 𝑘+1 = 𝑥 𝑘 − 𝑡𝑘 ∇𝑓(𝑥 𝑘 ) где точка 𝑥 0 задается пользователем; ∇𝑓(𝑥 𝑘 ) − градиент функции 𝑓(𝑥), вычисленный в точке 𝑥 𝑘 ; величина шага 𝑡𝑘 задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия: 2 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 ) < 0 или 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 ) < −ε‖∇𝑓(𝑥 𝑘 )‖ , 0 < 𝜀 < 1. Построение последовательности {𝑥 𝑘 } заканчивается в точке 𝑥 𝑘 , для которой ‖∇𝑓(𝑥 𝑘 )‖ < 𝜀1 , где 𝜀1 − заданное малое положительное число, или 𝑘 ≥ 𝑀, где 𝑀 − предельное число итерации, или при двукратном одновременном выполнении двух неравенств: ‖𝑥 𝑘+1 − 𝑥 𝑘 ‖ < 𝜀2 и | 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 )| < 𝜀2 , где 𝜀2 − малое положительное число. Схема решения задачи градиентным методом Этап 1. Задается 𝑥 0 , 0 < 𝜀 < 1, 𝜀1 > 0, 𝜀2 > 0, 𝑀 − предельное количество итераций. Вычислим градиент функции в произвольной точке: ∇𝑓(𝑥) = ( 𝜕𝑓(𝑥) 𝜕𝑓(𝑥) ,…, ) 𝜕𝑥1 𝜕𝑥𝑛 28

Этап 2. Примем 𝑘 = 0. Этап 3. Вычислим ∇𝑓(𝑥 𝑘 ) Этап 4. Проверим выполнение критерия окончания ‖∇𝑓(𝑥 𝑘 )‖ < 𝜀1 : 1) если ‖∇𝑓(𝑥 𝑘 )‖ < 𝜀1 , процесс поиска закончен, 𝑥 ∗ = 𝑥 𝑘 ; 2) если ‖∇𝑓(𝑥 𝑘 )‖ ≥ 𝜀1 , то перейдём к этапу 5. Этап 5. Проверим 𝑘 ≥ 𝑀: 1) если 𝑘 ≥ 𝑀, то процесс поиска окончен: 𝑥 ∗ = 𝑥 𝑘 ; 2) если 𝑘 < 𝑀, то перейдём к этапу 6. Этап 6. Задается величину шага 𝑡𝑘 . Этап 7. Вычислим 𝑥 𝑘+1 = 𝑥 𝑘 − 𝑡𝑘 ∇𝑓(𝑥 𝑘 ). Этап 8. Проверим выполнение условия 2 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 ) < 0 ( или 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 ) < −ε‖∇𝑓(𝑥 𝑘 )‖ ): 1) если условие выполнено, то перейдём к этапу 9; 2) если условие не выполнено, положим 𝑡𝑘 = 𝑡𝑘 2 и перейдём к этапу 7. Этап 9. Проверим выполнение условий ‖𝑥 𝑘+1 − 𝑥 𝑘 ‖ < 𝜀2 и | 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 )| < 𝜀2 : 1) если два условия выполнены при текущем значении 𝑘 и 𝑘 = 𝑘 − 1, то процесс поиска окончен, 𝑥 ∗ = 𝑥 𝑘+1 ; 2) если хотя бы одно из условий не выполнено, положим 𝑘 = 𝑘 + 1 и перейдём этапу 3 [19]. 29

Геометрическая интерпретация метода для 𝑛 = 2 приведена на рис. 3.4. Рис 3.4 3.3. Метод Ньютона Опишем метод Ньютона для задачи 𝐽(𝑢) → 𝑖𝑛𝑓; 𝑢 ∈ 𝑈, (1) где 𝐽(𝑢) ∈ 𝐶 2 (𝑈), 𝑈 − выпуклое замкнутое множество из 𝐸 𝑛 . Пусть 𝑢0 ∈ 𝑈 − некоторое начальное приближение. Если известно 𝑘 − 𝑒 приближение 𝑢𝑘 , то приращение функции 𝐽(𝑢) ∈ 𝐶 2 (𝑈) в точке 𝑢𝑘 можно представить в виде 1 𝐽(𝑢) − 𝐽(𝑢𝑘 ) = 〈𝐽′ (𝑢𝑘 ), 𝑢 − 𝑢𝑘 〉 + 〈𝐽′′ (𝑢𝑘 )(𝑢 − 𝑢𝑘 ), 𝑢 − 𝑢𝑘 〉 + 𝑜(|𝑢 − 𝑢𝑘 |2 ). 2 Возьмем квадратичную часть этого приращения 1 𝐽𝑘 (𝑢) ≡ 〈𝐽′ (𝑢𝑘 ), 𝑢 − 𝑢𝑘 〉 + 〈𝐽′′ (𝑢𝑘 )(𝑢 − 𝑢𝑘 ), 𝑢 − 𝑢𝑘 〉 2 (2) и определим вспомогательное приближение 𝑢̅𝑘 из условий 𝑢̅𝑘 ∈ 𝑈, 𝐽𝑘 (𝑢̅𝑘 ) = inf 𝐽𝑘 (𝑢). 𝑈 (3) Следующее (𝑘 + 1) − 𝑒 приближение будем искать в виде (4) 30

𝑢𝑘+1 = 𝑢𝑘 + 𝛼𝑘 (𝑢̅𝑘 − 𝑢𝑘 ), 0 ≤ 𝛼𝑘 ≤ 1. В зависимости от способа выбора величины 𝛼𝑘 в (4) можно получить различные варианты метода (2) − (4), называемого методом Ньютона. Укажем несколько наиболее употребительных способов выбора 𝛼𝑘 [20]. 1) В (4) можно принять αk = 1, k = 0,1,2, … (5) В этом случае, как следует из (4), uk+1 = uk (k = 0,1,2, …), т. е. условие (3) сразу определяет следующее (k + 1)-e приближение. Иначе говоря, uk+1 ∈ U, Jk (uk+1 ) = inf Jk (u). (6) В частности, когда U = E n , в точке минимума функции Jk (u) ее производная Jk' (u) обращается в нуль, т. е. (7) Jk' (uk+1 ) = 𝐽′ (𝑢𝑘 ) + 𝐽′′ (𝑢𝑘 )(𝑢𝑘+1 − 𝑢𝑘 ) = 0 Это значит, что на каждой итерации метода (2) − (5) пли (6) нужно решать линейную алгебраическую систему уравнении (7) относительно неизвестной разпости 𝑢𝑘+1 − 𝑢𝑘 . Если матрица этой системы 𝐽′′ (𝑢𝑘 ) − невырожденная, то из (7) имеем −1 𝑢𝑘+1 = 𝑢𝑘 − (𝐽′′ (𝑢𝑘 )) 𝐽′ (𝑢𝑘 ), 𝑘 = 0,1,2, … (8) Широко известный метод Ньютона для решения системы уравнений 𝐹(𝑢) = {𝐹1 (𝑢), … , 𝐹𝑛 (𝑢)} = 0, 𝑢 ∈ 𝐸 𝑛 , представляет собой итерационный процесс −1 𝑢𝑘+1 = 𝑢𝑘 − (𝐹 ′ (𝑢𝑘 )) 𝐹(𝑢𝑘 ) (9) где 𝐹 ′ (𝑢𝑘 ) − матрица, i-я строка которой равна 𝐹𝑖′ = (𝐹𝑖𝑢1 , … , 𝐹𝑖𝑢𝑛 ). Сравнение формул (8) и (9) показывает, что метод (8) решения задачи (1) в случае 𝑈 = 𝐸 𝑛 представляет собой известный метод Ньютона для решения 31

уравнения 𝐽′ (𝑢) = 0, определяющего стационарные точки функции 𝐽(𝑢). Отсюда происходит название метода (2) − (4) и в общем случае [23]. 2) В качестве 𝛼𝑘 в (4) можно принять 𝛼𝑘 = 𝜔 𝑖0 , где 𝑖0 − минимальный среди 𝑖 ≥ 0 номер, для которых выполняется неравенство 𝐽(𝑢𝑘 ) − 𝐽(𝑢𝑘 + 𝜔𝑖 (𝑢̅𝑘 − 𝑢𝑘 )) ≥ 𝜀𝜔𝑖 |𝐽𝑘 (𝑢̅𝑘 )|, Где 𝜔, 𝜀 − параметры метода, 0 < 𝜔; 𝜀 < 1. 3) Возможен выбор 𝛼𝑘 в (4) из условий [3] 0 ≤ 𝛼𝑘 ≤ 1, 𝑓𝑘 (𝛼𝑘 ) = min 𝑓𝑘 (𝛼), 𝑓𝑘 (𝛼) = 𝐽(𝑢𝑘 + 𝛼(𝑢̅𝑘 − 𝑢𝑘 )). 0≤𝛼≤1 3.4. Программная реализация метода Ньютона Стратегия метода Ньютона (Newton) состоит в построении последовательности точек {𝑥 𝑘 } , 𝑘 = 0, 1, 2, …, таких, что 𝑓(𝑥 𝑘+1 ) < 𝑓(𝑥 𝑘 ), 𝑘 = 0, 1, 2, ….Точки последовательности {𝑥 𝑘 } вычисляются по правилу 𝑥 𝑘+1 = 𝑥 𝑘 + 𝑑 𝑘 , 𝑘 = 0, 1, 2, …, где точка 𝑥 0 задается пользователем; а направление спуска 𝑑 𝑘 определяется для каждого значения 𝑘 по формуле 𝑑 𝑘 = −𝐻 −1 (𝑥 𝑘 )∇𝑓(𝑥 𝑘 ) (3.1) Выбор 𝑑 𝑘 по формуле (3.1) гарантирует выполнение требования 𝑓(𝑥 𝑘+1 ) < 𝑓(𝑥 𝑘 ), при условии, что 𝐻(𝑥 𝑘 ) > 0. Формула (3.1) получена из следующих соображений: 1) функция 𝑓(𝑥) аппроксимируется в каждой точке последовательности 1 {𝑥 𝑘 } квадратичной функцией 𝐹𝑘 = 𝑓(𝑥 𝑘 ) + (∇𝑓(𝑥 𝑘 ), 𝑑 𝑘 ) + (𝑑 𝑘 , 𝐻(𝑥 𝑘 )𝑑 𝑘 ); 2 2) направление 𝑑 𝑘 определяется из необходимого условия экстремума первого порядка: 𝑑𝐹𝑘 𝑑𝑑 𝑘 = 0. Таким образом, при выполнении требования 𝐻(𝑥 𝑘 ) > 0 последовательность минимумов квадратичных является функций 𝐹𝑘 , последовательностью точек 𝑘 = 0, 1, 2, …(рис.3.5). Чтобы обеспечить выполнение требования 𝑓(𝑥 𝑘+1 ) < 𝑓(𝑥 𝑘 ), 𝑘 = 0, 1, 2, … даже в тех 32

случаях, когда для каких-либо значений матрица Гессе 𝐻(𝑥 𝑘 ) не окажется положительно определенной, рекомендуется для соответствующих значений 𝑘 вычислить точку 𝑥 𝑘+1 по методу градиентного спуска 𝑥 𝑘+1 = 𝑥 𝑘 − 𝑡𝑘 ∇𝑓(𝑥 𝑘 ) с выбором величины шага 𝑡𝑘 из условия 𝑓 (𝑥 𝑘 − 𝑡𝑘 ∇𝑓(𝑥 𝑘 )) < 𝑓(𝑥 𝑘 ) [1]. Построение последовательности {𝑥 𝑘 } заканчивается в точке 𝑥 𝑘 , для которой ‖∇𝑓(𝑥 𝑘 )‖ < 𝜀1 , где 𝜀1 − заданное малое положительное число, или 𝑘 ≥ 𝑀, где 𝑀 − предельное число итерации, или при двукратном одновременном выполнении двух неравенств: ‖𝑥 𝑘+1 − 𝑥 𝑘 ‖ < 𝜀2 и | 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 )| < 𝜀2 , где 𝜀2 − малое положительное число. Рис. 3.5 Схема решения задачи методом Ньютона: Этап 1. Задается 𝑥 0 , 𝜀1 > 0, 𝜀2 > 0, 𝑀 − предельное число итераций. Найти градиент функции ∇𝑓(𝑥) и матрицу Гессе 𝐻(𝑥). 33

Этап 2. Примем 𝑘 = 0. Этап 3. Вычислим ∇𝑓(𝑥 𝑘 ). Этап 4. Проверим выполнение условия окончания ‖∇𝑓(𝑥 𝑘 )‖ < 𝜀1 : 1) если условие выполнено, процесс поиска закончен, 𝑥 ∗ = 𝑥 𝑘 ; 2) если условие не выполнено, то перейдём к этапу 5. Этап 5. Проверим 𝑘 ≥ 𝑀: 1) если 𝑘 ≥ 𝑀, то процесс поиска окончен: 𝑥 ∗ = 𝑥 𝑘 ; 2) если 𝑘 < 𝑀, то перейдём к этапу 6. Этап 6. Вычислим элементы матрицы 𝐻(𝑥 𝑘 ). Этап 7. Вычислим обратную матрицу 𝐻−1 (𝑥 𝑘 ). Этап 8. Проверим выполнение условия 𝐻−1 (𝑥 𝑘 ) > 0: 1) если условие выполнено, то перейти к этапу 9; 2) если нет, то перейдём к этапу 10, положив 𝑑 𝑘 = −∇𝑓(𝑥 𝑘 ). Этап 9. Вычислим 𝑑 𝑘 = −𝐻−1 (𝑥 𝑘 )∇𝑓(𝑥 𝑘 ). Этап 10. Найти точку 𝑥 𝑘+1 = 𝑥 𝑘 + 𝑡𝑘 𝑑 𝑘 , положив 𝑡𝑘 = 1, если 𝑑 𝑘 = −𝐻 −1 (𝑥 𝑘 )∇𝑓(𝑥 𝑘 ), или выбрав 𝑡𝑘 из условия 𝑓(𝑥 𝑘+1 ) < 𝑓(𝑥 𝑘 ), если 𝑑 𝑘 = −∇𝑓(𝑥 𝑘 ) Этап 11. Проверим выполнение условий ‖𝑥 𝑘+1 − 𝑥 𝑘 ‖ < 𝜀2 и | 𝑓(𝑥 𝑘+1 ) − 𝑓(𝑥 𝑘 )| < 𝜀2 : 1) если одва условия выполнены при текущем значении 𝑘 и 𝑘 = 𝑘 − 1, то процесс поиска окончен, 𝑥 ∗ = 𝑥 𝑘+1 ; 2) если хотя бы одно из условий не выполнено, положим 𝑘 = 𝑘 + 1 и перейдём к этапу 3 [1]. 34

4. ТЕСТИРОВАНИЕ ПО И ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ Далее по приведенным выше алгоритмам было создано ПО с графическим пользовательским интерфейсом GUI MATLAB(см. на рис. 4.1 и на рис. 4.2). Рис. 4.1 Окно редактирования формы для методов минимизации функций одной переменной 35

Рис. 4.2 Окно редактирования формы для методов минимизации функций многих переменных Теперь будем рассмотривать такие главные компоненты, которые отображаются на выше интерфейсе формы (см. на рис. 4.1 и на рис. 4.2). 1) Одна кнопка, созданная в программе Рис. 4.3 Созданная кнопка в программе. Кнопка «Find» выполняет поиск минимизации функций и возвращает нахожденные результаты поставленной задачи. 2) Компонент «Static Text» для вывода названия. 3) Компонент «Edit» для выода результатов работы. 4) Область графика 36

Рис. 4.4 Область для отображения графика. Протестируем нахождение экстремума функции методом половинного деления. Задача 1: Найти минимум функции 𝑓(𝑥) = 2𝑥 2 − 12𝑥 методом половинного деления. 37

Рис. 4.5 Окно вывода нахождения минимума функции методом половинного деления Нажимаем на кнопку «Find», после этого полученные результаты отображают в области вывода: 𝑋𝑚𝑖𝑛 = 3.05, 𝐹𝑚𝑖𝑛 = −17.995, 𝐼 = 55 и график нарисован, как показано на рис. 4.6. Рис. 4.6 Окно вывода резултата Протестируем нахождение экстремума функции методом золотого сечения. Задача 2: Найти минимум функции 𝑓(𝑥) = 𝑥 4 + 2𝑥 2 + 4𝑥 + 1 методом золотого сечения. . 38

Рис. 4.7 Окно вывода нахождения минимума функции методом золотого сечения. Нажимаем на кнопку «Find», после этого полученные результаты отображают в области вывода: 𝑋𝑚𝑖𝑛 = −0.6828, 𝐹𝑚𝑖𝑛 = −0.5814, 𝐼 = 10 и график нарисован, как показано на рис. 4.8. Рис. 4.8 Окно вывода резултата 39

Протестируем нахождение экстремума функции градиентным методом. Задача 3: Найти локальный минимум функции 𝑓(𝑥) = 2𝑥1 2 + 𝑥1 𝑥2 + 𝑥2 2 градиентным методом. Рис. 4.9 Окно вывода нахождения минимума функции градиентным методом Нажимаем на кнопку «Find», после этого полученные результаты отображают в области вывода: 𝑋1𝑚𝑖𝑛 = −0.02171, 𝑋2𝑚𝑖𝑛 = 0.23807, 𝐹𝑚𝑖𝑛 = 0.0524515, 𝐼 = 5 и график нарисован, как показано на рис. 4.10. 40

Рис. 4.10 Окно вывода резултата Протестируем нахождение экстремума функции методом Ньютона. Задача 4: Найти локальный минимум функции 𝑓(𝑥) = 2(1 + 𝑥2 )3 + 3(𝑥1 − 1)2 методом Ньютона. Рис. 4.11 Окно вывода нахождения минимума функции методом Ньютона 41

Нажимаем на кнопку «Find», после этого полученные результаты отображают в области вывода: 𝑋1𝑚𝑖𝑛 = 1, 𝑋2𝑚𝑖𝑛 = −0.875, 𝐹𝑚𝑖𝑛 = 0.00390625, 𝐼 = 5 и график нарисован, как показано на рис. 4.12. Рис. 4.12 Окно вывода резултата 42

ЗАКЛЮЧЕНИЕ В выпускной квалификационной работе были получены следующие результаты:  изучена и определена общая задача;  исследованы характеристики различных численных методов;  составлен алгоритм различных численных методов;  исследованы возможности пакета программирования Matlab по решению экстремальных задач;  выполнены программные реализации алгоритмы различных численных методов с помощью обеспечением программы GUI MATLAB (Graphical User Interface - MatrixLaboratory) для нахождения экстремумов функции. Созданное ПО было протестировано на контрольных примерах, и может быть использовано для нахождения экстремумов функции. В ходе выполнения выпускной квалификационной работы были приобретены практические и теоретические знания и навыки в области математики, а также создания приложения. Таким образом, задачи, поставленные в выпускной квалификационной работе, были выполнены, а цель – достигнута. 43

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Методы оптимизации. Практический курс: учебное пособие с мультимедиа сопровождением / А.В. Пантелеева, Т.А. Летова. – М.: Логос, 2011. – 424 с: ил. 2. Васильева Ф. П. Численные методы решения экстремальных задач: Учеб. пособие для вузов – 2-е изд., перераб. И доп.- М.: Наук, Гл. ред. физ.-мат. лит., 1988-552 с.- ISBN 5-02-013796-0. 3. Аттетков А.В., Зарубин В.С., Канатников А.Н. Введение в методы оптимизации,- М.: Финансы и статистика, Инфра-М, 2008. 4. Киреев В.И., Пантелеев А.В. Численные методы в примерах и задачах. - М.: Высшая школа, 2008. 5. Ильин В. А., Садовничий В. А., Сендов Бл. X. Математический анализ. Начальный курс.— М.: Изд-во МГУ, 1985.— 660 с. 6. Карманов В.Г. Математическое программирование.— М.: Наука, 1986.— 288 с. 7. Ашманов С.А. Линейное программирование.— М.: Наука, 1981.— 8. 304 с. 9. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы.—М.: Наука, 1987.—600 с. 10.Габасов Р., Кириллова Ф.М. Методы оптимизации.— Минск: Изд-во Б ГУ, 1981.— 352 с. 11.Ильин В.А., Садовничий В.А., Сендов Бл.X. Математический анализ. Начальный курс.— М.: Изд-во МГУ, 1985.— 660 с. 12.Карманов В.Г. Математическое программирование.— М.: Наука, 1986.— 288 с. 13.Ляшенко И.Н., Карагодова Е.А., Черникова Н. В., Шор Н.3. Линейное и нелинейное программирование.— Киев: Вища школа, 1975.— 372 с. 14.Марчук Г.И. Методы вычислительной математики.— М.: Наука, 1980.— 536 с. 15.Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации.—М.: Наука, 1978.—352 с. 16.Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях,—М.: Высшая школа, 1986.— 287 с. 17.Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.— М.: Наука, 1975.— 320 с. 18.Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений.—М.: Наука, 1978.— 592 с. 44

19.Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.— М.: Наука, 1986.— 328 с. 20.Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач.— М.: Наука, 1986.— 288 с. 21.Абрамов Л.М., Капустин В.Ф. Математическое программирование.— Л.: Изд-во ЛГУ, 1981.—328 с. 22.Вилков А.В., Жидков Н.П., Щедрин Б.М. Метод отыскания глобального минимума функции одного переменного Ц Журн. вычислит. матем. и матем. физики.— 1975.— Т. 15, № 4.— С. 1040— 1042. 23.Воробьев Н.Н. Числа Фибоначчи.— М.: Наука, 1978.— 144 с. 24.Певный А.Б. Об оптимальных стратегиях поиска максимума функции с ограниченной старшей производной Ц Журн. вычисл. матем. и матем. физики.— 1982.— Т. 22, № 5.— С. 1061—1066. 25.Пиявский С.А. Один алгоритм отыскания абсолютного экстремума функции Ц Журн. вычисл. матем. и матем. физики.— 1972.— Т. 12, № 4.— С. 888—896. 26.Ильин В.А., Позняк Э.Г. Основы математического анализа.— М.: Наука, ч. I, 1971.— 600 с, ч. И, 1973.—448 с. 27.Никольский С.М. Курс математического анализа.— М.: Наука, 1973.— Т. 1.— 432 с. Т. 2.- 392 с. 28.Терёхин В.В. Т- Моделирование в системе MATLAB: Учебное пособие /Кемеровский государственный университет. – Новокузнецк: Кузбассвузиздат, 2004. -376с. 29.Си Шарп: Создание приложений для Windows.Мн.: Харвест, 2003. 384 с. 30.Фридман, А.Л. Язык программирования С++ / А.Л.Фридман. - М.: Бином, 2006. - 523с.: ил. 4. Лахатин, А.С. Языки программирования. Учеб. пособие / А.С. Лахатин, Л.Ю. Искакова. - Екатеринбург, 1998. 548с.: ил. 45

ПРИЛОЖЕНИЕ 1. Отдельный m-файл g1.m function F1 = g1( x) F1=2*x*x-12*x; End function pushbutton1_Callback(hObject, eventdata, handles) % hObject handle to pushbutton1 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) a=3; b=10; e=0.1; k=0; syms x; f=2*x.^2-12*x; while (b-a)> e k=k+1; u1=(a+b-e)/2; u2=(a+b+e)/2; f1=g1(u1); f2=g1(u2); if f1 < f2 b=u2; else a=u1; end xmin=(a+b)/2; fmin=g1(xmin); end x1=-1:0.01:8; [X1]=meshgrid(x1'); F=2*X1.^2-12*X1; plot(X1,F,'r',xmin,fmin,'b*'); set(handles.xmin,'string',xmin); set(handles.fmin,'string',fmin); set(handles.i,'string',k); 46

2. Отдельный m-файл g2.m function F2 = g2( x ) F2=x.^4+2*x.^2+4*x+1; end function pushbutton1_Callback(hObject, eventdata, handles) % hObject handle to pushbutton1 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) a=-1; b=0; e=0.01; k=0; syms x; f=x.^4+2*x.^2+4*x+1; u1=a+(3-sqrt(5))/2*(b-a); u2=a+b-u1; f1= g2(u1); f2= g2(u2); while (b-a)>e if f1<f2 b=u2; u2=u1; f2=f1; u1=a+(3-sqrt(5))/2*(b-a); f1= g2(u1); else a=u1; u1=u2; f1=f2; u2=a+b-u1; f2= g2(u2); end k=k+1; xmin=(a+b)/2; fmin=g2(xmin); end x1=-1:0.001:0; [X1]=meshgrid(x1'); F=X1.^4+2*X1.^2+4*X1+1; plot(X1,F,'r',xmin,fmin,'b*'); set(handles.xmin,'string',xmin); set(handles.fmin,'string',fmin); %set(handles.t,'string',Nsec); 47

set(handles.i,'string',k); 3. Отдельный m-файл g3.m function F3 = g3( x1,x2) F3=2*x1.^2+x1.*x2+x2.^2; end function pushbutton2_Callback(hObject, eventdata, handles) % hObject handle to pushbutton2 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) e1 = 0.1; e2 = 0.1; x0 = [1;1]; Kmax = 100; a1=-2; a2=2; b1=-2; b2=2; alf1=0.1; alf2=0.1; x1=[a1:alf1:a2]; x2=[b1:alf2:b2]; f = 2*x1.^2+x1.*x2+x2.^2; x=x0; Xm = x; t0=0.1; k = 0; i=1; while k < Kmax; k = k + 1; Gr = [4*x(1)+x(2); 2*x(2)+x(1)]; if sqrt(Gr(1).^2+Gr(2).^2)<e1 xmin=x; fmin=g3(xmin(1),xmin(2)); break; end if sqrt(Gr(1).^2+Gr(2).^2)>e1 h = -t0*Gr; f1=g3(x(1),x(2)); x1=x+h; f2= g3(x1(1),x1(2)); while f2-f1>0 t0=t0/2; 48

h = -t0*Gr; x1=x+h; f2_1= g3(x1(1),x1(2)); f2=f2_1; end if (f2-f1)<0&& sqrt(sum((x1-x).^2 ))<e1 && abs(f2-f1)< e2 xmin=x1; fmin=g3(xmin(1),xmin(2)); break; end end i = i + 1; Xm(:,i) = x1; x=x1; end x1=[a1:alf1:a2]; x2=[b1:alf2:b2]; [X1,X2] = meshgrid(x1', x2'); F = 2*X1.^2+X1.*X2+X2.^2 ; [C, h] = contour(X1, X2, F); clabel(C, h) hold on; plot(Xm(1,:), Xm(2,:), '-+'); text(Xm(1,1) + 0.1, Xm(2,1) + 0.1, 'M0'); plot(xmin(1),xmin(2), '*'); hold off set(handles.x1min,'string',xmin(1)); set(handles.x2min,'string',xmin(2)); set(handles.fmin,'string',fmin); set(handles.i,'string',i); 49

4. Отдельный m-файл g4.m function F4 = g4( x1,x2 ) F4=2*(1+x2).^3+3*(x1-1).^2 ; end function pushbutton2_Callback(hObject, eventdata, handles) % hObject handle to pushbutton2 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) e1=0.1; e2=0.1; K=100; k=0; i=1; x0=[1;1]; x1=-2:0.1:2; x2=-2:0.1:2; [X1,X2] = meshgrid(x1', x2'); F =2*(1+X2).^3+3*(X1-1).^2 ; x=x0; Xm= x; while k<K k = k + 1; Gr = [6*(x(1)-1); 6*(1+x(2)).^2]; if sqrt(Gr(1).^2+Gr(2).^2)<e1 xmin=x; fmin=g4(xmin(1),xmin(2)); break; end if sqrt(Gr(1).^2+Gr(2).^2)>e1 DFx1x1=6; DFx1x2=0; DFx2x1=0; DFx2x2=12*(x(2)+1); G1=zeros(2,2); G1(1,1)=DFx1x1(:); G1(1,2)=DFx1x2(:); G1(2,1)=DFx2x1(:); G1(2,2)=DFx2x2(:); H=inv(G1); if H(1,1)>0 && H(1,1)*H(2,2)-H(2,1)*H(1,2)> 0 d=-H*Gr; 50

t0=1; f1=g4(x(1),x(2)); x1=x+t0*d; f2= g4(x1(1),x1(2)); else d=-Gr; t0=0.5;% 0<t<2; f1=g4(x(1),x(2)); x1=x+t0*d; f2=g4(x1(1),x1(2)); end if sqrt(sum((x1-x).^2 ))<e1 && abs(f2-f1)< e2 xmin=x1; fmin=g4(xmin(1),xmin(2)); break; end end i = i + 1; Xm(:,i) = x1; x=x1; end y1=xmin(1); y2=xmin(2); x1=-2:0.1:2; x2=-2:0.1:2; [X1,X2] = meshgrid(x1', x2'); F = 2*(1+X2).^3+3*(X1-1).^2 ; [C, h] = contour(X1, X2, F); clabel(C, h) hold on; plot(Xm(1,:), Xm(2,:), '-+'); text(Xm(1,1) + 0.1, Xm(2,1) + 0.1, 'M0'); plot(xmin(1),xmin(2), '*k'); hold off set(handles.x1min,'string',y1); set(handles.x2min,'string',y2); set(handles.fmin,'string',fmin); set(handles.i,'string',i); 51

Выпускная квалификационная работа выполнена мной совершенно самостоятельно. Все использованные в работе материалы и концепции из опубликованной научной литературы и других источников имеют ссылки на них. «___» ________________ _____ г. __________________________ (подпись) __________________ (Ф.И.О.) 52

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв