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. Методом скорейшего спуска решим систему уравнений
Так как диагональные элементы матрицы являются преобладающими, то в качестве начального приближения выберем:
Следовательно, вектор невязок на нулевом шаге равен
Далее последовательно вычисляем
Отсюда
причем
Аналогично находятся последующие приближения и оцениваются невязки. Что касается данного примера, можно отметить, что итерационный процесс сходится достаточно медленно (невязки уменьшаются).
Достарыңызбен бөлісу: |
