2014 dxdy logo

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

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




 
 диагональное преобладание матрицы
Сообщение18.05.2008, 13:01 
Вопрос такой.
Систему линейных уравнений Ax = b можно привести в виду x = Bx+c, и если норма матрицы B меньше 1, то метод решения системы сходится.
Какие есть способы преобразования Ax = b к x = Bx+c таким образом, чтобы ||B|| гарантированно была меньше 1 (или, что то же самое, добиться диагонального преобладания в матриче A, если оно отсутствует)?

 
 
 
 
Сообщение18.05.2008, 13:12 
да вроде бы никаких. Все способы так или иначе используют какую-либо специфику матрицы. В противном случае ох, и сладкая была бы жизнь.

 
 
 
 
Сообщение19.05.2008, 16:26 
Аватара пользователя
Не совсем понятно, какой метод Вы имеете в виду.
Вот, например, метод простой итерации
$$x^{n}=x^{n-1}+\tau\left(b-Ax^{n-1}\right)$$
сходится, если норма матрицы перехода $S=E-\tau A$ меньше 1.
Если матрица A невырождена, то всегда можно привести систему к виду $$A^TAx=A^Tb$$ и выбрав любое положительное $\tau < 2/||A^TA||$ обеспечить $||S||<1$, т.е. сходимость.

 
 
 
 
Сообщение20.05.2008, 11:43 
[quote="worm2"][/quote]
Этот способ вроде бы подходит, только объясните, почему $\tau принимает именно такие значения для сходимости: $\tau < 2/||A^TA||$

 
 
 
 
Сообщение20.05.2008, 15:48 
Аватара пользователя
Думал, что где-то найду готовое доказательство этого довольно известного факта, да что-то не нашёл.

Написанное мною верно для сингулярной нормы матрицы (т.е. максимального по модулю собственного значения), которая подчинена евклидовой норме вектора.
Пусть $A$ --- положительно определённая матрица, $\tau < 2/||A||$, а $\lambda$ --- собственное значение матрицы $S=E-\tau A$. Оценим $|\lambda|$ сверху:
$$x-\tau Ax = \lambda x$$
$$Ax = \frac{1-\lambda}{\tau} x$$.
учитывая положительную определённость A, а также, что $||A|| < 2/\tau$, т.е. максимальное собственное значение $A$ не превосходит $2/\tau$, получаем: $0 < (1-\lambda)/\tau < 2/\tau$, откуда $|\lambda| < 1$, т.е. $S$ --- матрица, задающая сжимающее отображение, откуда всё и следует.
Если нужно подробнее разжевать, то можно почитать теорему о необходимом и достаточном условии сходимости метода простой итерации (см., например, Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. — Численные методы, гл. 6, пар. 3 "Метод простой итерации").

Пусть теперь $A$ --- произвольная невырожденная матрица. Тогда $A^TA$ --- положительно определённая матрица, и к ней можно применить вышеописанные рассуждения. Отсюда и получается оценка $\tau < 2/||A^TA||$, гарантирующая сходимость.

Добавлено спустя 6 минут 32 секунды:

Предупреждаю, что для плохо обусловленных матриц этот метод катастрофически плох. Дело в том, что число обусловленности матрицы $A^TA$ является квадратом числа обусловленности матрицы $A$. С точки зрения вычислителя это означает: если наилучший метод решения системы $Ax=b$ требует n дополнительных значащих цифр в промежуточных вычислениях, то рассмотренный метод потребует 2n дополнительных значащих цифр.

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


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