Методи на хордите, секущите и допирателните (Нютон) за числено решаване на нелинейни уравнения.
страницата се нуждае от дописване/преглеждане
В числените методи се разграничават няколко метода за апроксимация на корен на уравнение на една променлива.
Основната идея при тях е че се избира подходящ интервал $[a,b]$, в чиито краища функцията приема различни знаци и чрез някой от методите
се построява редица от точки ${\{x_i\}}_{i=0}^n$, докато за някое n се достигне стойност на $x_i$, която достатъчно да приближава търсения корен.
В тази тема се описва метод на хордата, метод на секущата и метод на допирателната (още известен като метод на Нютон), както и се прави практическа оценка
на скоростта с която се доближават до търсения корен.
Метод на хордите
Описание
Нека имаме функция $f(x)$ дефинирана в интервал $[a,b]$.
Искаме да намерим число, достатъчно близко до корена $\xi$ на уравнението $f(x)=0$, който да е в интервала $(a,b)$ (ако е една от точките a или b няма да е интересно).
За да се приложи метода на хордите трябва да са на лице следните условия:
1. $f(x)\in C^2[a,b]$.
2. $f^{\prime}(x).f^{\prime\prime}(x)>0 за \forall x\in [a,b]$, т.е. функцията да няма екстремуми или инфлексни точки в зададения интервал.
Геометричният смисъл на метода на хордите е, че избираме единия от краищата на функцията за статичен. В случая това е краят, за който стойността
$f.f^{\prime\prime}>0$. Нека в частност разгледаме случая, когато функцията е монотонно растяща и изпъкнала, тогава взимаме левия край на интервала.
Другият край се определя като $x_0$ и оттам започва да се строи редицата от стойностти ${\{x_i\}}_{i=0}^n$.
(картинка 1)
Построява хорда между текущото $f(x_n)$, което при нас в началната стъпка е $f(a)$ и функционалната стойност в фиксираната точка, в случая $b$.
Построената хорда се пресича с абсцисната ос и пресечната точка се определя като $x_{n+1}$. Вече се разглежда новия интервал $[x_{i+1},b]$ и се повтаря стъпката, докато не получим число, достатъчно близо до корена.
Аналитичен израз на формулите за пресмятане на $x_{n+1}$ чрез $x_n$
Намерили сме си $x_n$ и това което трябва да направим е да построим правата между $(x_n,f(x_n))$ и $(b,f(b))$.
В аналитичен смисъл това, разбира се, означава да си построим полинома от първа степен, който интерполира $f(x)$ в точките $x_n$ и $b$. Според формулата на Нютон търсеният полином е:
$l_n(x) = f(x_n) + f[x_n,b](x-x_n)$. Остава само да намерим точката $x_{n+1}$, за която $l_n(x_{n+1}) = 0$
$f(x_n) + f[x_n,b](x_{n+1}-x_n) = 0 \iff$
$\iff x_{n+1} = x_n - \frac{f(x_n)}{f[x_n,b]} = x_n - \frac{f(x_n)}{f(b)-f(x_n)}(b-x_n)$
И получаваме рекурентната зависимост
1.$x_0 = a$
2.$x_{n+1} = x_n - \frac{f(x_n)}{f(b)-f(x_n)}(b-x_n)$
Редицата генерирана от тази рекурентна зависимост клони към корена, при $n \to \infty$.
Нека в нашия случай $x_n \to \alpha$ при $n \to \infty$
$\Rightarrow \alpha = \alpha - \frac{f(\alpha)}{f(\alpha)-f(b)}(\alpha-b) \Leftarrow f(\alpha)(\alpha - b)$, но
$\alpha < \xi \Rightarrow \lim_{n \to \infty}x_n = \xi$
Твърдение (практическа оценка на метода)
Методът на хордите е сходящ метод със скорост на геометрична прогресия.
Доказателство:
Нека разглеждаме случая, в който b е неподвижна точка и имаме изображението $\phi (x) = x - \frac{f(x)}{f(x)-f(b)}(x-b)$. Другият случай е аналогичен.
Ще използваме следствието на теоремата за редица, образувана чрез свиващо изображение в затворен интервал.
То гласи следното:
Ако $\phi$ притежава непрекъсната производна в околност на неподвижната си точка $\xi$, като $|\phi^{\prime}(\xi) |<1$, тогава при достатъчно
добро начално приближение $x_0$ съществуват константи $c>0$ и $q, 0<q<1$ такива че редицата ${\{x_i\}}_{i=0}^n$, построена чрез рекурентната зависимост
$x_{n+1} = \phi (x_n)$ е изпълнено $|x_n-\xi|<c.q^n$.
Което е именно геометрична прогресия. Т.e. следва да докажем, че за нашето изображение с неподвижна точка $\xi$ е изпълнено $|\phi^{\prime}(\xi) |<1$.
$\phi^{\prime}(\xi)= 1 - \frac{f^{\prime}(\xi)(\xi - b)}{f(\xi)-f(b)} - f(\xi) \left ( \frac{x - b}{f(x) - f(b)} \right )^{\prime} =$
$= 1 - \frac{f^{\prime}(\xi)(\xi - b)}{0-f(b)}$
$= \frac{f(b)-f^{\prime}(\xi)(b - \xi)}{f(b)}$
Първо преработваме знаменателя. Според теоремата на Лагранж за крайните нараствания съществува точка $\theta_1$ между $\xi$ и $b$ такава че
$f(b) - f(\xi) = f^{\prime}(\theta_1) (b - \xi) \Leftarrow f(b) = f^{\prime}(\theta_1) (b - \xi)$
Прилагайки развитие по ред на Тейлър съществува точка $\theta_2$ между $\xi$ и $b$ такава че
$f(b) = f(\xi) + \frac{f^{\prime}(\xi)}{1!} (b - \xi) + \frac{f^{\prime\prime}(\theta_2)}{2!} (b - \xi) ^ 2 \Rightarrow$
$\Rightarrow f(b) - f^{\prime}(\xi) (b - \xi) = \frac{f^{\prime\prime}(\theta_2)}{2} (b - \xi) ^ 2$
което е и числителя на $\phi^{\prime}(\xi)$
В крайна сметка се получава
$f^{\prime}(\xi) = \frac{f^{\prime\prime}(\theta_2)}{2 f^{\prime}(\theta_1)}(b-\xi)$
Нека си взмемем $M = \max_{x \in [a,b] } f^{\prime\prime}(x)$ и $M = \min_{x \in [a,b]} f^{\prime}(x)$
$\Rightarrow |\phi^{\prime}(\xi)| \leq \frac{M}{2m}(b-\xi) < 1 \Rightarrow$ са изпълнени условията на следствието
следователно метода на хордите се приближава до корена със скорост на геометрична прогресия.
Метод на секущите
Описание
Нека имаме функция $f(x)$ дефинирана в интервал $[a,b]$.
Отново искаме да намерим число, достатъчно близко до корена $\xi$ на уравнението $f(x)=0$, който да е в интервала $(a,b)$.
За да се приложи метода на секущите, трябва да са на лице следните условия:
1. $f(x)\in C^2[a,b]$.
2. $f^{\prime}(x).f^{\prime\prime}(x)>0 за \forall x\in [a,b]$
При този метод трябва да намерим две начални стойности $x_0$ и $x_1$, за които $f(x_i).f^{\prime\prime}(x_i)>0$
Отново разглеждаме случая, когато функцията е монотонно растяща и изпъкнала, тогава двете начални стойности ще са отдясно на корена $\xi$.
Между функционалните стойности при текущите $x_{n-1}$ и $x_n$ се построява секуща и точката, в която тя пресича абсцисната ос, се определя за $x_{n+1}$ като така се строи редицата от стойностти ${\{x_i\}}_{i=0}^n$.
(картинка 2)
Аналитичен израз на формулите за пресмятане на $x_{n+1}$ чрез $x_n$ и $x_{n-1}$
Тук трябва да построим секуща през точките $x_n$ и $x_{n-1}$. Но какво е една секуща, ако не полином от първа степен интерполиращ f в $x_n$ и $x_{n-1}$
$l_n(x) = f(x_n) + f[x_n,x_{n-1}](x-x_n)$. Остава само да намерим точката $x_{n+1}$, за която $l_n(x_{n+1}) = 0$
$f(x_n) + f[x_n,x_{n-1}](x_{n+1}-x_n) = 0 \iff$
$\iff x_{n+1} = x_n - \frac{f(x_n)}{f[x_n,x_{n-1}]} = x_n - \frac{f(x_n)}{f(x_n)-f(x_{n-1})}(x_n-x_{n-1})$
И получаваме рекурентната зависимост
$x_{n+1} = x_n - \frac{f(x_n)}{f(x_n)-f(x_{n-1})}(x_n-x_{n-1})$
при добре избрани $x_0$ и $x_1$ за $n = 1,2,3 ...$
Теорема (ред на сходимост на метода на секущите)
Методът на секущите има ред на сходимост $r= \frac{1+\sqrt{5}}{2}$.
Т.е. ако началните приближения $x_0$ и $x_1$ при метода на секущата са избрани
така, че $|x_i-\xi| \leq C.q^{r^i}$ за $i = 0,1$,
където $C>0, 0<q<1$ са констанити такива че $\frac{C.M}{2m} \leq 1$ а $r= \frac{1+\sqrt{5}}{2}$
$r$ е положителния корен на уравнението $r^2-r+1=0$, $M = \max_{x \in [a,b]} f''(x)$ и $m = \min_{x \in [a,b]} f'(x)$
Тогава $|x_n-\xi| \leq C.q^{r^n} (\forall n \in N)$.
Доказателство:
Доказателството се извършва чрез индукция по n
База: За $n=0,1$ формулировката предполага, че твърдението е изпълнено.
Допускаме, че е твърдението е изпълнено за всяко естествено число $\leq n$
Ще докажем че е в сила за $n=n+1$
Нека $l_n(x)$ е полинома от първа степен интерполиращ $f$ във $x_{n-1},\ x_n$
От формула за представяне на грешката следва че $f$ може да се представи по следния начин:
$f(x)= l_n(x) + \frac{f '' (\theta_1)}{2} (x-x_n)(x-x_{n-1})$
за някое $\theta_1$ в интервала $(x_{n-1},x_n)$
От друга страна, ако $f(x)$ се развие в ред на Тейлър в точката $\xi$се получава следното:
$f(x) = f(\xi) + f'(\theta_2) (x-\xi)$
за някое $\theta_2$ в интервала $(x_{n-1},x_n)$
Приравняваме двата израза при $x = x_{n+1}$ и като вземем предвид, че $f(\xi)=0$
се получава
$|f^{\prime}(\theta_2)| |x_{n+1} - \xi| = \left | \frac{f''(\theta_1)}{2} \right | |x_{n+1}-x_{n-1}||x_{x+1}-x_n|$
Но съгласно индукционното предположение
$|x_{n-1}-\xi| \leq C.q^{r^{n-1}}$
$|x_{n}-\xi| \leq C.q^{r^{n}}$
Следователно
(2)($\frac{MC}{2m}\le1$ по условие)
Но $r$ е положителният корен на уравнението $r^2-r-1 = 0$ Следователно
$r+1=r^2 \Rightarrow r^{n-1}(1+r)=r^{n+1}$
Горното неравенство добива вида
$|x_{n+1}-\xi| \leq C.q^{r^{n+1}}$
Което трябваше да докажем.
Забележка: Тъй като r= $\frac{1+\sqrt{5}}{2} >1$ може да заключим, че методът на секущите е значително
по-бързо сходящ от метода на хордите