Opakování Newtonova metoda, metoda tečen *k+l = Xk - —-- f(Xk) Newtonova metoda je metoda druhého řádu pro jednoduchý kořen £. Fourierovy podmínky Věta Nechť f E C2[a, b] a nechť rovnice f (x) = 0 má v intervalu jediný kořen £. Nechť f, f" nemění znaménka na intervalu [a,b], přičemž f'(x) ^ 0, Vx G [a,b]. Nechť počáteční aproximace x° je ten z krajních bodů a, b, v němž znaménko funkce je stejné jako znaménko f" na intervalu [a, b]. Pak posloupnost {x/(}^l0 určená Newtonovou metodou konverguje monotónně k bodu £. Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 2/15 Metoda sečen Derivaci v bodě x,- u Newtonovy metody nahradíme sěrnicí sečny v bodech [xk-i,f(xk_x) a [xk, f(xk). Xk - xk i Xfe+i =xk- j-j----zt{xk), i = 1,2,... f(ki) - ř(xfe_i) Pozor! Při pokusu o co nejpřesnější výpočet může dojít k nedefinovanému výrazu typu 0/0. Věta Nechť rovnice f(x) = 0 má kořen £ a nechť derivace f, f" jsou spojité v okolí bodu £, přičemž /"'(£) 7^ 0. Posloupnost určená metodou sečen konverguje ke kořenu £, pokud zvolíme počáteční aproximace x0, xx dostatečně blízko bodu £ a metoda je řádu (1 + VŠ)/2 = 1,618. Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 3/15 Metoda regula falsi Předpokládejme f(a)f(b) < 0, f G C[a,b]. Použijeme metodu sečen, přitom vybíráme iterace tak, aby ve dvou po sobě jdoucích měla f opačné znaménko: xk+i =xk- -jt^—^—f(xk), k = 0,1,..., t(xk) - t(xs) kde s = s(k) je největší index takový, že f(xk)f(xs) < 0, přitom f(x0)f(x1) < 0 (tj. např. x0 = a, x1 = b). Poznámka: pokud je funkce f konvexní nebo konkávni na [a, b], je xs jeden z krajní bodů intervalu. Řád metody: 1 Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 4/15 Quasi Newtonova metoda (plus/minus) Tečnu u Newtonovy metody nahradíme sečnou procházející bodem (xk, f(xk)) a bodem (xk + f(xk), f(xk + f(xk))), respektive bodem (xk — f(xk), f(xk — f(xk))). Přitom pokud je bod xk blízko hledaného kořene £, pak hodnota f(xk) je blízká nule a sečna procházející uvedenými body je blízká tečně vedené bodem xk. Xk+l = Xk ± fix,) - f(xk ± f(xk)) Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 5/15 Iteracní funkce: f2 (x) g{x)-X±f(x)-f(x±f(x)) Poznámka: Quasi Newtonova metoda se také někdy nazývá Steffensenova - viz dále. Věta Nechť f G C1 [a, b], £ G [a, b] nechť je řešením rovnice f(x) = 0 a /"'(£) ý 0- existuje e > 0 tak, že posloupnost {x*}^_0 generovaná quasi Newtonovou metodou konverguje k bodu £ pro každou počáteční aproximaci x° G [£ — £,£ + e] n [a, b]. Pokud má funkce f v okolí bodu £ spojitou druhou derivaci, je řád metody alespoň 2. Důkaz: ĽHospitalovo pravidlo. < □ ► < fll ► 1. Pak modifikovaná Newtonova metoda =xk- M je metoda druhého řádu. Důkaz: Konec opakování Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 7/15 Urychlení konvergence - Aitkenova č2-metoda Veta Nechť je dána posloupnost {x*}£l0, Xk ý k = 0,1,2,..., lim Xk = £, a nechť tato posloupnost splňuje podmínky Xk+i-Š = (C+7*)(x*-£), k = 0,1,2,..., \C\<1, lim 7fe = 0. K—^oo Pak posloupnost (Xk+1 - Xkf xk+2 - 2xk+i + xk je definována pro všechna dostatečně velká k a platí *k-€ lim k—>oo Xk — C, o, tj. posloupnost {xk} konverguje k limitě £ rychleji než posloupnost {xk}. Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 8/15 Geometrická interpretace Položme e(xk) = xk - xk+i = xk - £ - (xk+1 - £) = (xk - £)(1 + C + jk) z{xk+i) = *k+i ~ xk+2 = {xk+i - Oí1 + C + 7/c+i) = = {xk - £)(C + 7*)(1 + C + lk+1) « e(x*)(C + 7*) 0.05 0.1 0.15 0.2 0.25 0.3 0.35 <9> <1> l -00.0 JiŕT Zelinka Numerické metody 5. přednáška, 18. března 2015 9/15 Rovnice přímky: t , e{xk) - e{xk+1) y - e{xk) =-(x - xk) Xk — Xk+l Průsečík s osou x (y = 0) je bod xk t{xk){xk ~ xk+i) (xk+1 - xk) 2 Xk = Xk--r-z-r- = Xk e(xk) - e(xk+1) xk+2 - 2xk+1 + xk Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 10 / 15 Steffen se nova metoda Buď g iterační funkce pro rovnici x = g{x). Položme Yk = g{xk), zk = g(yk), (y/c - *k)2 Xk+l = xk zk - 2yk + xk V tomto případě je tedy e(xk) = xk - yk, e{yk) = yk - zk. Tato iterační metoda se nazývá Steffensenova a může být popsána iterační funkcí g{X) {g{X))- Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 11 / 15 / n *kg(g(xk)) ~ g2{xk) xkg(yk) - (yk) V{Xk) g{g{xk)) - 2g(xk) + xk g(yk) - 2yk + xk xkzk - (yk)2 _ xk(zk - 2yk + xk) - (yk - xkf *k ~ 2y7c + xk zk- 2yk + xk {yk ~ xk)2 = xk-- zk - 2y'k + xk Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 12 / 15 Veta O y?(£) = £ implikuje g(£) = £. O Jestliže g(0 = £, existuje a 7^ 1, pak m = c Věta Nechť funkce g má spojité derivace až do řádu p + 1 včetně v okolí bodu x = £. Nechť iterační metoda x*+i = g"(x*) je řádu p pro bod £. Pak pro p > 1 je iterační metoda x*+i = V?(x/c) řádu 2p — 1. Pro p = 1 je tato metoda řádu alespoň 2 za předpokladu 7^ I- Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 13 / 15 Múllerova metoda Múllerova metoda je zobecněním metody sečen. Metoda sečen v podstatě znamená, že pro dané aproximace Xk, Xk i bodu £ aproximujeme funkci f přímkou procházející body [*k-i, f{*k-i)], [xk, f{xk)] a za další aproximaci bodu £ vezmeme průsečík této přímky s osou x. Múllerova metoda užívá tři aproximace Xk 2, xfc-i. *k a křivku y = f (x) aproximujeme parabolou určenou těmito body. Průsečík této paraboly s osou x, který je nejbližší k Xk, vezmeme za další aproximaci xk+\. Touto metodou lze najít i násobné a komplexní kořeny. Jiří Zelinka Numerické metody 5. přednáška, 18. března 2015 14 / 15 xk 2. xk-i. x/c jsou již vypočtené aproximace. Sestrojme polynom P(x) = a(x - xkf + b(x -xk) + c procházející body [x*_2, f(x*_2)], [x*_i, f (x*_i)], [x*,f(x*)], t.j. splňující podmínky P(x') = f(x'), i = k — 2, k — 1, k. Z nich plyne = fW _ {Xk-2 ~ Xkf [f{> < & > 4 * * a * > « -O^O-Jin Zelinka Numerické metody 5. přednáška, 18. března 2015 15 / 15