2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Сходимость метода Зейделя
Сообщение13.01.2011, 09:42 
TOTAL писал(а):
Приведите здесь точно, что в Бахвалове написано.

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

 
 
 
 Re: Сходимость метода Зейделя
Сообщение13.01.2011, 09:49 
Аватара пользователя
Sonic86 в сообщении #399164 писал(а):
TOTAL писал(а):
Приведите здесь точно, что в Бахвалове написано.

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

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

 
 
 
 Re: Сходимость метода Зейделя
Сообщение13.01.2011, 10:51 
Sonic86 в сообщении #399155 писал(а):
В Бахвалове написано, что $X_n$ сходится, если собственные значения $\lambda$ матрицы $A$ меньше 1 по модулю

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

 
 
 
 Re: Сходимость метода Зейделя
Сообщение13.01.2011, 11:04 
Sonic86 в сообщении #399155 писал(а):
В Бахвалове написано, что $X_n$ сходится, если собственные значения $\lambda$ матрицы $A$ меньше 1 по модулю (или надо $Re \lambda _j < 1$? :roll: )

Для сходимости необходимо и достаточно, чтобы все собственные числа матрицы $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$ положительно определена.

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

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

 
 
 
 Re: Сходимость метода Зейделя
Сообщение13.01.2011, 13:23 

(Оффтоп)

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

 
 
 
 Re: Сходимость метода Зейделя
Сообщение13.01.2011, 13:44 

(Оффтоп)

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

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

 
 
 
 Re: Сходимость метода Зейделя
Сообщение13.01.2011, 14:04 

(Оффтоп)

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

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group