22. Градиентные методы решения систем линейных уравнений решения систем линейных уравнений. Метод наискорейшего спуска. Общая характеристика метода, его сходимость и вычислительная устойчивость.

 

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

Дана система уравнений

,                                                           (1)

где -симметричная положительно определенная матрица (невырожденная). Решение этой системы может быть найдено  при помощи итерационного процесса:

,    0, 1, ...  .                                              (2)

Здесь  – вектор невязки на –ом шаге: 

,                                               (3)

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

,   0, 1, ... .                                          (4)

Если матрица А не является симметричной, то от системы (1) можно перейти к системе , где  – симметричная матрица.

Формулы (2), (3), (4) – расчетные формулы метода наискорейшего спуска. В качестве  можно взять любой вектор. Критерий остановки расчетов: . В рассматриваемом случае симметричной положительно определенной матрицы  итерационный процесс сходится со скоростью геометрической прогрессии. Условие сходимости: 

 ,                      (5).                                                            

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