2014 dxdy logo

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

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




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

 
 
 
 Re: Система нелинейных равнений
Сообщение13.11.2005, 03:54 
Аватара пользователя
:evil:
С риском обнаружить свою серость при всем честном народе, но не интересует ли Вас условие $\|\rm{F(Y) - E}\| \le \xi < 1$ ($\rm{E}$ - единичная матрица)? Мне кажется, что это - достаточное условие.

 
 
 
 
Сообщение13.11.2005, 16:34 
$$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^*$.
Я правильно вас понял? Большое спасибо за мысль. Буду теперь это условие проверять:-).

 
 
 
 
Сообщение13.11.2005, 16:43 
Аватара пользователя
cyborg писал(а):
...
$$
\|Y_{n+1}-Y_{n}\|=\ldots\leq\xi\|Y_n\|.
$$
Далее получается
$$
\|Y_{n+1}-Y_n\|\leq\xi\|Y_0\|,
$$
...

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

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

 
 
 
 
Сообщение14.11.2005, 06:15 
Аватара пользователя
:evil:

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

 
 
 
 
Сообщение14.11.2005, 15:21 
Да ничего. У кого есть какие-либо мысли или книгу какую посоветовать можите. Пишите...

 
 
 
 
Сообщение14.11.2005, 19:38 
Аватара пользователя
:evil:

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

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

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

 
 
 
 
Сообщение15.11.2005, 20:34 
Аватара пользователя
:evil:
Фокус-покус в том, что нам не нужны корни (а тем более, аналитически). Существуют методы ограничения корней сверху по коэффициентам полинома. Есть и пара легко считаемых необходимых критериев. Например, произведение собственных чисел равно определителю матрицы, а сумма суть ее след. Если все собственные числа в единичном круге, то $|{\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$), то процесс сей довольно быстр.

 
 
 
 
Сообщение15.11.2005, 21:24 
Аватара пользователя
:evil:
1248 писал(а):
в том числе максималное по модулю собственное значение


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

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

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

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

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

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


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