NANSI teorija !!!
I KOLOKVIJUM
I. Uvod
1. Navedite izvore grešaka pri izračunavanju vrijednosti funkcije:
Greška metode (odsijecanja) i greška računanja (zaokruživanja).
2. Greška metode (odsijecanja) je:
razlika između tačne vrednosti i rezultata dobijenog primenom datog algoritma korišćenjem tačne aritmetike.
3. Greška zaokruživanja – računanja
razlika između rezultata dobijenog primenom datog algoritma korišćenjem tačne aritmetike i rezultata dobijenih istim
algoritmom i korišćenjem netačne aritmetike.
4. Tačnost se odnosi na:
Bliskost dobijenog rešenja i stvarnog rešenja problema.Sama stabilnost ne garantuje tacnost.Tacnost zavisi od
uslovljenosti problema i stabilnosti algoritma.
5. Tačni odgovori:
• Problem je osjetljiv ili slabo uslovljen ako relativna promjena rješenja može da bude mnogo veća od promjene u
ulaznim podacima.
• Problem je osetljiv ili loše uslovljen ukoliko su relativne promene u izlazima mnogo veće od relativnih promena u
ulazima.
• Problem je slabo uslovljen ako je njegov kondicioni broj mnogo veći od 1.
• Uslovljenost problema ne zavisi od algoritma koji se koristi za njegovo rješavanje.
6. Pod približnim brojem x* podrazumijeva se:
broj koji se od tačnog broja x neznatno (apsolutna i relativna greška) razlikuje i zamjenjuje ga u računanjima
7. Pravilo po kome se svakom realnom broju dodjeljuje mašinski broj zove se :
redukciono preslikavanje. Najčešće korišćena pravila su odsijecanje i zaokruživanje na najbliži.Odsecanje je postupak
kojim se odsecaju cifre od neke cifre na desno,bez korekcije vrednosti preostalog broja.Zaokruzivanje je postupak kojim
se broj x aproksimira najblizim masinskim brojem tako ste se uzima masinski broj cija je poslednja memorisana cifra
veca za 1 ukoliko je cifra iza nje veza ili jednaka 5.
8. Ukupna greška
Ukupna greška = f^^(x^) - f(x) = (f^^(x^) - f(x^)) + (f(x^) - f(x)), Ukupna greška = greška metode + greška
argumenta
9. Greska racunanja:
Računska greška = greška odsecanja + greška zaokruživanja
10. Problem je dobro definisan ako:
Rješenje postoji, jedinstveno je, kontinualno zavisi od podataka.Resenje i dalje moze da bude osetljivo na ulazne
podatke,algoritam ne sme da uvecava ovu osetljivost.
11. Problem je neosjetljiv ili dobro uslovljen ako:
relativne promjene u ulazima proizvode slične relativne promjene u izlazima.
12. Problem je osetljiv ili lose uslovljen:
Ukoliko su relativne promene u izlazima mnogo vece od relativnih promena u ulazima.Problem je osetljiv ako je
kondicioni broj mnogo veci od 1.
13. Kondicioni broj povezuje:
Relativnu grešku unapred sa relativnom greškom unazad: |relativna greška unapred|= cond x |relativna greška unazad|.
Cond- faktor pojacanja greske rezultata.
14. Algoritam je stabilan ako:
Su rezultati relativno neosetljivi na perturbacije u toku računanja (ako je proizvedeni rezultat rešenje bliskog problema).
15. Sistem pokretnog zareza je normalizovan ako:
je vodeća cifra do 0 različita od 0 za svaki broj različit od 0.Osobine: konacan i diskretan,ne mogu se predstaviti svi
realni brojevi.
II. Numeričke metode linearne algebre
1. Napišite zadatak određivanja rješenja sistema linearnih algebarskih jednačina u matričnom obliku.
Za zadatu matricu A dimenzije mxn i zadati vektor b dimenzije m odrediti vektor x dimenzije n koji zadovoljava
jednačinu: Ax=b. Ako se vektor b može izraziti kao linearna kombinacija kolona matrice A onda koeficijenti linearne
kombinacije predstavljaju komponente rješenja sistema.
2. Navedite definiciju kondicionog broja matrice.
cond(A) = ||A|| ∙ ||A-1|| ako je A nesingularna matrica, cond(A) = ∞ ako je A singularna. Kondicioni broj matrice je
mjera odnosa “rastezanja-skupljanja” i “uvrtanja” koje matrica proizvodi nad ne-nula vektorom.
3. Osobine kondicionog broja matrice:
Za bilo koju matricu A: cond(A)>=1;
Za jediničnu matricu I: cond(I)=1 cond(ϒA)=cond(A).
4. Tačni odgovori:
• Greška direktnih postupaka za rješavanje SLAJ zavisi od odabira pivota i eliminacionih matrica.
• Ako je matrica A nesingularna, sistem ima jedinstveno rešenje.
• Ako je matrica A singularna, broj rješenja sistema Ax=b zavisi od izbora vektora b.
• Kondicioni broj matrice nije povezan sa egzistencijom rješenja SLAJ.
• Kondicioni broj matrice uvijek utiče na grešku rješenja SLAJ.
5. Gausova metoda elimincije za rešavanje SLAJ
Svođenje opšteg linearnog sistema Ax=b na gornju trougaonu formu.
Koraci:
1. Elemenat a11 uzima se kao pivot da bi se anulirali elementi prve kolone ispod prve vrste. Sistem dobija oblik
M1Ax=M1
2. Bira se Mb, rešenje se ne menja.
2 sa a22 kao pivotom čime se anuliraju elementi druge kolone ispod druge vrste i dolazi se do sistema M2M1Ax = M2M1
3. Proces se nastavlja sa odgovarajućim pivotom sa ciljem anuliranja odgovarajućih elementa odgovarajuće kolone
matrice dok svi subdijagonalni elementi ne budu anulirani. Na taj način dolazi se do gornjeg trougaonog sistema MAx =
Mb.
n-1...M1Ax = Mn-1...M1b = Mb koji se može rešiti povratnom zamenom (unazad) i koji je ekvivalentan polaznom
sistemu.
6. Objasnite LU faktorizaciju.
Proizvod LkLj je gornja trougaona matrica ako je k<j, te je L = M-1 = M1-1...Mn-1-1 = L1...Ln-1 jedinična donja
trougaona matrica. Po načinu konstrukcije U=MA je gornja trougaona matrica. Ax=b
→
LUx=b, prvo se Ly=b riješi
zamjenom unaprijed, a onda Ux=y zamjenom u nazad. y=Mb je transformisana desna strana u Gausovoj eliminaciji.
7. Objasnite kompletan pivoting:
Kompletan pivoting je proces kojim se najveci element u preostalom(netransformisanom) delu matrice postavlja na
mesto pivota. Zahteva zamenu kolona i vrsta i rezultuje do faktorizacijom matrice PAQ = LU gde je L jedinicna donja
trougaona matrica,U gornja trougaona matrica,a matrice P i Q su permutacione matrice.Kompletan pivoting je teorijski
vise nego superioran u odnosu na parcijalni pivoting,ali ima odredjenu cenu.Numericka stabilnost parcijalnog pivotinga
je adekvatna za vecinu prakticnih primena i on se gotovo uvek koristi kod primene Gausove eliminacije.
8. Objasnite parcijalni pivoting.
Svaki nenula element moze da bude pivot u praksi treba ga birati tako da se minimizira greska.Trebalo bi posao raditi
tako da se izbegne povecanje prethodnih gresaka redukcionog dela matrice elementarnom eliminacionom matricom.
Množitelje formirati tako da ne prelaze vrijednost 1 po veličini, što se može postići biranjem maksimalnog elemenata na
dijagonali ili ispod nje za pivota. Ovaj postupak se naziva parcijalni pivoting i značajan je za stabilnu implementaciju
Gausove eliminacije za opšte linearne sisteme.
9. Gaus-Jordan-ova eliminacija.
Matrica se transformiše na dijagonalnu a ne trougaonu formu; Kombinacije vrsta se formiraju i koriste tako da se
anuliraju elementi iznad i ispod dijagonale; Eliminaciona matrica koja se koristi za dati vektor kolonu a je oblika
=
−−−−+−+−00001...00...00...10...00...010...00...01...00...010...111111knkkkkkkaaaaaammmm
Osobine Gaus – Jordanove eliminacije:
U fazi elimininacije iste operacije nad vrstama primenjuju se na vektor desne strane sistema.Kada se matrica svede na
dijagonalnu formu, komponente resenja se direktno sracunavaju po jednacinama. Poslednja operacija zahteva samo n
deljenja, ali je ukupna cena ipak iznad cene LU faktorizacije.
10. Navedite opšti oblik stacionarnog iterativnog postupka za rješavanje SLAJ.
xk+1=Gxk+c Matrica G i vektor c biraju se tako da je fiksna tačka funkcije g(x)=Gx+c rješenje jednačine Ax=b. Metod
je stacionaran ako su matrica i vektor c konstantni za sve iteracije.
11. Opišite Jakobijev iterativni postupak za rešavanje SLAJ
A = M – N,
