Выбор оптимального места строительства очистного сооружения (стр. 2 из 3)
Введём на
целевую функцию 
.Вектора
называются сопряжёнными, если:·
·
где
— матрица Гессе 
. | Теорема (о существовании). Существует хотя бы одна система  сопряжённых направлений для матрицы , т.к. сама матрица (её собственные вектора) представляет собой такую систему. |
1.4.1 Обоснование метода
Нулевая итерация
Рисунок 2 - Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) к точке экстремума.
Пусть
Тогда
.Определим направление
так, чтобы оно было сопряжено с 
: 
Разложим
в окрестности 
и подставим 
: 
Транспонируем полученное выражение и домножаем на
справа: 
В силу непрерывности вторых частных производных
. Тогда: 
Подставим полученное выражение в (3):
Тогда, воспользовавшись (1) и (2):
Если
, то градиент в точке 
перпендикулярен градиенту в точке , тогда по правилам скалярного произведения векторов: 
Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления
: 
[править]К-я итерация
На k-й итерации имеем набор
.Тогда следующее направление вычисляется по формуле:
где
непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.Это выражение может быть переписано в более удобном итеративном виде:
Алгоритм
· Пусть
— начальная точка, 
— направление антиградиента и мы пытаемся найти минимум функции . Положим 
и найдем минимум вдоль направления 
. Обозначим точку минимума 
.· Пусть на некотором шаге мы находимся в точке
, и 
— направление антиградиента. Положим 
, где выбирают либо 
(стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с 
), либо 
(алгоритм Полака–Райбера). После чего найдем минимум в направлении 
и обозначим точку минимума 
. Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив 
и повторив шаг.Формализация
1. Задаются начальным приближением и погрешностью:
2. Рассчитывают начальное направление:
3.
o Если
или 
, то 
и останов.o Иначе если
, то 
и переход к 3; иначе 
и переход к 2.1.5 Метод Ньютона
Метод Ньютона является градиентным методом поиска минимума функции нескольких переменных, использующим информацию о первых и вторых производных функции. На основе квадратичной аппроксимации функции формируется последовательность итераций таким образом, чтобы во вновь получаемой точке градиент аппроксимирующей функции обращался в нуль.
Метод Ньютона определяет направление эффективного поиска в окрестности точки минимума, но не обладает свойством убывания функции от итерации к итерации. Однако в случае положительной определенности матрицы Гессе направление по методу Ньютона оказывается направлением спуска.
Обоснование
Чтобы численно решить уравнение
методом простой итерации, его необходимо привести к следующей форме: 
, где 
— сжимающее отображение.Для наилучшей сходимости метода в точке очередного приближения
должно выполняться условие 
. Решение данного уравнения ищут в виде 
, тогда: 
В предположении, что точка приближения «достаточно близка» к корню
, и что заданная функция непрерывна 
, окончательная формула для 
такова: 
С учётом этого функция
определяется выражением: 
Эта функция в окрестности корня осуществляет сжимающее отображение[1], и алгоритм нахождения численного решения уравнения
сводится к итерационной процедуре вычисления: