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

в математический дисциплина числовая линейная алгебра, а расщепление матрицы это выражение, которое представляет данное матрица как сумма или разность матриц. Много итерационные методы (например, для систем дифференциальные уравнения) зависят от прямого решения матричных уравнений, включающих матрицы более общие, чем трехдиагональные матрицы. Эти матричные уравнения часто можно решить напрямую и эффективно, если записать их в виде разбиения матрицы. Техника была разработана Ричард С. Варга в 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} ^ {(м + 1)} = mathbf {D} ^ {- 1} ( mathbf {U} + mathbf {L}) mathbf {x} ^ {(м) } + mathbf {D} ^ {- 1} mathbf {k}.}$[5][6]

(7)

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

${ Displaystyle mathbf {x} ^ {(м + 1)} = ( mathbf {D} - mathbf {L}) ^ {- 1} mathbf {U} mathbf {x} ^ {(м) } + ( 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 {align} & 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 {align}}}$

(11)

${ displaystyle { begin {align} & 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 {align}}}$

${ displaystyle { begin {align} 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 {выравнивается}}}$

С B⁻¹ ≥ 0 и C ≥ 0, расщепление (11) - регулярное расщепление. С А⁻¹ > 0, спектральный радиус ${ Displaystyle rho ( mathbf {D})}$ <1. (Приблизительный собственные значения из D находятся ${ displaystyle lambda _ {i} приблизительно -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 {align} & mathbf {(DL) ^ {- 1}} = { frac {1} {120}} { begin {pmatrix} 20 & 0 & 0 5 & 30 & 0 13 & 6 & 24 end {pmatrix }}, end {выровнены}}}$

${ displaystyle { begin {align} & mathbf {(DL) ^ {- 1} U} = { frac {1} {120}} { begin {pmatrix} 0 & 40 & 60 0 & 10 & 75 0 & 26 & 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 & 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 {align} & 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 {выравниваются}}}$

${ displaystyle { begin {align} & 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 {выравнивается}}}$

${ displaystyle { begin {align} & 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 & 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

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

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

Примечания

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

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