1
NUMERIČKO RJEŠAVANJE SISTEMA ALGEBARSKIH
LINEARNIH JEDNADŽBI
Seminarski rad iz Linearne algebre
4
1. NUMERIČKO RJEŠAVANJE SISTEMA ALGEBARSKIH LINEARNIH
JEDNADŽBI
Problem rješavanja sistema jednadžbi je jedan od najčešćih problema sa kojima se susreću
inženjeri i naučnici. Pri tome jednadžbe mogu biti algebarske, transcedentalne, obične ili
parcijalne diferencijalne jednadžbe. Također, one mogu biti i linearne ili nelinearne. Ipak,
ovdje će se obraditi samo (numeričko) rješavanje sistema linearnih jednadžbi. Sistem od
n
linearnih jednačina sa
n
nepoznatih se može napisati u obliku:
a
11
x
1
+
a
12
x
2
+
…
+
a
1
n
x
n
=
b
1
a
21
x
1
+
a
22
x
2
+
…
+
a
2
n
x
n
=
b
2
..................
(1)
a
n
1
x
1
+
a
n
2
x
2
+
…
+
a
nn
x
n
=
b
n
gdje
x
i
(
i
=
1
,
2
, . . . , n
)
predstavljaju nepoznate promjenljive,
a
i j
(
i , j
=
1
,
2
, . . . , n
)
konstantne koeficijente, a
b
i
(
i
=
1
,
2
, . . . , n
)
nehomogene članove. Sistem jednačina (1) se
može napisati i u matričnoj formi:
Ax
=
b
(
2
)
gdje je
A
matrica koeficijenata (matrica sistema), a
x
i
b
su vektori kolone, odnosno:
A
=
[
a
11
a
12
a
21
a
22
⋯
b
1
b
2
⋮
⋱
⋮
a
n
1
a
n
2
⋯
b
n
]
, x
=
[
x
1
x
2
⋮
x
n
]
, b
=
[
b
1
b
2
⋮
b
n
]
Broj jednadžbi može biti i drugačiji od n, ali je u većini inženjerskih problema jednak
broju nepoznanica.
Riješiti sistem (1), odnosno (2) znači naći vrijednosti
x
i
(
i
=
1
,
2
, . . . , n
)
koje istovremeno
zadovoljavaju sve jednačine sistema. Pri tome, mogu se desiti 4 slučaja:
• Jedinstveno rješenje - sistem je određen.
5
• Nema rješenja - sistem je protivrječan.
• Beskonačan broj rješenja - sistem ima nedovoljan broj jednadžbi, tj. neodređen je.
• Trivijalno rješenje - sistem je homogen i
x
i
=
0
(
i
=
1
,
2
, . . . , n
)
U rješavanju sistema linearnih algebarskih jednadžbi postoje dva fundamentalno različita
pristupa:
• Direktne metode
• Iterativne metode
Direktne metode predstavljaju sistematske procedure koje se zasnivaju na principu
eliminacije. Za razliku od njih, iterativne metode asimptotski dovode do rješenja pomoću
neke iterativne procedure u kojoj se pretpostavi neko rješenje, ono se uvrsti u sistem
jednadžbi kako bi se dobilo odstupanje, ili greška, a zatim se na osnovu tog odstupanja,
odnosno greške, dobije poboljšano rješenje.
1.1. Direktne metode
1.1.2. Cramerovo pravilo
Posmatrajmo sistem linearnih algebarskih jednadžbi,
Ax
=
b
, sa
n
jednačina. Cramerovo
1
pravilo kaže da je rješenje takvog sistema dato sa
x
j
=
det
(
A j
)
det
(
A
)
(
j
=
1
,
2
, . . . , n
)(
4
)
gdje je (
A j
) matrica
n × n
koja se dobija zamjenom kolone
j
matrice
A
sa kolonom
vektora
b
. U ovom slučaju determinante se vrlo lako izračunaju pomoću pravila dijagonala.
Međutim, za sisteme sa više jednadžbi to pravilo ne važi i neophodno je koristiti metodu
kofaktora. Broj množenja i dijeljenja pri korištenju metode kofaktora jednak je
(
n
−
1
)(
n
+
1
)
! ,
pri čemu je
n
dimenzija kvadratne matrice. Lako je izračunati da je za slučaj 10 jednačina,
koji predstavlja mali sistem jednačina, broj operacija jednak 360,000,000, a za samo 100
jednadžbi ovaj broj je reda 10157. Očigledno je da Cramerovo pravilo nije efikasno u
rješavanju velikih sistema jednadžbi, tako da je neophodno koristiti neke druge metode.
1
Gabrijel Kramer (
fr.
Gabriel Cramer
;
Ženeva
,
31. jul
1704
—
Banjol sir Sez
,
4. januar
1752
) je bio
švajcarski
matematičar
. Rođen je
u
Ženevi
. Pokazao je interesovanje za
matematiku
veoma rano. Sa 18 godina je doktorirao, a sa 20 je bio zamjenik šefa katedre za
matematiku.
7
Rješenje:
Postupak rješavanja počinje rješavanjem prve jednadžbe za nepoznanicu
x
1
. Na taj način
imamo:
x
1
= [20 − (−20)
x
2
− (−20)
x
3
]/80
Uvrštavajući ovu jednadžbu u jednadžbu drugu i treću dobiva se, respektivno:
− 20[20 − (−20)
x
2
− (−20)
x
3
]/80 + 40
x
2
− 20
x
3
= 20
− 20[20 − (−20)
x
2
− (−20)
x
3
]/80 − 20
x
2
+ 130
x
3
= 20
koje se mogu pojednostaviti na oblik:
35
x
2
− 25
x
3
= 25 (1)
−25
x
2
+ 125
x
3
= 25 (2)
Ako sada riješimo jednadžbu (1) za
x
2
, dobijamo:
x
2
= [25 − (−25)
x
3
]/35
Uvrštavajući posljednju jednadžbu u jednadžbu (2) nakon pojednostavljenja dobiva se:
750
7
x
3
=
300
7
Na taj način, zadati sistem jednadžbi se svodi na sistem jednadžbi:
80
x
1
−
20
x
2
−
20
x
3
=
20
35
x
2
− 25
x
3
= 25
750
7
x
3
=
300
7
čime je završen proces eliminacije. Sada se vrlo lako može dobiti rješenje sistema zamjenom
unazad, tj.:
