Метод простой итерации

[iludus]

Здравствуйте!
Разбираю метод простой итерации. Их вроде бы много разных видов. Тот, который называется методом Якоби, понятен. А ещё есть другой, по которому у меня возник вопрос. так он описывается:
Дана система уравнений:

$$Ax = b.$$

Тогда

$$0 = b - Ax,$$

$$x = b - Ax + x,$$

$$x = (b - Ax)\tau + x,$$

$$x = (E - \tau A)x + \tau b, $$

$$x = Bx + \tau b,$$

где

$$B = E - \tau A.$$

Последней формула

$$x = Bx + \tau b$$

и является итерационной.

Вопрос в следующем - откуда тут берётся параметр

$$\tau << 1$$

? Почему мы имеем право его писать? И ещё одно: E - это единичная матрица? Или что-то другое? Потому что единичные матрицы обычно же через I обозначаются...

[ewert]

Имеем право, ибо нам так захотелось -- его ввести, этот параметр, и никто не в силах нам этого запретить.

Стандартно: оператор в правой части будет гарантированно сжимающим, если исходный оператор $A$ эрмитов и, более того, строго положителен, и если тау меньше удвоенной нормы оператора, обратного к нему. Ну т.е. фактически -- произведение тау на максимальное собственное число $A$ должно быть меньше двух.

На практике норма исходного оператора (т.е. его максимальное собственное число) обычно очень большая, потому и тау требуется очень маленькая. Т.е. метод работает, но (на практике) удручительно медленно.

[iludus]

ewert, в принципе же можно сказать, что

$$\tau$$

очень маленькое, так как в равенстве

$$x = (b - Ax)\tau + x$$

левые и правые части должны быть приблизительно равны, а при большом

$$\tau$$

такого не будет?

[ewert]

Нет, нельзя так говорить. Тут откровенно подразумевается, что уравнение (в смысле система, но какая разница) после этого будет решаться стандартной итерационной схемой $x_{n+1}=F(x_n)$, где $F$ -- оператор, стоящий в правой части, и притом сжимающий. Ну так гарантируется это именно при указанных ограничениях. Тут размахивание руками не поможет, оценки должны быть честными. И, в частности, положительность исходного оператора -- важна по существу.

[iludus]

ewert, спасибо за ответ! Насколько я понимаю, метод будет нормально работать, если у нас у матрицы А диагональные элементы сильно больше остальных?
А вообще существуют какие-то универсальные "хорошие" численные методы для решения систем линейных уравнений, или они подбираются исходя из задачи?

[ewert]

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

[iludus]

ewert, а вот математические пакеты всякие вроде Maple - они же наверное используют что-то одно для всех систем? Вряд ли ведь они по методу простой итерации считают? Есть же какие-то более современные алгоритмы?

[мат-ламер]

Пока ewert молчит рискну вставить свои пять копеек. Насчёт Maple ничего не знаю, так как приходилось численно решать уравнения только в Матлабе. Подозреваю, что итерационные методы в нём используются оганичено, так как большей частью требуют априорных знаний о спектре матрицы. В Матлабе используется метод сопряжённых градиентов и родственные ему (для несимметричных матриц), которые не требуют знания спектра матриц. Предварительно матрицу можно преобразовать, чтобы она имела лучшую обусловленность.