Сходимость метода Зейделя

[Sonic86]

Вчера решали численно СЛУ. СЛУ $AX=B$ переписывалась в виде $X=B+CX$, а затем решение итерировалось через $X_{n+1}=B+CX_n$. В некоторых случаях $X_n$ сходится, в некотором расходится. В Бахвалове написано, что $X_n$ сходится, если собственные значения $\lambda$ матрицы $A$ меньше 1 по модулю (или надо $Re \lambda _j < 1$? ) (а Калиткин в этом вроде как сомневался), причем говорилось, что переставляя уравнения системы, можно получить разную скорость сходимости (или расходимости) для метода. (препод тоже предлагал переставлять уравнения)
Можно сделать так: положим $x_j = \frac{y_j}{K}$, тогда собственные значения новой матрицы примут вид $\frac{\lambda _j}{K}$. Подбирая $K$ достаточно большим, можно добиться выполнения условия $|\lambda _j| < 1$ (или $Re \lambda _j < 1$), в результате метод будет сходится.
Правильно?
Если да, то почему в книжках об этом не написано (или я не заметил?)?

[TOTAL]

Sonic86 в сообщении #399155 писал(а):

Вчера решали численно СЛУ. СЛУ $AX=B$ переписывалась в виде $X=B+CX$, а затем решение итерировалось через $X_{n+1}=B+CX_n$. В некоторых случаях $X_n$ сходится, в некотором расходится. В Бахвалове написано, что $X_n$ сходится, если собственные значения $\lambda$ матрицы $A$ меньше 1 по модулю (или надо $Re \lambda _j < 1$? ) (а Калиткин в этом вроде как сомневался)

Приведите здесь точно, что в Бахвалове написано.

[Sonic86]

TOTAL писал(а):

Приведите здесь точно, что в Бахвалове написано.

Ой, у меня с собой нету... Я дома скопирую цитату и принесу.

[TOTAL]

Sonic86 в сообщении #399164 писал(а):

TOTAL писал(а):

Приведите здесь точно, что в Бахвалове написано.

Ой, у меня с собой нету... Я дома скопирую цитату и принесу.

Заодно прочитайте, что Бахвалов понимает под методом Зейделя. Сравните со своим "Зейделем".

[Padawan]

Sonic86 в сообщении #399155 писал(а):

В Бахвалове написано, что $X_n$ сходится, если собственные значения $\lambda$ матрицы $A$ меньше 1 по модулю

Может матрицы $C$? Это следует из того, что тогда некоторая степень $C^n$ будет иметь норму меньше $1$. Значит, некоторая степень итерационного оператора будет сжимающей.

[ewert]

Sonic86 в сообщении #399155 писал(а):

В Бахвалове написано, что $X_n$ сходится, если собственные значения $\lambda$ матрицы $A$ меньше 1 по модулю (или надо $Re \lambda _j < 1$? )

Для сходимости необходимо и достаточно, чтобы все собственные числа матрицы $C$ были по модулю меньше единицы (необходимо, поскольку имеется в виду сходимость при любом начальном приближении). Это не метод Зейделя, а метод простых итераций, причём в простейшем варианте -- без введения параметра. Условия сходимости гарантированы, например, диагональным преобладанием матрицы, и когда вам предлагали попереставлять уравнения -- имели в виду, видимо, добиться такой перестановкой именно диагонального преобладания (изредка это возможно).

Sonic86 в сообщении #399155 писал(а):

Можно сделать так: положим $x_j = \frac{y_j}{K}$, тогда собственные значения новой матрицы примут вид $\frac{\lambda _j}{K}$.

Какой такой новой-то?... Матрица $C$ от этой замены не изменится, другим станет $B$, однако сходимость определяется именно матрицей $C$ и совершенно никак не зависит от $B$.

Параметр стандартно вводится совсем по-другому: $\frac{1}{\tau}(\vec x_{n+1}-\vec x_{n})=\vec b-A\vec x_{n}$, т.е. $\vec x_{n+1}=\tau\vec b+\vec x_{n}-\tau A\vec x_{n}$, что соответствует итерационной процедуре для решения уравнения $\vec x=\tau\vec b+C\vec x$, где $C\equiv I-\tau A$. Иногда при удачном выборе $\tau$ удаётся добиться того, чтобы матрица $C$ стала сжимающей. Во всяком случае, для симметричной матрицы $A$ этот трюк помогает тогда и только тогда, когда матрица $A$ положительно определена.

[Sonic86]

Всем большое спасибо! А я думал, что все зависит от $A$, а не от $C$...
Про метод Зейделя я вообще только вчера ночью узнал В следующий раз буду знать.

[ewert]

Кстати, чтоб уж закончить. Необходимость условия $|\lambda_k|<1\ (\forall k)$ вполне очевидна -- иначе будет расходиться последовательность $\vec u_{n+1}=C\vec u_{n}$ (а если нечаянно сойдётся, то у $C$ есть собственное число $\lambda=1$ и, значит, исходная матрица $A$ вырождена). Достаточность этого условия -- факт более трудный. Его доказывают по Padawan'у -- обычно с использованием жорданова представления матрицы. Однако гораздо идейнее (и технически проще) использовать аналитические свойства матрицы $(A-\lambda I)^{-1}$, к тому же этот подход ещё и обобщается без особых изменений и на бесконечномерный случай. Только это требует знания комплексного анализа, который обычно проходят гораздо позже матриц (но, впрочем, раньше численных методов).

[Sonic86]

(Оффтоп)

мдя. К сожалению должен признать, что знаний о маломальской работе с собственными значениями у меня совсем нет . Боюсь, что придется как-то сесть и за полгодика хотя бы их выучить...

[ewert]

(Оффтоп)

Sonic86 в сообщении #399249 писал(а):

мдя. К сожалению должен признать, что знаний о маломальской работе с собственными значениями у меня совсем нет . Боюсь, что придется как-то сесть и за полгодика хотя бы их выучить...

Боюсь, что придётся. Без знания спектральных свойств матриц в анализе итерационных алгоритмов -- никак.

[Sonic86]

(Оффтоп)

да я детям задачку решал просто. Я серьезно пытаюсь только ТЧ заниматься...