Алгоритмы вычислительной математики

Размещено на http://www.allbest.ru/

Тема работы

«Алгоритмы вычислительной математики»

1. Метод гиперплоскостей для построения выпуклой области, множество неупорядоченных элементов

алгоритм нелинейное уравнение функция неопределенность

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

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

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

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

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

Выбираем произвольным образом первые (N+I) граничные точки и строим по ним (N+1) гиперплоскости. Для каждой построенной гиперплоскости запоминаются координаты граничных точек, по которым она построена, и координаты ее вершины.

В декартовой системе координат строим четыре точки 1,2,3,4 по осям Х1 и Х2, с координатами точки 1 (5,10), точки 2(7,3), точки 3(9,7), 4(10,13).

Узнаем, работоспособен ли объект с параметрами Х.

Берём исходное множество:

Вершиной данной гиперплоскости условимся называть ту точку из выбранных (N+1) точек, через которую не проводится гиперплоскость.

Берем точки 1,2,3, проводим прямые 1-2, 2-3, 3-1.

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

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

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

Берем точку 4 и для нее ищем генеральную гиперплоскость.

Предполагаем, что для точки 4 главная гиперплоскость будет 1-3.

Для точки 4 генеральная гиперплоскость 1-3

После удаляем генеральную гиперплоскость и плоскость повторяющуюся. Удаляем генеральную 1-3.

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

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

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

Знаки неравенств и определяются в результате подстановки координат вершин гиперплоскости в уравнение гиперплоскости. При этом используется свойство вершин принадлежать области работоспособности. Символ соответствует отрицательному знаку результата подстановки, символ - положительному. Для удобства использования результатов построения области работоспособности все неравенства приводятся к виду 0.

Построение гиперплоскости через заданные N граничных точек.

Эта процедура занимает центральное место в данном алгоритме. Коэффициенты гиперплоскости (неравенства) определяются в результате решения системы линейных алгебраических уравнений (N + 1)-го порядка. Систему получают в результате составления уравнений гиперплоскостей, записав вместо переменных координаты N точек, через которые необходимо провести гиперплоскость:

--------------------------------

.

Так как количество неизвестных коэффициентов (N+I), то необходимо одному из них задать произвольное значение, например a = 1. Однако в этом случае невозможно построить гиперплоскость параллельную оси координат X.

Аналогично, если присвоить значение другому коэффициенту b = 1 уравнений (1), то предлагаемый подход будет неприменим для построения гиперплоскостей, параллельных соответствующим осям координат, а при задании k 0 - для построения гиперплоскостей, проходящих через начало координат.

С целью устранения второго недостатка вводятся (N+1)-я переменная Z и дополнительная точка. Тогда построение гиперплоскости осуществляется в (N+1)-м пространстве, а произвольное значение присваивается коэффициенту при переменной Z. Координаты дополнительной точки необходимо выбирать такими, чтобы ни одна из гиперплоскостей не была параллельна оси координат (N+1)- й переменной Z. Это требование выполняется, если значение хотя бы одной из координат дополнительной точки (не считая координаты по оси Z) меньше минимального или больше максимального значения соответствующей координаты множества граничных точек. Значения остальных координат задаются произвольно.

В результате решения системы (N+1)-го порядка определяются значения коэффициентов (N+1)-й гиперплоскости. Исключение из уравнений гиперплоскостей дополнительной переменной позволяет получить уравнение плоскости в N-мерном пространстве.

То есть берём n+1 точку в многомерном пространстве , где через каждое n точек проводится гиперплоскость, и ставится произвольная точка 5 (0,11,1) , точка 6 (0,8,1) , точка 7 (0,11,1) .

Уравнение плоскости имеет вид aX1+bX2+гZ+C=0.

2. Решение нелинейных уравнений на основе метода минимизации функций многих переменных

2.1 Формирование нелинейной функции многих переменных

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

Ф = Ф(X1,X2,…,Xn). (1)

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

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

Будем считать набор численных значений X1,X2,…,Xn координатами некоторой точки n-мерного пространства, которую можно представить вектором . Для такой точки можно подсчитать значения функции . Выделим из совокупности точек n-мерного пространства те точки, которым соответствуют равные значения функции , где Ф0 - некоторое численное значение. Геометрическое место точек с равными значениями функции называют поверхностью равного уровня. Изменив уровень Ф0 функции, получим другую поверхность равного уровня, причем различные поверхности равных уровней вложены одна в другую, но нигде не соприкасаются. Отсутствие общих точек у этих поверхностей непосредственно следует из свойства однозначности функции.

Градиентом функции будем называть вектор

, (2)

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

Исходные данные: начальная точка поиска ; градиент функции ; градиент функции в начальной точке нормируется по уравнению , где ; ; начальная матрица nЧn, равная единичной матрице, H(1,1) = E[1,1]; е - коэффициент, задающий точность одномерного поиска; Д - точность поиска минимума функции.

1. Вычисляем вектор направления . (3)

2. Формируем вектор (4)

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

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

3. Вычисляем градиент и приращение градиента

. (5)

4. Находим новую матрицу Н по рекуррентной формуле

. (6)

5. Переходим на этап 1 с новыми начальными условиями.

Отметим некоторые вычислительные особенности метода ДФП. Метод подвержен накоплению ошибок, вследствие чего рекомендуется время от времени «забывать» накопленную информацию и начинать вычислительный процесс заново. Для этого необходимо предусмотреть «обновление» расчетов. Оно заключается в замене с некоторой периодичностью (обычно через n или 2n итераций) текущей матрицы Н единичной матрицей Е. При обновлении на каждой итерации метод ДФП превращается в метод наискорейшего спуска.

При расчете на ЭВМ первая производная функции по некоторому параметру Xi заменяется первой разделенной разностью

, (7)

где X1, Xi, Xn - координаты точки , в которой вычисляется производная.

Для метода ДФП рассматриваются 2 варианта реализации, которые различаются только методами одномерного поиска. В первом варианте применяется метод золотого сечения, во втором - квадратичная аппроксимация. Рассмотрим кратко эти методы.

2.2 Сокращение интервала неопределенности методом золотого сечения

Название метода указывает на его связь с золотым делением отрезка, т.е. таким делением отрезка на две неравные части X и Y (X>Y), при котором , где .

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

; б-1 = 0; б0 = 1, (8)

если при этом происходит убывание функции.

На рис. 1 изображена последовательность точек б0, б1, б2 , полученная согласно алгоритму (8).

Рис. 1. Последовательность точек б

Из рис.1 видно, что интервал неопределенности лежит между точками б0 и б2. Выберем новую точку б3 так, чтобы получить золотое сечение интервала неопределенности (рис. 2).

Рис. 2. Сокращение интервала неопределенности

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

, (9)

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

2.3 Сокращение интервала неопределенности методом квадратичной аппроксимации

В основе метода лежит аппроксимация функции Ф() квадратичным полиномом. Для ускорения поиска на этапе выделения интервала неопределенности необходимо ввести, как и ранее, переменный шаг i в (4):

; (10)

0 = 1, если при этом происходит убывание функции, -1 = 0, - коэффициент, численное значение которого в начале одномерного поиска равно нулю, а затем возрастает на 1 через каждые R шагов. Пусть произведены измерения функции в точках 0, 1, 2 согласно алгоритму . Интервал неопределенности лежит между точками 0 и 2 (рис. 1). Для сокращения интервала заменяем реальную функцию Ф() аппроксимирующей функцией Фапр(), которая проходит через те же точки 0, 1, 2, Фапр()=a2+b+c и имеет координату минимума опт= - b/(2a). Связывая неизвестные коэффициенты a, b, c со значениями 0, 1, 2 и Ф(0), Ф(1), Ф(2) получаем расчетную формулу:

. (11)

Причем точка 3=опт (рис. 2) попадает внутрь интервала неопределенности 2 - 0.

Новый интервал неопределенности уменьшился и стал равным 2 - 1. Вычислительный процесс сокращения интервала необходимо продолжить, пока не будет выполнено условие одномерного поиска (9).

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

,

где H - симметричная и положительно определенная матрица вторых частных и смешанных производных (матрица Гессе, или гессиан), с - постоянный вектор, b - константа.

Оптимальное решение приведенной задачи соответствует нулевым значениям первых производных, то есть

, откуда .

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

Среди подобных алгоритмов одним из наиболее популярных и используемых в пакете Optimization Toolbox является так называемый BFGS-алгоритм, получивший свое название по фамилиям предложивших его авторов (Broyden, Fletcher, Goldfarb, Shanoo), в котором аппроксимация Н производится итерационно, по формуле

, где , .

Заметим, что наиболее удобно иметь аппроксимацию не матрицы Н, а обратной к ней матрицы Н-1, приведенное рекуррентное соотношение подобную замену допускает, при этом сам алгоритм становится практически идентичным хорошо известному отечественным исследователям алгоритму Давидона-Флетчера-Пауэлла, за тем исключением, что в последнем векторы q заменены на векторы s и наоборот.

Именно такие алгоритмы являются основой численных методов, заложенных в распространенные математические пакеты прикладных программ (MS Excel, Mathcad, Mathlab).

Блок-схема алгоритма минимизации функции многих переменных метода Давидона-Флетчера-Пауэлла приведена на рис. 3.

Размещено на http://www.allbest.ru/

Рис. 3. Блок-схема алгоритма минимизации функции

2.4 Минимизация многомерной функции при наличии линейных ограничений на основе метода Давидона-Флетчера-Пауэлла

.

Имеются ограничения:

.

Ранее (без ограничений) матрица была единичной, теперь она рассчитывается по формуле:

Размещено на Allbest.ru