Kramerove mape

Maturski, seminarski i diplomski radovi iz informatike.

Jedan od najznačajnijih problema u simboličkoj analizi(SA) je eksponencijalni porast broja sabiraka u razvijenom obliku simboličkog izraza sa porastom broja čvorova i elemenata analiziranog kola. Kao posledica ove činjenice sužena je primena simboličke analize na kola relativno male složenosti.
Značajan trud se ulaže u razvoj algoritama koji treba da omoguće analizu složenijih kola. Matrični metodi su se osamdesetih godina prošlog veka pokazali kao superiorni u odnosu na druge metode jer su omogućili simboličku analizu elektronskih kola veće složenosti nego do tada [1].
Metod eliminacije promenjivih, koji je veoma efikasan u numeričkoj analizi, nije našao širu primenu u SA, pre svega zbog glomaznih izraza sa velikim brojem potiranja u međurezultatima [2],[3]. Iz tog razloga matrični metodi SA za rešavanje sistema linearnih jednačina najčešće primenjuju Kramerove mape (pravila), pri čemu se problem svodi na određivanje determinanata matrice sistema jednačina koji opisuje kolo u simboličkom obliku. Efikasanost metoda simboličke analize procenjuje se prema zauzeću memorije kao i prema ukupnom vremenu analize elektronskog kola. Algoritam za određivanje determinante koji je ovde naveden upravo ima namenu da poboljša efikasnost SA.

2 KRAMEROVE MAPE (PRAVILA)

Kramerove mape (pravila) su teoreme u linearnoj algebri, koje daju rešenja sistema linearnih jednačina pomoću determinanti. Dobila je ime po Gabrijelu Krameru (1704. - 1752.).
Računski, radi se o neefikasnom postupku, i stoga se ne koristi u praksi u slučajevima kada je broj jednačina u sistemu veliki. Međutim, ovo pravilo je od teorijskog značaja jer daje eksplicitni izraz za rešenje sistema.

2.1 Elementarna formulacija

Sistem jednačina predstavljen u formi množenja matrica kao:
gde je kvadratna matrica A invertibilna a vektor x je vektor kolone promenljivih: (xi).
Teorema onda tvrdi da:
gde je Ai matrica koja se dobija zamenom i-te kolone iz A vektorom kolone c. Radi jednostavnosti, ponekad se koristi samo jedan simbol kao što je Δ da predstavi det(A) a notacija Δi se koristi da predstavi det(Ai). Stoga se jednačina (1) može kompaktnije zapisati kao

2.2 Apstraktna formulacija

Neka je R komutativni prsten, a A n×n matrica sa koeficijentima iz R. Onda
gde Adj(A) označava adjungovanu matricu matrice A, det(A) je determinanta, a I je jedinična matrica.
PRIMER:
Dobar način da se Kramerovo pravilo iskoristi za matrice dimenzije 2×2 je pomoću sledeće formule:

1 UVOD 3
2 KRAMEROVE MAPE (PRAVILA) 4
2.1 Elementarna formulacija 4
2.2 Apstraktna formulacija 4
3 PRIMENE U DIFERENCIJALNOJ GEOMETRIJI 6
4 PRIMENE U ALGEBRI 8
5 ZAKLJUČAK 9
6 LITERATURA 10