Теория и практика параллельных вычислений
Метод сопряженных градиентов
Рассмотрим теперь совершенно иной подход к решению систем линейных уравнений, при котором к искомому точному решению x*
системы Ax=b строится последовательность приближенных решений x0, x1, ..., xk, ... При этом процесс вычислений организуется таким способом, что каждое очередное приближение дает оценку точного решения со все уменьшающейся погрешностью, и при продолжении расчетов оценка точного решения может быть получена с любой требуемой точностью. Подобные итерационные методы решения систем линейных уравнений широко используются в практике вычислений. К преимуществам итерационных методов можно отнести меньший объем (по сравнению, например, с методом Гаусса) необходимых вычислений для решения разреженных систем линейных уравнений, возможность более быстрого получения начальных приближений искомого решения, наличие эффективных способов организации параллельных вычислений. Дополнительная информация с описанием таких методов, рассмотрением вопросов сходимости и точности получаемых решений может быть получена, например, в [[6], [22]].
Рис. 8.4. График зависимости экспериментального и теоретического времени проведения эксперимента на двух процессорах от объема исходных данных
Одним из наиболее известных итерационных алгоритмов является метод сопряженных градиентов, который может быть применен для решения симметричной положительно определенной системы линейных уравнений большой размерности.
Напомним, что матрица А является симметричной, если она совпадает со своей транспонированной матрицей, т.е. А=АТ. Матрица А называется положительно определенной, если для любого вектора x справедливо: xTAx>0.
Известно (см., например, [[6], [22]]), что после выполнения n итераций алгоритма (n есть порядок решаемой системы линейных уравнений), очередное приближение xn совпадает с точным решением.
