Решение систем линейных алгебраических уравнений для больших разреженных матриц (стр. 2 из 6)
В результате нужно отметить, что в целом, матрица A обладает теми же свойствами, что и в случае одномерной, задачи, хотя ее структура может не быть ленточной, что зависит от способа нумерации узлов сетки
Обсудим размерность полученной СЛАУ. Предположим как и ранее, что требуемая точность аппроксимации равна ² = 10−6. Поскольку ² ∼ h2, то требуемый шаг сетки нужно выбрать порядка 10−3, т.к.
√ 3 × 103 = 106. Таh ∼ ². Число узлов здесь оказывается равным 10 кому же числу равно число неизвестных n. Таким образом, мы имеем матрицу размерности 106 × 106.Нетрудно догадаться, что если рассмотреть, не квадрат, а куб, то число неизвестных будет примерно равно n = 109. В расчетной практике встречаются задачи, где нужно определять не одну функцию, а несколько. Например, в гидродинамике при учете теплопереноса имеем четыре скалярных неизвестных (три компоненты поля скорости и поле температуры). Если рассматривать конечно-разностную аппроксимацию этой задачи с точностью ² = 10−6, то получим размерность n = 4 · 109.
Рассмотренные выше два примера показывают характерные источники задач линейной алгебры, приводящие к СЛАУ с большими разреженными матрицами. Естественно, что при решении таких СЛАУ необходимо развивать специальные методы вычислительной алгебры.
Рассмотрим другую нумерацию узлов, показанную на рис. 2. Здесь использовано так называемое красно-черное разбиение (или чернобелое). Вначале нумеруются узлы, сумма индексов которых – четное число, а потом узлы, сумма индексов которых дает нечетное число. Таким образом, вектор переменных вводится по правилу вектор неизвестных по правилу
u1,1 = x1, u1,3 = x2, u2,2 = x3, u3,1 = x4, u3,3 = x5
– это красные неизвестные, а
u1,2 = x6, u2,1 = x7, u2,3 = x8, u3,2 = x9
– черные неизвестные.
0 1
Рис. 2: Конечно-разностная сетка. Красно-черное разбиение.
Соответствующая красно-черному разбиению матрица дается формулой
| 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 A = 0 0 0 0 −1 −1 −1 0 −1 0 −1 −1 0 −1 −1 0 | 0 0 0 0 4 0 0 −1 | −1 −1 0 0 −1 0 −1 0 −1 −1 −1 −1 0 −1 0 −1 0 0 −1 −1 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 |
| 0 0 −1 −1 −1 | ||
Видно, что A является симметричной блочной (состоящей из четырех блоков) разреженной матрицей с диагональным преобладанием.
ТЕСТ РУБЕЖНОГО КОНТРОЛЯ № 1
1. Если исходная краевая задача порождает самосопряженный оператор, то какого вида матрицу следует ожидать после дискретизации? (выберите один из ответов)
(a) диагональную;
(b) верхнюю треугольную;
(c) трехдиагональную; (d) симметричную.
2. Зависит ли структура матрицы от способа нумерации узлов (выберите один из ответов)
(a) зависит;
(b) не зависит;
(c) не зависит, если оператор краевой задачи самосопряженный; (d) не зависит, если матрица ленточная.
3. Выберите из списка все разреженные матрицы
(a) диагональная;
(b) ленточная;
(c) нижняя треугольная; (d) теплицева.
4. При аппроксимации конечными разностями второго порядка двумерного уравнения Лапласа потребовалась точность 10−10. Каков порядок матрицы соответствующей СЛАУ получится, т.е. размерность n? (выберите один из ответов)
(a) 10−10;
(b) 1010;
(c) 105;
(d) 10100.
2 Векторные и матричные нормы
Напомним некоторые основные определения и утверждения из линейной алгебры. В данном пособии мы будем иметь дело с квадратными вещественными матрицами размерности n × n.
2.1 Векторные нормы
Определение 1. Пусть V – векторное пространство над полем F (R или C). Функция k · k: V → R является векторной нормой, если для всех x, y ∈ V выполняются следующие условия:
(1) kxk ≥ 0 (неотрицательность);
(1a) kxk = 0 тогда и только тогда, когда x = 0 (положительность);
(2) kcxk = |c|kxk для всех чисел c ∈ F (абсолютная однородность);
(3) kx + y| ≤ kxk + kyk (неравенство треугольника).
Это привычные свойства евклидовой длины на плоскости. Евклидова длина обладает и другими свойствами, независимыми от приведенных аксиом (например, выполнено тождество параллелограмма). Подобные дополнительные свойства оказываются несущественными для общей теории норм и поэтому не причисляются к аксиомам.
Функцию, для которой выполнены аксиомы (1), (2) и (3), но не обязательно (1а), называют векторной полунормой. Это более общее понятие, чем норма. Некоторые векторы, отличные от нулевого, могут иметь нулевую длину в смысле полунормы.
Определение 2. Пусть V – векторное пространство над полем F (R или C). Функция (x,y): VxV → F является скалярным произведением, если для всех x, y, z ∈ V следующие условия:
(1) (x,x) ≥ 0 (неотрицательность);
(1a) (x,x) = 0 тогда и только тогда, когда x = 0 (положительность);
(2) (x + y,z) = (x,z) + (y,z) (аддитивность); (3) (cx,y) = c(x,y) для всех чисел c ∈ F (однородность);
(4) (x,y) = (y,x) для любых x,y (эрмитовость).
Примеры векторных норм. В конечномерном анализе используются так называемые `p-нормы
.Наиболее распространенными являются следующие три нормы
; 
(евклидова норма);Естественно, что существует бесконечно много норм. Например, нормой также является выражение max{kxk1 + kx||2} или такое
kxkT = kTxk,
где T – произвольная невырожденная матрица.
Имеет место теорема, с теоретической точки зрения показывающая достаточность только одной нормы
Теорема 1. В конечномерном пространстве все нормы эквивалентны, т.е. для любых двух норм k · kα, k · kβ и для любого x выполняется неравенство
kxkα ≥ C(α,β,n)kxkβ
где C(α,β,n) – некоторая постоянная, зависящая от вида норм и от размерности матрицы n.
Для норм k · k1, k · k2, k · k∞ константа C(α,β,n) определяется таблицей
| α\β | 1 | 2 √ | ∞ |
| 1 | 1 | n | n √ |
| 2 | 1 | 1 | n |
| ∞ | 1 | 1 | 1 |
Проверим выполнение некоторых из неравенств.
Очевидно, что kxk1 ≤ nkxk∞. Это следует из неравенства
,которое получается, если в kxk1 заменить компоненты на максимальное значение. Неравенство достигается, если xi = xmax, т.е. все компоненты равны друг другу. Тем самым это неравенство является точным, поскольку иногда становится равенством.
Проверку остальных неравенств оставляем читателю (см. также
[10]).
Несмотря на теоретическую эквивалентность норм, с практической точки зрения норма вектора большой размерности n может отличаться от другой нормы того же вектора в n раз. Поэтому выбор нормы при больших n имеет значение с практической точки зрения.
Геометрические свойства норм k·k1, k·k2, k·k∞ могут быть прояснены в случае R2. Графики уравнений kxk1 = 1, kxk2 = 1, kxk∞ = 1 показаны на рис. 3. .
2.2 Матричные нормы
Обозначим пространство квадратных матриц порядка n через Mn.
Определение 3. Функция k·k, действующая из Mn в Rn, называется матричной нормой, если выполнены следующие свойства
Рис. 3: Графики уравнений kxk1 =1, kxk2 =1, kxk∞=1.
1. kAk ≥ 0, kAk = 0 ⇔ A = 0;
2. kλAk = |λ|kAk;
3. kA + Bk ≤ kAk + kBk (неравенство треугольника);