Применение метода Зейделя-Гаусса к квадратичным функциям

Аппроксимация квадратичными функциями гораздо более распространена. Пусть задана квадратичная функция (3): , которая является, как было показано ранее, выпуклой функцией с минимумом в точке . Возьмем начальную точку х⁰=(1, 1) (это можно считать начальной локализацией). Зафиксируем и найдем экстремум по координате х₂ из уравнения: , , .

Далее фиксируем и отыскиваем экстремум по х₁, , , . Как видно за одну итерацию, содержащую два шага, экстремум не найден.

Делаем следующий шаг из точки х₁, , , , . Следующий шаг из дает . Закончена вторая итерация. Продолжая вычисления, получим точку , т.е. последовательность сходится к экстремальной точке. Теперь встает вопрос, когда закончить вычисления? Т.к. метод З-Г сходится, то вычисления можно прервать на любой итерации. Обычно задают некоторую малую величину e, по координатам или d по значению функции. Вычисления заканчиваются тогда, когда разница между значениями координат (или функции) на текущей и на предыдущей итерациях станет меньше или равна данной величине e или d. Метод З-Г достаточно прост, но имеет малую скорость сходимости, т.к. на каждой итерации в общем случае надо делать n шагов при несепарабельных функциях.

Градиентные методы.

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

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

Пусть задана сепарабельная функция и начальная точка х⁰=(–0,6;–2,6), у⁰=4,68. Вычислим в точке х⁰ проекции градиента:

Построим на графике линий равного уровня проекции градиента в определенном масштабе и результирующий вектор L₁, который дает направление наибольшего изменения функции в точке х⁰. Если провести через L₁ плоскость, перпендикулярную {x₁, x₂}, то эта плоскость, рассекая поверхность , выделит на ней параболу. Теперь надо найти точку экстремума полученной параболы. Для этого следует записать уравнение параболы в данной плоскости (плоскости градиента) с помощью параметра m, учитывающего направление антиградиента:

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

Определим параметр m исходя из экстремума функции :

,

Теперь определим координаты точки х⁽¹⁾, в которой функция по направлению L₁ достигает экстремума.

,

,

Значение функции в этой точке: у⁽¹⁾=1,3. Полученная точка х⁽¹⁾ по направлению L₁ показана на рисунке. Линия градиента касается в этой точке линии равного уровня функции у.

Продолжая вычисления, а именно: 1) определяя проекции градиента, 2) составляя уравнения параболы в плоскости градиента , 3) находя параметр m из условия экстремума функции , 4) определяя координаты точки х⁽²⁾, в которой функция по направлению градиента достигает экстремум, получим следующие результаты:

Итерация
х	(-0,6;2,6)	(-0,08;1,82)	(0,48;2,19)	(0,65;1,94)	(0,83;2,06)	(0,89;1,98)
у	4,68	1,3	0,41	0,14	0,043	0,014

В математике доказывается, что метод наискорейшего спуска сходится. Значит, вычисления можно прервать на любом шаге, если выполнена заданная точность. Например, если задана точность по значениям функции у на смежных шагах d£0,05. Тогда разность на 4 и 5 итерациях , следовательно, на пятой итерации вычисления можно закончить.

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

Пусть дано квадратичное уравнение в матричной форме:

,

которое запишем в развернутой форме через матрицу Н и С:

Запишем градиент функции у:

Возьмем теперь любое направление S с проекциями S₁ и S₂ и составим для этого направления уравнение экстремальной линии через параметр m для любой точки (х₁, х₂):

Раскрыв скобки и продифференцировав по m, получим:

Отсюда определяем m из условия экстремума по m:

Нетрудно заметить, что данное выражение можно переписать так:

,

что соответствует матричной записи:

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

, или:

, (6)

В общем виде, для функции многих переменных:

Покажем, насколько упростилась процедура определения m для квадратичной функции . Зададимся начальной точкой с координатами .

Определим проекции градиента в точке х⁰:

На рисунке показаны линии уровня и проекции градиента. Определяем m по (6):

Координаты экстремальной точки по L₁:

;

Далее вычисляются проекции градиента во вновь найденной точке :

, и строится направление L₂. Затем вычисляется m для второй итерации по (6): .

Координаты экстремальной точки по направлению L₂:

Как видно, за две итерации методом наискорейшего спуска была достигнута малая окрестность экстремума функции. В этом и состоит основное преимущество данного метода над методом Зейделя-Гаусса.

Градиентные методы с заданием параметра шага m

Для поиска экстремума функций с большим числом переменных метод наискорейшего спуска становится трудоемким (если не применять ЭВМ). Поэтому был предложен ряд его модификаций.

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

, где n=1,2… – номер итерации, К – коэффициент.

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

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

Выбираем m в виде последовательности , причем К берем близким к m⁰, пусть К=0,2.

Тогда на первой итерации m⁰=0,2.

На второй итерации при и проекциях градиентов в точке х⁽¹⁾

получим:

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