диагональное преобладание матрицы

[Kraft]

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

[ewert]

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

[worm2]

Не совсем понятно, какой метод Вы имеете в виду.
Вот, например, метод простой итерации

$$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$, т.е. сходимость.

[Kraft]

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

[worm2]

Думал, что где-то найду готовое доказательство этого довольно известного факта, да что-то не нашёл.

Написанное мною верно для сингулярной нормы матрицы (т.е. максимального по модулю собственного значения), которая подчинена евклидовой норме вектора.
Пусть $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 дополнительных значащих цифр.