Решение линейных систем с разными правыми частями методом сопряженных градиентов с предварительным условием Текст научной статьи по специальности «Математика»
Аннотация научной статьи по математике, автор научной работы — Емельянова Т.В., Зюзина Н.Ю., Тюрьмина М.В., Зюзина А.Б.
В статье рассмотрено одна из самых мощных итерационных схем для решения симметричных, положительно определенных линейных систем метод сопряженных градиентов с предварительными условиями. Во многих приложениях требуется решить ряд уравнений с одинаковой матрицей коэффициентов. Комбинация метода сопряженных градиентов с фильтром Чебышева, применяемого только к части матрицы коэффициентов, как предварительное условие, задает некоторые специфические свойства сходимости метода сопряженных градиентов . Матрица предварительного условия, имея большое количество собственных значений около единицы, не ухудшает распределение остальных. Эта процедура дает возможность создать базис Крылова меньшей размерности, который имеет наименьшие собственные значения и соответствующие собственные вектора. Главное преимущество этого метода в то, что полученные предварительные условия может быть использована для решения ряда систем с небольшими дополнительными затратами.
Похожие темы научных работ по математике , автор научной работы — Емельянова Т.В., Зюзина Н.Ю., Тюрьмина М.В., Зюзина А.Б.
SOLUTION OF LINEAR SYSTEMS WITH DIFFERENT RIGHT PART OF THE CONJUGATE GRADIENT METHOD WITH THE PRECONDITIONS
The article deals with one of the most powerful iterative schemes for solving symmetric positive definite linear systems conjugate gradient method with the preconditions. In many applications it is necessary to solve a series of equations with the same coefficient matrix. The combination of the conjugate gradient method with a polynomial Chebyshev filter applied to only part of the coefficient matrix, as a precondition, sets some specific properties of convergence of the conjugate gradient method . It is shown that the matrix precondition, having a large number of eigenvalues around unity, does not impair the remaining allocation. This procedure makes it possible to create a basis for the Krylov smaller dimension, which has the smallest eigenvalues and the corresponding eigenvectors. The main advantage of this method is that the resulting pre-conditions can be used for a number of systems with little additional cost.
Текст научной работы на тему «Решение линейных систем с разными правыми частями методом сопряженных градиентов с предварительным условием»
канд. техн. наук, доцент, кафедра «Прикладная математика», Арзамасский политехнический институт (филиал) ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева»
старший преподаватель, кафедра «Прикладная математика», Арзамасский политехнический институт (филиал) ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева»
старший преподаватель, кафедра «Прикладная математика», Арзамасский политехнический институт (филиал) ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева»
А.Б. Зюзина студент,
Нижегородский филиал ФГАОУ ВПО «Национальный исследовательский университет
«Высшая школа экономики»
РЕШЕНИЕ ЛИНЕЙНЫХ СИСТЕМ С РАЗНЫМИ ПРАВЫМИ ЧАСТЯМИ МЕТОДОМ СОПРЯЖЕННЫХ ГРАДИЕНТОВ С ПРЕДВАРИТЕЛЬНЫМ УСЛОВИЕМ
Аннотация. В статье рассмотрено одна из самых мощных итерационных схем для решения симметричных, положительно определенных линейных систем - метод сопряженных градиентов с предварительными условиями. Во многих приложениях требуется решить ряд уравнений с одинаковой матрицей коэффициентов. Комбинация метода сопряженных градиентов с фильтром Чебышева, применяемого только к части матрицы коэффициентов, как предварительное условие, задает некоторые специфические свойства сходимости метода сопряженных градиентов. Матрица предварительного условия, имея большое количество собственных значений около единицы, не ухудшает распределение остальных. Эта процедура дает возможность создать базис Крылова меньшей размерности, который имеет наименьшие собственные значения и соответствующие собственные вектора. Главное преимущество этого метода в то, что полученные предварительные условия может быть использована для решения ряда систем с небольшими дополнительными затратами.
Ключевые слова: линейные системы, симметричные положительно определенные матрицы, метод сопряженных градиентов, полиномы Чебышева.
T.V. Emelyanova, Arzamas Polytechnic Institute
N.U. Zyuzina, Arzamas Polytechnic Institute
M.V. Tyurmina, Arzamas Polytechnic Institute
A.B. Zyuzina, Higher School of Economics
SOLUTION OF LINEAR SYSTEMS WITH DIFFERENT RIGHT PART OF THE CONJUGATE GRADIENT
METHOD WITH THE PRECONDITIONS
Abstract. The article deals with one of the most powerful iterative schemes for solving symmetric positive definite linear systems - conjugate gradient method with the preconditions. In many applications it is necessary to solve a series of equations with the same coefficient matrix. The combination of the conjugate gradient method with a polynomial Chebyshev filter applied to only part of the coefficient matrix, as a precondition, sets some specific properties of convergence of the conjugate gradient method. It is shown that the matrix precondition, having a large number of eigenvalues around unity, does not impair the remaining allocation. This procedure makes it possible to create a basis for the Krylov smaller dimension, which has the smallest eigenvalues and the corresponding eigenvectors. The main advantage of this method is that the resulting pre-conditions can be used for a number of systems with little additional cost.
Keywords: linear systems, symmetric positive definite matrices, conjugate gradient method, Chebyshev polynomials.
Решение систем линейных уравнений с одинаковой матрицей коэффициентов и разными правыми частями является одной из самых часто решаемых задач. Эта задача возникает, например, при решении нелинейных систем методом Ньютона, где приближенная матрица Якоби фиксируется в течение нескольких итераций. Каждая итерация в этом случае требует решения линейной системы с постоянной матрицей и с изменяющейся правой частью, которая зависит от предыдущей итерации.
В [2] предложено использовать метод сопряженных градиентов с предварительным условием, заданным в виде полинома Чебышева, примененного только к части матрицы коэффициентов.
2. Метод сопряженных градиентов с предварительным условием В статьях [5,6] были рассмотрены системы линейных уравнений с заданными правыми частями.
Рассмотрим решения систем уравнений с произвольной правой частью: Ах = Ь , (1)
где Ае й"х" - симметричная положительно определенная матрица большой размерности, и Ь е й" - правая часть [2].
Один из самых мощных методов для решения таких линейных систем является метод сопряженных градиентов с предварительным условием.
Пусть М - некоторая невырожденная матрица размерности ". Умножим уравнение (1) на матрицу М- , получим систему
которая в силу невырожденности матрицы М имеет то же точное решение х*.
Введем обозначения А = М
1Ь и запишем систему (2) в виде: Ах = Ь . (3)
Система (3) алгебраически эквивалентна системе (1), но спектральные характеристики матрицы А отличаются от характеристик матрицы А, что ведет к изменению скорости сходимости численных методов для системы (3) по отношению к системе (1).
Процесс перехода от системы (1) к системе (3) с целью улучшения характеристик матрицы для ускорения сходимости к решению называется процессом решения задачи с предварительным условием, а матрица М - матрицей предварительного условия [4].
3. Фильтр Чебышева
Рассмотрим разложение симметричной положительно определенной матрицы А по собственным значениям [1]:
хг = х(0), ш, = Ь - Ах, А = иАиТ = и1Л1и[ + и2Л2иТ, (4)
где матрица А разложена на две части:
Л1 - диагональная матрица, содержащая все собственные значения матрицы А, которые меньше заданного положительного числа у. Число ¡л обозначает ограничивающее значение
фильтрации и определено условием 0 <л<1тах;
и1 - прямоугольная матрица, столбцы которой - соответствующий ортонормированный набор собственных векторов в матричной форме;
Л2 и и2 - соответствующие дополнительные матрицы.
Пусть х(0) е Н" - начальное приближение для решения системы (1), и пусть г(0) = Ь - Ах(0) - соответствующий вектор невязок. Рассмотрим вектор фильтрации:
wf = Fm(A)r(0) = UiFm(A1)U1rr(0) + U2Fm(A2)UT2r(0), (5)
где Fm - полиномиальная функция степени m определяемая выражением:
где Tm - обычный полином Чебышева степени m;
Qm - функция линейного отображения, которая преобразует интервал [m, U в
единичный интервал [—1, 1] (0m(m) = 1 и 0m(1tmax) = -1).
Для некоторых значений m , 1max(A) и e можно определить степень m полинома Tm так, чтобы уTm (0m(0))|<e и, следовательно, ||Fm(2)||¥<e на [m, 1max]. Используя выражение (5), можно записать
||ujwf112 < I|Fm(Л2)|2\\uT2r(0)||2 < e\\UT2r(0)||2. (7)
Уравнение (7) использует фильтр Чебышева в виде полинома Чебышева с матрицей A для данного вектора r(0) и может уменьшить собственные компоненты в r(0) связанные со всеми собственными значениями в диапазоне [m, lmax(A)] относительно других.
Необходимое число итераций для достижения данного уровня фильтрации e непосредственно зависит от скорости сходимости полиномов Чебышева на интервале [m, lmax], которая зависит от отношения lmax/m .
В [2] было предложено использовать полиномы Чебышева с матрицей A для уменьшения до величины e собственных компонентов вектора r(0) = b — Ax(0), связанных со всеми собственными значениями в диапазоне [m, lmax(A)]. Фильтр Чебышева wf = Fm+1(A)r(0) и соответствующее итерационное приближение xf связаны равенством b — Axf = wf.
Следует отметить, что данный полиномиальный фильтр выполняет фиксированное количество шагов для заданных значений lmax(A), m и £ независимо от правой части.
Каждая итерация в методе сопряженных градиентов с предварительным с условием состоит из поиска x(') е + Ki(M
1A, z(0)) с начальными условиями z(0) = M^b и
1A, z(0)), где Ki(M"'A, z(0)) - '-ое подпространство Крылова [3], представлено как:
т. к. A^Fm (A) = Fm (A)A— и, следовательно,
M-1A = A-1 (I — Fm(A))A = (I — Fm(A))A-1 A . (9)
Заметим, что если матрица A - симметричная положительно определенная, то матрица M"' = A
\I — Fm(A)) - симметричная положительно определенная. Матрицы A-1 и Fm(A) коммутируют, тогда матрица M_1 - симметричная.
Используя разложение симметричной положительно определенной матрицы A = ULUT, получим
M-1 = UЛ—1(I — Fm (L))UT, (10)
где Л—1(I — Fm(Л)) - диагональная положительно определенная, Fm(l)е [—e, 1) для всех А из
Матрицы M^A и AMимеют одни и те же собственные значения, которые являются собственными значениями (I - Fm(A)). Поэтому, собственные значения M ^A заданы как
(1 - Fm(А,)), где li, i е , - собственные значения A.
Важным аспектом в использовании такого фильтра Чебышева в качестве предварительного условия является то, что он действует однородно на диапазоне [m Amax(A)], независимо от правой части, в противоположность методу сопряженных градиентов, который ищет полином, минимизирующий норму ошибки в данной линейной системе.
В работе рассмотрен метод сопряженных градиентов с предварительным условием для решения последовательности линейных систем с одной матрицей и разными правыми частями. Данный метод основан на использовании полиномов Чебышева, применяемых только к диагональной матрице, содержащей собственные значения матрицы коэффициентов А, как предварительное условие, с помощью которого строится базис Крылова меньшей размерности в методе сопряженных градиентов.
1. Ashby S.F., Manteuffel T.A., Otto J.S. A comparison of adaptive Chebyshev and least squares polynomial preconditioning for Hermitian positive definite linear systems. - SIAM J. Sci. Comput., No 13, 1992, pp. 1-29.
2. Gene H. Golub, Daniel Ruiz, And Ahmed Touhami. A hybrid approach combining Chebyshev filter and conjugate gradient for solving linear systems with multiple right-hand sides. -SIAM J. Matrix Anal. Appl. Vol. 29, No. 3, pp. 774-795.
3. Giraud L., Ruiz D., Touhami A. Krylov based and polynomial iterative solvers combined with partial spectral factorization for SPD linear systems. - Berlin, Heidelberg, 2005. pp. 635-655.
4. Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности. -Новосибирск: Изд-во НГТУ, 2000.
5. Емельянова Т.В., Кусков А.А. Применение метода золотого сечения в матричных уравнениях // XI Всероссийская школа-конференция молодых ученых «Управление большими системами». - М.: ИПУ РАН, 2014. С. 149-158.
6. Зюзина Н.Ю., Аминов И.Л. Итерационный метод решения систем матричных уравнений // XI Всероссийская школа-конференция молодых ученых «Управление большими системами». - М.: ИПУ РАН, 2014. С. 218-226.