Lineární modely -11. přednáška Lineární diferenční rovnice Ondřej Klíma 2. 5. 2013 11. přednáška Lineární diferenční rovnice Osnova přednášky • Reálné polynomy a jejich kořeny • Lineární diferenční rovnice • Homogenní lineární diferenční rovnice • Nehomogenní lineární diferenční rovnice 11. přednáška Lineární diferenční rovnice Polynomy s reálnými koeficienty • Kořen polynomu f g K[x] je c g K takové, že f (c) = 0. • Prvek c g K je kořenem f právě tehdy, když (x - c) | f. m Argument: dělíme se zbytkem f = (x - c) ■ q + r, kde r je polynom menšího stupně, tzn. konstanta. • Nechť f g K[x] je nenulový polynom a c g K kořen f. Přirozené číslo k se nazývá násobnost kořene c, jestliže (x - c)k | f a (x - c)^1 f ŕ. • Nenulový polynom f g C [x] stupně n má právě n kořenů, počítáme-li je i s jejich násobností. • Je-li c dvojnásobný kořen f, pak f (x) = (x - c)2g(x). Proto c je kořenem ŕ'(x) = 2(x - c)flf + (x - c) V = (x - c)(...). • Je-li f polynom s reálnými koeficienty a c jeho kořen, potom komplexně sdružené číslo č je také kořenem f. 11. přednáška Lineární diferenční rovnice Homérovo schéma • Jak se efektivně počítá f (c)? m Nechť f (x) = anxn + an_-|xn~1 h-----v a^x + a0. Pak f {x) = ((... ((a„x + a„_i) • x + an_2) • • •) • x + aA) ■ x + a0 • Proto po dosazení c máme f {c) = ((••• ((a„c + a„_i) • c + an_2) • • •) • c + aA) • c + a0 • Homérovo schéma je tabulkový zápis tohoto výpočtu: an an_i . ... a(- .. . ... a! a0 c b, .. • bi b0 f(c) kde = £>,■• c + a,-, f (c) = b0 ■ c + a0. 11. přednáška Lineární diferenční rovnice Homérovo schéma - příklad Příklad Určete zda je c = -3 kořenem polynomu f = 2x6 + 5x5 - 2x4 - 7x2 + 5x - 3. 2 5 -2 0 -7 5 -3 -3 2 -1 1 -3 2 -1 0 Proto f{-3) = 0. 11. přednáška Lineární diferenční rovnice Homérovo schéma - pokračování Pro dělení se zbytkem f(x) = (x - c) ■ q + r, platí r = f(c). Nechť f = anxn + an_-|xn~1 h-----h a-|x + a0, q = fcn-ix"-1 + • • • + £hx + £>0. Porovnejme koeficienty v f(x) = (x - c) ■ q + r. Dostaneme: xn an = Ďn_i /?n_i = an xn~1 an_! = Ďn_2 - c bn_2 = bn^ c + an^ x' a,- = - bj ■ c = bj ■ c + a, x a-\ = b0 - b-\C b0 = b-\C + a0 a0 = r- b0c r = b0c + a0 3n 3n-1 . ... a(- .. . ... a^ a0 c • • ■ bi b0 r 11. přednáška Lineární diferenční rovnice Homérovo schéma - příklad - násobnost kořenů Příklad ^ Určete násobnost kořenu c = -3 polynomu f = 2x6 + 5x5 - 2x4 - 7x2 + 5x - 3. 2 5 -2 0 -7 5 -3 -3 2 -1 1 -3 2 -1 0 • Tedy f(x) = (x + 3)(2x5 - x4 + x3 - 3x2 + 2x - 1). • c = -3 je vícenásobný, jestliže je kořenem polynomu 2x5 - x4 + x3 - 3x2 + 2x - 1 . 2 -1 1 -3 2 -1 -3 2 -7 22 -69 209 -628 Není. 11. přednáška Lineární diferenční rovnice Racionální kořeny Věta Nechť f = anxn + an_-|Xn~1 h-----\- a-|X + a0 e Z[x] a £ ye racionální kořen polynomu f takový, že p,q e Z, q > 0 a nsd(p, qr) = 1. Pa/c qr | a„,p | a0. Příklad Nalezněte všechny racionální kořeny polynomu f[x) = 4x3 + x2 - x + 5. Pokud je racionální číslo c kořenem f, pak cg {1,-1,5,-5,-,--,-,--}. Pozn: v předchozím příkladu jsme násobnost nemuseli zkoušet. 11. přednáška Lineární diferenční rovnice Diferenční rovnice Definice Diferenční rovnice řádu k je formule f (n + k) = F(n, f (n), f (n + 1),..., f (n + k - 1)), kde F je funkce v k + 1 promněnných. Posloupnost f(0), ...,f(k- 1) nazýváme počáteční podmínky. Funkce F a počáteční podmínky jednoznačně určují posloupnost 11. přednáška Lineární diferenční rovnice Lineární diferenční rovnice Definice Diferenční rovnice se nazývá lineární, jestliže existují skaláry(konstanty) a0, a-i,..., ak, b takové, že F(x0, Xt ,..., xk) = a0x0 + é?ix-| + • • • + akxk + b. Příklad (Lineární diferenční rovnice druhého řádu) Fibonacciho posloupnost (vycházení schodů) P(n + 2) = P(n+V + P(n), p(0)=p(1) = 1 je lineární diferenční rovnice. Zde dokonce a0 = b = 0. (a-i = a2 = 1). 11. přednáška Lineární diferenční rovnice Homogenní lineární diferenční rovnice Definice Homogenní lineární diferenční rovnice řádu k je formule f(n + k) = aA f(n) + a2f(n + 1), • • • + akf(n + k - 1). • Píšeme také: Xn + fyXn-i + • • • + bkxn_k = 0. 9 Hovoříme též o homogenní lineární rekurenci. • Řešení je nekonečná poslopnost x = (xn)^0 g • Součet dvou řešení je opět řešení. • Skalární násobek řešení je opět řešení. • Množina řešení je vektorovým prostorem a každý vektor je jednoznačně dán posloupností x = {xn)knzl e • Tzn. dimenze je rovna řádu k. • Rádi bychom nalezli vhodná bázická řešení. • Ostatní řešení dostaneme jako jejich lineární kombinace. 11. přednáška Lineární diferenční rovnice Hledání bazických řešení o Uvažujme možnost xn = Xn pro nějaký skalár A. • Pak dostáváme podmínku \"-k{\k+ bi\k^ ■■■ + bk) = 0 • Ta znamená, že buď A = 0 nebo je A kořenem tzv. charakteristického polynomu v závorce. • Zde předpokládáme bk ^ 0, tj. 0 není kořenem charakteristického polynomu. • Předpokládejme, že charakteristický polynom má k různých kořenů \-\,... ,\k. 9 Každý z kořenů nám dává jedno možné řešení xn = (A,)n. • Můžeme za tímto účelem rozšířit uvažované pole skalárů z M na C (později). 11. přednáška Lineární diferenční rovnice Hledání bazických řešení - pokračování • Nezávislost plyne z nezávislosti k vektorů (1, A/, Xf,..., Xj ). • K tomu se použije Vandermondův determinant: Ai A2 A3 1 xk X\ A2, , Ar 1 , Ar 1 A Ar 1 n 1 ) g M a také ^(A? - A£) = |z|nsin(/i(^) g M (pro libovolné n). • Řešení rekurence jsou také xn = c ■ \z\n cos(rkp) + d ■ \z\n s\n(ri(p), kde c, d jsou libovolná reálná čísla. • Opět potřebujeme nezávislost a můžeme kombinovat s ostatními bazickými řešeními. 11. přednáška Lineární diferenční rovnice Příklad — nereálné kořeny • Rekurence xn = 2xn_-| - 2xn_2,x0 = 0,x-| = 1 . • Charakteristický polynom: A2 - 2A + 2 = (A - 1 )2 + 1 . • Kořeny A1j2 = 1 ± / = V2(cos f ± /sin ^). • Explicitní vztah p(n) = c- V2~ncos(^f) + d ■ V2~nsin(^f), kde p(0) = 0,p(1) = 1. • Tedy 0 = c a 1 = c + d. Tj. d = 1. • Celkem p(n) = V2 sin(—). 11. přednáška Lineární diferenční rovnice Nehomogenní diferenční rovnice • Nehomogenní lineární diferenční rovnice řádu k je formule f(n + k) = aA f(n) + a2f{n + 1), • • • + akf(n + k - 1) + b(ri), kde a-i,..., ak jsou skaláry (z R) a b polynom (nad R). • Všechna řešení nehomogenních lineárních diferenčních rovnic můžeme dostat tak, že najdeme jedno řešení a přičteme celý vektorový prostor dimenze k řešení odpovídajících zhomogenizované diferenční rovnici. • Hledáme (tzv. partikulární) řešení ve tvaru polynomu xn = "o + "1 n H-----h asns s neznámými koeficienty a-„ i = 1,..., s, kde s je stupeň polynomu b. • Dosazením do diferenční rovnice dostatneme systém s + 1 rovnic pro s + 1 proměnných a,. 11. přednáška Lineární diferenční rovnice Příklad — nehomogenní diferenční rovnice Příklad Najděte posloupnost, která vyhovuje nehomogenní diferenční rovnici s počátečními podmínkami: xn+2 = xn+A + 2xn - n, X0 = 2, XA = 5. • Obecné řešení zhomogenizované rovnice je tvaru a(-1)n + /?2n. o Partikulárním řešením je ^ + \ . • Obecné řešení dané nehomogenní rovnice bez počátečních podmínek je tedy a(-1 )n + b2n + ^ + \. • Dosazením do počátečních podmínek zjistíme konstanty a = -\, b = 2. Dané rovnici s počátečními podmínkami tedy vyhovuje posloupnost i(-iri+2"+i + ^ + i 11. přednáška Lineární diferenční rovnice Shrnutí • Prostor všech řešení homogenní lineání diferenční rovnice řádu k je vektorový prostor dimenze k. m Všechna řešení jsou generována fundamentálním systémem k řešení, který lze obdržet z kořenů charakteristického polynomu. • Všechna řešení nehomogenní lineání diferenční rovnice obdržíme, když přičteme jedno pevně zvolené partikulární řešení ke všem řešením zhomogenizované lineání diferenční rovnice. 9 Řešení vyhovující daným počátečním podmínkám Xq = f0,..., Xfc_i = fk_-\ hledáme z obecného řešení dosazením podmínek a určením koeficientů lineání kombinace fundamentálních řešení. 11. přednáška Lineární diferenční rovnice Požadavky Řešení lineárních diferenčních rovnic • řádu 2 a 3 • a to homogenních i nehomogenních • s to i s násobými a komplexními kořeny 11. přednáška Lineární diferenční rovnice