☰ matematika1

Rješavanje trokutastih sustava LINEARNA ALGEBRA Primjeri

Gaussova eliminacija

Lako vidimo da se rješenje sustava ne mijenja ako izvršimo bilo koju od sljedećih radnji:

i): neku jednadžbu pomnožimo s brojem različitim od nule,
ii): zamijenimo dvije jednadžbe,
iii): jednu jednadžbu pribrojimo drugoj,
iv): zamijenimo dvije varijable.

Radnje i) i iii) često vršimo istovremeno: jednoj jednadžbi dodamo drugu jednadžbu pomnoženu s nekim brojem.

Ove radnje odgovaraju sljedećim radnjama na proširenoj matrici sustava:

(i'): neki redak pomnožimo s brojem različitim od nule;
(ii'): zamijenimo dva retka;
(iii'): jedan redak pribrojimo drugome;
(iv'): zamijenimo dva stupca u matrici .

Kombinirajući radnje (i') i (iii') imamo: jednom retku dodamo drugi redak pomnožen s nekim brojem.

Koristeći navedene transformacije matricu svodimo na gornje trokutasti oblik. Taj postupak se zove Gaussova eliminacija. Neka je zadan sustav $4 \times 4$

	$\displaystyle a_{11}x_1+a_{12}x_2+a_{13}x_3+a_{14}x_4=b_1$
	$\displaystyle a_{21}x_1+a_{22}x_2+a_{23}x_3+a_{24}x_4=b_2$
	$\displaystyle a_{31}x_1+a_{32}x_2+a_{33}x_3+a_{34}x_4=b_3$	(2.5)
	$\displaystyle a_{41}x_1+a_{42}x_2+a_{43}x_3+a_{44}x_4=b_4$

Neka je $a_{11}\neq 0$ . Tada stavimo

$\displaystyle % m_{i1}=a_{i1}/a_{11}, \quad i=2,3,4$

i oduzmemo prvu jednadžbu pomnoženu s $m_{i1}$ od

-te jednadžbe

te dobijemo sustav

$\displaystyle a_{11}x_1+a_{12}x_2+a_{13}x_3+a_{14}x_4=b_1$
$\displaystyle a'_{22}x_2+a'_{23}x_3+a'_{24}x_4=b'_2$
$\displaystyle a'_{32}x_2+a'_{33}x_3+a'_{34}x_4=b'_3$
$\displaystyle a'_{42}x_2+a'_{43}x_3+a'_{44}x_4=b'_4$

gdje je

$\displaystyle % a'_{ij}=a_{ij}-m_{i1}a_{1j}, \quad b'_i=b_i-m_{i1}b_1.$

Primijetimo da je varijabla

eliminirana iz tri posljednje jednadžbe. Brojevi $m_{i1}$ kojima se u postupku eliminacije množi prva jednadžba zovu se multiplikatori. Neka je i $a'_{22}\neq 0$ . Tada stavimo

$\displaystyle % m_{i2}=a'_{i2}/a'_{22}, \quad i=3,4$

i oduzmemo drugu jednadžbu pomnoženu s $m_{i2}$ od

-te jednadžbe

. Rezultat je sustav

$\displaystyle a_{11}x_1+a_{12}x_2+a_{13}x_3+a_{14}x_4=b_1$
$\displaystyle a'_{22}x_2+a'_{23}x_3+a'_{24}x_4=b'_2$
$\displaystyle a''_{33}x_3+a''_{34}x_4=b''_3$
$\displaystyle a''_{43}x_3+a''_{44}x_4=b''_4$

gdje je

$\displaystyle % a''_{ij}=a'_{ij}-m_{i2}a'_{2j}, \quad b''_i=b'_i-m_{i2}b'_2.$

Konačno, stavimo

$\displaystyle % m_{i3}=a''_{i3}/a''_{33}, \quad i=4$

i oduzmemo treću jednadžbu pomnoženu s $m_{i3}$ od četvrte jednadžbe. Rezultat je gornje trokutasti sustav

$\displaystyle a_{11}x_1+a_{12}x_2+a_{13}x_3+a_{14}x_4=b_1$
$\displaystyle a'_{22}x_2+a'_{23}x_3+a'_{24}x_4=b'_2$
$\displaystyle a''_{33}x_3+a''_{34}x_4=b''_3$
$\displaystyle a'''_{44}x_4=b'''_4$

gdje je

$\displaystyle % a'''_{ij}=a''_{ij}-m_{i3}a''_{2j}, \quad b'''_i=b''_i-m_{i3}b''_2.$

Dobiveni gornje trokutasti sustav sada riješimo na način koji je opisan u poglavlju 2.3.

Broj računskih operacija potrebnih za svođenje kvadratnog sustava reda na gornje trokutasti oblik iznosi

$\displaystyle % \sum_{i=1}^n 2i (i-1) = 2\frac{n(n+1)(2n+1)}{6}-2\frac{n(n+1)}{2} \approx \frac{2}{3}n^3.$

Vidimo da je za veće dimenzije

broj računskih operacija potreban za rješavanje trokutastog sustava zanemariv u odnosu na broj računskih operacija potrebnih za svođenje na trokutasti oblik. Na modernim računalima (Pentium 350), koja izvršavaju do

milijuna operacija u sekundi, svođenje sustava dimenzije

na trokutasti oblik traje oko

sekundi, dok za

traje

sati, a za

traje

puta duže, odnosno oko

godina.

Postupak Gaussove eliminacije koji smo upravo opisali za sustav reda četiri na očit se način može poopćiti na sustave proizvoljnog reda. Ukoliko je neki od brojeva s kojima dijelimo jednak nuli, potrebno je dodatno koristiti postupak pivotiranja koji je opisan u poglavlju 2.4.2.

Postupak Gaussove eliminacije možemo interpretirati i kao množenje proširene matrice sustava s lijeve strane s elementarnim matricama transformacije. Neka je $\begin{bmatrix}A&\vline& \mathbf{b}\end{bmatrix}$ proširena matrica sustava (2.5) i neka je

$\displaystyle % M_1=\begin{bmatrix} 1 & 0 &0&0\\ -m_{21}&1&0&0\\ -m_{31}&0&1&0\\ -m_{41}&0&0&1 \end{bmatrix}.$

Tada je

$\begin{displaymath}\begin{split}\begin{bmatrix}A_1&\vline&\mathbf{b}_1\end{bmatr... ...&a'_{42}&a'_{43}&a'_{44}&\vline&b'_4 \end{bmatrix}. \end{split}\end{displaymath}$

Dalje, neka je

$\displaystyle % M_2=\begin{bmatrix} 1 & 0 &0&0\\ 0&1&0&0\\ 0&-m_{32}&1&0\\ 0&-m_{42}&0&1 \end{bmatrix}.$

Tada je

$\begin{displaymath}\begin{split}\begin{bmatrix}A_2&\vline&\mathbf{b}_2\end{bmatr... ...\ 0&0&a''_{43}&a''_{44}&\vline&b''_4 \end{bmatrix}. \end{split}\end{displaymath}$

Konačno, neka je

$\displaystyle % M_3=\begin{bmatrix} 1 & 0 &0&0\\ 0&1&0&0\\ 0& 0&1&0\\ 0&0&-m_{43}&1 \end{bmatrix}.$

Tada je

$\begin{displaymath}\begin{split}\begin{bmatrix}A_3&\vline&\mathbf{b}_3\end{bmatr... ...''_3\\ 0&0&0&a'''_{44}&\vline&b'''_4 \end{bmatrix}. \end{split}\end{displaymath}$

Zadatak 2.4 Napišite program za svođenje proširene matrice sustava na trokutasti oblik.

Poglavlja

Rješavanje trokutastih sustava LINEARNA ALGEBRA Primjeri