Algoritmi i Gaussit

Jeni duke lexuar pjesë nga libri në punim e sipër: Matricat dhe përcaktorët Matricat Kuptimi dhe barazia e matricave Simboli Matrica drejtkëndore Matrica komplekse Matricat e tipit të njëjtë Matrica katrore Matrica njështyllore Matrica njërreshtore Zero matrica Barazia e matricave Veprimet lineare me matrica Llojet e posaçme të matricave katrore Shumëzimi i matricave Fuqia e matricave katrore Transponimi i matricës Matricat regulare, singulare dhe inverse Forma matriciale e sistemit të ekuacioneve lineare Matricat katrore të posaçme Matrica e Hermitit Rangu i matricës Përcaktimi praktik i rangut të matricës Matricat ekuivalente Transformimet elementare të matricës Forma kanonike e matricës Matrica e zgjeruar Përcaktorët Kuptimi i tyre Vetit e përcaktorëve Njehësimi i vlerës së përcaktrorëve Matrica e adjunguar dhe përcaktori i adjunguar Sistemet e ekuacioneve Sistemi i tri ekuacioneve lineare me tri të panjohura Formula e Cramerit Zgjidhëshmëria e sistemit të ekuacioneve lineare Sistemi i n ekuacioneve lineare me n të panjohura Algoritmi i Gaussit Format lineare Forma matriciale e sistemit të ekuacioneve lineare Format lineare Rangu i matricës Pavarshmëria e formave lineare Pavarshmëria e rreshtave dhe e shtyllave të matricës Matricat ekuivalente Transformimet elementare të matricës Përcaktimi praktik i rangut të matricës Forma kanonike e matricës Teorema e Kronecker-Capellit Matrica e zgjeruar

Një metodë praktike për zgjidhjen e sistemit të $n$ ekuacioneve Iineare me $n$ të panjohura është ajo e Gaussit që quhet algoritmi i Gaussit. Të shohim tani këtë algoritëm.

Le të marrim sistemin:

${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}&=&b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}&=&b_{2}\\&\vdots &\\a_{n1}x_{1}+a_{n2}x_{2}+\dots +a_{nn}x_{n}&=&b_{n}\\\end{matrix}}$

dhe le të supozojmë se $a_{11}\neq 0$. Ekuacionin e parë të këtij sistemi e shumëzojmë me radhë me numrat:

${\frac {a_{21}}{a_{11}}},\;{\frac {a_{31}}{a_{11}}},\;{\frac {a_{41}}{a_{11}}},\;\dots ,\;{\frac {a_{n1}}{a_{11}}}$

dhe barazimet e përftuara i zbresim me radhë prej ekuacionit të dytë, ekuacionit të tretë, . . . , ekuacionit të fundit. Kështu merret sistemi:

${\begin{matrix}a_{11}x_{1}&+&a_{12}x_{2}&+&a_{13}x_{3}&+&\cdots \;+&a_{1n}x_{n}&=&b_{1}\\&&a_{22}^{1}x_{2}&+&a_{23}^{1}x_{3}&+&\cdots \;+&a_{2n}^{1}x_{n}&=&b_{2}^{1}\\&&a_{32}^{1}x_{2}&+&a_{33}^{1}x_{3}&+&\cdots \;+&a_{3n}^{1}x_{n}&=&b_{3}^{1}\\&&&&&&&&\vdots &\\&&a_{n1}^{1}x_{2}&+&a_{n3}^{1}x_{3}&+&\cdots \;+&a_{nn}^{1}x_{n}&=&b_{n}^{1}\\\end{matrix}}$

Në këtë sistem e panjohura $x_{1}$ është eliminuar nga të gjitha ekuacionet, përveç ekuacionit të parë. Përsërisim këtë veprim në sistemin (a) ku ekuacionin e dytë të tij e shumëzojmë me radhë me numrat:

${\frac {a_{32}^{1}}{a_{22}^{1}}},\;{\frac {a_{42}^{1}}{a_{22}^{1}}},\;{\frac {a_{52}^{1}}{a_{22}^{1}}},\;\dots ,\;{\frac {a_{n2}^{1}}{a_{22}^{1}}},\;ku\ a_{22}^{1}\neq 0$

dhe pastaj barazimet e përftuara i zbresim me radhë prej ekuacionit të tretë, ekuacionit të katërt, . . . , ekuacionit të fundit. Me këtë rast sistemi do ta merrë këtë trajtë:

${\begin{matrix}a_{11}x_{1}&+&a_{12}x_{2}&+&a_{13}x_{3}&+&\cdots \;+&a_{1n}x_{n}&=&b_{1}\\&&a_{22}^{1}x_{2}&+&a_{23}^{1}x_{3}&+&\cdots \;+&a_{2n}^{l}x_{n}&=&b_{2}^{l}\\&&&&a_{33}^{2}x_{3}&+&\cdots \;+&a_{3n}^{2}x_{n}&=&b_{3}^{2}\\&&&&&&&&\vdots &\\&&&&a_{n2}^{2}x_{3}&+&\cdots \;+&a_{nn}^{2}x_{n}&=b_{n}^{2}\\\end{matrix}}$

Me përsëritjen e këtij algoritmi $n-1$ herë do të përftohet sistemi:

${\begin{matrix}a_{11}x_{1}&+&a_{12}x_{2}&+&a_{13}x_{3}&+&\cdots \;+&+a_{1n}x_{n}&=&b_{1}\\&&a_{22}^{1}x_{2}&+&a_{23}^{1}x_{3}&+&\cdots \;+&+a_{2n}^{1}x_{n}&=&b_{l}^{1}\\&&&&a_{33}^{3}x_{3}&+&\cdots \;+&+a_{3n}^{3}x_{n}&=&b_{3}^{2}\\&&&&&&&\vdots &\vdots &\\&&&&&&&a_{nn}^{n-1}x_{n}&=&b_{n}^{n-1}\\\end{matrix}}$(...34a)

i cili quhet sistemi trekëndor dhe është ekuivalent me sistemin (34). Zgjidhja e sistemit të fundit mund të reduktohet në zgjidhjen e ekuacionit linear me një të panjohur. Vërtet, kur vlerën e panjohurës $x_{n}$, të njehsuar nga ekuacioni i fundit, e zëvendësojmë në atë të parafundit, marrim ekuacionin linear me të panjohurën $x_{n-1}$. Kur vlerat e njehsuara të $x_{n}$ dhe $x_{n-1}$ i zëvendësojmë në ekuacionin e tretë nga fundi, përsëri marrim ekuacionin linear me një të panjohur - me të panjohurën $x_{n-2}$. Ky proces vazhdohet derisa edhe ekuacioni i parë i sistemit (34a) nuk reduktohet në një ekuacion me një të panjohur, nga njehsohet vlera e të panjohurës $x_{1}$. Pra, kjo metodë e zgjidhjes së sistemit të ekuacioneve lineare quhet algoritmi i Gaussit.

Shembuj

Me algoritmin e Gaussit të zgjidhet sistemi:

${\begin{matrix}\ x_{1}&+&2x_{2}&-&3x_{3}&+&4x_{4}&-&\ x_{5}&=\!-1\\2x_{1}&-&\ x_{2}&+&3x_{3}&-&4x_{4}&+&2x_{5}&=\ 8\ \\3x_{1}&+&\ x_{2}&-&\ x_{3}&+&2x_{4}&-&\ x_{5}&=\ 3\ \\4x_{1}&+&3x_{2}&+&4x_{3}&+&2x_{4}&+&2x_{5}&=\!-2\\\ x_{1}&-&\ x_{2}&-&\ x_{3}&+&2x_{4}&-&3x_{5}&=\!-3\\\end{matrix}}$

Z g j i d h j e: Duke aplikuar algoritmin e Gaussit marrim këto sisteme ekuivalente:

${\begin{matrix}\ x_{1}&+&2x_{2}&-&\ 3x_{3}&+&\ 4x_{4}&-&\ x_{5}&=-1\\&-&5x_{2}&+&\ 9x_{3}&-&12x_{4}&+&4x_{5}&=\;10\\&-&5x_{2}&+&\ 8x_{3}&-&10x_{4}&+&2x_{5}&=\ \;6\\&-&5x_{2}&+&16x_{3}&-&14x_{4}&+&6x_{5}&=\ \;2\\&-&3x_{2}&+&\ 2x_{3}&-&\ 2x_{4}&-&2x_{5}&=-2\\\ x_{1}&+&2x_{2}&-&\ 3x_{3}&+&\ 4x_{4}&-&\ \ x_{5}&=\ -1\\&-&5x_{2}&+&\ 9x_{3}&-&12x_{4}&+&\ 4x_{5}&=\ \;10\\&&&-&\ \ x_{3}&+&\ 2x_{4}&-&\ 2x_{5}&=\ -4\\&&&&\ 7x_{3}&-&\ 2x_{4}&+&\ 2x_{5}&=\ -8\\&&&-&17x_{3}&+&26x_{4}&-&22x_{5}&=\!-40\\\ x_{1}&+&2x_{2}&-&\ 3x_{3}&+&\ 4x_{4}&-&\ \ x_{5}&=\ -1\\&-&5x_{2}&+&\ 9x_{3}&-&12x_{4}&+&\ 4x_{5}&=\ \;10\\&&&-&\ \ x_{3}&+&\ 2x_{4}&-&\ 2x_{5}&=\ -4\\&&&&&&12x_{4}&-&12x_{5}&=\!-36\\&&&&&-&\ 8x_{4}&+&12x_{5}&=\ \;28\\\ x_{1}&+&2x_{2}&-&\ 3x_{3}&+&\ 4x_{4}&-&\ \ x_{5}&=\ -1\\&-&5x_{2}&+&\ 9x_{3}&-&12x_{4}&+&\ 4x_{5}&=\ \;10\\&&&-&\ \ x_{3}&+&\ 2x_{4}&-&\ 2x_{5}&=\ -4\\&&&&&&12x_{4}&-&12x_{5}&=\!-36\\&&&&&&&&\ 4x_{5}&=\quad 4\\\end{matrix}}$