Неизвестный итерационный метод

[Alik]

Возвращаясь к исходному вопросу, как можно теоритически показать, что детерминант матрицы

\[ \begin{gathered} \left[ {\begin{array}{*{20}c} 1 & 0 & 0 & \dots & 0 & {a_{j1}s_1} \\ 0 & 1 & 0 & \dots & 0 & {a_{j2}s_2} \\ 0 & 0 & 1 & \dots & 0 & {a_{j3}s_3} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & a_{jn}{s_n} \\ {a_{j1}} & {a_{j2}} & {a_{j3}} & \dots & {a_{jn}} & 0 \\ \end{array} } \right] \\ \end{gathered} \]

равен произведению последней строки на последний столбец, т.е $det(M)=s_1a_{j1}^2+s_2a_{j2}^2+\dots+s_na_{jn}^2 $

[frankusef]

Return_of_Jedi, Это Вы точно загнули.

[Alik]

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

[ewert]

Евгений Машеров в сообщении #307987 писал(а):

наидешевейший способ использовать для вычислений правило Крамера - это

наидешевейший способ использовать для вычислений правило Крамера - это вовсе его не использовать. С этим согласен.

[Alik]

Повторяю медленно и по слогам: нужно доказать сходимость метода. Для этого можно воспользоваться правилом Крамера. Как будут производиться вычисления - это другой вопрос, beyond the theoretical proof. Убеждать меня в том, что скорость сходимости наверняка будет маленькой не надо, потому что во-первых я это понимаю, а во-вторых задача методическая. Но какой соблазн просто чего-то написать, это ведь легче, чем дать какое-нибудь дельное предложение.

[Евгений Машеров]

Легко указать условия, при которых матрица, используемая в итеративном процессе, не имеет решения (из-за нулевого определителя).
Немногим сложнее построить пример, когда процесс длится бесконечно без приближения к решению.
Возможно, существуют достаточно нетривиальные ограничения на s, при которых процесс сходится, но я их указать не могу (и, похоже, чтобы найти такие s, надо бы сперва решить исходную систему).
Суть метода, собственно, проста. Мы по очереди "подгоняем" решение одного уравнения из системы, перебирая их все поочерёдно, при этом изменяем все x на величины, пропорциональные коэффициентам данного уравнения, умноженным на эти самые s. Величина y есть коэффициент пропорциональности, который и подбирается. Т.е. расширенная матрица здесь "пошлая роскошь" и дань излишней формализации, найти такое y можно куда проще.
При этом растут невязки при других уравнениях, и ни из чего не следует, что (по крайней мере "при произвольных s") общая невязка системы (сумма квадратов, абсолютных величин, максимальная и т.п.) будет непременно уменьшаться.

[Alik]

Евгений Машеров в сообщении #309007 писал(а):

Легко указать условия, при которых матрица, используемая в итеративном процессе, не имеет решения (из-за нулевого определителя).

Для этого нужно вывести (Laplace expansion) формулу определителя:

$det(M_j)=-(a_{j1}^2s_1+a_{j2}^2s_2+\dots+a_{jn}^2s_n) $

пользуясь этим же разложением и правилом Крамера легко показать, что

$y^{(i+1)}=\frac {a_{j1}x_1^{(i)}+a_{j2}x_2^{(i)}+\dots+a_{jn}x_n^{(i)}-b_j} {a_{j1}^2s_1+a_{j2}^2s_2+\dots+a_{jn}^2s_n} $

ну поскольку $x_j^{(i+1)}=x_j^{(i)}+a_{jk}s_ky^{(i+1) $ остается доказать, что $y^{(i+1)} \to 0$

[Евгений Машеров]

О! Сами видите!
Поскольку нигде в условии не указано, что все s>0, очевидно, нулевой знаменатель получается тривиальным образом. То есть появляется необходимое (но явно недостаточное) условие на s.
А теперь построим пример расходимости.
Положим матрицу А единичной, вектор свободных членов нулевым, вектор s единичным. Начальное приближение x=1.
Очевидно, что при любых положительных х величина у будет положительна, как и "поправка" к х.
То есть будем уходить всё далее от решения x=0.

[Alik]

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

[Евгений Машеров]

Ещё раз. Построен контрпример. Показывающий, что процесс, вообще говоря, расходящийся. Поэтому прибегать к тонким методам анализа - всё равно, что требовать ЭЭГ для диагностики смерти мозга, если голову отрезали бензопилой.
Быть может, чего-то удастся добиться, введя некие правила выбора s. Но без этого - не сходится.

[Alik]

ОК, в моей физической задаче условия следующие:
коэффициенты $a_{ij}$ и элементы в правой части $b_j$ - целые, причем вектор $\mathbf{b}$ ненулевой.
константы $s_j$ - положительные, строго больше единицы

[Евгений Машеров]

То, что целые - не даёт ничего. То, что положительные - уже избавляет от деления на ноль. Ненулёвость B, похоже, несущественна. Но вот сходимость...

[Alik]

Евгений Машеров в сообщении #309125 писал(а):

Но вот сходимость...

Очевидно, что нужно представить приближенное решение как точное плюс исчезающая добавка. В методе простой итерации добавка - это геометрическая прогрессия со знаменателем меньше единицы. Нечто подобное будет и здесь если подставить

$y^{(i+1)}=\frac {a_{j1}x_1^{(i)}+a_{j2}x_2^{(i)}+\dots+a_{jn}x_n^{(i)}-b_j} {a_{j1}^2s_1+a_{j2}^2s_2+\dots+a_{jn}^2s_n} $ в $x_j^{(i+1)}=x_j^{(i)}+a_{jk}s_ky^{(i+1)} $

и ввести коэффициент затухания $z^{(i+1)}=\frac{a_{jk}s_k} {a_{j1}^2s_1+a_{j2}^2s_2+\dots+a_{jn}^2s_n} < 1$

Получим $x_j^{(i+1)}=x_j^{(i)}+z^{(i+1)}\Delta x_j^{(i)} $ где $\Delta x_j^{(i)}=a_{j1}x_1^{(i)}+a_{j2}x_2^{(i)}+\dots+a_{jn}x_n^{(i)}-b_j$

Понятно, что $\Delta x_j^{(i)}$ в начале каждого периода $n$ умножается на один и тот же $z^{(i+1)}<1$, т.е. при числе периодов $p \to \infty$ $[z^{(i+1)}]^p\to 0$.

Остаются по крайней мере два главных и два второстепенных вопроса:

I) что происходит с $\Delta x_j^{(i)}$, может быть он увеличивается
II) как записать точное решение системы

1) если $\Delta x_j^{(i)}$ уменьшается, то как это влияет на скорость сходимости
2) какое число периодов $p$ необходимо для сходимости конечное или бесконечное

[Alik]

Я все больше склоняюсь к выводу, что этот метод похож на хаотическую релаксацию
http://www.cs.wisc.edu/techreports/1995/TR1263.pdf
http://www.doc.ic.ac.uk/~dvd03/Documents/asynchronous.pdf
вот только доказать его сходимость пока не удается...

[Return_of_Jedi]

frankusef:

Почему же загнул?

При разложении по минорам считаем:

Третьего порядка - 5 сложений + 12 перемножений.
Четвертого порядка - 23 сложения + 52 перемножения.
Пятого порядка - 119 сложений + 265 перемножений...

Alik, собственно по Вашему методу сказать пока ничего не могу, но если он работает, то в любом случае имеет право на жизнь.

Успехов в дальнейшей его разработке!