×   HOME PREDAVANJA

SADRŽAJ OSNOVE LINEARNA ALGEBRA VEKTORI I GEOMETRIJA FUNKCIJE DERIVACIJE NIZOVI I REDOVI INDEKS

VJEŽBE

SADRŽAJ OSNOVE LINEARNA ALGEBRA VEKTORI I GEOMETRIJA FUNKCIJE DERIVACIJE NIZOVI I REDOVI

KVIZ

SADRŽAJ OSNOVE LINEARNA ALGEBRA VEKTORI I GEOMETRIJA FUNKCIJE DERIVACIJE NIZOVI I REDOVI

PODSJETNIK

SADRŽAJ OSNOVE LINEARNA ALGEBRA VEKTORI I GEOMETRIJA FUNKCIJE DERIVACIJE NIZOVI I REDOVI

JAVA NETPLOT OCTAVE Traži ...

☰   matematika1 Matrični zapis sustava linearnih     LINEARNA ALGEBRA     Gaussova eliminacija

Rješavanje trokutastih sustava

Matrica $U$ je gornje trokutasta ako

$$% i>j \Longrightarrow u_{ij}=0.$$

Drugim riječima, svi elementi koji leže ispod dijagonale su nula. Primjer gornje trokutaste matrice reda pet je

$$% U= \begin{bmatrix} u_{11}&u_{12}&u_{13}&u_{14}&u_{15}\\ 0 & ... ...&u_{33}& u_{34}&u_{35}\\ 0&0&0&u_{44}&u_{45}\\ 0&0&0&0&u_{55} \end{bmatrix}$$

Slično, matrica $L$ je donje trokutasta ako

$$% i<j \Longrightarrow l_{ij}=0,$$

odnosno elementi iznad dijagonale su nula.

Teorem 2.3   Ako su svi dijagonalni elementi kvadratne gornje trokutaste matrice $U$ različiti od nule, tada sustav $U\mathbf{x}=\mathbf{b}$ ima jedinstveno rješenje.

Dokaz.

Ilustrirajmo prvo rješavanje sustava za $n=5$ . Prvo napišimo sustav u skalarnom obliku

$$u_{11}x_1+u_{12}x_2+u_{13}x_3+u_{14}x_4+u_{15}x_5= b_1$$

$$u_{22}x_2+u_{23}x_3+u_{24}x_4+u_{25}x_5= b_2$$

$$u_{33}x_3+u_{34}x_4+u_{35}x_5=b_3$$

$$u_{44}x_4+u_{45}x_5= b_4$$

$$u_{55}x_5= b_5$$

Peta jednadžba sadrži samo nepoznanicu $x_5$ i možemo je riješiti odmah:

$$% x_5={\frac{b_5}{u_{55}}}.$$

Dobivenu vrijednost od $x_5$ možemo uvrstiti u četvrtu jednadžbu koju potom riješimo i dobijemo

$$% x_4={\frac{b_4-u_{45}x_5}{u_{44}}}.$$

Uvrštavanjem $x_4$ i $x_5$ u treću jednadžbu te rješavanjem te jednadžbe dobijemo

$$% x_3={\frac{b_3-u_{34}x_4-u_{35}x_5}{u_{33}}}.$$

Nastavljajući ovim postupkom dobijemo

$$% x_2={\frac{b_2-u_{23}x_3-u_{24}x_4-u_{25}x_5}{u_{22}}}$$

i

$$% x_1={\frac{b_1-u_{12}x_2-u_{13}x_3-u_{14}x_4-u_{15}x_5}{u_{11}}}.$$

Kako su po pretpostavci dijagonalni elementi $u_{ii}$ različiti od nule, ove formule jednoznačno određuju $x_i$ . Ovaj postupak se očito može izvesti za proizvoljnu dimenziju $n$ pa je teorem dokazan.     

Q.E.D.

Ovaj postupak se jednostavno može izvršiti na računalu. Odgovarajući program u programskom jeziku C glasi

 
    for (i=n;i>=1;i--){ 
       for (j=n;j>i;j--)
          b[i]=b[i]-u[i][j]*b[j];
       b[i]=b[i]/u[i][i];
    }

Nakon završetka programa, rješenje $\mathbf{x}$ se nalazi na mjestu gdje se na početku nalazio vektor $\mathbf{b}$ .

Program za rješavanje gornje trokutastog sustava u programskom jeziku Matlab izgleda nešto jednostavnije:

    for i=n:-1:1
       for j=n:-1:i+1
          b(i)=b(i)-u(i,j)*b(j)
       end
       b(i)=b(i)/u(i,i)
    end

Isti program u programskom jeziku FORTRAN, ovaj put napisan korištenjem uzlazne petlje, izgleda ovako:

    do k=1,n
       i=n-k+1
       do j=i+1,n
          b(i)=b(i)-u(i,j)*b(j)
       enddo
       b(i)=b(i)/u(i,i)
    enddo

Broj računskih operacija potrebnih za rješavanje gornje trokutastog sustava iznosi

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

Na modernim računalima (Pentium 350), koja izvršavaju do $30$ milijuna operacija u sekundi, rješavanje trokutastog sustava dimenzije $n=1000$ traje oko $1/30$ sekunde.

Postupak za rješavanje donje trokutastog sustava $L\mathbf{x}=\mathbf{b}$ je sličan i dan je u sljedećem Matlab programu:

    for i=1:n
       for j=i+1:n
          b(i)=b(i)-l(i,j)*b(j)
       end
       b(i)=b(i)/l(i,i)
    end

Kako se trokutasti sustavi lako rješavaju, rješenje općeg (netrokutastog) sustava dobijemo tako da pomoću Gaussove eliminacije zadani sustav svedemo na trokutasti oblik.

Zadatak 2.3   Zadajte nekoliko gornje i donje trokutastih sustava i riješite ih pomoću opisanih Matlab programa. Pri tome možete koristiti program Octave On-line.

Matrični zapis sustava linearnih     LINEARNA ALGEBRA     Gaussova eliminacija