Решение систем линейных алгебраических уравнений для больших разреженных матриц (стр. 1 из 6)
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГO
ОБРАЗОВАНИЯ
“ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ”
В.А.Еремеев
РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ
АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ДЛЯ БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ
(учебно-методическое пособие)
Ростов-на-Дону
2008
В.А.Еремеев. Решение систем линейных алгебраических уравнений для больших разреженных матриц: Учебно-методическое пособие. – г.Ростов-на-Дону, 2008 г. – 39 с.
В данном пособии в концентрированном виде содержится информация о решении систем линейных алгебраических уравнений для разреженных матриц большой размерности. Пособие состоит из четырех основных модулей:
1. задачи линейной алгебры с разреженными матрицами на примере дискретизации уравнения Пуассона;
2. векторные и матричные нормы;
3. итерационные методы;
4. методы подпространств Крылова.
Пособие предназначено для преподавания дисциплин в рамках магистерской образовательной программы “Математическое моделирование и компьютерная механика”.
Пособие также предназначено для студентов и аспирантов факультета математики, механики и компьютерных наук, специализирующихся в области математического моделирования, вычислительной математики и механики твердого деформируемого тела.
Пособие подготовлено в рамках гранта ЮФУ K-07-T-41.
Содержание
1 Задачи линейной алгебры с разреженными матрицами на примере дискретизации уравнения Пуассона 4
1.1 Решение уравнения −x00 = f(t) . . . . . . . . . . . . . . . 4
1.2 Решение уравнения Пуассона . . . . . . . . . . . . . . . . 6
2 Векторные и матричные нормы 11
2.1 Векторные нормы . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Матричные нормы . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Связь векторных и матричных норм . . . . . . . . . . . 15
3 Итерационные методы 19
3.1 Определения и условия сходимости итерационных методов 19
3.2 Метод простой итерации . . . . . . . . . . . . . . . . . . . 23
3.3 Метод Якоби . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Метод Гаусса-Зейделя . . . . . . . . . . . . . . . . . . . . 25
3.5 Метод последовательной верхней релаксации (SOR) . . . 26
3.6 Метод симметричной последовательной верхней релак-
сации (SSOR) . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Методы подпространств Крылова 30
4.1 Инвариантные подпространства . . . . . . . . . . . . . . 30
4.2 Степенная последовательность и подпространства Кры-
лова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Итерационные методы подпространств Крылова . . . . . 33
Заключение 38
Литература 38
Дополнительная литература 39
1 Задачи линейной алгебры с разреженными матрицами на примере дискретизации уравнения Пуассона
Основным источником задач линейной алгебры для матриц большой размерности являются задачи, получаемые в результате дискретизации краевых задач математической физики. Далее рассмотрим два примера, иллюстрирующих особенности получаемых матричных задач.
1.1 Решение уравнения −x00 = f(t)
Рассмотрим простейшую краевую задачу
−x00 = f(t), x(0) = x(1) = 0.
Для дискретизации этой краевой задачи воспользуемся методом конечных разностей. Введем равномерную сетку на единичном отрезке
ti = hi, i = 0,...n + 1, h = 1/(n + 1)
так, чтобы t0 = 0, tn+1 = 1. Используем обозначения
xi = x(ti), fi = f(ti).
Для дискретизации второй производной воспользуемся центральной конечной разностью
,которая аппроксимирует x00(ti) c точностью O(h2). Тогда исходная краевая задача сводится к системе линейных алгебраических уравнений (СЛАУ) относительно
−xi−1 + 2xi − xi+1 = h2fi (i = 1,...,n)
или c учетом краевых условий x0 = xn+1 = 0
2x1 − x2 = = h2f1,
−x1 + 2x2 − x3 = h2f2,
, 
.Эту СЛАУ можно записать также в матричном виде
Ax = b,
где
| 2 −1 A = 0 | −1 0 2 −1 −1 2 | ... ... ... ... | 0 0 0 | 00 0 , |
0 0 0 ... −1 2
| x1 x2 x3 , x = ... xn | b1 b2 b3 b = ... bn |
Обратим внимание на следующие свойства матрицы A.
• A – разреженная матрица, она трехдиагональная;
• A – симметричная и, более того, положительно определенная. Это свойство она унаследовала от свойств оператора исходной краевой задачи;
• Структура A достаточно простая, ее элементы вычисляются по простым формулам. Следовательно, для ее хранения в памяти компьютера нет необходимости использовать типы данных, предназначенные для хранения заполненных матриц.
Обсудим размерность полученной СЛАУ. Предположим, что требуемая точность аппроксимации равна ² = 10−6. Поскольку ² ∼ h2, то
−3, т.к. h ∼ √². Т.е. требуемый шаг сетки нужно выбрать порядка 10 мы имеем матрицу размерности 103 × 103. На практике, размерность должна быть выше, чтобы удовлетворить большей точности. 
0 1
Рис. 1: Конечно-разностная сетка. Естественная нумерация узлов.
1.2 Решение уравнения Пуассона Рассмотрим более сложную краевую задачу
−∆u(x,y) = f(x,y), u|Γ = 0,
где u = u(x,y) – неизвестная функция, f(x,y) – известная, заданные на единичном квадрате (x,y) ∈ Ω = [0,1]×[0,1]}, Γ = ∂Ω – граница Ω. Введем на Ω равномерную сетку, так что координаты узлов даются формулами xi = hi, yi = hi, i = 0,...N + 1, h = 1/(N + 1).
Используем обозначения
ui,j = u(xi,yj), fi,j = f(xi,yj).
Для дискретизации вторых производных в операторе Лапласа ∆ воспользуемся формулами для центральной конечной разности
,Таким образом, исходная краевая задача сводится к СЛАУ
−ui−1,j + 4ui,j − ui+1,j − ui,j−1 − ui,j+1 = h2fi,j (1) относительно ui,j. Для того, чтобы свести ее к стандартному виду Ax = b, необходимо преобразовать ui,j к выражению с одним индексом, т.е. перенумеровать каким-то образом. Выбор нумерации влияет, вообще говоря, на структуру матрицы A.
Рассмотрим случай N = 3. Соответствующая сетка показана на рис. 1, где использована естественная нумерация внутренних узлов. Полые кружки соответствуют граничным узлам, в которых известно значение функции, а сплошные – внутренним.
Если преобразовать конечно-разностное уравнение (1) в матричное уравнение Ax = b, вводя вектор неизвестных по правилу u1,1 = x1, u1,2 = x2, u1,3 = x3, u2,1 = x4,..., u3,3 = x9,
| то матрица A принимает вид | ||||||||
| | −1 0 0 4 −1 0 −1 0 0 | 0−1 0−1 4−1 0−1 0 | 0 0 −1 0 −1 4 0 0 −1 | 0 0 0 −1 0 0 4 −1 0 | 0 0 0 0 −1 0 0 4 −1 | 00 0 0 0 −1 0 −1 4 | ||
| 4 −1 0 −1 A = 0 0 0 0 0 | −1 4 −1 0 −1 0 0 0 0 | 0 −1 4 0 0 −1 0 0 0 | ||||||
Видно, что A является симметричной ленточной разреженной матрицей с диагональным преобладанием.