Метод итераций для СЛАУ Анализ сходимости

[eugrita]

При описании итерационного метода решения систем линейных уравнений $A\vec{x}=\vec{b}$ оно записывается в виде
$\vec{X}^{k+1}=B \cdot \vec {X}^k+\vec{d}$ где $B=E-A^t \cdot H$ и $H=\operatorname{diag}(A)^{-1}$ (по простому $b_{ij}=-a_{ij}/a_{ii}$ при $j \ne i $ и $b_{ii}=0$
обычно указывается
(а) эквивалентное условие его сходимости - все собственные значения по модулю <1 и
(б)достаточное условие сходимости-т.н. диагональное преобладание.
Никто как правило не указывает примеры сходимости при отсутствии диагонального преобладания.
У меня получается эквивалентность (а) и (б) но для случая симметричного оператора.
В самом деле, симметричная матрица B получается ортогональным преобразованием из диагональной матрицы собств значений $\Lambda$ так $B=T^{-1}\cdot \Lambda \cdot T$
В качестве нормы рассмотрим бесконечную норму $||B||=\max(|A_{ij}|)$ очевидно $||\Lambda||<1, ||T||<1$, $T^{-1}$ тоже ортогональна и совпадает с транспонированной поэтому и $ ||T^{-1}||<1$ по свойству субмультипликативности для норм
$||B||\leqslant ||T^{-1}|| \cdot ||\Lambda|| \cdot||T|| < 1$.
Верно ли это?
А вот для несимметричных операторов этот способ уже не проходит и если и искать примеры
сходимости метода с каким -то $| B_{ij}| >1$ то в классе несимметричных матриц.

2)Вообще для метода итераций можно получать разные матрицы хотя бы путем замены некоторых уравнений линейными комбинациями (простейший случай- перестановка уравнений). При этом совершенно непонятно когда может получиться матрица с диагональным преобладанием или с $\lambda _i <1$

[Andrey_Kireew]

Итеративный процесс сходится, когда отображение аргумента рекуррентного соотношения является сжимающим.
В Вашем случае, условие сходимости
$\left\lVert \frac{\partial}{\partial \vec {X}}(B \cdot \vec {X}^k+\vec{d})\right\rVert<1 $ или $\left\lVert B\rVert<1 $.
Получается, что верно.

[eugrita]

Все и так знают что $||B|| <1$ есть достаточное условие сходимости и тем самым, сжимающего отображения
Я же ищу матрицы с $||B|| \ge 1$ но с собств числами по модулю меньше 1
Среди симметричных их нет
Они вообще есть или их нет?

[Andrey_Kireew]

По крайней мере для спектральной нормы - ответ очевиден, так как она равна максимальному по модулю собственному числу.

[eugrita]

я имел и имею ввиду только максимальную норму или диагональное преобладание

[eugrita]

В некоторых курсах выделяют даже утверждение: любая норма матрицы не меньше ее спектрального радиуса, но дальше этого до примеров не идут
см также https://dxdy.ru/topic21988.html

[ewert]

eugrita в сообщении #1395565 писал(а):

Я же ищу матрицы с $||B|| \ge 1$ но с собств числами по модулю меньше 1

Возьмите любую нильпотентную матрицу -- любая её норма может быть сделана сколь угодно большой.

[eugrita]

ewert в сообщении #1395602 писал(а):

eugrita в сообщении #1395565 писал(а):

Я же ищу матрицы с $||B|| \ge 1$ но с собств числами по модулю меньше 1

Возьмите любую нильпотентную матрицу -- любая её норма может быть сделана сколь угодно большой.

спасибо как всегда evert Помню вас
Но нильпотентная матрица для примеров студентам должна быть закамуфлирована, т.е. чтобы по ее виду трудно было догадаться что все собств зн=0
А обычные жордановы клетки с кратным с.з <1 не подойдут? Из них путем поворота можно было бы наделать пристойные примеры того что надо

[eugrita]

Боюсь, что тема посвящена второстепенному вопросу если первостепенным считать применимость метода итераций СЛАУ.При решении СЛАУ разрешены преобразования (сложение уравнений с неким весом, изменяющие спектр матрицы. И, главное в итерационном методе видимо продумать алгоритм, приводящий матрицу к диагональному преобладанию. Легче всего путем преобразований сделать эл-ты главной диагонали максимальными по модулю в строке наподобие метода Гаусса с выбором главного элемента. Но этого недостаточно для диагонального преобладания и непонятно как изменится спектральный радиус - может станет больше может меньше 1
Хорошо бы понять и доказать какие матрицы принципиально нельзя привести к диагональному преобладанию за счет операций 2 типов а)сложение с весом строк б) перестановка столбцов (изменение последовательности неизвестных)

[Евгений Машеров]

Только вырожденные. Любую невырожденную матрицу можно Гауссом привести к единичной.

[ewert]

eugrita в сообщении #1395876 писал(а):

А обычные жордановы клетки с кратным с.з <1 не подойдут? Из них путем поворота можно было бы наделать пристойные примеры того что надо

Ну, если нужны демонстрационные матрицы, то их лучше сочинять программно. Скажем, взять нильпотентную матрицу, умножить на большое число и потом слегка зашумить, т.е. прибавить к ней маленькую случайную. С единичной вероятностью все собственные числа разойдутся -- но останутся, конечно, маленькими. А потом просто из предъявленных компьютером вариантов выбрать то, что приятнее для глаза.

eugrita в сообщении #1396153 писал(а):

И, главное в итерационном методе видимо продумать алгоритм, приводящий матрицу к диагональному преобладанию.

Главное совсем наоборот -- вовсе не задаваться таким вопросом. Я в курсе, что такая постановка задачи модна как учебная; но она абсолютно бессмысленна с практической точки зрения. Поскольку никакого мало-мальски универсального алгоритма нет. А ловить блох (или чего там делают коты, когда им заняться нечем) необходимости не вижу.

[eugrita]

ewert в сообщении #1397001 писал(а):

eugrita в сообщении #1395876 писал(а):

А обычные жордановы клетки с кратным с.з <1 не подойдут? Из них путем поворота можно было бы наделать пристойные примеры того что надо

Ну, если нужны демонстрационные матрицы, то их лучше сочинять программно. Скажем, взять нильпотентную матрицу, умножить на большое число и потом слегка зашумить, т.е. прибавить к ней маленькую случайную. С единичной вероятностью все собственные числа разойдутся -- но останутся, конечно, маленькими. А потом просто из предъявленных компьютером вариантов выбрать то, что приятнее для глаза.

eugrita в сообщении #1396153 писал(а):

И, главное в итерационном методе видимо продумать алгоритм, приводящий матрицу к диагональному преобладанию.

Главное совсем наоборот -- вовсе не задаваться таким вопросом. Я в курсе, что такая постановка задачи модна как учебная; но она абсолютно бессмысленна с практической точки зрения. Поскольку никакого мало-мальски универсального алгоритма нет. А ловить блох (или чего там делают коты, когда им заняться нечем) необходимости не вижу.

Ладно. Давайте вообще метод итераций для СЛАУ выбросим на помойку. и не будем пудрить мозги студентам. Ничем не лучше других, а головной боли много. Так и нет понятного эквивалентного критерия спектрального радиуса <1. Он теоретически интересен условиями сжимающего отображения а практическая значимость видимо=0

[ewert]

eugrita в сообщении #1398360 писал(а):

Давайте вообще метод итераций для СЛАУ выбросим на помойку. и не будем пудрить мозги студентам.

Давайте лучше немного подумаем. Любой метод предназначен для тех случаев, для которых он предназначен. Метод простых итераций работает в двух стандартных ситуациях: если есть диагональное преобладание или если матрица положительна. Оба варианта взяты отнюдь не с потолка -- если одно или другое в приложениях появляется, то по вполне принципиальным причинам, и появляется достаточно часто. А вот добиться диагонального преобладания, если его не было изначально, невозможно приблизительно со стопроцентной вероятностью. Отсюда и вывод -- чем следует пудрить мозги студентам и чем не следует.

[Mikhail_K]

eugrita в сообщении #1398360 писал(а):

Давайте вообще метод итераций для СЛАУ выбросим на помойку

ewert в сообщении #1398362 писал(а):

Метод простых итераций работает в двух стандартных ситуациях: если есть диагональное преобладание или если матрица положительна.

ewert в сообщении #1398362 писал(а):

А вот добиться диагонального преобладания, если его не было изначально, невозможно приблизительно со стопроцентной вероятностью.

Добавлю к этому, что добиться выполнения второго условия (положительности матрицы) как раз можно. А именно, перейти от исходной системы $Ax=b$ к системе $A^TAx=A^Tb$ (если система комплексная, то $A^*Ax=A^*b$). Если исходная матрица квадратная и невырожденная (а только в этом случае можно вообще надеяться на метод простой итерации), то получится эквивалентная система с положительной матрицей.

ewert в сообщении #1398362 писал(а):

А вот добиться диагонального преобладания, если его не было изначально, невозможно приблизительно со стопроцентной вероятностью.

Ну, можно попытаться привести матрицу к диагональному виду, вот и будет диагональное преобладание)) Правда, после этого оно уже будет не нужно)) Полностью согласен, что такого рода задания суть запудривание мозгов.

[ewert]

Mikhail_K в сообщении #1398366 писал(а):

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

Да, только следует считаться с одним крайне неприятным обстоятельством: умножение на сопряжённую матрицу сильно портит число обусловленности (оно возводится в квадрат). А за скорость сходимости итерационного процесса отвечает именно число обусловленности -- чем оно выше, тем ближе знаменатель соответствующей геометрической прогрессии к единице.