Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI LINEARNA ALGEBRA

Determinante i rekurentna formula

Matrice, determinante...

Determinante i rekurentna formula

Postod heisenberg96 » Petak, 19. Avgust 2016, 23:24

Pozdrav,

Pitanje:

Koje uslove mora da ispunjava neka determinanta [inlmath]n[/inlmath]-tog reda da bi rekli da je ona "pravilna" i mogli primjeniti rekurentnu formulu ?

Da li je to slucaj u ovom zadatku ? Ovdje počinje njena pravilnost, ako se ne varam tek sa [inlmath]n-2[/inlmath] determinantom, pa koja je tu ideja ?
[dispmath]\begin{vmatrix}
3 & 2 & 0 & 0 & \cdots & 0 & 0 & 0\\
1 & 3 & 1 & 0 & \cdots & 0 & 0 & 0\\
0 & 2 & 3 & 2 & \cdots & 0 & 0 & 0\\
\vdots\\
0 & 0 & 0 & 0 & \cdots & 1 & 3 & 1\\
0 & 0 & 0 & 0 & \cdots & 0 & 2 & 3
\end{vmatrix}[/dispmath]
rjesenje je
[dispmath]2^{n+1}-1[/dispmath]
PS. (znam da vas vec i previše smaram ovih par dana i izvinjavam se na tome :oops: )

Hvala unaprijed dobrim ljudima foruma :D :D
Poslednji put menjao Daniel dana Subota, 20. Avgust 2016, 09:44, izmenjena samo jedanput
Razlog: Zamena slike determinante Latex-kodom (hvala, Herien Wolf)
 
Postovi: 10
Zahvalio se: 10 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Determinante i rekurentna formula

Postod Herien Wolf » Petak, 19. Avgust 2016, 23:54

Cenim da je moglo i ovako bez priložene slike. Moj post se odnosi samo na tehničku stranu. Na tvoje pitanje će neko drugi da odgovori :)
[dispmath]\begin{vmatrix}
3 & 2 & 0 & 0 & \cdots & 0 & 0 & 0\\
1 & 3 & 1 & 0 & \cdots & 0 & 0 & 0\\
0 & 2 & 3 & 2 & \cdots & 0 & 0 & 0\\
\vdots\\
0 & 0 & 0 & 0 & \cdots & 1 & 3 & 1\\
0 & 0 & 0 & 0 & \cdots & 0 & 2 & 3
\end{vmatrix}[/dispmath]
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 231
Zahvalio se: 87 puta
Pohvaljen: 213 puta

  • +1

Re: Determinante i rekurentna formula

Postod Trougao » Subota, 20. Avgust 2016, 08:44

Obicno su rekurentne determinante tipa te koju si dao, brojevi na glavnoj i dve sporedne dijagonale. Ako naslutis resenje mozes dokazati indukcijom.
[inlmath]1.[/inlmath] Baza indukcije [inlmath]n=1[/inlmath].
To je determinanta [inlmath]1\times1[/inlmath]. I iz donjeg desnog ugla vidimo da je to samo [inlmath]3[/inlmath].
Znaci [inlmath]D_1=3[/inlmath], uporedimo to sa formulom koju smo pretpostavili resenje. [inlmath]D_1=2^{1+1}-1=2^2-1=4-1=3[/inlmath]
I imamo da je baza tacna.
[inlmath]2.[/inlmath] Korak pretpostavimo da vazi za [inlmath]n-1[/inlmath] ([inlmath]D_{n-1}=2^n-1[/inlmath] ).
I sada racunamo za [inlmath]n[/inlmath].
[dispmath]\begin{align}
\begin{vmatrix}
3 & 2 & 0 & 0 & \cdots & 0 & 0 & 0\\
1 & 3 & 1 & 0 & \cdots & 0 & 0 & 0\\
0 & 2 & 3 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots& \vdots & &\vdots & \vdots & \vdots\\
0 & 0 & 0 & 0 & \cdots & 1 & 3 & 1\\
0 & 0 & 0 & 0 & \cdots & 0 & 2 & 3
\end{vmatrix}_n&=3\cdot D_{n-1}-\begin{vmatrix}
3 & 2 & 0 & 0 & \cdots & 0 & 0 & 0\\
1 & 3 & 1 & 0 & \cdots & 0 & 0 & 0\\
0 & 2 & 3 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots\\
0 & 0 & 0 & 0 & \cdots & 2 & 3 & 2\\
0 & 0 & 0 & 0 & \cdots & 0 & 0 & 2
\end{vmatrix}_{n-1}\\
\\
&=3\cdot D_{n-1}-2\cdot\begin{vmatrix}
3 & 2 & 0 & 0 & \cdots & 0 & 0 & 0\\
1 & 3 & 1 & 0 & \cdots & 0 & 0 & 0\\
0 & 2 & 3 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots\\
0 & 0 & 0 & 0 & \cdots & 1 & 3 & 1\\
0 & 0 & 0 & 0 & \cdots & 0 & 2 & 3
\end{vmatrix}_{n-2}
\end{align}[/dispmath]
I sada na kraju imamo:
[dispmath]D_n=3\cdot D_{n-1}-2\cdot D_{n-2}[/dispmath]
U tu jednacinu zamenimo pretpostavljeno resenje [inlmath]D_n=3\left(2^n-1\right)-2\left(2^{n-1}-1\right)=3\cdot2^n-3-2^n+2=2^{n+1}-1[/inlmath] i tu je kraj.
Naravno posto je jako tesko pretpostaviti sta je resenje i naslutiti ga, uzecemo sada da ne znamo sta je resenje. Ponavljamo ovaj isti postupak sa laplasovom formulom po zadnjoj koloni kao u induktivnom koraku i dobijamo onu rekurentnu jednacinu.
[dispmath]D_n=3\cdot D_{n-1}-2\cdot D_{n-2}[/dispmath]
One se resavaju pomocu karakteristicne jednacine:
[dispmath]t^2=3t-2\\
t^2-3t+2=0\\
t_{1,2}=\frac{3\pm\sqrt{9-4\cdot2}}{2}=\frac{3\pm1}{2}\\
t_1=2\\
t_2=1[/dispmath]
Sva resenja rekurentne jednacine(ukoliko su koreni karakteristicne jednacine razliciti) [inlmath]a_n=a\cdot a_{n-1}+b\cdot a_{n-2}[/inlmath] su opisana sa:
[dispmath]a_n=\alpha\cdot t_1^n+\beta\cdot t_2^n[/dispmath]
Ovde alfa i beta dobijamo iz pocetnih uslova [inlmath]a_0[/inlmath] i [inlmath]a_1[/inlmath].
Pa prema ovome imamo:
[dispmath]D_n=\alpha\cdot 2^n+\beta\cdot1^n=\alpha\cdot2^n+\beta[/dispmath]
Ovde su nam pocetni uslovi determinanta velicine [inlmath]n=1[/inlmath] i [inlmath]n=2[/inlmath] koje lako mozemo izracunati i na kraju resimo sistem da bismo dobili [inlmath]\alpha[/inlmath] i [inlmath]\beta[/inlmath].
[dispmath]D_1=2\cdot\alpha+\beta\\
D_2=4\cdot\alpha+\beta[/dispmath]
a [inlmath]D_1[/inlmath] i [inlmath]D_2[/inlmath] su naravno [inlmath]3[/inlmath] i [inlmath]7[/inlmath].
[dispmath]3=2\cdot\alpha+\beta\\
7=4\cdot\alpha+\beta[/dispmath]
I sada [inlmath]\alpha=2[/inlmath] a [inlmath]\beta=-1[/inlmath].
Konacno resenje je:
[dispmath]D_n=2\cdot2^n-1=2^{n+1}-1[/dispmath]
Trougao  OFFLINE
 
Postovi: 150
Zahvalio se: 57 puta
Pohvaljen: 107 puta

Re: Determinante i rekurentna formula

Postod heisenberg96 » Subota, 20. Avgust 2016, 09:09

Trougao je napisao:Obicno su rekurentne determinante tipa te koju si dao, brojevi na glavnoj i dve sporedne dijagonale.

Mozes li mi reci sta si tacno mislio pod tim? Kako da na osnovu glavne i sporedne dijagonale prepoznam rekurentnu ?
Hvala na rjesenju, dobio sam slicno samo sto je kod mene bilo da je
[dispmath]D_n=3D_{n-2}-2D_{n-2}[/dispmath] jer sam mislio da ne mogu da pisem [inlmath]n-1[/inlmath] jer njeno "ponavljanje" pocinje tek na [inlmath]n-2[/inlmath] , pa ako mozes to da mi razjasnis
hvala puno :)
 
Postovi: 10
Zahvalio se: 10 puta
Pohvaljen: 0 puta

Re: Determinante i rekurentna formula

Postod Trougao » Subota, 20. Avgust 2016, 09:20

Ajde da se izrazim "strucno" ne postoji algoritam koji utvrdjuje da li je proizvoljna determinanta velicine [inlmath]n[/inlmath] rekurentna ili ako postoji nesta sa racunarom da se utvrdi, onda je to za metod olovka i papir previse komplikovano. To je stvar prakse ali kao sto rekoh 99% posto determinanti koje su rekurentne i koje mozes dobiti a da nije neki olimpijski zadatak, imace brojeve postavljene po nekom sablonu na glavnoj dijagonali i dve sporedne koje su odmah do nje.
Kod ovakvih determinanti da bi dobio rekurentnu jednacinu pocinjes obicno sa Laplasovim razvojem po zadnjoj koloni. Kad uzmem da razvijam po [inlmath]3[/inlmath] koja se nalazi u donjem desnom uglu dobijem determinantu istu kao pre samo sto su joj odbacene poslednja kolona i vrsta znaci determinanta je velicine [inlmath]n-1[/inlmath].
Ako ti to nije jasno raspisi poslednjih 5-6 vrsta i idi postupno.
Trougao  OFFLINE
 
Postovi: 150
Zahvalio se: 57 puta
Pohvaljen: 107 puta

Re: Determinante i rekurentna formula

Postod heisenberg96 » Subota, 20. Avgust 2016, 09:27

Hvala ti na ulozenom trudu, sad je mnogo jasnije

:) :D
 
Postovi: 10
Zahvalio se: 10 puta
Pohvaljen: 0 puta

Re: Determinante i rekurentna formula

Postod Daniel » Subota, 20. Avgust 2016, 10:35

Znači, možeš da uočiš pravilnost,
[dispmath]D_1=\begin{vmatrix}
3
\end{vmatrix}[/dispmath][dispmath]D_2=\begin{vmatrix}
3 & 1\\
2 & 3
\end{vmatrix}[/dispmath][dispmath]D_3=\begin{vmatrix}
3 & 2 & 0\\
1 & 3 & 1\\
0 & 2 & 3
\end{vmatrix}[/dispmath][dispmath]D_4=\begin{vmatrix}
3 & 1 & 0 & 0\\
2 & 3 & 2 & 0\\
0 & 1 & 3 & 1\\
0 & 0 & 2 & 3
\end{vmatrix}[/dispmath][dispmath]D_5=\begin{vmatrix}
3 & 2 & 0 & 0 & 0\\
1 & 3 & 1 & 0 & 0\\
0 & 2 & 3 & 2 & 0\\
0 & 0 & 1 & 3 & 1\\
0 & 0 & 0 & 2 & 3
\end{vmatrix}[/dispmath][dispmath]\vdots[/dispmath]
i pri tome vidiš da na dijagonali koja je odmah iznad glavne brojevi naizmenično počinju jedinicom ili dvojkom (kod parnih članova niza počinju jedinicom, a kod neparnih članova niza dvojkom).
Slično i za dijagonalu koja je ispod glavne, samo što je kod nje obrnut slučaj.
I to je ta pravilnost niza [inlmath]D_n[/inlmath], koji zatim predstavljamo preko rekurentne formule.
Istina, budući da se kod determinante koja je u zadatku zadata na prvom mestu dijagonale koja je iznad glavne nalazi dvojka, iz toga bi se možda dalo zaključiti da [inlmath]n[/inlmath] mora biti neparno. Međutim, to nas u postupku i ne ograničava previše, jer se ovim rekurentnim postupkom pokazuje da formula [inlmath]D_n=2^{n+1}-1[/inlmath] važi i za neparne i za parne članove.



Ako se radi preko indukcije, baza indkucije bi trebalo da obuhvati [inlmath]n=1[/inlmath] i [inlmath]n=2[/inlmath], budući da se u indukcijskoj pretpostavci član niza izražava preko dva prethodna člana.


Heisenberg, molim te, ubuduće bez ovakvih slika. Koristi Latex. :)
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Determinante i rekurentna formula

Postod heisenberg96 » Ponedeljak, 22. Avgust 2016, 19:11

Hvala na odgovoru admine, kad se tako problem sagleda, vise nije problem :D






Hocu, moja greska :) :)
 
Postovi: 10
Zahvalio se: 10 puta
Pohvaljen: 0 puta


Povratak na LINEARNA ALGEBRA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 57 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 16:37 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs