\myAddDate{27}{03}{09}
    Пусть \( \{\phi_i\}_0^n \)- ортонормированная система. Тогда наименьшее отклонение:
    \[ 0 \leq \int_a^b{ \left( f(x) - \sum_{k=0}^n{C_k\phi_k(x)} \right)^2dx}
    = \]
     \[ \int_a^b{f^2(x)dx} - 2\sum_{k=0}^n{C_k(\phi_k,f) } +
    \sum_{k=0}^n{C_k^2} = \]
    \[ (f,f) - \sum_{k=0}^n{C_k^2} \geq 0 \]
    
    Таким образом, мы получили неравенсвто Бесселя:
    \[ \sum_{k=0}^n{C_k^2}  \leq ||f||^2 \]
    
    
    Если система \(\{\phi_k\}_0^n\) -- ортонормированный базис, и
    \((\phi_k,\phi_l) = \delta_{kl}\), то полученное неравенство Бесселя станет
    равенством Парсеваля: \[ ||f||^2 = \sum_{k=0}^\infty C_k^2 \]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\chapter{Численное решение нелинейных уравнений и систем нелинейных уравнений}
 \section{Введение}
 Пусть задана функция \( f(x), x \in \mathbb{R} \), причем функция f
 непрерывна.\\ Будем решать уравнение на отрезке \([a,b]\)
 
 \[ f(x) = 0, x \in [a,b] \]
 
 Процесс решения разбивают на 2 этапа:
 \begin{enumerate}
   \item Локализуем корни (при этом корни могут быть комплексные)
   \item Строим итерационный метод нахождения корня
 \end{enumerate}
         
 \begin{myUnnumberedDefinition}
 a-окрестностью корня \(x_*\) называется множество точек
 \[U_a(x_*) = \{x: |x-x_*| \leq a\} \]
 \end{myUnnumberedDefinition}    

Рассмотрим способы локализации корня:

\begin{enumerate}
  \item Разобьем отрезок \( [a,b] \) множеством точек \( \{x_i\}_1^N \)
    \[ a \leq x_0 < x_1 < \ldots < x_N \leq b \]
   Тогда можно утверждать, что если \(f(x_{i-1})f(x_i)<0 \), то на отрезке 
   \( [x_{i-1}..x_i] \) есть по крайней мере один корень (также их может быть
   нечетное число). Если же \(f(x_{i-1})f(x_i)>0 \), то сказать ничего нельзя,
   так как на этом отрезке либо четное число корней, либо корней нет вообще. 
  \item  Метод бисекции (деления пополам)
  Пусть
    \[ f(x) \in C[a,b]; ~ f(a) < 0, f(b)>0 \]
  Возьмем \( x_0 = \frac{a+b}{2}\).\\
   
   Если \(f(x_0) > 0\), то корень уравнения \( x_* \in (a,x_0) \)\\
   Если \(f(x_0) < 0\) , то корень уравнения \( x_* \in (x_0,b) \)\\
   Если \(f(x_0) = 0\), то мы нашли корень уравнения.\\
   
   В первом случае возьмем \( x_1 = \frac{a+x_0}{2}\), во втором \( x_1 =
   \frac{x_0+b}{2}\), и аналогично повотрим процедуру локализации корня, и так
   далее.
\end{enumerate}

В случае, если дана система уравнений 
\[
\begin{cases}
f_1(x_1,\ldots,x_m) = 0,\\
\ldots\\
f_m(x_1,\ldots,x_m) = 0,\\
\end{cases}
\]

ее можно представить в виде \( \vec{f}(\vec{x}) = 0 \), где
\( \vec{f} = (f_1, f_2, \ldots , f_m)^T , \vec{x} = (x_1, x_2, \ldots, x_m)^T \)

\section{Метод простой итерации}
Итак, мы решаем уравнение
\begin{equation}
    \label{eq_3_2_1}
    f(x)=0
\end{equation}

\( x_* \) - корень уравнения, локализованный на \(U_a(x_*)\)\\
Заменим уравнение на эквивалентное
\begin{equation}
    \label{eq_3_2_2} 
    x=S(x)
\end{equation}

\begin{equation}
    \label{eq_3_2_3}
    S(x) = x + r(x)f(x)
\end{equation}

где функция \( r(x) \) не меняет знак на \( U_a(x_*) \)\\
Построим последовательность \( \{x_n\} \) следующим образом:
\[x_0 \in U_a(x_*) \]
\begin{equation}
    \label{eq_3_2_4}
    x_{n+1} = S(x_n), ~ n=0,1,\ldots
\end{equation}

\begin{myUnnumberedDefinition}
Функция S(x) Липшиц-непрерывна (удовлетворяет условию Липшица) с константой q >0,
если \[ |S(x_1) - S(x_2)| \leq q|x_1 - x_2|, ~ \forall x_1, x_2 \in (a,b)\] 
\end{myUnnumberedDefinition}

\begin{myUnnumberedStatement}
 Если S(x) удовлетворяет условию Липшица с \( 0 < q < 1 \) на \( U_a(x_*)\) и
 \( |x-x_0| < a \), то метод простой итерации \eqref{eq_3_2_4} решения
 уравнения \eqref{eq_3_2_1} сходится, причем со скоростью геометрической
 прогрессии со знаменателем q.
\end{myUnnumberedStatement}
\begin{proof}
  По построению \( |x_0 - x_*| < a \), значит
  \[ |x_{n+1} - x_*| = |S(x_n) - S(x_*)| \leq q|x_n - x_*|  \Rightarrow \]
  \[  |x_n - x_*| \leq q^na \]
  
  \( \lim_{n\rightarrow \infty} q^n = 0 \), так как \( 0< q< 1\).\\
  Следовательно, метод сходится, причем со скоростью геометрической прогресси со
  знаменателем q. 
\end{proof}

\begin{myUnnumberedNote}
Если S(x) дифференцируема на \( U_a(x_*) \), то \( q = \sup_{x \in U_a(x_*)
} |S'(x)|\)
\end{myUnnumberedNote}

\begin{myUnnumberedNote}
Пусть f(x) дифференцируема, \( f'(x) >0 \) на \( U_a(x_*)\) и 
\( \exists M_1 = \sup_{x \in U_a(x_*)}|f'(x)|\)\\
Тогда запишем метод простой итерации в виде:
\[ \frac{x_{n+1}-x_{n}}{\tau} + f(x_n) = 0,\quad \tau > 0 \]
\[ x_{n+1} = S(x_n), \quad S(x) = x - \tau f(x)\]
Следовательно, \( \exists S'(x) = 1 - \tau f'(x)\) на \( U_a(x_*)\).
Для сходимости метода необходимо, чтобы \( q = \sup_{x \in U_a(x_*)}|1-\tau
f'(x)| < 1\), т.е. чтобы \( 0 < \tau < \frac{2}{M_1} \) 
\end{myUnnumberedNote}

\subsection{Метод Эйткена (ускорение сходимости)}
Метод Эйткена не является теоретически обоснованным, но при
приближенных значениях параметров позволяяет увеличить скорость
сходимости.

Пусть \( x_n - x_* \simeq Aq^n \), где A и q - некоторые константы. Тогда:
\[ x_{n-1} - x_* = Aq^{n-1}\]
\[ x_n - x_* = Aq^n\]
\[ x_{n+1} - x_* = Aq^{n+1}\]

следовательно,

\[ (x_{n+1} - x_n)^2 = A^2q^{2n}(q-1)^2 \]
\[ (x_{n+1} - 2x_n + x_{n-1}) = Aq^{n-1}(q-1)^2 \]

Откуда получаем:
\[ \frac{ (x_{n+1}-x_n)^2 }{x_{n+1} - 2x_n + x_{n-1}} = Aq^{n+1} = x_{n+1} -
x_*
\]

Стало быть:
\[ x_* \simeq x_{n+1} - \frac{ (x_{n+1}-x_n)^2 }{x_{n+1} - 2x_n + x_{n-1}} \]

Из-за неточности в качестве следующей итерации мы должны взять значение,
близкое к \( x_* \)

\section{Метод Ньютона и метод секущих}

Мы решаем уравнение
\begin{equation}
    \label{eq_3_3_1}
    f(x) = 0
\end{equation}

Пусть корень локализован на \( U_a(x_*)\), \( f(x) \in C^1( U_a(x_*) )\), при
этом \( f'(x) \neq 0 \) на \( U_a(x_*)\).\\
Разложим \( f(x_*) \) по Тейлору:
\[ 0= f(x_*) = f(x) + f'(x)(x_*-x) + o(x_*-x) \approx f(x) + f'(x)(x_*-x)\]
Положим в этой формуле \( x = x_n\), \( x_* = x_{n+1} \), тогда получим:

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

Взяв \( x_0 \in U_a(x_*)\), получаем метод Ньютона:

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}, ~ n=0,1,2,\ldots \]

На каждой итерации считать производную затратно, в то же время на небольшом
интервале она, как правило, меняется не сильно. Следовательно, можно
использовать производную, один раз вычисленную на первой итерации. Получаем
модифицированный метод Ньютона:

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_0)}, ~ n=0,1,2,\ldots ; x_0 \in U_a(x_*)
\]

Модифицированный метод Ньютона сходится медленнее обычного метода Ньютона, но
быстрее метода простой итерации.

\subsection{Метод Ньютона для системы уравнений}
Рассмотрим систему:

\begin{equation}
    \label{eq_3_3_2}
    \begin{cases}
    f_1(x_1,x_2) = 0,\\
    f_2(x_1,x_2) = 0,\\
    \end{cases}    
\end{equation}

Пусть \( (x_1^*, x_2^*) \) - ее решение. Разложим \( f_1 \) и \( f_2 \) в
окрестности корня:
\[ 0 = f_1(x_1^*, x_2^*) = f_1(x_1, x_2) + \frac{\partial f_1(x_1,
x_2)}{\partial x_1 }(x_1^* - x_1) + \frac{\partial f_1(x_1,
x_2)}{\partial x_2 }(x_2^* - x_2) + \ldots 
\]

\[ 0 = f_2(x_1^*, x_2^*) = f_2(x_1, x_2) + \frac{\partial f_2(x_1,
x_2)}{\partial x_1 }(x_1^* - x_1) + \frac{\partial f_2(x_1,
x_2)}{\partial x_2 }(x_2^* - x_2) + \ldots 
\]

Заменяя \( x_i \) на \( x_i^n\) и \( x_i^*\) на \(x_i^{n+1} \), получим:

\[  f_1(x_1^n, x_2^n) + \frac{\partial f_1(x_1^n,
x_2^n)}{\partial x_1 }(x_1^{n+1} - x_1^n) + \frac{\partial f_1(x_1^n,
x_2^n)}{\partial x_2 }(x_2^{n+1} - x_2^n) = 0 
\]

\[  f_2(x_1^n, x_2^n) + \frac{\partial f_2(x_1^n,
x_2^n)}{\partial x_1 }(x_1^{n+1} - x_1^n) + \frac{\partial f_2(x_1^n,
x_2^n)}{\partial x_2 }(x_2^{n+1} - x_2^n) = 0 
\]

Обозначим \( x^n = (x_1^n, x_2^n)^T \), \( f^n = (f_1^n, f_2^n)^T \), а также
\begin{equation}
    \label{eq_3_3_3}
    I(x^n) = 
    \left[
    \begin{matrix}
      \frac{\partial f_1(x_1^n,x_2^n)}{\partial x_1 } & \frac{\partial f_1(x_1^n,
x_2^n)}{\partial x_2 }\\
      \frac{\partial f_2(x_1^n,x_2^n)}{\partial x_1 } & \frac{\partial
      f_2(x_1^n, x_2^n)}{\partial x_2 }
    \end{matrix}
    \right] 
\end{equation}
 
 Тогда уравнение можно записать в виде:
 \begin{equation}
    \label{eq_3_3_4}
    f(x^n) + I(x^n)(x^{n+1} - x^n) = 0
 \end{equation}

Если \( \forall n \; \exists I^{-1}(x^n)\), то 
\begin{equation}
    \label{eq_eq_3_3_4}
    x_{n+1} = x^n - I^{-1}(x^n)f(x^n), ~ n=0,1,2,\ldots;\quad x_0 \text{ --
    задано}
\end{equation} 

\begin{myUnnumberedNote}
Считать \( I^{-1}(x^n)\) не очень удобно, поэтому обычно вводят погрешность 
\[ v^{n+1} = x^{n+1} - x^n \]
и решают на каждой итерации уравнение:
\[ I(x^n)v^{n+1} = -f(x^n) \]

\end{myUnnumberedNote}

\begin{myUnnumberedNote}
В случае системы можно применить модифицированный метод Ньютона:
\[ x^{n+1} =x^n - I^{-1}(x^0)f(x^n)  \]
Но в этом случае скорость сходимости будет значительно меньше.
\end{myUnnumberedNote}

Если дана система из m уравнений:
\[
\begin{cases}
f_1(x_1,\ldots,x_m) = 0,\\
f_2(x_1, \ldots, x_m) = 0,\\
\ldots\\
f_m(x_1,\ldots,x_m) = 0,\\
\end{cases}
\]

то также можно использовать метод Ньютона, в этом случае 
\[ I(x^n)_{ij} = \frac{\partial f_i(x_n)}{\partial x_j}, \quad i,j =
\overline{1,m} \]
Система в этом случае имеет тот же вид:
\[ f(x^n) + I(x^n)(x^{n+1} - x^n) = 0\]