Metoda tečen

Jeden krok metody tečen při hledání řešení f(x)=0. x_n představuje původní odhad, v bodě f(x_n) je sestrojena tečna ke křivce f(x). V místě, kde tečna protíná osu x, se nachází nový odhad x_{n+1}.

Metoda tečen je iterační numerická metoda užívaná v numerické matematice k nalezení kořenů funkce nebo k řešení soustavy nelineárních algebraických rovnic. Nazývá se také Newtonova metoda (nebo Newton-Raphsonova metoda) a metodou tečen je označována, protože přesnější řešení rovnice f(x) = 0 je hledáno ve směru tečny funkce f(x).

Popis algoritmu

Newtonova metoda tečen slouží k nalezení řešení rovnice f(x) = 0 za předpokladu, že známe derivaci funkce f'(x), tedy směrnici tečny. Pro jednoduchost dále předpokládejme, že x i f(x) jsou skaláry.

Animovaná ukázka hledání řešení f(x)=0.

Dalším nezbytným předpokladem je znalost počáteční hodnoty x_0, v jejíž blízkosti hledáme řešení. Pokud se funkce f(x) chová rozumně (je spojitá, hladká a monotónní v intervalu, ve kterém hledáme řešení), lze očekávat řešení v místě, kde tečna sestrojená z bodu f(x_0) protíná osu x. +more (Směrnice této tečny je f'(x_0). ) Tento průsečík označíme x_1 a vypočteme jej podle následujícího vztahu.

:x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}

Za splnění výše uvedených předpokladů by měla hodnota f(x_1) být blíže nule než původní f(x_0). Stejný postup můžeme opakovat a najít tak ještě přesnější hodnotu x_k.

:x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}

Iteraci provádíme tak dlouho, dokud hodnota f(x_0) neleží dostatečně blízko nuly. Pokud metoda konverguje a pokud kořen není násobný, je konvergence velice rychlá. +more S každou iterací se přibližně zdvojnásobí počet desetinných míst, která jsou správně (přesněji, konvergence je kvadratická). Častým kriteriem pro ukončení výpočtu proto bývá okamžik, kdy vzdálenost dvou po sobě jdoucích iterací je dostatečně malá.

Odvození iteračního vzorce

Víme, že rovnice tečny tk funkce f(x) v libovolném bodě xk je dána vzorcem, jelikož derivace je směrnicí tečny (koeficient lineárního členu):

t_k : y = f'(x_k) \cdot x + b

Zároveň také víme, že tečna tk prochází bodem \left [ x_k, f(x_k) \right ]. Po dosazení:

f(x_k) = f'(x_k) \cdot x_k + b

b = f(x_k) - f'(x_k) \cdot x_k

Hledáme bod \left [ x_{k+1}, 0 \right ], což je průnik tečny tk v bodě xk s osou x, a zároveň dosadíme vyjádřené b:

0 = f'(x_k) \cdot x_{k+1} + f(x_k) - f'(x_k) \cdot x_k

f'(x_k) \cdot x_{k+1} = f'(x_k) \cdot x_k - f (x_k)

Odtud již plyne:

x_{k+1} = x_{k} - \frac{f(x_k)}{f'(x_k)}

Příklad: Výpočet druhé odmocniny

Úkolem je vypočítat druhou odmocninu kladného reálného čísla a.

:x = \sqrt{a}

Problém lze definovat také jako nalezení kořenu funkce f(x) = x^2 - a, neboli řešení rovnice f(x) = 0.

Vypočteme derivaci f'(x).

:f'(x) = 2x

Dosadíme do obecného vzorce a upravíme.

: x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{x_k^2-a}{2x_k}

: x_{k+1} = \frac{1}{2} \left( x_k + \frac{a}{x_k} \right)

Získáváme tak rekurentní rovnici, u které jako počáteční podmínku můžeme zvolit x_0 = a.

Ukázka výpočtu x = \sqrt{9}, neboli x^2-9 = 0, metodou tečen. +more Výpočet \sqrt{9} (druhé odmocniny z devíti) bude podle výše uvedeného algoritmu probíhat následovně.

a = 9 x0 = 9 x1 = 5 x2 = 3.4 x3 = 3.02352941176471 x4 = 3.00009155413138 x5 = 3.00000000139698 x6 = 3.00000000000000 x7 = 3.00000000000000

Je vidět, že po několika málo krocích se hodnota x_k nemění a ustálí se (konverguje) na hodnotě 3, což odpovídá správnému výsledku.

Poznámky

Aproximace derivace

Pokud známe pouze funkci f(x) a neznáme její derivaci f'(x), můžeme se pokusit derivaci nahradit numerickou derivací. Případně je možné řešit úlohu metodou sečen, která znalost derivace nevyžaduje.

Vektory

Je-li funkce f(x) skalární funkcí vektorového argumentu („z vektoru vypočte skalár“), je nutné hledat xk+1 proti směru gradientu. Předpis pro iteraci lze potom napsat následovně.

:\mathbf x_{k+1} = \mathbf x_k - \Delta \mathbf x_k

: \Delta \mathbf x = \left[ \begin{matrix} \frac{f(\mathbf x)}{\frac{\partial f}{\partial x_1}}, \ldots, \frac{f(\mathbf x)}{\frac{\partial f}{\partial x_n}} \end{matrix} \right]^T

Pokud je funkce f(x) vektorovou funkcí vektorového argumentu („z vektoru vypočte vektor“), lze předpis pro iteraci napsat následovně.

:\mathbf x_{k+1} = \mathbf x_k - \mathbf J (\mathbf x_k) ^ {-1} \mathbf f(\mathbf x_k)

Matice J je takzvaná Jacobiho matice obsahující parciální derivace.

: \mathbf J(\mathbf x) = \frac{\partial f_i}{\partial x_j} = \left[ \begin{matrix} \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} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & \ldots & \frac{\partial f_n}{\partial x_n}\end{matrix} \right]

Související články

Fraktál Newton - fraktál generovaný Newtonovou metodou * Linearizace - jedním ze způsobů linearizace je nahrazení části křivky její tečnou

Externí odkazy

Newtonova metoda: http://math. fce. +morevutbr. cz/vyuka/matematika/numericke_metody/node10. html * Řešení rovnic, Newtonova metoda: https://web. archive. org/web/20071031001614/http://vydra. troja. mff. cuni. cz/bobo/fyzika/num3_metodanewtonova. cz.

Kategorie:Numerická matematika