% Lection 13 by wictor
\myAddDate{30}{03}{09}

\subsection{Метод секущих}

	Запишем метод Ньютона:
	$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}, \quad x_0 \in U_a(x_*),\quad
	n=0,1,2,\ldots. $$
	
	Заменим в нем $ f'(x^n) $ на $ \frac{f(x^n) - f(x^{n-1})}{x^n - x^{n-1}} $.
	
	Получим
	\begin{equation}
	\label{eq_3_3_5}
	x^{n+1} = x^n - \frac{x^n - x^{n-1}}{f(x^n) - f(x^{n-1})}f(x^n)
	\end{equation} 
	
	Поскольку в записи данного метода учавствуют три последовательные итерации
	($x^{n+1},\, x^n \, \text{и} \, x^{n-1}$), то он называется двухшаговым
	методом. Для того, чтобы воспользоваться им, требуется задать два начальных
	приближения ($x^0$ и $x^1$). Их можно получить методом простой итерации или
	методом Ньютона.
	
	Заметим, что, используя метод секущих, мы получаем $x^{n+1}$ при помощи	
	интерполяции функции $f$ полиномом первой степени (линейной функцией),
	используя ее значение в узлах $x^n$ и $x^{n-1}$.
	
	\section{Сходимость метода Ньютона и оценка сходимости}
	
	Рассматривается нелинейное уравнение 
	\begin{equation}
    \label{eq_3_4_1}
    	f(x) = 0.
    \end{equation}

    Запишем для него метод Ньютона:
	\begin{equation}
    \label{eq_3_4_2}
    	x^{n+1} = x^n - \frac{f(x^n)}{f'(x^n)}, \quad n = 0,1,\ldots; \quad x^0 \in
    	U_a(x_*).
    \end{equation}
    
    Запишем это метод в более общем виде:
    $$ x^{n+1} = S(x^n),\quad \text{где }S(x) = x - \frac{f(x)}{f'(x)}. $$
    Тогда
    $$ S'(x) = 1 - \frac{(f'(x))^2 - f(x)f''(x)}{(f'(x))^2} =
    \frac{f(x)f''(x)}{(f'(x))^2}. $$
    Заметим, что $S'(x_*) = 0$.
    
    Пусть $z_n = x^n - x_*$ -- погрешность. Тогда
    $$ z^{n+1} = x^{n+1} - x_* = S(x^n) - S(x_*) = S(z_n + x_*) - S(x_*). $$
    
    Воспользуемся формулой Тейлора с остаточным членом в форме Лагранжа:
    $$ z^{n+1} = S(x_*) + S'(x_*)z_n + \frac{1}{2} S''(\tilde{x}^n)z_n^2 -
    S(x_*) = \frac{1}{2} S''(\tilde{x}^n)z_n^2, $$
    где $ \tilde{x}^n = x^n + \theta z_n, \quad |\theta|<1.$
    
    Пусть $ \exists M>0$ такое, что
    \begin{equation}
    \label{eq_3_4_3}
    	\frac{1}{2} |S''(x)|\leq M, \quad x \in U_a(x_*).
    \end{equation}
    
    Тогда
    $$ |z_{n+1}| \leq M |z_n|^2, $$
    $$ M|z_{n+1}| \leq (M |z_n|)^2. $$
    Применим это неравенство рекурсивно, получим
    $$ M|z_{n}| \leq (M |z_0|)^{2^n}, $$
    $$ |z_{n}| \leq \frac{1}{M}(M |z_0|)^{2^n}. $$
    Если $ M |z_0| < 1 $, то при $ n \rightarrow \infty $ получаем $ |z_n|
    \rightarrow 0 \: \Rightarrow \: x^n \rightarrow x_*.  $
	
    Таким образом, для сходимости данного метода достаточно потребовать
    \begin{equation}
    \label{eq_3_4_4}
    	|z_0| = |x_0 - x_*| \leq \frac{1}{M}.
    \end{equation}
    
    Для $z_n$ имеем оценку
    \begin{equation}
    \label{eq_3_4_5}
    	|z_n| = |x_n - x_*| \leq \frac{1}{M}(M |x_0 - x_*|)^{2^n}.
    \end{equation}
    
    Мы доказали следующую теорему.
    
    \begin{myUnnumberedTheorem}[об оценке скорости сходимости метода Ньютона]
    	Пусть \linebreak $ \exists M > 0 $ такое, что
    	$$ \frac{1}{2} \left| \left( \frac{f(x)f'(x)}{(f'(x))^2} \right) ' \right|
    	\leq M \quad \forall x \in U_a(x_*), $$
    	$$ |x_0 - x_*| \leq \frac{1}{M}. $$
    	Тогда метод Ньютона сходится и имеет место оценка
    	$$ |x_n - x_*| \leq \frac{1}{M}(M |x_0 - x_*|)^{2^n}. $$
    	
    \end{myUnnumberedTheorem}
    
    \begin{myUnnumberedNote}
    	Если метод Ньютона сходится, то он сходится очень быстро.
    \end{myUnnumberedNote}

    \begin{myUnnumberedNote}
    	Начальное приближение должно быть близко к корню (в соответствии с
    	условием \eqref{eq_3_4_4}).
    \end{myUnnumberedNote}

    Напомним, что модифицированный метод Ньютона имеет вид:
    $$ x^{n+1} = x^n - \frac{f(x^n)}{f'(x^0)}. $$
    Для этого метода $S(x)$ имеет вид
    $$ S(x) = x - \frac{f(x)}{f'(x^0)}. $$
    Для этого метода аналогичное утверждение не имеет место, ибо $S'(x_*) \neq 0$
    в общем случае.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
\chapter{Разностные методы решения задач математической физики}
	\section{Разностные схемы для первой краевой задачи для уравнения
	теплопроводности}
	Рассмотрим область $D = \{ (x,y) \in \mathbb{R}^2 :\: 0<x<1,\, 0<t\leq T \} $
	($T$ -- заданное положительное число).
	
	Запишем первую краевую задачу для уравнения теплопроводности в этой области:
	\begin{equation}
    \label{eq_4_1_1}
    	\frac{\partial u}{\partial t} = \frac{\partial^2 u}{\partial x^2} +
    	f(x,t),\quad (x,t) \in D,
	\end{equation}
	краевые условия:
	\begin{equation}
    \begin{cases}
    \label{eq_4_1_2}
    	u(0,t) = \mu_1(t), \\
    	u(1,t) = \mu_2(t),
    \end{cases}
	\end{equation}
	начальное условие:
	\begin{equation}
    \label{eq_4_1_3}
    	u(x, 0) = u_0(x).
	\end{equation}
	
	Введем следующие обозначения:
	
	$$ \omega_h = \{ x_i = ih,\, i = 1, \ldots, N-1,\, hN=1 \}, $$
	$$ \overline{\omega}_h = \{ x_i = ih,\, i = 0, \ldots, N,\, hN=1 \}, $$
	$$ \omega_{\tau} = \{ t_j = j\tau,\, j = 1, \ldots, j_0,\, \tau j_0=T \}, $$
	$$ \overline{\omega}_{\tau} = \{ t_j = j\tau,\, j = 0, \ldots, j_0,\, \tau
	j_0=T \}, $$
	$$ \omega_{\tau h} = \omega_{\tau} \times \omega_h, $$
	$$ \overline{\omega}_{\tau h} = \overline{\omega}_{\tau} \times
	\overline{\omega}_h, $$
	$$ u_i^n = u(x_i, t_n), $$
	$$  f_i^n = f(x_i, t^n). $$
	Множества $\omega_*$ и $\overline{\omega}_*$ называются сетками, элементы этих
	множеств -- узлами. Значения $\tau$ и $h$ называются шагами сетки. Внутренними
	узлами назовем узлы сетки $\omega_{\tau h}$. 
	
	%Внешними узлами назовем узлы $ (x,
	%t) \in \overline{\omega}_{\tau h}, $ такие, что $ x = 0 $ или $x = 1$.
	
	Будем обозначать численное решение поставленной задачи через $y(x, t).$ Пусть 
	$$ y_i^n = y(x_i, t_n). $$