Сибирский федеральный университет

Перевод названия: Inexpensive stopping criteria in the conjugate gradient method

Тип публикации: статья из журнала

Год издания: 2015

Ключевые слова: conjugate gradient method, Stopping criteria, метод сопряженных градиентов, критерии останова итераций

Аннотация: Обсуждаются некоторые аспекты численной реализации метода сопряженных градиентов для решения систем линейных алгебраических уравнений с симметричной положительно определенной матрицей при наличии ошибок округления. Рассмотрены как пошаговое поведение некоторых широко распространенных версий алгоритма, так и критерии останова итерационного процесса. In the paper, some aspects of the numerical implementation of the conjugate gradient method (CGM) for systems of linear algebraic equations with symmetric positive definite matrix in the presence of round-off errors are discussed. With exact calculations, CGM provides an exact solution in a finite number of iteration steps. But in fact CGM is an iterative process and the weak point in an iterative process is in a stopping criterion. It is required to determine the number of the iteration step, after which the accuracy of an approximation to a solution of a system of linear equations may not be considerably improved with a particular computer. Hence, the construction of inexpensive stopping criteria for CGM being the aim of this paper is an urgent problem. For four popular versions of CGM, the step-by-step behavior as well as stopping criteria for an iterative process are considered. Numerical results show that the most accurate approximation is achieved by the CGM-version where descent directions and residual vectors are orthogonal in the energy and Euclidean metrics, respectively, at each iteration step. A practical stopping criteria for CGM is proposed as a formula that enables one to determine the number of the CGM iteration step, starting with which the progress is no longer being made. The application of the constructed criteria to the solution of specific systems of linear algebraic equations with ill-conditioned matrices is demonstrated.

Журнал: Вычислительные технологии

Выпуск журнала: Т. 20, № 2

Номера страниц: 44-55

ISSN журнала: 15607534

Место издания: Новосибирск

Издатель: Федеральное государственное бюджетное учреждение науки Институт вычислительных технологий Сибирского отделения Российской академии наук

• Киреев Игорь Валериевич (Институт вычислительного моделирования СО РАН)

• Ядро РИНЦ (eLIBRARY.RU)
• Список ВАК