Метод покоординатного спуска (Гаусса—Зейделя)

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

Постановка задачи решения системы уравнений в терминах методов оптимизации

Задача решения системы уравнений:

(1)

с эквивалентна задаче минимизации функции

(2)

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

Для решения этой задачи итерационными методами начинают с произвольных значений и строят последовательные приближения:

или покоординатно:

(3)

которые сходятся к некоторому решению при .

Различные методы отличаются выбором «направления» для очередного шага, то есть выбором отношений

Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра , минимизирующим величину как функцию от . Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям . Последний метод применим для отыскания max и min таблично заданной функции .

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

Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :

где выбирается

· постоянной, в этом случае метод может расходиться;

· дробным шагом, то есть длина шага в процессе спуска делится на некое число;

· наискорейшим спуском:

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

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

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

(5)

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

Алгоритм

1. Задаются начальное приближение и точность расчёта

2. Рассчитывают , где

3. Проверяют условие останова:

· Если , то и переход к шагу 2.

· Иначе и останов.

Метод покоординатного спуска (Гаусса—Зейделя)

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