3.8. Метод скорейшего спуска (градиента) для случая системы линейных алгебраических уравнений

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

Представим систему линейных уравнений в следующем виде:

(3.38)

Запишем выражение (3.38) в операторной форме:

(3.39)

Здесь приняты следующие обозначения:

; ; . (3.40)

В методе скорейшего спуска решение ищут в виде

, (3.41)

где и - векторы неизвестных на p и p+1 шагах итераций; вектор невязок на p-ом шаге определяется выражением

, (3.42)

а (3.43)

В формуле (3.43) используется скалярное произведение двух векторов, которое определяется следующей формулой:

(3.44)

В формуле (3.43) - транспонированная матрица Якоби, вычисленная на p-ом шаге. Матрица Якоби вектор – функции f(x) определяется как

(3.45)

Нетрудно убедиться, что для системы (3.39) матрица Якоби равна

(3.46)

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

Замечания

• Как видно из выражения (3.45), матрица Якоби не зависит от шага итерации.

• Требования минимизации погрешности на каждом шаге обусловили то, что метод градиента более сложен (трудоемок), чем методы Якоби и Зейделя.

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

Обсуждение

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

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

• В качестве недостатка приближенных методов можно отметить то, что они часто расходятся, достаточные условия сходимости (преобладание диагональных элементов) можно обеспечить только для небольших систем из 3 – 6 уравнений.

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

Так как диагональные элементы матрицы являются преобладающими, то в качестве начального приближения выберем:

Следовательно, вектор невязок на нулевом шаге равен

Далее последовательно вычисляем

Отсюда

причем

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