Метод простой итерации с оптимальным выбором параметра для с

[.alexey]

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

[ASA]

А поконкретнее? О каком параметре идет речь?

[.alexey]

Метод простой итерации(выбором оптимального параметра) для нелинейного уравнения: Дана функция $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 $$

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

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

[ASA]

В одномерном случае для сходимости метода требуется , чтобы отображение $\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}$. Вот и смотрите, можно это перенести на многомерный случай? Скорее нет, чем да.

[мат-ламер]

.alexey. Не совсем понятно, как Вы определили константы $M$ и $m$ для многомерного случая.

[ASA]

мат-ламер в сообщении #217177 писал(а):

.alexey. Не совсем понятно, как Вы определили константы $M$ и $m$ для многомерного случая.

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

[мат-ламер]

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

[.alexey]

Да, $m$ и $M$ - матрицы.

мат-ламер в сообщении #217251 писал(а):

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

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

Цитата:

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

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

[ASA]

.alexey в сообщении #217342 писал(а):

Есть какая-нибудь более популярная книга, где это можно найти?

Есть куча книг по численным методам. На вскидку:
1. Березин, Жидков
2. Бахвалов (и, кажется, тоже) Жидков
3. Калиткин

.alexey в сообщении #217342 писал(а):

Цитата:

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

Почему только в одномерном?

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

[мат-ламер]

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

[Sharky]

Извините что нагло вклиниваюсь, но чтобы не создавать новый топик - из каких соображений выбирается начальное приближение корня x_0? Просто берется любая граница, или есть какие-то ньюансы?