Сходящаяся матрица

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

Предыстория

Когда последовательные степени матрицы T становятся малыми (то есть, когда все элементы T приближаются к нулю после возведения T в последовательные степени), матрица T сходится к нулевой матрице. Регулярное расщепление матрицы неособой A T матрице приводит к сходящейся . Полусходящееся расщепление матрицы A приводит к полусходящейся T. матрице Общий итерационный метод сходится для любого начального вектора, если T сходится, а при определенных условиях — если T полусходимо.

Определение

назовем размера n × n Матрицу T , сходящейся матрицей если

$\lim _{k\to \infty }(\mathbf {T} ^{k})_{ij}=0,$ ( 1 )

для каждого i = 1, 2,..., n и j = 1, 2,..., n .

Пример

Позволять

${\begin{aligned}&\mathbf {T} ={\begin{pmatrix}{\frac {1}{4}}&{\frac {1}{2}}\\[4pt]0&{\frac {1}{4}}\end{pmatrix}}.\end{aligned}}$

Вычисляя последовательные степени T , получаем

${\begin{aligned}&\mathbf {T} ^{2}={\begin{pmatrix}{\frac {1}{16}}&{\frac {1}{4}}\\[4pt]0&{\frac {1}{16}}\end{pmatrix}},\quad \mathbf {T} ^{3}={\begin{pmatrix}{\frac {1}{64}}&{\frac {3}{32}}\\[4pt]0&{\frac {1}{64}}\end{pmatrix}},\quad \mathbf {T} ^{4}={\begin{pmatrix}{\frac {1}{256}}&{\frac {1}{32}}\\[4pt]0&{\frac {1}{256}}\end{pmatrix}},\quad \mathbf {T} ^{5}={\begin{pmatrix}{\frac {1}{1024}}&{\frac {5}{512}}\\[4pt]0&{\frac {1}{1024}}\end{pmatrix}},\end{aligned}}$

${\begin{aligned}\mathbf {T} ^{6}={\begin{pmatrix}{\frac {1}{4096}}&{\frac {3}{1024}}\\[4pt]0&{\frac {1}{4096}}\end{pmatrix}},\end{aligned}}$

и вообще,

${\begin{aligned}\mathbf {T} ^{k}={\begin{pmatrix}({\frac {1}{4}})^{k}&{\frac {k}{2^{2k-1}}}\\[4pt]0&({\frac {1}{4}})^{k}\end{pmatrix}}.\end{aligned}}$

С

$\lim _{k\to \infty }\left({\frac {1}{4}}\right)^{k}=0$

и

$\lim _{k\to \infty }{\frac {k}{2^{2k-1}}}=0,$

T — сходящаяся матрица. Обратите внимание, что ρ ( T ) = 1/4 радиус ( где ρ , T ) представляет собой T , спектральный поскольку 1/4 ​ ​ единственное собственное T. значение —

Характеристики

Пусть T — матрица размера n × n . Следующие свойства эквивалентны тому, что T является сходящейся матрицей:

1. $\lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0,$ по какой-то естественной норме;
2. $\lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0,$ для всех естественных норм;
3. $\rho (\mathbf {T} )<1$;
4. $\lim _{k\to \infty }\mathbf {T} ^{k}\mathbf {x} =\mathbf {0} ,$ для каждого х .

Итеративные методы

Основная статья: Итерационный метод

Общий итерационный метод включает в себя процесс преобразования системы линейных уравнений

$\mathbf {Ax} =\mathbf {b}$ ( 2 )

в эквивалентную систему вида

$\mathbf {x} =\mathbf {Tx} +\mathbf {c}$ ( 3 )

для некоторой матрицы T и вектора c . После того, как начальный вектор x ⁽⁰⁾ выбран, последовательность векторов приближенных решений генерируется путем вычисления

$\mathbf {x} ^{(k+1)}=\mathbf {Tx} ^{(k)}+\mathbf {c}$ ( 4 )

для каждого k ≥ 0. Для любого начального вектора x ⁽⁰⁾ ∈ $\mathbb {R} ^{n}$, последовательность $\lbrace \mathbf {x} ^{\left(k\right)}\rbrace _{k=0}^{\infty }$ определяемая формулой ( 4 ), для каждого k ≥ 0 и c ≠ 0, сходится к единственному решению ( 3 ) тогда и только тогда, когда ρ ( T ) <1, то есть T является сходящейся матрицей.

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

Основная статья: Расщепление матрицы

— Разбиение матрицы это выражение, которое представляет данную матрицу как сумму или разность матриц. В приведенной выше системе линейных уравнений ( 2 ) при A несингулярном матрица A может быть разделена, то есть записана в виде разности

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

так что ( 2 ) можно переписать как ( 4 ) выше. Выражение ( 5 ) является регулярным расщеплением A тогда и только тогда, когда B ⁻¹ ≥ 0 и C ≥ 0 , то есть B ⁻¹ и C имеют только неотрицательные записи. Если расщепление ( 5 ) является регулярным расщеплением матрицы A и A ⁻¹ ≥ 0 , тогда ρ ( T ) < 1 и T — сходящаяся матрица. Следовательно, метод ( 4 ) сходится.

Полусходящаяся матрица

назовем размера n × n Матрицу T полусходящейся , если предел

$\lim _{k\to \infty }\mathbf {T} ^{k}$ ( 6 )

существует. Если A , возможно, сингулярна, но ( 2 ) непротиворечива, то есть b находится в диапазоне A , то последовательность, определенная ( 4 ), сходится к решению ( 2 ) для каждого x ⁽⁰⁾ ∈ $\mathbb {R} ^{n}$ тогда и только тогда, когда T полусходится. расщепление ( 5 ) называется полусходящимся A. В этом случае расщеплением

См. также

• Метод Гаусса – Зейделя
• метод Якоби
• Список матриц
• Нильпотентная матрица
• Последовательное чрезмерное расслабление

Ссылки

• Берден, Ричард Л.; Фейрес, Дж. Дуглас (1993), Численный анализ (5-е изд.), Бостон: Приндл, Вебер и Шмидт , ISBN  0-534-93219-3 .
• Исааксон, Юджин; Келлер, Герберт Бишоп (1994), Анализ численных методов , Нью-Йорк: Дувр , ISBN  0-486-68029-0 .
• Карл Д. Мейер-младший; Р. Дж. Племмонс (сентябрь 1977 г.). «Сходящиеся степени матрицы с приложениями к итерационным методам для сингулярных линейных систем». SIAM Journal по численному анализу . 14 (4): 699–705. дои : 10.1137/0714047 .
• Варга, Ричард С. (1960). «Факторизация и нормализованные итерационные методы». В Лангере, Рудольф Э. (ред.). Краевые задачи в дифференциальных уравнениях . Мэдисон: Издательство Университета Висконсина . стр. 121–142. LCCN   60-60003 .
• Варга, Ричард С. (1962), Матричный итеративный анализ , Нью-Джерси: Прентис – Холл , LCCN   62-21277 .