The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b01dma [2025/05/30 23:45] – [Příklad (silná indukce)] zapleka3statnice:bakalar:b4b01dma [2025/05/31 10:26] (current) – [Příklad 2 – násobný kořen] mistrjirka
Line 423: Line 423:
 Je-li $n+1$ složené, rozdělíme ho na dva menší činitele $a,b$ (to lze díky tomu že víme, že čísla která nejsou prvočíslo jsou dělitelná ne jen sama sebou a 1) a pro oba už známe rozklad (protože čísla jsou menší než $n$ a pro ty už jsme si to dokázali) → jejich součinem dostaneme Je-li $n+1$ složené, rozdělíme ho na dva menší činitele $a,b$ (to lze díky tomu že víme, že čísla která nejsou prvočíslo jsou dělitelná ne jen sama sebou a 1) a pro oba už známe rozklad (protože čísla jsou menší než $n$ a pro ty už jsme si to dokázali) → jejich součinem dostaneme
 rozklad i pro $n+1$.   rozklad i pro $n+1$.  
 +
 ===== 7. Rekurentní rovnice =====  ===== 7. Rekurentní rovnice ===== 
 +
  – základní vlastnosti homogenních lineárních rekurentních rovnic (jejich množina řešení tvoří vektorový prostor dimenze rovné řádu rovnice, takže řešení lze generovat pomocí vhodné báze), jak najít vhodnou bázi (pomocí kořenů charakteristického polynomu).  – základní vlastnosti homogenních lineárních rekurentních rovnic (jejich množina řešení tvoří vektorový prostor dimenze rovné řádu rovnice, takže řešení lze generovat pomocí vhodné báze), jak najít vhodnou bázi (pomocí kořenů charakteristického polynomu).
  
-**Definice:** Rekurentní vztah či rekurzivní vztah pro posloupnost ${a_k}$ je libovolná rovnice typu +**Definice:**  
-$F(a_n, a_{n-1}, a_{n-2}, \dots, a_0) = 0$, kde $F$ je nějaká funkce. Např. podstata problému Hanojských věží se dá vyjádřit vztahem + 
-$H_n - 2 \cdot H_{n-1} - 1 = 0$.+Rekurentní (nebo také rekurzivní) vztah pro posloupnost $\{a_k\}$ je libovolná rovnice typu: 
 +$$ 
 +F(a_n, a_{n-1}, a_{n-2}, \dots, a_0) = 0 
 +$$ 
 +kde $F$ je nějaká funkce. 
 + 
 +Například problém Hanojských věží lze vyjádřit vztahem: 
 +$$ 
 +H_n = 2 \cdot H_{n-1} + 1 
 +\quad\text{tedy}\quad 
 +H_n - 2H_{n-1} - 1 = 0 
 +$$
  
 ====Lineární rekurentní rovnice====  ====Lineární rekurentní rovnice==== 
-popřípadě **lineární rekurzivní rovnice** řádu $k \in \mathbb{N}_0$ je libovolná rovnice ve tvaru 
  
-$a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_2(n)a_{n+2} + c_1(n)a_{n+1} + c_0(n)a_n = b_n$ pro všechna $n \geq n_0$,+Lineární rekurentní rovnice (nebo také lineární rekurzivní rovnice) **řádu $k$** je rovnice tvaru: 
 +$$ 
 +a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n 
 +\quad \text{pro všechna } n \geq n_0 
 +$$
  
-kde $n_0 \in \mathbb{Z}$, $c_i(n)$ pro $i = {0, \dots, k-1}$ (tzv. koeficienty rovnice) jsou nějaké funkce $\mathbb{Z} \mapsto \mathbb{R}$, přičemž $c_0(n)$ není identicky nulová funkce, a ${b_n}_{n\geq n_0}$ (tzv. pravá strana rovnice) je pevně zvolená posloupnost reálných čísel. +  * $k$ je řád rovnice – největší indexový posun v levé straně. 
-Jestliže $b_n = 0$ pro všechna $n \geq n_0$, pak se příslušná rovnice nazývá homogenní.+  * Koeficienty $c_i(n)$ jsou funkce $\mathbb{Z} \to \mathbb{R}$ (mohou být konstantní nebo závislé na $n$). 
 +  * $b_n$ je tzv. pravá strana rovnice (např. nulová, nebo jiná posloupnost).
  
-  * Základní vlastnosti – jejich množina řešení tvoří vektorový prostor dimenze rovné řádu rovnice, takže řešení lze generovat pomocí vhodné báze.+Rovnice se nazývá **homogenní**, pokud platí $b_n = 0$ pro všechna $n \geq n_0$.
  
-  * Jak najít vhodnou bázi – pomocí kořenů charakteristického polynomu.+  * Množina všech řešení homogenní rovnice tvoří **vektorový prostor** dimenze $k$. 
 +  * Řešení lze vyjádřit pomocí **báze** tohoto prostoru, kterou určujeme z kořenů tzv. charakteristického polynomu.
  
 ====Řešení==== ====Řešení====
  
-Nechť je dána **lineární rekurentní rovnice**+Nechť je dána lineární rekurentní rovnice: 
 +$$ 
 +a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n 
 +$$
  
-$a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n$ pro všechna $n \geq n_0$. +**Řešením** rozumíme posloupnost $\{a_n\}_{n=n_0}^\infty$, která po dosazení splňuje rovnici pro všechna $n \geq n_0$.
- +
-Jako její řešení označíme libovolnou posloupnost $\{a_n\}_{n=n_0}^{\infty}$ takovou, že po dosazení odpovídajících členů do dané rovnice dostáváme pro všechna $n$ pravdivý výrok.+
  
 ====Charakteristická rovnice==== ====Charakteristická rovnice====
  
 **Definice:** **Definice:**
-Nechť je dána lineární rekurentní rovnice s konstantními koeficienty+$$ 
 +a_{n+k} + c_{k-1}a_{n+k-1} + \dots + c_0a_n = b_n 
 +$$ 
 + 
 +Pokud je $b_n = 0$ pro všechna $n$, rovnice se nazývá **homogenní** a můžeme k ní přiřadit **charakteristický polynom**: 
 +$$ 
 +p(\lambda) = \lambda^k + c_{k-1}\lambda^{k-1} + \dots + c_1\lambda + c_0 
 +$$ 
 + 
 +Řešením rovnice $p(\lambda) = 0$ (tzv. **charakteristická rovnice**) jsou tzv. **charakteristická čísla** (nebo také **kořeny** či „vlastní čísla“). 
 + 
 +  * Každé charakteristické číslo $\lambda$ generuje **jednu základní posloupnost** $a_n=\lambda^n$. Mluvíme-li o „vektorovém prostoru“, nemyslíme tím čísla $\lambda$, ale **množinu všech posloupností** vzniklých lineárními kombinacemi těchto základních posloupností. 
 +  * Pokud má polynom $p$ více různých kořenů $\lambda_1,\dots,\lambda_m$, tvoří **bázi** prostoru řešení posloupnosti $\lambda_1^n,\dots,\lambda_m^n$. Libovolná lineární kombinace 
 +$$ 
 +a_n = \alpha_1\lambda_1^n+\dots+\alpha_m\lambda_m^n 
 +$$ 
 +    * je také řešením, takže celý prostor řešení má dimenzi $m$. 
 +  * Má-li některý kořen násobnost $r>1$, přidávají se do báze i členy $n\lambda^n,\,n^2\lambda^n,\dots,n^{r-1}\lambda^n$, aby dimenze prostoru zůstala rovna řádu $k$. 
 + 
 +Pomocí těchto tvarů sestavíme obecné řešení homogenní rovnice – každý kořen přispívá jedním nebo více lineárně nezávislými členy. 
 + 
 +====Příklad 1 – dva různé kořeny==== 
 + 
 +Homogenní rovnice druhého řádu 
 +$$ 
 +a_{n+2}-3a_{n+1}+2a_n=0 
 +$$ 
 +má charakteristický polynom $p(\lambda)=\lambda^2-3\lambda+2$   
 +a kořeny $\lambda_1=1,\;\lambda_2=2$. 
 + 
 +  * Základní řešení: $u_n = 1^n = 1$, $v_n = 2^n$. 
 +  * Obecné řešení: $$a_n = \alpha\cdot1 + \beta\cdot2^n.$$ 
 +  * Prostor všech řešení je tedy 2-rozměrný a jeho (jednou z možných) bází je $\{\,1,\,2^n\}$. 
 + 
 +====Příklad 2 – násobný kořen==== 
 + 
 +Rovnice 
 +$$ 
 +a_{n+2}-2a_{n+1}+a_n=0 
 +$$ 
 +má charakteristický polynom $p(\lambda)=(\lambda-1)^2$, kořen $\lambda=1$ s násobností 2.
  
-$a_{n+k} + c_{k-1}a_{n+k-1} + \dots + c_1a_{n+1} + c_0a_n = b_n$ pro všechna $n \geq n_0$.+  * Základní řešení: $u_n = 1^n = 1$, $v_n = n\cdot1^n = n$. 
 +  * Obecné řešení: $$a_n = \alpha + \beta n.$$ 
 +  * Znovu dostáváme 2-rozměrný prostor řešení, tentokrát s bází $\{\,1,\,n\}$.
  
-Její charakteristický polynom (characteristic polynomial) je definován jako polynom 
  
-$p(\lambda) = \lambda^k + c_{k-1}\lambda^{k-1} + \dots + c_1\lambda + c_0$. 
  
-Kořeny charakteristického polynomu se nazývají charakteristická čísla, popřípadě vlastní čísla dané rovnice (characteristic numbers/roots or eigenvalues). 
  
-K získání charakteristických čísel potřebujeme vyřešit rovnici 
-$p(\lambda) = \lambda^k + c_{k-1}\lambda^{k-1} + \dots + c_1\lambda + c_0 = 0$, které se také říká charakteristická rovnice. 

Trace: • syntax

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b01dma (generated for current page)