2014 dxdy logo

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

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




 
 Метод простой итерации с оптимальным выбором параметра для с
Сообщение25.05.2009, 09:33 
Как обосновать метод простой итерации с оптимальным выбором параметра для системы нелинейных уравнений? Есть метод простой итерации с оптимальным выбором параметра для нелинейного уравнения. Если его записать по аналогии для системы уравнений, то он вроде бы тоже работает.
Можно ли использовать оптимальный выбор параметра в методе при решении системы уравнений? Если да, то как это обосновать?

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение25.05.2009, 15:08 
А поконкретнее? О каком параметре идет речь?

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение25.05.2009, 17:26 
Метод простой итерации(выбором оптимального параметра) для нелинейного уравнения:
Дана функция $f(x)$ и отрезок локализации $[a,b]$. 
$$M = \max\limits_{x \in [a,b]} f'(x); m = \min\limits_{x \in [a,b]} f'(x)$$

$$\alpha =\frac 2 {m + M}$$

$\alpha$ - параметр 

$$q = \frac {|M - m|} { |M + m|}$$

$$x^{(n+1)} = x^{(n)} - \alpha * f(x^{(n)})$$

пока $$|x^{(n+1)}-x^{(n)}| > \frac {1-q} {q} \varepsilon $$
Для системы нелинейных уравнений я написал всё аналогично только для матриц и векторов

$$X = \left( \begin{array} {ccc} x_1 \\ x_2 \\ \cdots \\x_n \end{array}  \right)$$

$$F(X) = \left( 
\begin{array} {ccc} 
f_1(x_1, x_2, ..., x_n) \\
f_2(x_1, x_2, ..., x_n) \\
\cdots \\
 f_n(x_1, x_2, ..., x_n) \end{array}  
\right)$$
 
$$F'(X) = \left( 
\begin{matrix} 
\frac {\partial f_1} {\partial x_1} && \frac {\partial f_1} {\partial x_2} && \hdots && \frac {\partial f_1} {\partial x_n} \\
\frac {\partial f_2} {\partial x_1} && \frac {\partial f_2} {\partial x_2} && \hdots && \frac {\partial f_2}{\partial x_n} \\
\vdots && \vdots  && \ddots  && \vdots  \\
\frac {\partial f_n} {\partial x_1} && \frac {\partial f_n} {\partial x_2} && \hdots && \frac {\partial f_n} {\partial x_n} 
\end{matrix}  \right)$$

$$M = \max\limits_{X \in D} F'(X); m = \min\limits_{X \in D} F'(X)$$

D - область локализации

$$\alpha = 2 * (m + M)^{-1}$$

$\alpha$ - параметр 

$$q = \frac {norm(M - m)} { norm(M + m)}$$

$$X^{(n+1)} = X^{(n)} - \alpha * F(X^{(n)})$$

пока $$norm(X^{(n+1)}-X^{(n)}) > \frac {1-q} {q} \varepsilon $$

Так вот, можно ли так писать? Всмысле теоретически будет работать? (на практике работает) Как доказать (обосновать), что это верно? (если верно)

Или скажите, где это прочитать можно?

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение25.05.2009, 23:51 
В одномерном случае для сходимости метода требуется , чтобы отображение $\varphi(x)=x-\alpha f(x)$ было сжимающим. Для этого достаточно, чтобы$|\varphi'(x)|\le q<1$ $\forall x\in [a,b]$. А для этого достаточно, чтобы $f'(x)$ не меняла знак на $[a,b]$. Действительно, пусть для простоты $0<m\le f'(x)\le M$ $\forall x\in [a,b]$. Тогда
$$
-q=-\frac{M-m}{M+m}=1-\alpha M\le\varphi'(x)=1-\alpha f'(x)\le 1-\alpha m=\frac{M-m}{M+m}=q,
$$
если $\alpha=\frac{2}{M+m}$. Вот и смотрите, можно это перенести на многомерный случай? Скорее нет, чем да.

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение26.05.2009, 08:12 
Аватара пользователя
.alexey. Не совсем понятно, как Вы определили константы $M$ и $m$ для многомерного случая.

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение26.05.2009, 11:50 
мат-ламер в сообщении #217177 писал(а):
.alexey. Не совсем понятно, как Вы определили константы $M$ и $m$ для многомерного случая.

Я так понял, что это не константы, а матрицы.

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение26.05.2009, 14:49 
Аватара пользователя
.alexey. Посмотрите книгу Дж.Ортега В.Рейнболдт. "Итерационные методы решения нелинейных систем ...". В частности, метод (7) на стр. 389.

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение26.05.2009, 19:41 
Да, $m$ и $M$ - матрицы.

мат-ламер в сообщении #217251 писал(а):
alexey. Посмотрите книгу Дж.Ортега В.Рейнболдт. "Итерационные методы решения нелинейных систем ...". В частности, метод (7) на стр. 389.

Вряд ли я смогу достать эту книгу. :( В электронном виде её скорее всего нет. А среди библиотек она только в НБ МГУ есть.
Есть какая-нибудь более популярная книга, где это можно найти?

Цитата:
В одномерном случае для сходимости метода требуется , чтобы отображение $\varphi(x)=x-\alpha f(x)$ было сжимающим.

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

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение26.05.2009, 21:58 
.alexey в сообщении #217342 писал(а):
Есть какая-нибудь более популярная книга, где это можно найти?
Есть куча книг по численным методам. На вскидку:
1. Березин, Жидков
2. Бахвалов (и, кажется, тоже) Жидков
3. Калиткин
.alexey в сообщении #217342 писал(а):
Цитата:
В одномерном случае для сходимости метода требуется , чтобы отображение $\varphi(x)=x-\alpha f(x)$ было сжимающим.

Почему только в одномерном?
Конечно же не только в одномерном. Просто в многомерном случае подобрать $\alpha$ (обратимую матрицу, а может и даже какую-нибудь биекцию) не так-то просто.

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение27.05.2009, 16:44 
Аватара пользователя
.alexey. Может попробуйте покопать в следующем направлении. Посмотрите, есть ли аналогия между методом итерации с ускорением и градиентным методом минимизации суммы квадратов невязок. Условие и скорость сходимости градиентного метода посмотрите в учебниках по оптимизации.

 
 
 
 Re: Метод простой итерации с оптимальным выбором параметра для с
Сообщение14.04.2010, 23:28 
Аватара пользователя
Извините что нагло вклиниваюсь, но чтобы не создавать новый топик - из каких соображений выбирается начальное приближение корня x_0? Просто берется любая граница, или есть какие-то ньюансы?

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


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