2014 dxdy logo

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

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




 
 Метод простой итерации
Сообщение14.04.2009, 19:20 
Здравствуйте!
Разбираю метод простой итерации. Их вроде бы много разных видов. Тот, который называется методом Якоби, понятен. А ещё есть другой, по которому у меня возник вопрос. так он описывается:
Дана система уравнений: $$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 обозначаются...

 
 
 
 
Сообщение14.04.2009, 19:35 
Имеем право, ибо нам так захотелось -- его ввести, этот параметр, и никто не в силах нам этого запретить.

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

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

 
 
 
 
Сообщение14.04.2009, 19:46 
ewert, в принципе же можно сказать, что $$\tau$$ очень маленькое, так как в равенстве $$x = (b - Ax)\tau + x$$ левые и правые части должны быть приблизительно равны, а при большом $$\tau$$ такого не будет?

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

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

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

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

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

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


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