Метод Гаусса - Зейделя

В данном методе требуется построить последовательность точек , таких, что

.

Точку задаёт пользователь. Остальные точки последовательности вычисляются по правилу:

, (6)

где j = 0, 1, 2, … - номер цикла вычислений; k = 0, 1, …, n -1 – номер итерации внутри цикла; - единичный вектор, у которого (k + 1)-я проекция равна 1.

Величина шага определяется из условия

.

Решение этой задачи одномерной минимизации можно осуществить либо из условия , либо численно, с использованием методов одномерной минимизации, когда решается задача

.

Если уравнение имеет высокую степень и у него трудно определить корни, то можно аппроксимировать функцию полиномом второй или третьей степени и определить из условий

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

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

Если функция удовлетворяет условиям теоремы 1, то построение последовательности по методу покоординатного спуска обеспечивает выполнение условия .

Алгоритм:

Шаг 1. Задать: начальную точку -малые положительные числа, M – предельное число циклов счета, кратное n, где n – размерность вектора x. Найти градиент .

Шаг 2. Задать номер цикла j =0.

Шаг 3. Проверить условие :

а) если условие выполняется, , расчет окончен;

б) если нет, то перейти к шагу 4.

Шаг 4. Задать k = 0.

Шаг 5. Проверить условие :

а) если , то перейти к шагу 6;

б) если , то положить j = j + 1 и перейти к шагу 3.

Шаг 6. Вычислить .

Шаг 7. Проверить выполнение критерия окончания :

а) если критерий выполняется, , расчет окончен;

б) если нет, то перейти к шагу 8.

Шаг 8. Вычислить из условия

.

Шаг 9. Вычислить

.

Шаг 10. Проверить выполнение условий

:

а) если выполняются оба условия в двух последовательных циклах с номерами j и j - 1, то расчет окончен, найдена точка ;

б) если не выполняется хотя бы одно из условий, то положить k = k + 1 и перейти к шагу 5.

Геометрическая интерпретация метода для n = 2 приведена на рисунке 4.5.

Рисунок 4.5.

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

Решение:

1. Зададим , M: , , M =10.

Найдем градиент функции в произвольной точке

2. Зададим j = 0.

3⁰. Проверим выполнение условия : j = 0 < 10 = M.

4⁰. Зададим k = 0.

5⁰. Проверим выполнение условия : k = 0 < 1 = n – 1.

6⁰. Вычислим : .

7⁰. Проверим условие : .

8⁰. Определим величину шага из условия

.

Воспользуемся формулой ( 6 ) при k = 0, j = 0:

Поскольку , то или . Подставляя полученные выражения в , имеем .

Из необходимого условия экстремума или находим . Т.к. , то найденное значение шага обеспечивает минимум функции по .

9⁰. Определим .

10⁰. Проверим условия :

.

Полагаем k = 1 и переходим к шагу 5.

5¹. Проверим выполнение условия : k = 1 = n – 1.

6¹. Вычислим : .

7¹. Проверим условие : .

8¹. Определим величину шага из условия

.

Воспользуемся формулой ( 6 ) при k = 1, j = 1:

Поскольку , то или . Подставляя полученные выражения в , имеем .

Из необходимого условия экстремума или находим . Т.к. , то найденное значение шага обеспечивает минимум функции по .

9¹. Определим .

10¹. Проверим условия :

.

Полагаем k = 2 и переходим к шагу 5.

5². Проверим выполнение условия : k = 2 > n – 1.

Зададим , переходим к шагу 3.

3¹. Проверим выполнение условия : j = 1 < 10 = M.

4¹. Зададим k = 0.

5³. Проверим выполнение условия : k = 0 < 1 = n – 1.

6³. Вычислим : .

7³. Проверим условие : .

8³. Зададим (см. п. 8⁰).

9³. Вычислим

10³. Проверим условия :

.

Полагаем k = 1 и переходим к шагу 5.

5⁴. Проверим выполнение условия : k = 1 = n – 1.

6⁴. Вычислим : .

7⁴. Проверим условие : .

8⁴. Зададим (см. п. 8¹).

9⁴. Вычислим

10⁴. Проверим условия :

.

Полагаем k = 2 и переходим к шагу 5.

5⁵. Проверим выполнение условия : k = 2 > n – 1.

Зададим , переходим к шагу 3.

3². Проверим выполнение условия : j = 2 < 10 = M.

4². Зададим k = 0.

5⁶. Проверим выполнение условия : k = 0 < 1 = n – 1.

6⁵. Вычислим : .

7⁵. Проверим условие : .

8⁵. Зададим (см. п. 8⁰).

9⁵. Вычислим

10⁵. Проверим условия :

.

Условия выполнены в двух последовательных циклах с номерами j = 2 и j - 1= 1. Расчет окончен, найдена точка .

Функция строго выпукла, имеет единственный минимум в точке . Решение задачи представлено на рисунке 4.6.

Рисунок 4.6.

4.4 Метод сопряженных градиентов (Флетчера – Ривса)

Данный метод также получил название метода сопряженных градиентов.

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

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

.

Точку задаёт пользователь. Остальные точки последовательности вычисляются по правилу:

,

,

,

а числа выбираются из условия

.

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

.

Величина шага определяется для каждого значения k из условия

. (7)

Решение этой задачи одномерной минимизации можно осуществить либо из условия , либо численно, с использованием методов одномерной минимизации, когда решается задача

.

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

Если функция - квадратичная с положительно определенной матрицей Гессе (H >0), то метод Флетчера-Ривса является конечным и сходится не более, чем за n шагов (где n – размерность вектора x).

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

где .

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

Теорема 3 Если квадратичная функция с неотрицательно определенной матрицей Гессе достигает своего минимального значения на , то метод Флетчера-Ривса обеспечивает отыскание точки минимума не более, чем за n шагов.

Теорема 4 Если функция ограничена снизу, а ее градиент удовлетворяет условию Липшица , где L>0, то в алгоритме Полака-Рибьера .

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

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

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

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

.

Алгоритм:

Шаг 1. Задать: начальную точку -малые положительные числа, M – предельное число итераций. Найти градиент .

Шаг 2. Положить k =0.

Шаг 3. Вычислить .

Шаг 4. Проверить выполнение критерия окончания :

а) если критерий выполняется, , расчет окончен;

б) если нет, то перейти к шагу 5.

Шаг 5. Проверить условие :

а) если неравенство выполняется, то , расчет окончен;

б) если нет, то при k =0 перейти к шагу 6, а при перейти к шагу 7.

Шаг 6. Определить .

Шаг 7. Определить

, .

Шаг 8. Определить .

Шаг 9. Найти из условия .

Шаг 10. Вычислить .

Шаг 11. Проверить выполнение условий

:

а) если выполняются оба условия в двух последовательных итерациях с номерами k и k -1, то расчет окончен, найдена точка ;

б) если не выполняется хотя бы одно из условий, то положить k = k + 1 и перейти к шагу 3.

Геометрическая интерпретация метода для n = 2 приведена на рисунке 4.7.

Рисунок 4.7.

Пример: Методом сопряженных градиентов найти локальный минимум функции

Решение:

1. Зададим , M: , , M =10.

Найдем градиент функции в произвольной точке

2. Положим k = 0.

3⁰. Вычислим : .

4⁰. Проверим условие : .

5⁰. Проверим условие : .

6⁰. Определим : .

9⁰. Определим из условия (первая итерация выполняется по методу наискорейшего спуска).

10⁰. Вычислим .

11⁰. Проверим условия: :

.

Полагаем k = 1, переходим к шагу 3.

3¹. Вычислим : .

4¹. Проверим условие : .

5¹. Проверим условие : .

7¹. Определим .

8¹. Определим

.

9¹. Определим из условия . Воспользуемся формулой

.

Подставляя полученное выражение в , имеем:

.

Применяя необходимое условие безусловного экстремума

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

10¹. Вычислим .

11¹. Проверим условия :

Полагаем k = 2, переходим к шагу 3.

3². Вычислим : .

4². Проверим условие : .

Расчет окончен. Найдена точка .

Проанализируем полученную точку:

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

Решение задачи представлено на рисунке 4.8.

Рисунок 4.8.

Дата добавления: 2015-07-20