Расщепление матрицы - Matrix splitting

в математический дисциплина числовая линейная алгебра, а расщепление матрицы это выражение, которое представляет данное матрица как сумма или разность матриц. Много итерационные методы (например, для систем дифференциальные уравнения ) зависят от прямого решения матричных уравнений, включающих матрицы более общие, чем трехдиагональные матрицы. Эти матричные уравнения часто можно решить напрямую и эффективно, если записать их в виде разбиения матрицы. Техника была разработана Ричард С. Варга в 1960 г.^[1]

Регулярные расколы

Мы стремимся решить матричное уравнение

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {k} ,}$

(1)

куда А дано п × п неособый матрица и k дано вектор столбца с п составные части. Разбиваем матрицу А в

${\displaystyle \mathbf {A} =\mathbf {B} -\mathbf {C} ,}$

(2)

куда B и C находятся п × п матрицы. Если для произвольного п × п матрица M, M имеет неотрицательные записи, мы пишем M ≥ 0. Если M имеет только положительные записи, мы пишем M > 0. Аналогично, если матрица M₁ − M₂ имеет неотрицательные записи, мы пишем M₁ ≥ M₂.

Определение: А = B − C это регулярное расщепление A если B⁻¹ ≥ 0 и C ≥ 0.

Считаем, что матричные уравнения вида

${\displaystyle \mathbf {B} \mathbf {x} =\mathbf {g} ,}$

(3)

куда грамм заданный вектор-столбец, может быть решен непосредственно для вектора Икс. Если (2) представляет собой регулярное расщепление А, то итерационный метод

${\displaystyle \mathbf {B} \mathbf {x} ^{(m+1)}=\mathbf {C} \mathbf {x} ^{(m)}+\mathbf {k} ,\quad m=0,1,2,\ldots ,}$

(4)

куда Икс⁽⁰⁾ - произвольный вектор, может быть выполнено. Эквивалентно пишем (4) в виде

${\displaystyle \mathbf {x} ^{(m+1)}=\mathbf {B} ^{-1}\mathbf {C} \mathbf {x} ^{(m)}+\mathbf {B} ^{-1}\mathbf {k} ,\quad m=0,1,2,\ldots }$

(5)

Матрица D = B⁻¹C имеет неотрицательные записи, если (2) представляет собой регулярное расщепление А.^[2]

Можно показать, что если А⁻¹ > 0, тогда ${\displaystyle \rho (\mathbf {D} )}$ <1, где ${\displaystyle \rho (\mathbf {D} )}$ представляет спектральный радиус из D, и поэтому D это сходящаяся матрица. Как следствие, итерационный метод (5) обязательно сходящийся.^[3][4]

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

Матричные итерационные методы

Многие итерационные методы можно описать как разбиение матрицы. Если диагональные элементы матрицы А все ненулевые, и выразим матрицу А как матричная сумма

${\displaystyle \mathbf {A} =\mathbf {D} -\mathbf {U} -\mathbf {L} ,}$

(6)

куда D это диагональная часть А, и U и L соответственно строго верхний и нижний треугольный п × п матрицы, то имеем следующее.

В Метод Якоби можно представить в матричной форме как разбиение

${\displaystyle \mathbf {x} ^{(m+1)}=\mathbf {D} ^{-1}(\mathbf {U} +\mathbf {L} )\mathbf {x} ^{(m)}+\mathbf {D} ^{-1}\mathbf {k} .}$[5][6]

(7)

В Метод Гаусса-Зейделя можно представить в матричной форме как разбиение

${\displaystyle \mathbf {x} ^{(m+1)}=(\mathbf {D} -\mathbf {L} )^{-1}\mathbf {U} \mathbf {x} ^{(m)}+(\mathbf {D} -\mathbf {L} )^{-1}\mathbf {k} .}$[7][8]

(8)

Методика последовательное чрезмерное расслабление можно представить в матричной форме как разбиение

${\displaystyle \mathbf {x} ^{(m+1)}=(\mathbf {D} -\omega \mathbf {L} )^{-1}[(1-\omega )\mathbf {D} +\omega \mathbf {U} ]\mathbf {x} ^{(m)}+\omega (\mathbf {D} -\omega \mathbf {L} )^{-1}\mathbf {k} .}$[9][10]

(9)

Пример

Регулярное расщепление

В уравнении (1), позволять

${\displaystyle \mathbf {A} ={\begin{pmatrix}6&-2&-3\\-1&4&-2\\-3&-1&5\end{pmatrix}},\quad \mathbf {k} ={\begin{pmatrix}5\\-12\\10\end{pmatrix}}.}$

(10)

Применим расщепление (7), который используется в методе Якоби: мы разбиваем А таким образом, что B состоит из все диагональных элементов А, и C состоит из все недиагональных элементов А, отрицается. (Конечно, это не единственный полезный способ разбить матрицу на две матрицы.) У нас есть

${\displaystyle {\begin{aligned}&\mathbf {B} ={\begin{pmatrix}6&0&0\\0&4&0\\0&0&5\end{pmatrix}},\quad \mathbf {C} ={\begin{pmatrix}0&2&3\\1&0&2\\3&1&0\end{pmatrix}},\end{aligned}}}$

(11)

${\displaystyle {\begin{aligned}&\mathbf {A^{-1}} ={\frac {1}{47}}{\begin{pmatrix}18&13&16\\11&21&15\\13&12&22\end{pmatrix}},\quad \mathbf {B^{-1}} ={\begin{pmatrix}{\frac {1}{6}}&0&0\\[4pt]0&{\frac {1}{4}}&0\\[4pt]0&0&{\frac {1}{5}}\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}\mathbf {D} =\mathbf {B^{-1}C} ={\begin{pmatrix}0&{\frac {1}{3}}&{\frac {1}{2}}\\[4pt]{\frac {1}{4}}&0&{\frac {1}{2}}\\[4pt]{\frac {3}{5}}&{\frac {1}{5}}&0\end{pmatrix}},\quad \mathbf {B^{-1}k} ={\begin{pmatrix}{\frac {5}{6}}\\[4pt]-3\\[4pt]2\end{pmatrix}}.\end{aligned}}}$

С B⁻¹ ≥ 0 и C ≥ 0, расщепление (11) - регулярное расщепление. С А⁻¹ > 0, спектральный радиус ${\displaystyle \rho (\mathbf {D} )}$ <1. (Приблизительный собственные значения из D находятся ${\displaystyle \lambda _{i}\approx -0.4599820,-0.3397859,0.7997679.}$) Следовательно, матрица D сходится и метод (5) обязательно сходится для задачи (10). Обратите внимание, что диагональные элементы А все больше нуля, недиагональные элементы А все меньше нуля и А является строго по диагонали.^[11]

Метод (5) применительно к проблеме (10) тогда принимает вид

${\displaystyle \mathbf {x} ^{(m+1)}={\begin{pmatrix}0&{\frac {1}{3}}&{\frac {1}{2}}\\[4pt]{\frac {1}{4}}&0&{\frac {1}{2}}\\[4pt]{\frac {3}{5}}&{\frac {1}{5}}&0\end{pmatrix}}\mathbf {x} ^{(m)}+{\begin{pmatrix}{\frac {5}{6}}\\[4pt]-3\\[4pt]2\end{pmatrix}},\quad m=0,1,2,\ldots }$

(12)

Точное решение уравнения (12) является

${\displaystyle \mathbf {x} ={\begin{pmatrix}2\\-1\\3\end{pmatrix}}.}$

(13)

Первые несколько итераций для уравнения (12) перечислены в таблице ниже, начиная с Икс⁽⁰⁾ = (0.0, 0.0, 0.0)^Т. Из таблицы видно, что метод явно сходится к решению (13), хотя и довольно медленно.

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle x_{3}^{(m)}}$
0.0	0.0	0.0
0.83333	-3.0000	2.0000
0.83333	-1.7917	1.9000
1.1861	-1.8417	2.1417
1.2903	-1.6326	2.3433
1.4608	-1.5058	2.4477
1.5553	-1.4110	2.5753
1.6507	-1.3235	2.6510
1.7177	-1.2618	2.7257
1.7756	-1.2077	2.7783
1.8199	-1.1670	2.8238

Метод Якоби

Как указано выше, метод Якоби (7) совпадает с конкретным регулярным расщеплением (11) продемонстрировано выше.

Метод Гаусса-Зейделя

Поскольку диагональные элементы матрицы А в проблеме (10) все ненулевые, мы можем выразить матрицу А как расщепление (6), куда

${\displaystyle \mathbf {D} ={\begin{pmatrix}6&0&0\\0&4&0\\0&0&5\end{pmatrix}},\quad \mathbf {U} ={\begin{pmatrix}0&2&3\\0&0&2\\0&0&0\end{pmatrix}},\quad \mathbf {L} ={\begin{pmatrix}0&0&0\\1&0&0\\3&1&0\end{pmatrix}}.}$

(14)

Тогда у нас есть

${\displaystyle {\begin{aligned}&\mathbf {(D-L)^{-1}} ={\frac {1}{120}}{\begin{pmatrix}20&0&0\\5&30&0\\13&6&24\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}&\mathbf {(D-L)^{-1}U} ={\frac {1}{120}}{\begin{pmatrix}0&40&60\\0&10&75\\0&26&51\end{pmatrix}},\quad \mathbf {(D-L)^{-1}k} ={\frac {1}{120}}{\begin{pmatrix}100\\-335\\233\end{pmatrix}}.\end{aligned}}}$

Метод Гаусса-Зейделя (8) применительно к проблеме (10) принимает вид

${\displaystyle \mathbf {x} ^{(m+1)}={\frac {1}{120}}{\begin{pmatrix}0&40&60\\0&10&75\\0&26&51\end{pmatrix}}\mathbf {x} ^{(m)}+{\frac {1}{120}}{\begin{pmatrix}100\\-335\\233\end{pmatrix}},\quad m=0,1,2,\ldots }$

(15)

Первые несколько итераций для уравнения (15) перечислены в таблице ниже, начиная с Икс⁽⁰⁾ = (0.0, 0.0, 0.0)^Т. Из таблицы видно, что метод явно сходится к решению (13), несколько быстрее, чем описанный выше метод Якоби.

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle x_{3}^{(m)}}$
0.0	0.0	0.0
0.8333	-2.7917	1.9417
0.8736	-1.8107	2.1620
1.3108	-1.5913	2.4682
1.5370	-1.3817	2.6459
1.6957	-1.2531	2.7668
1.7990	-1.1668	2.8461
1.8675	-1.1101	2.8985
1.9126	-1.0726	2.9330
1.9423	-1.0479	2.9558
1.9619	-1.0316	2.9708

Метод последовательного чрезмерного расслабления

Позволять ω = 1.1. Используя расщепление (14) матрицы А в проблеме (10) для метода последовательной сверхрелаксации имеем

${\displaystyle {\begin{aligned}&\mathbf {(D-\omega L)^{-1}} ={\frac {1}{12}}{\begin{pmatrix}2&0&0\\0.55&3&0\\1.441&0.66&2.4\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}&\mathbf {(D-\omega L)^{-1}[(1-\omega )D+\omega U]} ={\frac {1}{12}}{\begin{pmatrix}-1.2&4.4&6.6\\-0.33&0.01&8.415\\-0.8646&2.9062&5.0073\end{pmatrix}},\end{aligned}}}$

${\displaystyle {\begin{aligned}&\mathbf {\omega (D-\omega L)^{-1}k} ={\frac {1}{12}}{\begin{pmatrix}11\\-36.575\\25.6135\end{pmatrix}}.\end{aligned}}}$

Метод последовательной сверхрелаксации (9) применительно к проблеме (10) принимает вид

${\displaystyle \mathbf {x} ^{(m+1)}={\frac {1}{12}}{\begin{pmatrix}-1.2&4.4&6.6\\-0.33&0.01&8.415\\-0.8646&2.9062&5.0073\end{pmatrix}}\mathbf {x} ^{(m)}+{\frac {1}{12}}{\begin{pmatrix}11\\-36.575\\25.6135\end{pmatrix}},\quad m=0,1,2,\ldots }$

(16)

Первые несколько итераций для уравнения (16) перечислены в таблице ниже, начиная с Икс⁽⁰⁾ = (0.0, 0.0, 0.0)^Т. Из таблицы видно, что метод явно сходится к решению (13), немного быстрее, чем описанный выше метод Гаусса-Зейделя.

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle x_{3}^{(m)}}$
0.0	0.0	0.0
0.9167	-3.0479	2.1345
0.8814	-1.5788	2.2209
1.4711	-1.5161	2.6153
1.6521	-1.2557	2.7526
1.8050	-1.1641	2.8599
1.8823	-1.0930	2.9158
1.9314	-1.0559	2.9508
1.9593	-1.0327	2.9709
1.9761	-1.0185	2.9829
1.9862	-1.0113	2.9901

Смотрите также

• Список тем разбиения операторов
• Разложение матрицы
• М-матрица
• Матрица Стилтьеса

Примечания

1. Варга (1960)
2. Варга (1960 г., стр. 121–122).
3. Варга (1960 г., стр. 122–123).
4. Варга (1962 г., п. 89)
5. Бремя и ярмарки (1993, п. 408)
6. Варга (1962 г., п. 88)
7. Бремя и ярмарки (1993, п. 411)
8. Варга (1962 г., п. 88)
9. Бремя и ярмарки (1993, п. 416)
10. Варга (1962 г., п. 88)
11. Бремя и ярмарки (1993, п. 371)

Рекомендации

• Бэрден, Ричард Л .; Фэрс, Дж. Дуглас (1993), Числовой анализ (5-е изд.), Бостон: Приндл, Вебер и Шмидт, ISBN  0-534-93219-3.
• Варга, Ричард С. (1960). «Факторизация и нормализованные итерационные методы». В Лангере, Рудольф Э. (ред.). Краевые задачи в дифференциальных уравнениях.. Мэдисон: University of Wisconsin Press. С. 121–142. LCCN  60-60003.
• Варга, Ричард С. (1962), Матричный итерационный анализ, Нью-Джерси: Prentice-Hall, LCCN  62-21277.