Дипломная работа: Разработка компьютерного лабораторного практикума "Теория оптимизации и численные методы"

Введение

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

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

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

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

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

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

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

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

В направлении информатизации сферы образования работают сейчас практически все гуманитарные и технические учебные заведения разных стран. Разработки в этом направлении ведутся и в Московском авиационном институте. Кафедра «Математическая кибернетика» факультета «Прикладная математика и физика» института в течении многих лет разрабатывает учебные материалы с использованием компьютерных технологий. За это время создан комплекс компьютерных пособий и учебников, охватывающих предметы, читаемые преподавателями кафедры. Комплекс, включающий в себя более 70 компьютерных учебников, поддерживает 8 разделов курса "Теория управления", 7 разделов курса "Системный анализ", 3 раздела курса "Линейная алгебра и аналитическая геометрия", а также курсы "Теория графов", "Теория функций комплексного переменного", "Линейное программирование", "Линейные дифференциальные уравнения" и другие. Также функционирует кафедральных сайт в интернете, позволяющий студентам и преподавателям института обмениваться информацией дистанционно. В настоящее время на кафедре ведется работа по созданию других средств обучения с применением информационных технологий.

Кафедра «Математическая кибернетика» факультета «Прикладная математика и физика» института читает студентам курс «Методы оптимизации», изучающий методы оптимизации математических функций. На кафедре был создан практикум по этому курсу в среде Microsoft DOS, позволяющий студентам изучать методы на примерах, работая за компьютером в терминальном классе. В рамках дипломного проекта поставлена задача создания аналогичного практикума, работающего в сетевом режиме с целью упростить проведение работ. Также требуется расширить функционал имеющегося практикума для достижения большей наглядности примеров.

В рамках дипломного проекта требуется:

l   Изучить описываемые методы оптимизации и составить документацию по ним в мультимедийной форме.

l  Разработать архитектуру практикума

l  Разработать пользовательский интерфейс

l  Выбрать программные средства для разработки и составить алгоритмы

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

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

Раздел 3 содержит расчет экономических показателей, связанных с выполнением дипломного проекта.

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

1. Теоретическая часть

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

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

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

·     квадратичной функции 2-х переменных:

·          овражной функции

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

 1.1     Методы, реализованные в лабораторном практикуме

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

где

u  - текущая точка последовательности, причем – задается из физического содержания задачи или произвольно;

u   - последующая точка последовательности;

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

u  - шаг (число >0),

и отличаются друг от друга способом задания и выбором .

Алгоритм работы прямых методов схематически изображен на рис. 1.1

Рисунок 1.1. Алгоритм работы прямых методов

В практикуме реализованы:

l   методы первого порядка, использующие информацию о 1-х производных функции :

·     метод градиентного спуска;

·     метод наискорейшего градиентного спуска;

·     метод покоординатного спуска;

·     метод Гаусса-Зейделя;

·     метод сопряженных градиентов.

l   методы второго порядка, использующие для своей реализации информацию о 1-х и 2-х производных функции :

·     метод Ньютона;

·     метод Ньютона-Рафсона;

·     метод Марквардта

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

В практикуме реализованы следующие методы нулевого порядка:

·     метод случайного поиска

·     метод деформируемого многогранника

·     метод конфигураций

 1.1.1             Метод градиентного спуска

Алгоритм метода:

,

здесь:

o     - направление антиградиента функции;

o     - шаг выбирается из условия убывания функции в точках последовательности  

Геометрическая интерпретация метода:

Рисунок 1.2. Геометрическая интерпретация метода

Основной критерий окончания метода:

Построение последовательности заканчивается в точке, для которой

где - заданное малое положительное число, здесь

Начальные параметры метода: .

Изменяемый параметр метода: величина шага .

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

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

 1.1.2             Метод градиентного наискорейшего спуска

Алгоритм метода:

,

здесь

·    - направление антиградиента функции

·   - шаг вычисляется из условия наибольшего убывания функции в точках последовательности:

·  

Геометрическая интерпретация метода

Рисунок 1.3. Геометрическая интерпретация метода

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

Основной критерий окончания метода:

Начальные параметры метода:

Изменяемые параметры метода: отрезок для уточнения шага .

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

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

Проиллюстрируем ситуацию, при которой шаг  вычисляется численно методом дихотомии. Для этого построим график функции , которая в случае если  является квадратичной функцией, имеет вид:

Рисунок 1.4 Метод дихотомии

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

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

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

 1.1.3             Метод покоординатного спуска

Алгоритм метода:

здесь:

·           - проекция на ось  антиградиента функции

·           - шаг выбирается из условия убывания функции в точках последовательности:

Геометрическая интерпретация метода

Рисунок 1.5. Геометрическая интерпретация метода

Основной критерий окончания метода:

Начальные параметры метода:

Изменяемые параметры метода: величина шага  и направление проекции антиградиента (здесь абсциссы – ось , ординаты – ось )

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

 1.1.4             Метод Гаусса-Зейделя (наискорейшего покоординатного спуска)

Алгоритм метода:

здесь:

- проекция на ось  антиградиента функции

·          - шаг вычисляется из условия наибольшего убывания функции в точках последовательности:

Геометрическая интерпретация метода

Рисунок 1.6. Геометрическая интерпретация метода

Основной критерий окончания метода:

Начальные параметры метода: .

Изменяемые параметры метода: отрезок для уточнения шага .

Особенности реализации алгоритма. Задача о поиске оптимального шага  (задача ) решается численно методом дихотомии на отрезке  с заданной точностью .  Вопрос о границах отрезка   на каждой итерации решается пользователем. Направление проекции градиента меняется циклически: сначала спуск в направлении оси абсцисс, затем – ординат и т.д.

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

 1.1.5             Метод сопряженных градиентов

Алгоритм метода:

здесь:

·         

·         

·         

·          - шаг вычисляется из условия наибольшего убывания функции в точках последовательности:

Геометрическая интерпретация метода

Рисунок 1.7. Геометрическая интерпретация метода

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

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