%\documentstyle{report}
%\documentclass{report }

%\usepackage[cp866]{inputenc}
%\usepackage[cp1251]{inputenc}

%\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\documentclass[12pt,a4paper]{article}
%\usepackage[cp866]{inputenc}
\usepackage{pscyr}
\usepackage[cp1251]{inputenc}

\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
%\twocolumn \oddsidemargin =-2cm \topmargin -3cm \textheight=27cm
%\textwidth=17cm 
\textheight 22cm \textwidth 16cm \topmargin 0cm \oddsidemargin 0cm \evensidemargin 0cm
\pagestyle{empty}
\begin{document}
{\footnotesize Численные методы решения нелинейных систем

$f(x)=0, x=(x_1,\ldots,x_n),f=(f_1,\ldots,f_n)$
Как и в случае линейных систем отсутствует единый алгоритм нахождения корней и
более того, как правило, нет единственности.
1. Скалярное уравнение $f(x)=0$

т. Если 1) $f(x)\in C^2_{[a,b]}$

2) $f(a)f(b)<0$

3) $f"<0$ или $f''>0$

тогда уравнение $f(x)=0$ имеет единственное решение

Наиболее надежными и действенными методами в этом случае

a) метод деления отрезка пополам, т.е. отделения отрезка $[a_1,b_1]\in [a,b]$,
содержащего корень уравнения пользуясь правилом
$c_1=\frac{b-a}{2}, f(c_1)f(a)<0 \to a_1=a, b_1=c_1, f(c_1)f(a)>0,
a_1=c_1,b_1=b$ $\to |c_n-x^*|<\frac{|b-a|}{2^{n+1}}$

б) метод хорд

В этом случае точка с выбирается как точка пересечения хорды, соединяющей точки
$(a,f(a))$ ,$(b,f(b))$  с осью абсцисс т.е.

$c_n=\frac{a_nf(b_n)-b_nf(a_n)}{b_n-a_n}$

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

В реализации же наиболее простыми методами являются все же итерационные методы,
основанные на принципе сжимающих отображении

т. Если отображение  $\varphi(x)$ на некотором отрезке $R=\{ |x-x_0|<r\}$
удовлетворяет

а) условию Липшица $\forall x', x''\in R$
$|\varphi(x')-\varphi(x'')|\leq \alpha  |x'-x''|$ с постоянной
$\alpha$,  удовлетворяющей условию $0<\alpha<1$

б) в точке $x_0$ имеет место неравенство

$|x_0-\varphi(x_0)|\leq(1-\alpha)r$,

тогда на отрезке R уравнение $x=\varphi(x)$  имеет единственный
корень $x=x^*$,  который может быть найден как предел
последовательности построенной по рекуррентному правилу
$x^{k+1}=\varphi(x^k), x^0\in R$  и имеет место оценка

$|x^k-x^*|\leq \frac{\alpha}{1-\alpha}|x^k-x^{k-1}|$, которая
фактически является критерием окончания итерационного процесса для
нахождения решения с заданной точностью.

Док-во:

a)Покажем, что отображение $\varphi:R\to R$. Пусть $x\in R$, тогда
$|\varphi(x)-x_0|=|\varphi(x)\pm\varphi(x_0)-x_0|\leq
|\varphi(x)-\varphi(x_0)|+|\varphi(x_0)-x_0|\leq
\alpha|x-x_0|+(1-\alpha)r\leq r$

б) покажем, что отображение $\varphi$  сжимающее т.е. $ \forall
x,y \in R, |\varphi(x)-\varphi(y)|\leq \alpha |x-y|$ - фактически
это условие Липшица. И следовательно из принципа сжимающих
отображений следует сходимость последовательности $\{
x^{k+1}=\varphi(x^k)\}\rightarrow_{k\to\infty} x^*=\varphi(x^*)$

в) критерий окончания:

$x^k=\varphi(x^{k-1}$ $x^*=\varphi(x^*)$,  вычитая из второго
равенства первое  будем иметь

$|x^*-x^k|=|\varphi(x^*)-\varphi(x^{k-1}|\leq \alpha
|x^*-x^{k-1}|$, с другой стороны
$|x^*-x^{k-1}|=|\varphi(x^*)-x^{k-1}+x^k-x^k|=|\varphi(x^{k-1})|\leq
|x^k-x^{k-1}|+|\varphi(x^*)-\varphi(x^{k-1})|\leq |x^k-x^{k-1}|+\alpha
|x^*-x^{k-1}|\to$

$|x^*-x^{k-1}|\leq\frac{|x^k-x^{k-1}|}{1-\alpha}$

$|x^*-x^k|\leq\alpha|x^*-x^{k-1}|\leq\frac{\alpha}{1-\alpha}|x^k-x^{k-1}|$,
таким образом из неравенства

$|x^k-x^{k-1}|\leq\frac{1-\alpha}{\alpha}\epsilon\to |x^*-x^k|\leq
\epsilon$

Замечание: неравенство Липшица выполнено если
$|\varphi'|\leq\alpha<1$, следствие формулы конечных приращений
Лагранжа.

Геометрическая интерпретация:
\begin{figure}
%\includegraphics[width=2.5in,height=1.5in]{gr7_1.eps}
\caption{$ x=\varphi(x),\quad 0< \varphi '<-1$}
\end{figure}
\begin{figure}
%\includegraphics[width=2.5in,height=1.5in]{gr7_2.eps}
\caption{ $x=\varphi(x), \quad -1<\varphi '<0 $}
\end{figure}


Пример: $ x=\frac 1 2 (x+ \frac a x), x^*=\sqrt x, a\in(0.5,1),
R=[a,1], x^0=\frac{1+a}{2}, r=\frac{1-a}{2}, \varphi(x)=\frac 1 2
(x+\frac a x), \alpha =?,
\alpha=\max_{x\in[a,1]}|\varphi'(x)|=\max_{x\in[a,1]}|\frac 1 2
(1-\frac a {x^2})|=\frac{1-a}{2a}\leq \frac 1 2 $,

$|x^0-\varphi(x^0)|=|\frac {1+a}{2}-\frac 1 2 (\frac
{1+a}{2}+\frac {2a}{1+a}|=\frac 1 4 \frac {(1-a^2)}{1+a}=\frac
{1-a}{2} \frac 1 2= r(1-r)$

Метод Ньютона. Уравнение $f(x)$ представим в виде: $ x=x+\lambda
f(x),\lambda\neq 0$ и построим последовательность по методу
простой итерации $x^{k+1}=x^k+\lambda f(x^k)=\varphi(x^k)$,
скорость сходимости будет тем выше, чем меньше
$|\varphi'=1+\lambda f'(x)|$.  Выберем $\lambda$  из условия
$\varphi'=1+\lambda f'=0,$ на к-шаге. Следовательно
$\lambda=-\frac 1{f'(x^k)}$

$x^{k+1}=x^k-\frac{f(x^k)}{f'(x^k)}$.  Итерационный процесс,
построенный по этому правилу называют методом Ньютона. Метод имеет
простую геометрическую интерпретацию: в точке $x^0$ к функции
$f(x)$  проводим касательную, уравнение которой есть
$y=f(x^0)+(x-x^0)f'(x^0)$  и $x^1$ выбираем из условия пересечения
касательной с осью абсцисс. В результате будем иметь
$x^1=x^0-\frac {f(x^0)}{f'(x^0)}$ и т.д. Геометрически каждый раз
мы заменяем отрезок дуги кривой касательной и нахождению точки ее
пересечения с осью абсцисс. Из рисунка видно, что
последовательность, построенная таким образом сходится к корню
уравнения $f(x)=0$ для выпуклых функций причем монотонно.

 Скорость  сходимости метода Ньютона.

 Опр. Будем говорить, что итерационный процесс сходится к $x^*$ со
 скоростью "p",  если имеет место оценка $|x^k-x^*|\leq
 \alpha|x^*-x^{k-1}|^p,0<\alpha<1$.

 Пусть $x*-$ точное решение уравнения $f(x^*)\equiv0$. Обозначим
 через $\omega$  интервал концами которого являются точки
 $x^0$и$x^*$. Тогда

 1) $|f(x^{k-1})|=|f(x^*)-f(x^{k-1})|=$

$\hbox{из формулы
  конечных приращений Лагранжа}=$

  $f'(\xi)|x^*-x^{k-1}|\geq
  \min_{\xi\in \omega}|f'||x^*-x^{k-1}|,
  m_1=\min_{\xi\in\omega}|f'(\xi)|$

2) $|x^k-x^{k-1}|=| \frac{f(x^{k-1})}{f'(x^{k-1})}| \geq
\frac{m_1}{M_1}|x^*-x^{k-1}| ,M_1=\max_{\xi\in\omega}|f'(\xi)|$

3) $|x^*-x^{k-1}|=|x^*-x^k+x^k-x^{k-1}|=$ {в силу
монотонности последовательности }$=|x^*-x^k|+|x^k-x^{k-1}|\to$

$|x^*-x^k|=|x^*-x^{k-1}|-|x^k-x^{k-1}|\leq|1-\frac
{m_1}{M_1})|x^*-x^{k-1}|$,  в силу определения постоянных
$m_1,M_1$, $0<\alpha=(1-\frac{m_1}{M_1})<1$ и следовательно
процесс Ньютона сходится к $x^*$. Покажем, что скорость сходимости
процесса Ньютона будет квадратичной в окрестности $x^*$. Используя
формулу Тейлора в окрестности т $x^{k-1}$ имеем $
f(x^*)=f(x^{k-1})+f'(x^{k-1})(x^*-x^{k-1})+\frac
{f''(\xi)}{2}(x^*-x^{k-1})^2,\xi\in\omega\to$
$x^*=x^{k-1}-\frac{f(x{k-1})}{f'(x^{k-1})}-(x^*-x^{k-1})^2\frac{f''(\xi)}{2f'(x^{k-1})}$
Вычитая это равенство из
$x^k=x^{k-1}-\frac{f(x{k-1})}{f'(x^{k-1})}$ будем иметь
$x^k-x^*=(x^*-x^{k-1})^2\frac{f''(\xi)}{2f'(x^{k-1})}\to$,что
$|x^k-x^*|=|x^*-x^{k-1}|^2|\frac{f''(\xi)}{2f'(x^{k-1})}|\leq
\frac {M_2}{2m_1}|x^*-x^{k-1}|,M_2=\max_{\xi\in\omega}|f''(\xi)|$.
Обозначим $\beta=\frac{M_2}{2m_1}=?<1$. Умножим последнее
равенство на $\beta$ в результате будем иметь $\beta
|x^k-x^*|\leq\beta^2|x^*-x^{k-1}|^2$, откуда следует, что в силу
сходимости процесса, начиная с некоторого номера сходимость будет
квадратичной.  пример: $f(x)=x^2=0,x^*=0$
$x^k=x^{k-1}-\frac{f(x^{k-1})}{f'(x^{k-1})}=x^{k-1}-\frac{(x^{k-1})^2}
{2x^{k-1}}=\frac{1}{2}x^{k-1}\to_{k\to\infty}0$

метод простой итерации в этом случае:

$x^{k+1}=x^k-(x^k)^2 $  и если $|\varphi'=(1-2x)|<1$ то процесс
будет сходится.

Системы нелинейных алгебраических уравнений

$f(x)=0,\quad x=(x_1,\ldots,x_n),\quad f=(f_1,\ldots,x_n),$ $x \in
R_n$,$\rho=||x-y||$,Мн-во: $S(x_0,r)=\{x:||x-x_0||\leq r\}$-
назовем замкнутым шаром радиуса $r$ с центром в точке $x_0$.
Заметим, что любой замкнутый шар в $R_n$- образует полное
метрическое пространство. Как и в случае скалярного уравнения
исходное  уравнение приведем к виду

$$ x=\varphi(x), \quad \varphi(x)=x-f(x)$$

Теорема. Пусть на замкнутом шаре $S(x_0,r)$ задана вектор функция
$\varphi(x)$ удовлетворяющая условиям

1) $\forall x,y \in S,\quad ||\varphi(x)-\varphi(y)||\leq \alpha
||x-y||,\quad 0<\alpha<1$

2) $||\varphi(x)-\varphi(y)||\leq (1-\alpha)r,$

тогда в замкнутом шаре $S(x_0,r)$ существует единственная
неподвижная точка $x^*$ отображения  $\varphi$, т.е. решение
уравнения $x^*=\varphi(x^*)$, а последовательность
$\{x^k\}_{k=0}^\infty$ образованная по рекуррентному правилу
$x^k=\varphi(x^{k-1})$ сходится к $x^*$ для любого $x^0\in S$  и
имеет место оценка

$$ ||x^*-x^k||\leq \frac {\alpha}{1-\alpha}||x^*-x^k|| $$

Док-во теоремы проводится аналогично док-ву теоремы для скалярного
уравнения с заменой символа $|.|\to||.||$

Замечание. Пусть $x,y\in S(x_0,r)$ и отображение $\varphi$
дифференцируемо, тогда имеет место формула конечных приращений
Лагранжа

$$
\varphi_i(x)-\varphi_i(y)=\sum_{j=1}^n\frac{\partial\varphi_i(\xi)}{\partial
x_j }(x_j-y_j), \quad \forall i=\overline{1,n},\quad \xi\in
S(x_0,r) $$

Обозначая

$$ \varphi'=\left (\begin{array}{cccc}
\frac{\partial\varphi_1}{\partial x_1 }&
\frac{\partial\varphi_1}{\partial x_2
}&\ldots\frac{\partial\varphi_1}{\partial x_n } \\
\frac{\partial\varphi_2}{\partial x_1 }&
\frac{\partial\varphi_2}{\partial x_2
}&\ldots\frac{\partial\varphi_2}{\partial x_n } \\
\ldots&\ldots&\ldots& \\ \frac{\partial\varphi_n}{\partial x_1 }&
\frac{\partial\varphi_n}{\partial x_2
}&\ldots\frac{\partial\varphi_n}{\partial x_n } \\
\end{array}\right )
 $$
 матрица Якоби
 И имея ввиду, что из формулы Лагранжа следует неравенство

 $$ ||\varphi(x)-\varphi(y)||\leq ||\varphi'||||x-y||
 $$
  в качестве $\alpha=||\varphi'||$

  Метод Ньютона

  Пусть

$$ f'=\left (\begin{array}{cccc} \frac{\partial f_1}{\partial x_1
}& \frac{\partial f_1}{\partial x_2 }&\ldots\frac{\partial
f_1}{\partial x_n } \\ \frac{\partial f_2}{\partial x_1 }&
\frac{\partial f_2}{\partial x_2 }&\ldots\frac{\partial
f_2}{\partial x_n } \\ \ldots&\ldots&\ldots&\\ \frac{\partial
f_n}{\partial x_1 }& \frac{\partial f_n}{\partial x_2
}&\ldots\frac{\partial f_n}{\partial x_n } \\
\end{array}\right )
 $$
матрица Якоби для вектор функции $f=(f_1,\ldots,f_n$ и пусть далее
$\det(f')\ne 0$ и существует обратная матрица $(f')^{-1}$ тогда
процесс

$$ x^{k+1}=x^k-(f')^{-1}f(x^k)$$ называют процессом Ньютона для
решения уравнения $f(x)=0$

Удобнее процесс Ньютона записать в форме

$$ x^{k+1}=x^k+p^k,$$ $$ f'(x^k)p^k=-f(x^k)$$

Имеет место теорема




Теорема. Если $f(x)$  непрерывна вместе с производными $f',f''$ в некотором
замкнутом шаре $S(x_0,r)$  и выполнены условия:

1) в точке $x_\in S(x_0,r)$ существует $(f')^{-1}$ и $||(f')^{-1}||<M_0$.

2) $||f(x_0)||\leq \delta$,

3)$\sum_{k=1}^n|\frac{\partial^2f_i}{\partial x_j\partial x_k})<M_2, \quad
\forall i,j=\overline{1,n},\quad \forall x\in S(x_0,r)$

4) $h=2nM_0^2\delta M_1\leq 1$

5) $ r'=M_0\delta \sum_{k=0}^\infty h^{2^k-1}<r$

Тогда уравнение $f(x)=0$  имеет решение $x^*\in S(x_0,r)$  к которому
сходится процесс Ньютона с начальным приближением $x_0$  и имеет место
оценка

$$
||x^k-x^*||\leq M_0\delta\frac{h^{2^k-1}}{1-h^{2^k}}
$$

Проверять условия теоремы затруднительно и  имеет значение утверждение,
что при приближении к корню системы скорость сходимости квадратична.

На практике очень часто процесс Ньютона заменяют процессом Ньютона-Рафсона

$ x^{k+1}=x^k-( f(x_0)')^{-1} f(x^k) $ , в котором матрицу Якоби обращают один раз
и тем самым уменьшают объем вычислений. Есть и другие модификации.

 }

\end{document}
