Решение систем линейных алгебраических уравнений для больших разреженных матриц (стр. 3 из 6)

4. kABk ≤ kAkkBk (кольцевое свойство).

Если последнее свойство не выполнено, то такую норму будем называть обобщенной матричной нормой.

Приведем примеры наиболее распространенных матричных норм.

1.

– максимальная столбцовая норма;

2.

– максимальная строчная норма;

3. kAk_M = n max |a_ij|;

i,j=1..n

4. kAk₂ = max ν_i – спектральная норма. Здесь ν_i – сингулярные i=1..n

числа матрицы A, т.е. ν_i² – собственные числа матрицы AA^T;

5.

– евклидова норма;

6.

норма.

Как и в случае векторных норм, все матричные нормы эквивалентны. Использование различных норм связано с удобством использования, а также с тем фактом, что матриц большой размерности значения нормы могут отличаться весьма значительно.

2.3 Связь векторных и матричных норм

Выше были даны примеры векторных и матричных норм, введенные независимо друг от друга. Вместе с тем, эти два понятия могут быть связаны при помощи двух понятий.

Определение 4. Матричная норма k · k называется согласованной с векторной нормой k · k, если для любой A ∈ M_n и любого x ∈ V выполняется неравенство

kAxk ≤ kAkkxk.

Заметим, что в этом неравенстве знак нормы относится к разным нормам – векторным и матричной.

Определение 5. Матричная норма называется подчиненной (операторной, индуцированной) соответствующей векторной норме, если она определена равенством

kAk = max kAxk.

kxk=1

Понятие операторной матричной нормы является более сильным, чем подчиненной:

Теорема 2. Операторная норма является подчиненной соответствующей матричной норме.

Доказательство. Действительно, из определения следует,

kAxk ≤ kAkkxk.

Следствие 2.3.1. Операторная норма единичной матрицы равна единице:

kEk = 1. Доказательство. Действительно, kEk = max kExk = 1.

kxk=1

Существует ряд утверждений, связывающих введенные матричные и векторные нормы.

1. Матричная норма k · k₁ являются операторной нормой, соответствующей векторной норме k · k₁.

2. Матричная норма k · k_∞ являются операторной нормой, соответствующей векторной норме k · k_∞.

3. Спектральная матричная норма k·k₂ являются операторной нормой, соответствующей евклидовой векторной норме k · k₂.

4. Матричные нормы k·k_E, k·k_M, k·k_`1 не являются операторными.

5. Матричная норма k · k₂ согласована с векторной нормой k · k₂.

6. Матричная норма k·k_M согласована с векторными нормами k·k₁, k · k_∞, k · k₂.

ТЕСТ РУБЕЖНОГО КОНТРОЛЯ № 2

1. Вычислите нормы k · k₁, k · k_∞, k · k_M, k · k_`1 матриц

(a) 

... 0 0

... 0 0 ^

A... 0 0 ^;

.. 

0 0 0−1 2

(b) 

41 0 1 0 0 0 0 0

^ −1 4 −1 0 1 0 0 0 0 ^_

^ 01 4 0 01 0 0 0 ^

^ −1 0 0 4 1 0 −1 0 0 ^

 A =  01 01 0 −1 0 ;

  0 01 0 1 4 0 0 −1 

  0 0 0 1 0 0 4 0 0 



 0 0 0 0 1 0 −1 4 −1  0 0 0 0 0 −1 0 −1 4

(c) 

4 0 0 0 0 −1 −1 0 0

^ 0 4 0 0 0 −1 0 −1 0 ^_

^ 0 0 4 0 0 −1 −1 −1 −1 ^

^ 0 0 0 4 0 0 −1 0 −1 ^

 A =  0 0 0 0 4 0 0 −1 −1 .

  −1 −11 0 0 4 0 0 0 

  −1 01 0 0 4 0 0 



 0 −11 0 1 0 0 4 0 

0 01 0 0 0 4

2. Если матричная норма является согласованной, то можно ли построить соответствующую ей векторную норму, чтобы она стала операторной? (выберите один из ответов)

(a) нельзя;

(b) можно;

(c) можно, если матрица симметрична; (d) можно для евклидовой нормы.

3. Если матричная норма k · k является операторной, то (выберите правильные ответы)

(a) она согласована;

(b) положительна;

(c) kEk = 1;

(d) kEk = n.

4. Операторная норма единичной матрицы равна (выберите один из ответов)

(a) чему угодно;

(b) единице; (c) n;

(d) n².

5. Согласованная норма единичной матрицы равна (выберите один из ответов)

(a) чему угодно;

(b) единице; (c) n;

(d) n².

3 Итерационные методы

3.1 Определения и условия сходимости итерационных методов

Различают прямые и итерационные методы решения систем линейных алгебраических уравнений (СЛАУ). Прямые методы получают решение за конечное число шагов, причем, если предположить, что это решение может быть получено в точной арифметике (когда нет ошибок округления), то это решение является точным. Итерационные методы, вообще говоря, всегда дают приближенное решение, для получения точного решения необходимо бесконечное число шагов. Интерес к итерационным методам связан как раз с решением СЛАУ с матрицами большой размерности. Прямые методы для таких матриц не дают требуемой точности. В случае разреженных матриц большой размерности итерационные методы дают заметный выигрыш в точности, быстродействии и экономии памяти.

Определение 6. Итерационный метод дается последовательностью

x(k+1) = G_kx(k) + g_k

или

³ ´

x(k+1) = x(k) + Q−_k 1 b − Ax(k) .

G_k называется матрицей перехода, а Q_k – матрицей расщепления, x⁽⁰⁾ предполагается известным начальным приближением.

Определение 7. Метод называется стационарным, если матрица перехода G_k (матрица расщепления Q_k) и не зависят от номера итерации k.

Далее ограничимся рассмотрением стационарных итерационных методов

x(k+1) = Gx(k) + g, G = E − Q−1A, g = Q−1b. (2)

В результате выполнения итерационного метода по начальному приближению строится последовательность

x(0), x(1), x

Рассмотрим погрешность k-й итерации. Пусть x^(∞) – точное решение исходной задачи, т.е.

Ax(∞) = b.

С другой стороны, x^(∞) должно удовлетворять уравнению

x(∞) = Gx(∞) + g.

Тогда погрешность k-й итерации дается формулой ε_k = x^(k)−x^(∞).

Установим для ε_k итерационую формулу. Имеем соотношения

x(1) = Gx(0) + g, x(2) = Gx(1) + g, x(3) = Gx(2) + g,

x

Gx^(k) + g,

...

Вычтем из них уравнение x^(∞) = Gx^(∞) + g. Получим

ε(1)	=	Gε(0),
ε(2)	=	Gε(1),
ε(3)	=	Gε(2),

,

...

Выражая все через погрешность начального приближения ε⁽⁰⁾, получим

ε(1)	=	Gε(0),
ε(2)	=	Gε(1) = G2ε(0),
ε(3)	=	Gε(2) = G2ε(1) = G3ε(0),

,

...

Таким образом, получаем формулу для погрешности на k-й итерации, которой будем пользоваться в дальнейшем:

ε(k) = Gkε(0). (3)

Рассмотрим сходимость итерационного метода (2). Поскольку сходимость метода состоит в том, чтобы погрешность убывала, нужно исследовать сходимость к нулю последовательности ε^(k). Для анализа сходимости нам потребуется понятие спектрального радиуса.

Определение 8. Спектральным радиусом матрицы G называется максимальное по модулю собственное число матрицы G:

ρ(G) = max |λ_i(G)|. i=1...n

Обратим внимание, что в этом определении участвуют все собственные числа, т.е. вещественные и комплексные.

Теорема 3 (Достаточное условие сходимости). Для сходимости итерационного метода достаточно выполнения неравенства

kGk < 1.