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

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

Регулярное разделение

Ищем решение матричного уравнения

$\mathbf {A} \mathbf {x} =\mathbf {k} ,$ ( 1 )

где A — заданная матрица размера n × n неособая , а k — заданный вектор-столбец с n компонентами. Разобьем матрицу А на

$\mathbf {A} =\mathbf {B} -\mathbf {C} ,$ ( 2 )

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

Определение: A = B − C является регулярным расщеплением A, если B ⁻¹ ≥ 0 и C ≥ 0 .

Предположим, что матричные уравнения вида

$\mathbf {B} \mathbf {x} =\mathbf {g} ,$ ( 3 )

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

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

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

$\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 имеет неотрицательные элементы, если ( ) представляет собой регулярное разбиение A. 2

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

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

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

Многие итеративные методы можно описать как расщепление матрицы. Если все диагональные элементы матрицы A не равны нулю и мы выражаем матрицу A как матричную сумму

$\mathbf {A} =\mathbf {D} -\mathbf {U} -\mathbf {L} ,$ ( 6 )

где D — диагональная часть матрицы A , а U и L — строго верхние и нижние треугольные матрицы размера n × n соответственно , то имеем следующее.

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

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

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

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

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

$\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 )

Пример

Обычное разделение

В уравнении ( 1 ) пусть

$\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 ), которое используется в методе Якоби: мы разделяем A таким образом, что B состоит из всех диагональных элементов A , а C состоит из всех недиагональных элементов A , отрицаемых . (Конечно, это не единственный полезный способ разбить матрицу на две матрицы.) У нас есть

${\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 )

${\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}}$

${\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}}$

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

Тогда метод ( 5 ), примененный к задаче ( 10 ), принимает вид

$\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 ) есть

$\mathbf {x} ={\begin{pmatrix}2\\-1\\3\end{pmatrix}}.$ ( 13 )

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

$x_{1}^{(m)}$	$x_{2}^{(m)}$	$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 ), продемонстрированному выше.

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

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

$\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 )

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

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

${\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 ), принимает вид

$\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 ) перечислены в таблице ниже, начиная с x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^Т . Из таблицы видно, что метод явно сходится к решению ( 13 ), несколько быстрее, чем описанный выше метод Якоби.

$x_{1}^{(m)}$	$x_{2}^{(m)}$	$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 ) матрицы A в задаче ( 10 ) для метода последовательной перерелаксации, имеем

${\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}}$

${\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}}$

${\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 ), принимает вид

$\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 ) перечислены в таблице ниже, начиная с x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^Т . Из таблицы видно, что метод явно сходится к решению ( 13 ), несколько быстрее, чем описанный выше метод Гаусса–Зейделя.

$x_{1}^{(m)}$	$x_{2}^{(m)}$	$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

См. также

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

Ссылки

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