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

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

СОДЕРЖАНИЕ

• 1 Регулярные расколы
• 2 Матричные итерационные методы
• 3 Пример
  • 3.1 Регулярное расщепление
  • 3.2 Метод Якоби
  • 3.3 Метод Гаусса – Зейделя
  • 3.4 Метод последовательной избыточной релаксации
• 4 См. Также
• 5 Примечания
• 6 Ссылки

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

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

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

( 1)

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

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

( 2)

где B и C - матрицы размера n × n. Если для любого п х п матрицы M, M имеет неотрицательные элементы, мы пишем M ≥ 0. Если M имеет только положительные элементы, мы пишем M gt; 0. Аналогично, если матрица M 1 - M 2 имеет неотрицательные элементы, мы пишем M 1 ≥ M 2.

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

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

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

( 3)

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

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

( 4)

где x ⁽⁰⁾ - произвольный вектор, может быть выполнено. Эквивалентно запишем ( 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 ^-1С имеет неотрицательные записи, если ( 2) представляет собой регулярное расщепление A.

Можно показать, что если ^-1 gt; 0, то lt;1, где представляет собой спектральный радиус из D, и, таким образом, D является матрица сходится. Как следствие, итерационный метод ( 5) обязательно сходится. ${\ Displaystyle \ rho (\ mathbf {D})}$${\ Displaystyle \ rho (\ mathbf {D})}$

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

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

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

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

( 6)

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

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

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

( 7)

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

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

( 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)

Пример

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

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

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

( 10)

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

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

( 11)

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

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

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

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

${\ displaystyle \ mathbf {x} ^ {(m + 1)} = {\ begin {pmatrix} 0 amp; {\ frac {1} {3}} amp; {\ frac {1} {2}} \\ [4pt] {\ frac {1} {4}} amp; 0 amp; {\ frac {1} {2}} \\ [4pt] {\ frac {3} {5}} amp; {\ frac {1} {5}} amp; 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), продемонстрированному выше.

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

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

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

( 14)

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

${\ displaystyle {\ begin {align} amp; \ mathbf {(DL) ^ {- 1}} = {\ frac {1} {120}} {\ begin {pmatrix} 20 amp; 0 amp; 0 \\ 5 amp; 30 amp; 0 \\ 13 amp; 6 amp; 24 \ end {pmatrix }}, \ end {выровнены}}}$

${\ displaystyle {\ begin {align} amp; \ mathbf {(DL) ^ {- 1} U} = {\ frac {1} {120}} {\ begin {pmatrix} 0 amp; 40 amp; 60 \\ 0 amp; 10 amp; 75 \\ 0 amp; 26 amp; 51 \ end { pmatrix}}, \ quad \ mathbf {(DL) ^ {- 1} k} = {\ frac {1} {120}} {\ begin {pmatrix} 100 \\ - 335 \\ 233 \ end {pmatrix}}. \ end {выровнено}}}$

Метод Гаусса – Зейделя ( 8), примененный к задаче ( 10), принимает вид

${\ displaystyle \ mathbf {x} ^ {(m + 1)} = {\ frac {1} {120}} {\ begin {pmatrix} 0 amp; 40 amp; 60 \\ 0 amp; 10 amp; 75 \\ 0 amp; 26 amp; 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) матрицы A в задаче ( 10) для метода последовательной сверхрелаксации, имеем

${\ displaystyle {\ begin {align} amp; \ mathbf {(D- \ omega L) ^ {- 1}} = {\ frac {1} {12}} {\ begin {pmatrix} 2 amp; 0 amp; 0 \\ 0.55 amp; 3 amp; 0 \\ 1.441 и 0.66 и 2.4 \ end {pmatrix}}, \ end {выравниваются}}}$

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

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

Метод последовательной сверхрелаксации ( 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 amp; 2.9062 amp; 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

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

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

Заметки

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

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