Метод на свиващите изображения за решаване на нелинейни уравнения. Ред на сходимост на итерационен подход.

Итерационен метод

Нека си имаме функцията $f(x)$ и да приемем, че тя има единствен корен $\xi$ в интервала $(a, b)$.
Сега да си мислим, че сме си образували (някак) функция $\varphi(x)$, такава че $f(x) = 0 \iff x = \varphi(x)$ (тази еквивалентност трябва да е валидна само в интервала $(a, b)$).
Нека $x_0 \in (a, b)$ - начално приближение.
Дефинираме си редицата $\{ x_i \}_{i=0}^{\infty}$ така че $x_i = \varphi(x_{i-1})$. При определени условия редицата $\{ x_i \}_{i=0}^{\infty}$ ще е сходяща и ще клони към единствения корен $\xi$. Т.е ако редицата клони към $\alpha$, като направим граничен преход в $x_i = \varphi(x_{i-1})$ получаваме $\alpha = \varphi(\alpha)$ и понеже $\xi$ е единствената неподвижна точка за $\varphi$ в интервала $(a, b)$ то със сигурност $\alpha = \xi$.

Условия за фи

Условие 1

$\varphi$ е изображение на $[a, b]$ върху $[a, b]$.

Условие 2

$\varphi$ има неподвижна точка в $[a, b]$.

Условие 2*

$\varphi$ е непрекъснато изображение от $[a, b]$ в $[a, b]$.

Лема: Ако $\varphi$ е непрекъснато изображение от $[a, b]$ в $[a, b]$ то $\varphi$ притежава неподвижна точка в $[a, b]$.
Доказателство: Нека $g(x) = \varphi(x) - x$. Изпълнено е, че $g(a) = \varphi(a) - a \ge 0 \And g(b) = \varphi(b)- b \le 0$. Ако $g(a) = 0 \lor g(b) = 0$ тогава очевидно имаме неподвижна точка - $a$ или $b$. Иначе $g(x)$ е непрекъсната в $[a, b]$ и си сменя знака - следователно се нулира (теорема на Вайерщтрас).

Условие 3

Дефиниция (Липшицови функции)

Казваме, че функцията $\varphi$ е липшицова в $[a, b]$ с константа $L > 0$ ако е изпълнено, че

(1)
\begin{align} |\varphi(x) - \varphi(y)| \le L|x - y| \qquad \forall x, y \in [a, b] \end{align}
Дефиниция (свиващо изображение)

$\varphi$ е свиващо изображение в $[a, b]$, ако е липшицово с константа $0 < q < 1$. Т.е $|\varphi(x) - \varphi(y)| \le q|x - y| \quad \forall x, y\in[a,b]$.

Условието

Ако $\varphi$ е свиващо изображение на $[a, b]$ в $[a, b]$.

Лема: Ако $\varphi$ е свиващо на $[a, b]$ в $[a, b]$, тогава $\varphi$ притежава единствена неподвижна точка.
Доказателство: Да предположим че съществуват две неподвижни точки $\xi_1, \xi_2$, т.е $\varphi(\xi_1) = \xi_1 \quad \varphi(\xi_2) = \xi_2$. Сега използваме факта, че $\varphi$ е свиващо: $|\varphi(\xi_1) - \varphi(\xi_2)| < q|\xi_1 - \xi_2| \iff |\xi_1 - \xi_2| < q|\xi_1 - \xi_2|$ - противоречие. Следователно съществува единствена неподвижна точка.

Теорема

Нека $\varphi$ е липшицово изображение на $[a, b]$ в $[a, b]$ с константа $q : 0 < q < 1$. Тогава за всяко $x_0 \in [a, b]$ редицата $\{ x_n \}_{n=0}^{\infty}$ зададена посредством $x_n = \varphi(x_{n-1}) \quad n \in \mathbb{N}$ е сходяща с единствена неподвижна точка $\xi$ на $\varphi$ в $[a, b]$, и е изпълнено $|x_n - \xi| < q^n(b - a) \quad n \in \mathbb{N}$.
Доказателство: Ще докажем, че е изпълнено $|x_n - \xi| \le q^n(b - a)$ - останалите работи следват от по-горе доказаните твърдения.

(2)
\begin{eqnarray} |x_n - \xi| &=& |\varphi(x_{n-1}) - \varphi(\xi)| \\ &\le& q|x_{n-1} - \xi| \\ &\vdots& \\ &\le& q^n|x_0 - \xi| \\ &\le& q^n|b - a| \\ \end{eqnarray}

Наблюдение: Използвайки теоремата за крайните нараствания: $\varphi(x) - \varphi(y) = \varphi'(\theta)(x - y)$ получаваме, че при $\varphi'(x) \le q < 1$ за всяко $x \in [a, b]$ имаме, че $|\varphi(x) - \varphi(y)| \le q|x - y|$ за всяко $x \in [a, b]$. Т.е ако $\varphi'(x) \le q < 1 \quad \forall x \in [a, b]$, то $\varphi(x)$ е свиващо в $[a, b]$.

Твърдение

Нека $\varphi$ притежава непрекъсната производна в околност на неподвижната си точка $\xi$, като $|\varphi'(\xi)| < 1$. Тогава при достатъчно добро начално приближение $x_0$ (достатъчно близко до $\xi$) съществуват стойности $c > 0$ и $q : 0 < q < 1$ такива че за редицата $\{ x_i \}_{i=0}^{\infty}$ построена $x_n = \varphi(x_{n-1}) \quad n \in \mathbb{N}$ е изпълнено $|x_n - \xi| \le Cq^n \quad \forall n \in \mathbb{N}$.

Доказателство: От това че $|\varphi'(x)| < 1$ и $\varphi'(x)$ непрекъсната, следва съществуването на околност $U$ на точката $\xi$ :

(3)
\begin{align} U = \{ x : |x - \xi| < \varepsilon \} \end{align}

за някое $\varepsilon$, такова че $| \varphi'(x)| \le q < 1 \quad \forall x \in U$. Ще покажем, че $x \in U \Rightarrow \varphi(x) \in U$.

(4)
\begin{eqnarray} |\varphi(x) - \xi| &=& | \varphi(x) - \varphi(\xi)| \\ &=& |\varphi'(\theta.(x-\xi)| \\ &\le& q|\underbrace{x - \xi}_{<\varepsilon}| \\ &<& q.\varepsilon \\ &<& \varepsilon \\ \end{eqnarray}

Следователно $\varphi(x) \in U$. Освен това $\varphi$ е свиващо в $U$ следователно $|x_n - \xi| \le q^n|U| = q^n C$.

Ред на сходимост на итерационен процес

Дефиниция

Казваме, че итерационният процес $x_{n+1} = \varphi(x_n) \quad n \in \mathbb{N}$ има ред на сходимост $p > 1$, ако съществуват константи $c > 0, q \in (0, 1)$, такива че $|x_n - \xi| \le C . q^{p^n} \quad \forall x \in \mathbb{N}$.

Теорема

Нека $\varphi(x)$ притежава непрекъснати производни до ред $p$ включително в околност на неподвижна точка на $\varphi - \xi$, като е изпълнено, че $\varphi^{(i)}(\xi) = 0$ за $i = 1, \dots, p-1$ и $\varphi^{(p)}(\xi) \ne 0$ тогава при достатъчно добро начално приближение $x_0$ съществува константа $c > 0$ и $q \in (0, 1)$ такава че $|x_n - \xi| < C.q^{p^n}$, т.е итерационният процес има ред на сходимост $p$.

Доказателство: Ще развием $\varphi$ в ред на Тейлор по отношение на точката $\xi$:

(5)
\begin{eqnarray} \varphi(x) &=& \varphi(\xi) + \sum_{k=1}^{p-1} \frac{\varphi^{(k)}(\xi)}{k!} (x-\xi)^k + \frac{\varphi^{(p)}(\theta)}{p!} (x-\xi)^p \\ &=& \xi + \frac{\varphi^{(p)}(\theta)}{p!} (x-\xi)^p \end{eqnarray}

защото всички по-малки производни са нули в точката $\xi$. Освен това може да приемем, че $\frac{\varphi^{(p)}(x)}{p!} \le M$ за околност $U$ на $\xi$.
т.е $|\varphi(x) - \xi| \le M|x - \xi|^p \quad \forall x \in U$. Сега ще използваме тази връзка за да разпишем $|x_{n+1} - \xi|$:

(6)
\begin{eqnarray} |x_{n+1} - \xi| &\le& M |x_n - \xi|^p \\ &\le& M(M|x_{n-1} - \xi|^p)^p \\ &=& M^{1+p}|x_{n-1} - \xi|^{p^2} \\ &\le& M^{1+p+p^2}|x_{n-2} - \xi|^{p^3} \\ &\vdots& \\ &\le& M^{1+p+\dots+p^n}|x_0 - \xi|^{p^{n+1}} \\ &=& M^{\frac{p^{n+1}-1}{p-1}}|x_0 - \xi|^{p^{n+1}} \\ &=& \underbrace{M^{-\frac{1}{p-1}}}_{C}(\underbrace{M^{\frac{1}{p-1}}|x_0 - \xi|}_{q})^{p^{n+1}} \\ \end{eqnarray}

и $q < 1$ ако $x_0$ е достатъчно близо до $\xi$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License