Тогда, воспользовавшись (1) и (2):

     

     Если  , то градиент в точке перпендикулярен градиенту в точке , тогда по правилам скалярного произведения векторов:

     

     Приняв  во внимание последнее, получим из выражения (4) окончательную формулу для вычисления :

     

     [править] К-я итерация

     На k-й итерации имеем набор .

     Тогда следующее направление вычисляется  по формуле:

     

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

     Это выражение может быть переписано в более удобном итеративном  виде:

     

     Алгоритм

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

     Формализация

1. Задаются  начальным приближением и погрешностью:
2. Рассчитывают начальное направление:

     

• Если  или , то и останов.
• Иначе если , то и переход к 3; иначе и переход к 2.

1.5 Метод Ньютона

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

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

Обоснование

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

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

     В предположении, что точка приближения  «достаточно близка» к корню  , и что заданная функция непрерывна , окончательная формула для такова:

     С учётом этого функция определяется выражением:

     Эта функция в окрестности корня  осуществляет сжимающее отображение^[1], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню уравнения .

     

 

     Рисунок 1 - Иллюстрация метода Ньютона (синим  изображена функция 

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

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

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

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

     

     где α — угол наклона касательной в точке .

     Следовательно искомое выражение для  имеет вид:

     

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

     Алгоритм

1. Задается  начальное приближение x₀.
2. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .

2. Решение задачи  в Mathcad 14

2.1 Первый способ - Сопряженный градиент

Начальное приближение

Функция Minimize ищет минимум  Функции методом сопряженного градиента

Функция Minimize ищет минимум  Функции методом сопряженного градиента

 
 
 
 
 
 
 
 
 
 
 
 
 

 

 
     

 
 
 

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

  Х=4.585, У=5.654 дают минимум затрат R=23890

2.2 Второй способ - Квази-Ньютон

При разных дополнительных параметрах. Результат одинаков

Дает такой же ответ 

 
     

 
 
 

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

  Х=4.585, У=5.654 дают минимум затрат R=23890

Заключение

     Были  рассмотрены градиентные методы нахождения экстремумов функции :

1. Метод Ньютона,
2. Сопряженных градиентов,
3. Покоординатного спуска (Гаусса—Зейделя),
4. Скорейшего спуска( метод градиента)

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

  Х=4.585, У=5.654 дают минимум затрат R=23890

 

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

1. Акулич  И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
7. http://ru.wikipedia.org