Система нелинейных уравнений: численное решение, сходимость

[cyborg]

Есть система нелинейных уравнений из некоторой прикладной области. Система
произвольной размерности и сильно параметризована. Общий вид системы:
$Y=F(Y)Y $,
где F(Y) - нелинейная по Y матриуа, Y - искомый вектор.
Надо построить численный метод ее решения. При решении столкнулся с прблеммой: не могу доказать сходимость метода простой итерации и найти соответствуещее множество параметров при которых он сходится. Нашел аналитическое выражение Якобина и показал,
что матричные нормы $\|\cdot\|_1, |\cdot\|_2$ от найденного якобиана больше равны единиц, но численное моделирование метода простой итерации дает решение системы.
Подскажите книгу или web-ресурс, где рассматриваются проблеммы существования решения
и сходимости методов для систем нелинейных уравнений. Моя научная деятельност в математике лежит в другой области, поэтому хотелось бы услышать мнение специалиста в этой области или того кто сталкивался с подобными проблемами.

[незваный гость]

С риском обнаружить свою серость при всем честном народе, но не интересует ли Вас условие $\|\rm{F(Y) - E}\| \le \xi < 1$ ($\rm{E}$ - единичная матрица)? Мне кажется, что это - достаточное условие.

[cyborg]

$$Y_{n+1}=F(Y_n)Y_n,\quad \|F(Y)-E\|\leq\xi<1$$

, тогда

$$\|Y_{n+1}-Y_{n}\|=\|F(Y_n)Y_n-Y_n\|=\|(F(Y_n)-E)Y_n\|\leq\|F(Y_n)-E\|\|Y_n\|\leq\xi\|Y_n\|$$

.
Далее получается

$$\|Y_{n+1}-Y_n\|\leq\xi\|Y_0\|$$

, тогда

$$\|Y_{n+p}-Y_n\|\leq\|Y_{n+p}-Y_{n+p-1}\|+\dots+\|Y_n+1-Y_n\|\leq$$

$$\leq(\xi^{n+p-1}+\dots+\xi^n)\|Y_0\|\leq\frac{\xi^n}{1-\xi}\|Y_0\|$$

Так как $\xi^n\to 0$, далее в силу полноты, $\|Y_n- Y^*\|\to 0$. Теперь если предположить, что
$\forall X,Y$ $\|F(X)X-F(Y)Y\|\leq\eta\|X-Y\|$, тогда

$$\|Y_{n+1}-F(Y^*)Y^*\|=\|F(Y_n)Y_n-F(Y^*)Y^*\|\leq\eta\|Y_n-Y^*\|$$

.
И т.к. $\|Y_n-Y^*\|\to 0$, то $F(Y^*)Y^*=Y^*$.
Я правильно вас понял? Большое спасибо за мысль. Буду теперь это условие проверять:-).

[dm]

cyborg писал(а):

...

$$ \|Y_{n+1}-Y_{n}\|=\ldots\leq\xi\|Y_n\|. $$

Далее получается

$$ \|Y_{n+1}-Y_n\|\leq\xi\|Y_0\|, $$

...

Как из первого следует второе?

[1248]

Я там опечатался:
\|F(Y_{n+1}-Y_n\|\leq\xi^n\|Y_0\|
и это может быть и не так, я желаемое выдал за действительное . Спасибо за замечание буду дальше думать...

[незваный гость]

Виноват-с. Работать не будет. Взять, к примеру, одномерный случай, $\rm{F(Y)}=const=1+\xi$. Тогда $\rm{Y}_n=(1+\xi)^n \rm{Y}_0$, и при положительном $\xi$ вельми велико может быть. Сожалею об отнятом у Вас времени.

[1248]

Да ничего. У кого есть какие-либо мысли или книгу какую посоветовать можите. Пишите...

[незваный гость]

Попробую еще раз. Не пинайте строго .

Вблизи точки $\rm{Y^*}$ $\rm{F(Y)Y \sim Y^* + J(Y^*) (Y-Y^*) }$. Тогда, для сходимости нам достаточно, чтобы все собственные числа якобиана $\rm{J(Y^*)}$были по модулю меньше единицы. У меня есть большой соблазн сказать "Есть такая партия! ой, партия зачеркните, норма!" (полунорма, квазинорма), но после прошлого конфуза - не буду. Добавлю лишь одно. Коли посчитать характеристический многочлен якобиана возможно, то у Полиа и Сегье есть хороший раздел о расположению корней полинома в круге. И книжка в библиотеке сей есть. Если будете идти этим путем, постараюсь дать более точную ссылку.

[1248]

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

[незваный гость]

Фокус-покус в том, что нам не нужны корни (а тем более, аналитически). Существуют методы ограничения корней сверху по коэффициентам полинома. Есть и пара легко считаемых необходимых критериев. Например, произведение собственных чисел равно определителю матрицы, а сумма суть ее след. Если все собственные числа в единичном круге, то $|{\rm tr}({\rm J(Y^*)})| = |\sum\limits_{k=1}^{n}\lambda_k| < n$, a $|\det({\rm J(Y^*)})| = |\prod\limits_{k=1}^{n}\lambda_k| < 1$. Еще одно свойство: $\lim\limits_{m \to \infty}\|{\rm J(Y^*)}^m \| = 0$. Если каждый раз возводить матрицу в квадрат (т.е. брать $m=2^k$), то процесс сей довольно быстр.

[незваный гость]

1248 писал(а):

в том числе максималное по модулю собственное значение

Вы не могли бы уточнить - собственное значение какой матрицы? (${\rm F(Y)}$ или $\frac{\partial \rm (F(Y) \cdot Y)}{\partial \rm Y}$). Если якобиана - боюсь, либо это временное/ локальное поведение, либо Вам повезло, и соответсвующий собственный вектор был с нулевым коэффициентом. В общем случае, может, и, наиболее вероятно, будет рассходиться - ну, хотя бы из-за ошибок представления чисел.

[1248]

Да это хорошая мысль на счет того, чтобы максимальное по модулю собственное значения
для любых $Y$ должно лежать в единичном круге. Спасибо. Я что-то там не то в начале подсчитал. Я спектральную норму считал, а она больше единицы. А вот как раз $|\lambda_{\max} {(J(Y))}|$ и в правду меьше единици, когда метод сходится и больше, когда рассходится.

Цитата:

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

Это точно достаточное условие для метода простой итерации в моем случаи или необходимое?

[незваный гость]

Для линейной системы это условие необходимое. Для нелинейной утверждать не рискну, особенно если нигде нет требования непрерывности $F(Y)$. Даже если предположить непрерывность якобиана, все равно мне не очевидно, что нет контрпримера с каким-нибудь хитро закрученным вращением собственных векторов. Хотя, в одномерном случае необходимость есть.

Мне кажется, что достаточность можно доказывать по аналогии с одномерным случаем.