Поиск максимума одной функции многих переменных методом покоординатного спуска и с помощью метода дихотомии

Реферат

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

Пояснительная записка к курсовой работе состоит из двух основных частей: теоретической и практической.

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

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

Объем пояснительной записки: 1

Количество рисунков: 3

Количество используемых источников: 3

Содержание

Введение

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

2. Решение задачи с использованием метода дихотомии

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

2.2 Алгоритм решения

3. Решение задачи с использованием метода покоординатного спуска

3.1 Описание метода покоординатного спуска

3.2 Алгоритм решения

Заключение

Список используемой литературы

Приложение 1. Листинг программы№1

Приложение 2. Листинг программы №2

Приложение 3. Листинг программы №3

Приложение 4. Результаты работы программы №1

Приложение 5. Результаты работы программы №3

Введение

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

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

Исходная функция имеет вид:

, где:

xiR –– параметры исходной функции;

p, qR –– некоторые параметры удовлетворяющие условию 1<pq<∞;

с=c(x1…xn) –– вспомогательная функция, записанная в неявном виде

→min.

Задача:

Найти xi*, : f(x1*…xn*)=f(x1…xn).

Выполним следующую замену: xi=axi+b, . При этом значение функции не изменится:

Таким образом, исходную область определения функции можно сузить до xiR[0;1]. Так как знаменатель не должен быть равным нулю, то xi≠xj i≠j. Но тогда все параметры можно расположить по возрастанию: x1x2…xixi+1…xn, а выбором a и b можно привести x1=0, xn=1.

Далее будем рассматривать задачу от n-2 переменных, т.к. x1 и xn являются константами.

2. Решение задачи с использованием метода дихотомии

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

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

Пусть f(x)=0 (1)

Где f(x) определена и непрерывна в некотором конечном и бесконечном интервале a<x<b. Требуется найти все или некоторые корни уравнения (1).Всякое значение , обращающее функцию f(x) в нуль, называется корнем уравнения (1). Поставленная задача распадается на несколько этапов:

1. Отделение корней, т.е. установление возможно более тесных промежутков [,], в которых содержится только по одному корню.

Нахождение приближенных (грубых) значений корней.

Вычисление корней с требуемой точностью.

Первая и вторая задача решаются аналитическими и графическими методами.

Отделение корней

Если уравнение f(x) = 0 имеет только действительные корни, то полезно составить таблицу значений функции f(x).Если в двух соседних точках и функция имеет разные знаки, то между этими точками лежит по меньшей мере один корень. Корень будет заведомо единственным, если определена на отрезке [,] и сохраняет постоянный знак.

Графические методы

Действительные корни уравнения f(x) = 0 приближенно можно определить как абсциссы точек пересечения графика функции f(x) с осью x.

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

Метод дихотомии

Дихотомия означает деление пополам. Пусть нашли такие точки и , что < 0, т.е. на [,] лежит по меньшей мере один корень. Найдем середину отрезка [,]. Получаем . Если f(x2) = 0, то если f()0, то из двух половин отрезка выберем ту, для которой выполняется условие < 0, т.к. корень лежит на этой половине. Затем вновь делим выбранный отрезок пополам и выбираем ту половину, на концах которой функция имеет разные знаки.

Если требуется найти корень с точностью , то продолжим деление пополам (если конечно функция в середине какого-либо отрезка не обращается в нуль), пока длина очередного отрезка не станет < 2. Тогда середина последующего отрезка установит значение с требуемой точностью. Метод дихотомии прост и очень надежен. Он сходится для любых непрерывных функций f(x), в том числе не дифференцируемых.

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

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

2.2 Алгоритм решения

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

Затем будем находить значение функции с() методом дихотомии.

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

Найдем корень этого нелинейного уравнения методом дихотомии.

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

Перебирая все xi, найдем максимум функции.

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

3. Решение задачи с использованием метода покоординатного спуска

3.1 Описание метода покоординатного спуска

Изложим этот метод на примере функции трех переменных .

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

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

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

Это зависит от функции и выбора нулевого приближения.

Метод спуска по координатам несложен и легко программируется на ЭВМ. Но сходится он медленно. Поэтому его используют в качестве первой попытки при нахождении минимума.

3.2 Алгоритм решения

Будем перебирать с с шагом какой-либо малой длины.

Зададим нулевое приближение, например:

Найдем частные производные .

Пусть при каком-то j

Тогда k-ое приближение считаем по формулам:

Шаг t