Применение метода сопряженных градиентов с предварительным условием к решению линейных систем

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 512. 2
Т.В. Емельянова
канд. техн. наук, доцент, кафедра «Прикладная математика», Арзамасский политехнический институт (филиал) ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева»
Н.Ю. Зюзина
старший преподаватель, кафедра «Прикладная математика», Арзамасский политехнический институт (филиал) ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева»
М.В. Тюрьмина
старший преподаватель, кафедра «Прикладная математика», Арзамасский политехнический институт (филиал) ФГБОУ ВПО «Нижегородский государственный технический университет им. Р.Е. Алексеева»
А.Б. Зюзина
студент,
Нижегородский филиал ФГАОУ ВПО «Национальный исследовательский университет
«Высшая школа экономики»
ПРИМЕНЕНИЕ МЕТОДА СОПРЯЖЕННЫХ ГРАДИЕНТОВ С ПРЕДВАРИТЕЛЬНЫМ УСЛОВИЕМ К РЕШЕНИЮ ЛИНЕЙНЫХ СИСТЕМ
Аннотация. В статье рассмотрен итерационный алгоритм решения симметричных, положительно определенных линейных систем, реализующий метод сопряженных градиентов с предварительными условиями. Метод сопряженных градиентов с фильтром Чебышева задает некоторые специфические свойства сходимости метода сопряженных градиентов. Главное преимущество этого метода в то, что полученные предварительные условия может быть использована для решения ряда систем с небольшими дополнительными вычислительными затратами. Проиллюстрирована работа метода числовыми экспериментами на наборе линейных систем.
Ключевые слова: линейные системы, симметричные положительно определенные матрицы, метод сопряженных градиентов, полиномы Чебышева, система компьютерной математики Scilab.
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
APPLICATION CONJUGATE GRADIENT METHOD WITH A PRE-CONDITION TO THE SOLUTION OF
LINEAR SYSTEMS
Abstract. The article describes an iterative algorithm for solving symmetric positive definite linear systems implementing conjugate gradient method with the preconditions. The conjugate gradient method with Chebyshev sets some specific properties of convergence of the conjugate gradient method. The main advantage of this method is that the resulting pre-conditions can be used to solve a number of systems with little additional computational cost. Illustrate how the method of numerical experiments on a set of linear systems.
Keywords: linear systems, symmetric positive definite matrices, conjugate gradient method, Chebyshev polynomials, Scilab.
1. Введение
В статье [3] рассмотрен метод решения последовательности линейных систем с одной матрицей коэффициентов и разными правыми частями, основанный на комбинации метода сопряженных градиентов и фильтра Чебышева. Реализация данного метода выполнена в системе компьютерной математики Scilab. Применение и эффективность итерационного метода продемонстрированы на примере решения последовательности больших систем линейных уравнений.
2. Алгоритм реализации фильтра Чебышева Для решения систем линейных уравнений с разными правыми частями был разработан итерационный алгоритм [3], в котором итерационное приближение вычисляется:
^ = (СтЬ + У, гДе ат+1 = 2СОт — (1)
и связано с вектором фильтрации следующего шага итерации формулами [3]:
Wf =™& lt-т+1>- = ^ Л& gt-г (0& gt- = ^^ '-(0& gt- = - Тт+1 (- ацЛ) г & lt-°>-,
Тт+1 (Ст) & lt-7т+1
где Ст = У™ м, ат = --- и от = Тт (Ст& gt- для всех т & gt- 0.
Дтах +т, а =_2_
тэх — т Дтах — т
Тогда итерационное значение вектора фильтрации может быть получено эквивалентным рекуррентным соотношением:
о ,. о
w, = w (m+1& gt- = 2(с ш (т& gt- -а^{т & gt-) — 1w (m-1& gt-, (2& gt-
о т о
т+1 т+1
которое соответствует обычной трехчленной рекуррентной формуле Чебышева, представляющей вектор w (m+1& gt- как зависимость от текущего значения w (m& gt- и предыдущего
значения w (m& quot-1>- для т & gt- 1, с начальным значением вектора w (0& gt- = г (0& gt- и w (1& gt-:
I -т Л
V Ст)
г (0& gt-
Обозначим: х ('- & gt- - 1-ую итерацию в методе сопряженных градиентов с предварительным условием и г ('-& gt- = Ь — Лх ('-& gt- = Л (х — х ('-& gt->-- соответствующую разность [3]. Применение полинома Чебышева [1] как предварительного условия состоит в приближенном решении линейной системы Лг ('- & gt- = г ('- & gt- с конечной разностью, которая задана соотношением г ('- & gt- - Л2(/& gt- = Рт (Л& gt-г ('- & gt-, и может быть выражена как:
2('-& gt- = Л& quot-1 (I — (Л& gt-)г ('->- = М-1г ('-& gt-. (3& gt-
Данный полиномиальный фильтр выполняет фиксированное количество шагов для заданных значений 1тах (Л& gt-, т и? независимо от правой части.
3. Использование подпространств Крылова для решения линейных систем Рассмотрим линейные системы с различными правыми частями и одной и той же матрицей коэффициентов:
Лх, = Ь, 1=1, …, 5, (4& gt-
где Л е Н& quot-™ — симметричная положительно определенная матрица- х, е Н и Ь, е Н -векторы.
Сначала решим первую систему Лх1 = Ь1 методом сопряженных градиентов с фильтром
Чебышева. Представим это решение как предварительное условие и используем полученный базис Крылова для вычисления решения остальных систем. Базис Крылова Wk получен после к итераций при решении первой системы в (4& gt-.
Таким образом, метод сопряженных градиентов используется для решения систем вида: М-1Лх, = М- (, & gt- 2& gt- (5& gt-
с начальным приближением х (0& gt- = Wk (WkгЛWk& gt--1WkгЬ, где Wk — базис Крылова, полученный после к итераций методом сопряженных градиентов с матрицей предварительного условия М-1Л.
Базис Крылова Wk, построенный с помощью метода сопряженных градиентов с
дополнительным условием, использует векторы поиска, а не разности векторов. В этом случае Wk — уже А-ортогональный базис подпространства Крылова, и Ас = ^^- диагональная матрица. Этот метод описан в алгоритме 4.1 [2].
4. Анализ сходимости алгоритма Применим разработанные алгоритмы для системы уравнений: Ах, = Ь ('- 1=1, …, 10,
где А=сНад (1, …, 100), Ь (1)($) = эт (/ + (/ + -2)Д0, / = 1… 100, и = 1… 10 и Ы = 2Р/100. В
качестве начальных значений возьмем х, 0) = гапС (100,1).
Определим влияние ограничивающего значения фильтрации т и уровня фильтрации е на примере решения первой системы. Предварительное условие, заданное в виде фильтра Чебышева [3], зависит от двух различных параметров, а именно, от выбора ограничивающего значения фильтрации у и уровня фильтрации е.
В Таблице представлены данные о количестве итераций в методе, реализующем фильтр Чебышева (ФЧ), и градиентном методе с фильтром Чебышева (ГМФЧ), а также общее количество их итераций (ФЧ * ГМФЧ) для различных значений уровня фильтрации? и ограничивающего значения фильтрации у. В этом примере, критерием остановки для метода
сопряженных градиентов является ||х* - х (к^ & lt- 1е — 9.
Таблица — Результирующие параметры методов
Значение? у = Лтах/100 у = Лтах/50 у = Лтах/20
ФЧ ГМФЧ ФЧ * ГМФЧ ФЧ ГМФЧ ФЧ * ГМФЧ ФЧ ГМФЧ ФЧ * ГМФЧ
10−15 177 1 177 125 2 250 79 4 316
10−10 120 1 120 85 3 255 54 7 378
10& quot-° 97 2 194 69 3 207 44 7 308
10−6 74 2 148 52 4 208 33 8 264
10& quot-4 51 4 204 36 5 180 23 11 253
Параметр у разбивает спектр матрицы, А на два подмножества и определяет скорость сходимости классических итераций Чебышева, которые будут выполняться на каждой итерации метода сопряженных градиентов. Снижение скорости сходимости полинома Чебышева для небольших значений у приводит к увеличению итераций фильтрации Чебышева на каждой итерации, и это может быть уравновешено только сильным уменьшением общего количества итераций в методе сопряженных градиентов с предварительным условием. Другими словами, уменьшать значение у стоит, только если существует очень сильная группировка собственных значений в спектре итерационной матрицы.
Второй параметр, уровень фильтрации е, непосредственно влияет на число итераций фильтра Чебышева. Для фиксированного значения у, если рассматривать общее количество итераций (ФЧ * ГМФЧ), то метод сопряженных градиентов один работает лучше, чем объединение метода сопряженных градиентов и фильтра Чебышева, потому что полином Чебышева действует однородно и независимо от собственных компонентов данной разности. Однако, следует отметить, что если многократно использовать сгенерированный фильтрованный базис Крылова для ускорения сходимости остальных решений, размер этого базиса имеет большое значение, и нужно рассматривать меньшие значения уровня фильтрации е, чтобы минимизировать его.
Эффективность базиса Крылова, полученного методом сопряженных градиентов с фильтром Чебышева как предварительным условием, показана на рисунках 1−4.
х (0) = гаМ (100,1)
х (0) = ь,
Рисунок 1 — Относительная итерационная ошибка для решения второй системы
: х (0) = X (0) = ганё (100,1) WA-1WTЬ,



-
: х^ч -г — -1
20 30
Рисунок 2. -Относительная итерационная ошибка для решения третьей системы
& quot-"-"-"-Г х (0) = гаМ (100,1) х (0) = WA-1WT ь




1
V
________

Рисунок 3 — Относительная итерационная ошибка для решения восьмой системы
х (0) = гаМ (100,1)
X (0) =
Рисунок 4 — Относительная итерационная ошибка для решения девятой системы
Метод сопряженных градиентов с фильтром Чебышева, не смотря на небольшое увеличение вычислений, имеет лучшую сходимость, чем градиентный метод с произвольно заданным предварительным условием, и может применяться для различных правых частей системы линейных уравнений.
Заключение
Решение систем линейных уравнений является стандартным этапом численного моделирования. Для его реализации разработано большое количество алгоритмов. В статье был рассмотрен метод сопряженных градиентов с предварительным условием для решения линейных систем с одной матрицей и разными правыми частями. Данный метод основан на использовании фильтра Чебышева, как предварительное условие, с помощью которого строится базис Крылова меньшей размерности в методе сопряженных градиентов.
Исследуемый алгоритм был реализован в системе программирования БсИаЬ, и его эффективность проиллюстрирована на примерах.
Список литературы:
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. Емельянова Т. В., Зюзина Н. Ю., Тюрьмина М. В., Зюзина А. Б. Решение линейных систем с разными правыми частями методом сопряженных градиентов с предварительным условием // Приволжский научный вестник. — № 12−3(52). — 2015. — C. 104−107.

ПоказатьСвернуть
Заполнить форму текущей работой