Toistuva kaava

Toistuva kaava on muotoa , joka ilmaisee sarjan jokaisen jäsenen aiempien jäsenten ja sekvenssin jäsenen numeron perusteella . $a_{n}=f(n,a_{n-1},a_{n-2},\dots ,a_{np})$ $a_n$ $s$ $n$

Rekursiivisia kaavoja käyttävien laskelmien yleinen ongelma on rekursiivisten funktioiden teorian aihe .

Toistuva yhtälö on yhtälö, joka yhdistää tietyn numeerisen sekvenssin useita peräkkäisiä jäseniä. Sellaista sekvenssiä, joka täyttää tällaisen yhtälön, kutsutaan toistuvaksi sekvenssiksi .

Esimerkkejä

Luonnollisen luvun tekijäfunktio täyttää toistuvan kaavan: $n!={\begin{cases}1,&n=0;\\(n-1)!\cdot n,&n\geqslant 1.\end{cases))$

Fibonacci-luvut saadaan lineaarisella toistuvalla kaavalla : $F_{n}={\begin{cases}0,&n=0;\\1,&n=1;\\F_{n-1}+F_{n-2},&n\geqslant 2.\ lopeta{tapaukset}}$

Integraalin arvo täyttää toistuvan kaavan: $\textstyle I_{n}=\int \sin ^{n}x\,dx$ $I_{n}={\frac {-\cos x\cdot \sin ^{n-1}x}{n}}+{\frac {n-1}{n}}I_{n-2 }.$

Besselin differentiaaliyhtälön ratkaisu voidaan kirjoittaa potenssisarjana : $y''+(1/x)y'+(1-\nu ^{2}/x^{2})y=0$ $y=\sum \limits _{n=0}^{\infty }a_{n}x^{2n+\nu }.$

Kertoimien määrittämiseksi riittää todeta se kaikille . Sen jälkeen saadaan heti tunnettu tulos:

a_n

4n(n+\nu )a_{n}+a_{n-2}=0

n\geq 1

a_{n}={\frac {(-1)^{n}a_{0}}{2^{2^{n}}n!(1+\nu )(2+\nu )\ cdots (n+\nu )}}.

Sivun pituus kaksinkertaistettaessa säännöllisen n - kulman sivujen lukumäärä : $a_{2n}={\sqrt {2R^{2}-2R{\sqrt {R^{2}-{\frac {a_{n}^{2}}{4}}}}}} ,\qquad n\geq 2,$

missä on rajatun ympyrän säde .

R

Lineaariset toistuvat yhtälöt

Lineaarisella toistuvalla yhtälöllä vakiokertoimilla on muoto:

f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=\varphi (n).

Tässä on ei-negatiivisia kokonaislukuja, on numerosarja, ovat vakiolukuja, , on annettu funktiolle . $n$ $f_{{n}}$ ${\displaystyle a_{1},a_{2},\ldots ,a_{r))$ $a_{{r}}\neq 0$ $\varphi (n)$ $n$

Homogeeniset lineaariset toistuvat yhtälöt

Oletetaan, että sarja numeroita täyttää homogeeninen lineaarinen toistuva yhtälö , jossa ovat ei-negatiivisia kokonaislukuja, annetaan vakionumeroita ja . $f_{0},f_{1},\dots$ $f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=0$ $n$ ${\displaystyle a_{1},\ldots ,a_{r))$ $a_{{r}}\neq 0$

Merkitään sekvenssin generoivalla funktiolla . Rakennetaan polynomi . Tätä polynomia voidaan pitää sekvenssiä generoivana funktiona . Tarkastellaan funktioiden generointituloa . Kerroin kohdassa ja määräytyy relaatiolla ja on yhtä suuri kuin nolla. Tämä tarkoittaa, että polynomilla on korkeintaan aste , joten rationaalisen funktion osoittajan aste on pienempi kuin nimittäjän aste. $F(z)$ $f_{0},f_{1},\dots$ ${\displaystyle K(z)=1+a_{1}z+a_{2}z^{2}+\ldots +a_{r}z^{r))$ $1,a_{1},a_{2},\ldots ,a_{r},0,0,\dots$ $C(z)=F(z)K(z)$ $c_{{n+r}}$ $z^{{n+r}}$ $n\geq 0$ $c_{n+r}=f_{0}0+\ldots +f_{n-1}0+f_{n}a_{r}+\ldots +f_{n+r}1=f_{n +r}+a_{1}f_{n+r-1}+\lpisteet +a_{r}f_{n}$ $C(z)$ $r-1$ $F(z)={\frac {C(z)}{K(z)}}$

Lineaarisen toistuvan yhtälön ominaispolynomia kutsutaan polynomiksi . Tämän polynomin juuria kutsutaan ominaispiirteiksi. Karakterista polynomia voidaan esittää muodossa , jossa ovat eri ominaisjuuret, ovat tunnusomaisten juurien monikertoja, . ${\displaystyle g(z)=z^{r}+a_{1}z^{r-1}+\ldots +a_{r))$ $g(z)=(z-\alpha _{1})^{e_{1}}(z-\alpha _{2})^{e_{2}}\cdots (z-\alpha _ {s})^{e_{s}}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{s))$ ${\displaystyle e_{1},\ldots ,e_{s))$ $e_{1}+e_{2}+\ldots +e_{s}=r$

Karakteripolynomi ja polynomi liittyvät toisiinsa relaatiolla . Tällä tavalla, $g(z)$ $K(z)$ $K(z)=z^{r}g\left({\frac {1}{z}}\right)$

K(z)=(1-\alpha _{1}z)^{e_{1}}(1-\alpha _{2}z)^{e_{2}}\cdots (1-\ alfa _{s}z)^{e_{s}}.

Rationaalinen funktio voidaan esittää murtolukujen summana:

F(z)={\frac {C(z)}{K(z)}}=\sum _{i=1}^{s}\sum _{k=1}^{e_{i }}{\frac {\beta _{ik}}{(1-\alpha _{i}z)^{k}}}.

Jokaisella tämän lausekkeen murto-osalla on muoto , joten se voidaan laajentaa seuraavan muotoiseksi potenssisarjaksi $\beta (1-\alpha z)^{{-k}}$

\beta (1-\alpha z)^{-k}=\beta \left[1+(-k)(-\alpha z)+\ldots +{\frac {(-k)\cdots ( -k-n+1)}{n!}}(-\alpha z)^{n}+\ldots \right]

Kerroin for tässä sarjassa on yhtä suuri $z^{n}$

{\frac {\beta (n+k-1)\cdots k}{n!)}}\alpha ^{n}=\beta {\binom {n+k-1}{n}}\ alpha ^{n}=\beta {\binom {n+k-1}{k-1}}\alpha ^{n}.

Siksi generoiva funktio ja on lineaarisen toistuvan yhtälön yleinen ratkaisu, jossa on polynomi asteina enintään . $F(z)=\sum _{n=0}^{\infty }\left(\sum _{i=1}^{s}p_{i}(n)\alpha _{i}^ {n}\oikea)z^{n}$ $f_{{n}}=\sum _{{i=1}}^{{s}}p_{{i}}(n)\alpha _{{i}}^{{n}}$ $p_{{i}}(n)$ $n$ $e_{{i}}-1$

Esimerkki

Olkoon vaadittava, että yhtälölle on löydettävä ratkaisu reunaehdoilla ja . $f_{{n+2}}-f_{{n+1}}+f_{{n}}=0$ $f_{{0}}=1$ $f_{{1}}=1$

Tällä yhtälöllä on ominaispolynomi , jossa , . Yleisellä ratkaisulla on muoto . Korvaamalla saamme , . Saamme arvot , . Siten . $z^{2}-z+1=(z-\alpha _{1})(z-\alpha _{2})$ $\alpha _{{1}}={\frac {1}{2}}+i{\frac {{\sqrt {3}}}{2}}=e^{{i{\frac {\pi } {3}}}}$ $\alpha _{{2}}={\frac {1}{2}}-i{\frac {{\sqrt {3}}}{2}}=e^{{-i{\frac {\pi }{3}}}}$ $f_{{n}}=c_{{1}}\alpha _{{1}}^{{n}}+c_{{2}}\alpha _{{2}}^{{n}}=c_ {{1}}e^{{{\frac {i\pi n}{3}}}}+c_{{2}}e^{({\frac {-i\pi n}{3}}} }$ $n = 0,1$ $c_{{1}}+c_{{2}}=1$ $c_{{1}}\alpha _{{1}}+c_{{2}}\alpha _{{2}}=1$ $c_{{1}}={\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}$ $c_{{2}}={\frac {1}{2}}+i{\frac {1}{2{\sqrt {3}}}}$ $f_{n}=\left({\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}\right)\left(\cos \left ({\frac {\pi n}{3}}\right)+i\sin \left({\frac {\pi n}{3}}\right)\right)+\left({\frac {1 }{2}}+i{\frac {1}{2{\sqrt {3}}}}\right)\left(\cos \left({\frac {\pi n}{3}}\right) -i\sin \left({\frac {\pi n}{3}}\right)\right)=\cos \left({\frac {\pi n}{3}}\oikea)+{\frac {1}{\sqrt {3}}}\sin \left({\frac {\pi n}{3}}\oikea)$

Sovellukset

On olemassa kaava, joka ilmaisee lineaarisen toistuvan sekvenssin yleistermin sen ominaispolynomin juurina. Esimerkiksi Fibonacci-sekvenssille tällainen kaava on Binet'n kaava . Rekursiivisia kaavoja käytetään kuvaamaan itseään rekursiivisesti kutsuvan algoritmin ajoaikaa. Tällaisessa kaavassa syöttömäärän ongelman ratkaisemiseen tarvittava aika ilmaistaan apualitehtävien ratkaisemiseen käytettynä aikana. [yksi] $n$

Katso myös

Lineaarinen toistuva sekvenssi
rekursiivinen funktio
rekursio
Päälause rekursiivisista suhteista (yksinkertaistettu ratkaisu tietyntyyppisille rekursiivisille suhteille, joita syntyy rekursiivisten algoritmien monimutkaisuuden analysoinnissa)

Muistiinpanot

↑ T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmit. Rakentaminen ja analyysi = Introduction To Algorithms / I. Krasikov. - Kustantaja "Williams", 2005. - S. 79. - 1296 s.

Kirjallisuus

Fujisawa T., Kasami T. Matematiikka radioinsinööreille: diskreettien rakenteiden teoria. - M. , kustantamo = Radio ja viestintä, 1984. - 240 s.