Aleksandar Karač Denis Spahić - ptf.unze.ba

NUMERIČKE METODE U INŽENJERSTVU

Aleksandar Karač

kancelarija 31 1111

tel: 44 91 20

[email protected]

http://ptf.unze.ba/numericke-metode-u-inzenjerstvu

MREZA

Denis Spahić

Kancelarija 4201

tel: 44 91 20

[email protected]

www.ptf.unze.ba

NMuI 19/20 http://ptf.unze.ba/numericke-metode-u-inzenjerstvu/ 2

Izvođenje nastave• predavanja: 2 časa sedmično

• vježbe (auditorne) : 2 časa sedmično

Obaveze studenata• redovno prisustvo na predavanjima i vježbama

• urađene zadaće (ukupno 2 zadaće) – PREDATE U ZADANOM ROKU!!!

Cilj predmeta • Razviti razumijevanje o matematičkim principima kod numeričkih metoda• Obezbijediti praktična znanja u primjeni numeričkih metoda u oblasti građevinarstva.• Usavršiti korištenje aplikativnih softvera u rješavanju inženjerskih problema.

Kompetencije (Ishodi učenja)

Po završetku kursa studenti će biti u stanju:• primijeniti tehnike traženja korijena nelinearnih jednačina radi rješavanja inženjerskih problema.• razviti linearni system jednačina za inženjerske problem i riješiti ga numerički.• sprovesti numeričko diferenciranje i integriranje• razviti i implementirati eksplicitne i implicitnu shemu konačnih razlika u rješavanju običnih diferencijalnih jednačina

O kursu Primjena numeričkih metoda u inženjerstvu



Provjera znanja

Konačna ocjena

• dvije zadaće u toku semestra (zadaci)

• dva testa/kolokvija u toku semestra (teorija, kviz pitanja)

• pismeni ispit (zadaci)

• prisustvo nastavi: 0 %

• zadaća: 30 %

• testovi/seminarski: 20 %

• pismeni ispit: 50 % (na ispitu se koristi lista formula/tabela dostupna na stranici kursa)!!!

Napomena: Svaka od stavki mora biti ispunjena minimalno 51%!!!

Ocjena 6 55-65%

Ocjena 7 65-75%

Ocjena 8 75-85%

Ocjena 9 85-95%

Ocjena 10 95-100%


Sadržaj kursa

1. Osnovne ideje i koncepti u numeričkoj analizi 1 sedmica

2. Rješavanje nelinearnih jednačina 2 sedmice

3. Rješavanje sistema linearnih jednačina 3 sedmice

T E S T I

4. Interpolacija i aproksimacija funkcija 2 sedmice

5. Numeričko diferenciranje i integriranje 2 sedmice

6. Rješavanje običnih diferencijalnih jednačina 3 sedmice

T E S T II / Integralni test



LITERATURA

• I. Demirdžić, Numerička matematika, IP Svjetlost, D.D., Zavod za udžbenike i nastavna sredstva, 1997.• M. Bertolino, Numerička analiza, Naučna knjiga, Beograd, 1981.• Z. Drmač i dr., Numerička analiza, Sveučilište u Zagrebu, Zagreb 2003.,

http://web.math.hr/~rogina/2001096/num_anal.pdf• M. Marić-Dedijer, Zbirka rješenih zadataka iz numeričke analize, Naučna knjiga, Građevinski fakultet, Beograd,

1992.• S.C. Chapra, R.P. Canale, Numerical Methods for Engineers, McGraw-Hill Education, Seventh Edition, 2015. • J. Hoffman, Numerical Methods for engineers and Scientists, Marcel Dekker, Inc., New York 1992• A. Querteroni et.al., Numerical mathematics, Springer, 2000

dodatna

osnovna

• Predavanja, vježbe, skripta (sve dostupno na web stranici)



ZADAĆA 1: (2) + (3)

Zadata: 24. oktobar 2019. godineRok za predaju: 6. decembar 2019. godine

ZADAĆA 2: (4) + (5) + (6)

Zadata: 5. decembar 2019. godineRok za predaju: 24. januar 2020. godine

Obaveze studenata

Provjera znanja

TEST 1: (1) + (2) + (3) 5. decembar 2019. godineTEST 2: (4) + (5) + (6) 23. januar 2020. godine



Korisne web stranice

• Numerical Methods from Eric Weisstein's World of Mathematics

http://mathworld.wolfram.com/topics/NumericalMethods.html

• Video of Gilbert Strang's Linear Algebra Lectures

http://web.mit.edu/18.06/www/Video/video-fall-99.html

• http://numericalmethods.eng.usf.edu/

• http://math.fullerton.edu/mathews/n2003/NumericalUndergradMod.html

• Doug Arnold's Page on Disasters due to Numerical Errors

http://www.math.psu.edu/dna/disasters/

• Numerical Methods — Online Course – Slides

http://math.jct.ac.il/~naiman/nm/

• Numerical Methods Lecture Notes: introduction

http://www.damtp.cam.ac.uk/lab/people/sd/lectures/nummeth98/introduction.htm



UvodOsnovne ideje i koncepti u numeričkoj analizi

Iteracija – ponavljanje niza radnji ili postupaka s ciljem poboljšanja prethodno dobivenih rezultata

1 0

2 1

1

( )( )

( )................

( ) - rekurzivna formulan n

x g xx g x

x g x

x g x

1

Ako niz konvergira ka graničnoj vrijednosti , imamo

lim lim ( ) ( )

pa zadovoljava jednačinu ( ).

n

n nn n

x

x g x g

x x g x


x

f(x)

A0

x0 x1

M

x2 x3

A1

g(x0)

B1

x

f(x)

x0 x2 x4 x3 x1

M

A0

A1

A2

A3

A4

x

f(x)

x0=x2 x1=x3

M

x

f(x)

B0

x3 x2

M

x1 x0

B1

B2

B3

A0

A1

A2

A3

a) b)

c) d)

Uvod


Aproksimacija – približno predstavljanje funkcija

Linearizacija – aproksimacija linearnom funkcijom

Ekstrapolacija – procjena nepoznatih veličina na proširenjem trenda dobijenog poznatim podacima

Predstavljanje brojeva

• brojni sistemi (decimalni, binarni, ...)

Uvod


• pri unosu podataka

• pri zaokruživanju u toku računanja

• usljed prekidanja (zanemarivanja članova višeg reda)

• usljed pojednostavljenja matematičkog modela

• ljudske greške i greške računara

Greške

• apsolutna greška

• relativna greška

x x x

x x xx x

Uvod


Osnovni zadatak: Za datu neprekidnu funkciju f (x), treba naći vrijednost x = takvu da je

f () = 0

x

f(x)

f(1)=0 f(2)=0 1 2

Rješavanje nelinearnih jednačina


Osnovni koraci u pronalaženju korijena

• Lokalizacija nula

- crtanje grafika funkcije (ručno, Excel, MathCAD, Matematica, web, ...)

- inkrementalno pretraživanje

- prethodna iskustva, ...

• Poboljšanje rješenja

- rješenje se nalazi u zadatom intervalu: metoda polovljenja, regula

falsi

- rješenje nije ograničeno u nekom intervalu: prosta interacija, Newtonova

metoda, modifikovana Newtonova metoda, metoda sječice



Ponašanje nelinearnih jednačina u blizini korijena

x

f(x)

2

a)

x

f(x)

b)

x

f(x)

c)

1 x

f(x)

d)

2 1 3



x

f(x)

e)

1=2 x

f(x)

f)

1=2=3

x

f(x)

g)

2=3 1 x

f(x)

h)

Ponašanje nelinearnih jednačina u blizini korijena



Metoda polovljenja intervala - bisekcija

x

f(x)

b=b0

f(b)

f(c)

f(a)

a=a0

a1

a2

c=b1 c=b2

c=a3

Ako je f(a)f(c)<0: a=a, b=c

Ako je f(c)f(b)<0: a=c, b=b

Ako je f(a)f(c) = 0: dobiva se rješenje

= cili dok se ne postigne željena tačnost, tj.

2a bc

( , )a b

1 2| | i/ili ( )i i ib a f c

Ideja: prepoloviti početni interval, u kojem se nalazi korijen, na dva podintervala, provjeriti u kojem podintervalu se nalazi korijen, i postupak nastaviti do željene tačnosti ili pronalaska rješenja.



Primjer

x

y

-5 -4 -3 -2 -1 0 1 2 3 4 5-3

-2

-1

0

1

2

3

4

5

fx=x-

Naći pozitivni korijen jednačine f (x) = x 2 – 2. Postupak rješavanja zaustaviti kada vrijednostrazlike između dvije uzastopne iteracije bude manja od 10-4, tj. |xi+1 – xi |

1. Lokalizacija nula

2 [a,b]=[1,2]

f (1)= –1<0 i f (2)=2>0

2. Primjena algoritma

1 2 1.52 2

( ) (1.5) 0.25 0, ( ) (1) 1 0 1, 1.5

1,1.5

a bc

f c ff a f a a b c




1 1.5 1.252 2

( ) (1.25) 0.4375 0, ( ) (1.5) 0.25 0 1.25, 1.5

1.25,1.5

1.25 1.5 1.3752 2

( ) (1.375) 0.109375 0, (1.5) 0.25 0 1.375, 1.5

1.3

a bc

f c ff b f a c b b

a bc

f c ff a c b b

75,1.5

1.4142

itd., itd., itd., ............. 14. iteracija




Prednosti:

• Korijen jednačine se nalazi unutar granica nekog intervala, tako da je konvergencija zagarantovana.

• Maksimalna greška metode je |bn-an|.

• S obzirom da se svakom iteracijom interval polovi, broj iteracija n, a time i broj računanja funkcije, koji je potreban da se prvobitni interval (bn,an) smanji na određeni interval (bn,an), dobiva se iz

0 0

0 0

1( ) ( )2

pa je1 log( )

log(2)

n n n

n n

b a b a

b anb a

Osnovni nedostatak ove metode je spora konvergencija, odnosno veliki broj iteracija radi postizanja željene tačnosti.




Metoda regula falsi

x

f(x)

b

f(b)

f(c)

f(a)

ac=x1

c=x2

( , )a b

Ideja: aproksimirati funkciju pravom linijom između krajnjih tačaka početnog intervala, i naći tačku x1, koja predstavlja prvu aproksimaciju rješenja. Postupak ponavljati do željene tačnosti ili pronalaska rješenja.

1 ( )( ) ( )

b ax b f bf b f a

Ako je f(a)f(xi)<0: a =a, b =xi

Ako je f(xi)f(b)<0: a =xi, b =b

Ako je f(a)f(xi)=0: dobiva se rješenje

=xi

ili dok se ne postigne željena tačnost, tj.

1 2| | i/ili ( )ib a f x



Primjer


1. Lokalizacija nula

2 [a,b]=[1,2]

f (1)= –1<0 i f (2)=2>0

2. Primjena algoritma

1

1

1

2 1( ) 2 2 1.33333( ) ( ) 2 ( 1)

( ) (1.33333) 0.2222 0, ( ) (2) 2 0 1.33333, 2

1.33333, 2

b ax b f bf b f a

f x ff b f a x b b

Metoda regula falsi



2

2

2

3

3

2 1.33333( ) 2 2 1.4( ) ( ) 2 ( 0.22222)

( ) (1.4) 0.04 0, ( ) (2) 2 0 1.4, 2

1.4, 2

2 1.4( ) 2 2 1.41176( ) ( ) 2 ( 0.04)

( ) (1.41176) 0.00692 0,

b ax b f bf b f a

f x ff b f a x b b

b ax b f bf b f a

f x f

3

( ) (2) 2 0 1.41176, 2

1.41176, 2

f b f a x b b

1.4142 itd., itd., itd., ............. 6. iteracija

Metoda regula falsi



x

y

xi xi+1

1 ( )i ix g x

1 1 1 2| | i/ili ( )i i ix x f x

Metoda proste iteracije

Ideja: Napisati jednačinu oblika f(x)=0 u obliku x=g(x) i iterativno je riješiti.



Uslov konvergencije:

1 1

1 1

1 1

1

( ) ( )

( ) ( ) '( )( ) ... ( )

'( )( )

'( )

'( ) 1

i i i

i i i

i i i

i i i

i

i

x e g x g

g g x g x x

x e g x

x e g e

e ge




Primjer

Na primjeru rješavanja jednačine f (x) = x 2 – x – 2 pokazati upotrebu metode proste iteracije.

2

2

( ) ( )

(a) 2

(b) 22(c) 1

2(d) 2

f x x g x

x x

x x

xxx xx x

x

x

y

0 1 2 3 4 5 6 7 8 9 10-3

-2

-1

0

1

2

3

4

5

6

7

8

9

10

g(x=x+x-x-/x-f(x=x

g(x= x+g(x=+/x

g(x=x-




2

0

21 0

22 1

23 2

(a) g(x) 2

3

( ) 3 2 7

( ) 7 2 47

( ) 47 2 2207itd.

1g (x) 2 1 za 2

x

x

x g x

x g x

x g x

x x

x

y

0 1 2 3 4 5 6 7 8 9 10

0

5

10

15

20

25

30

35

40

45

50

f(x=xg(x=x-





0

1 0

2 1

3 2

4 3

(b) g(x) 2

3

( ) 3 2 2.236

( ) 2.236 2 2.058

( ) 2.058 2 2.0014

( ) 2.0014 2 2.0004itd.

1 7g (x) 1 za x42 2

x

x

x g x

x g x

x g x

x g x

x

x

y

0 1 2 3 4-3

-2

-1

0

1

2

3

4

5

f(x=xg(x= x+





0

1 0

2 1

3 2

4 3

2

(c) g(x) 1 2 /

3( ) 1 2 / 3 1.6666( ) 1 2 /1.6666 2.2( ) 1 2 / 2.2 1.9091( ) 1 2 /1.9091 2.0476

itd.

1g (x) 1 za x 1

x

xx g xx g xx g xx g x

x

x

y

0 1 2 3 4 5-1

0

1

2

3

4

5

f(x=xg(x=+/x





x

f(x) M0

x0

x1

M1

M2

x2

Ideja: aproksimirati funkciju tangentom u početnoj aproksimaciji, i naći tačku x1, koja predstavlja sljedeću aproksimaciju rješenja. Postupak ponavljati (traženje tangente u novoj aproksimaciji) do željene tačnosti ili pronalaska rješenja.

1

1

1 1

1

( ) ( )iz '( )

ili ( ) ( ) '( )( ) ...

( )'( )

i i

i i

i i i i i

ii i

i

f x f xf xx x

f x f x f x x x

f xx xf x

1 1 1 2| | i/ili ( )i i ix x f x

dok se ne postigne željena tačnost, tj.

Newtonova metoda



Primjer


2

1

1

0

1

2

( ) 2'( ) 2

1 22

31 23 1.833332 31 21.83333 1.462212 1.83333

i ii i i

i i

i ii

f x xx x xf x x

x xx

x

x

x

x

y

0 1 2 3 4-1

0

1

2

3

4

5

6

7

8

9

10

fx=x-

x2

x0x1

Newtonova metoda



3

4

5

1 21.46221 1.4152 1.462211 21.415 1.414212 1.4151 21.41421 1.414212 1.41421

x

x

x

1.4142 x

y

0 1 2 3 4-1

0

1

2

3

4

5

6

7

8

9

10

fx=x-

x2

x0x1

Newtonova metoda



Prednosti:

• Tačnost metode je drugog reda, pa se svakom iteracijom udvostručava broj značajnih cifara

• Odlične osobine lokalne konvergencije.

Nedostaci:

• Problem određivanja prvog izvoda

Newtonova metoda



Ideja: aproksimirati funkciju tangentom u početnoj aproksimaciji, i naći tačku x1, koja predstavlja sljedeću aproksimaciju rješenja. Postupak ponavljati, korištenjem vrijednosti prvog izvoda za početnu aproksimaciju, do željene tačnosti ili pronalaska rješenja.

1

0

10

( )'( )

'( ) '( )

( )'( )

ii i

i

ii i

f xx xf x

f x f x

f xx xf x

1 1 1 2| | i/ili ( )i i ix x f x

dok se ne postigne željena tačnost, tj. x

f(x) M0

x0

x1

M1 M2

x2

M2

x3 x3

Modifikovana Newtonova metoda



Primjer


2

10 0

02

1

2

2

2

13

( ) 2'( ) 2

3

3 23 1.833332 3

1.83333 21.83333 1.606482 3

...1.41437 21.41437 1.41429

2 3

i ii i i

f x xx x xf x x

x

x

x

x

x

y

0 1 2 3 4-1

0

1

2

3

4

5

6

7

8

9

10

fx=x-

x2

x0x1

1.4142

Modifikovana Newtonova metoda



x

f(x) M0

x0

x1

M1

M2

x2

M3

x3

Ideja: nelinearna funkcija f(x) se lokalno aproksimira linearnom funkcijom g(x) (sječica). Korijen funkcije g(x) je sljedeća aproksimacija.

1

1

1

11

1

( )'( )

( ) ( )'( ) ( )

( )( ) ( )

ii i

i

i i

i i

i ii i i

i i

f xx xf x

f x f xf x g xx x

x xx x f xf x f x

1 1 1 2| | i/ili ( )i i ix x f x

dok se ne postigne željena tačnost, tj.

Metoda sječice (sekante)



Primjer


11

1

0 1

2

3

7

( )( ) ( )

4, 33 43 7 27 142 32 2 1.62 7

......1.41423 1.416061.41423 0.000055

0.000055 0.005221 1.41421

i ii i i

i i

x xx x f xf x f x

x x

x

x

x

x

y

0 1 2 3 4 5-10123456789

101112131415

fx=x-

x3

x0x1x2

1.4142




Prednosti:

• Tačnost metode je reda 1.62, pa je metoda znatno brža od proste iteracije. U slučaju kada je brzina izračunavanja vrijednosti funkcije povoljna u odnosu na izračunavanje prvog izvoda funkcije (tačnije, do 43% brža), metoda je brža i od Newtonove metode.




Problemi u numeričkom rješavanju jednačina

• nedovoljno dobra početna aproksimacija

• konvergencija prema pogrešnom korijenu

• korijeni koji su blizu jedan drugom

• mnogostruki korijeni

• tačke infleksije

• kompleksni korijeni

• loše postavljena nelinearna jednačina

• spora konvergencija



Smjernice u traženju korijena

• Proces lokalizacije bi trebao ograničiti korijen.

• Dobra početna aproksimacija je veoma važna.

• Metode s korijenom koji je ograničen u nekom intervalu su sigurnije nego one kojima korijen nije ograničen, jer zadržavaju rješenje u tom zatvorenom intervalu.

• Metode kojima korijen nije ograničen u nekom konačnom intervalu, kada konvergiraju, općenito konvergiraju brže od metoda s korijenom ograničenom u nekom konačnom intervalu.

• Za funkcije bez naglih promjena u ponašanju, većina algoritama uvijek konvergira ako je početna aproksimacija dovoljno blizu. Za ove slučajeve unaprijed je moguće procijeniti brzinu konvergencije.



• Mnogi, ako ne i većina, inženjerskih problema su jednostavni i dobro se ´ponašaju´. U takvim slučajevima, jednostavne metode, kao što je Newtonova metoda, mogu se primijeniti bez bojazni da se radi o nekom specijalnom slučaju.

•Ako se neki problem treba riješiti samo jednom, ili mali broj puta, efikasnost nije u prvom planu. Nasuprot tome, ako se rješavanje neke jednačine obavlja veliki broj puta, veoma važno je koristiti efikasnije metode.

Smjernice u traženju korijenaRješavanje nelinearnih jednačina


• Treba biti poznat maksimalan broj iteracija.

• U slučaju da metoda koristi prvi izvod funkcije, f ’ (x), mora se paziti da ovavrijednost u toku proračuna ne bude jednaka nuli.

• Test konvergencije oblika |xi+1-xi |, te vrijednost funkcije |f (xi+1 )| se moraju uzeti u obzir.

• Kada se dostigne konvergencija, konačna procjena korijena bi se trebala uvrstiti u funkciju f (x), kako bi se zagarantovalo da je f (x)=0 u granicama željenetačnosti.

Željene osobine metoda za rješavanje nelinearnih jednačina



Rješavanje sistema linearnih jednačina

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

......

...............................................

n n

n n

n n nn n n

a x a x a x ba x a x a x b

a x a x a x b

Problem rješavanja sistema jednačina (linearnih i nelinearnih) javlja se u gotovo svim segmentima inženjerstva i nauke. U ovom kursu pažnja je posvećena rješavanju sistema od nlinearnih jednačina sa n nepoznatih oblika:

xi – nepoznate promjenljive

Aij – koeficijenti nepoznatih promjenljivih

bi – nehomogeni članovi

i,j=1,2,...,n

Ax=b

A – matrica sistema

x – kolona vektor rješenja

b – kolona vektor nehomogenih članova

11 12 1 1 1

21 22 2 2 2

1 2

, ,

n

n

n n nn n n

a a a x ba a a x b

a a a x b

Α x b

U matričnom obliku:


11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

......

...............................................

n n

n n

n n nn n n


a x a x a x b

Rješenje sistema

Ax=b

može biti:

• jedinstveno – sistem je određen.

• bez rješenja – sistem je protivrječan.

• beskonačno mnogo rješenja – sistem ima nedovoljan broj jednačina.

• trivijalno (xi = 0)– sistem je homogen ( bi = 0 za i = 1,2,...,n )

1 ( 1, 2,..., )

n

ij j ij

a x b i n



Metode za rješavanje sistema linearnih jednačina

• Direktne metode – zasnivaju se na principu eliminacije. Dovode do rješenja nakon KONAČNOG broja računskih operacija.

- Cramerovo pravilo (direktna metoda, ne zasniva se na eliminaciji)

- Metode eliminacije – Gaussova metoda, Gauss-Jordanova

metoda, matrična metoda, metode faktorizacije

• Iterativne metode – asimptotski dovode do rješenja pomoću neke iterativne procedure, tj. Dovode do tačnog rješenja nakon BESKONAČNOG broja računskih operacija

- Jacobijeva metoda

- Gauss-Seidelova metoda

- Metode relaksacije



Rješavanje sistema linearnih jednačina – direktne metodeCramerovo pravilo (reda radi!!!)

Rješenje sistema dato je sa:

det( ) ( 1, 2,..., )det( )

j

jx j n AA

Aj – matrica nn, koja se dobija zamjenom kolone j matrice A s kolonom vektora b.

Za sistem s dvije jednačine:11 1 12 2 1

21 1 22 2 2

a x a x ba x a x b

1 12 11 1

2 22 21 21 2

11 12 11 12

21 22 21 22

i

b a a bb a a b

x xa a a aa a a a

rješenje je:

Metoda je gotovo neupotrebljiva kada se determinante izračunavaju metodom kofaktora – broj množenja i djeljenja je (n – 1)(n + 1)! Za n=10 broj operacija je 360 000 000, za n =100 reda 10157!!!


Metode eliminacije (Gaussova metoda)

1. Riješi se jedna od jednačina za neku nepoznatu u odnosu na druge nepoznate, i ta vrijednost se uvrsti u ostale jednačine sistema. Postupak se ponavlja dok se ne dođe do jednačine koja sadrži samo jednu nepoznatu. ( proces eliminacije )

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

......

...............................................

n n

n n

n n nn n n


a x a x a x b

1 12 2 11

11

( ... )n nb a x a xxa

22 2 2 2

2 2

....................................

...

n n

n nn n n

A x A x B

A x A x B

2 22

22

( ... )n nB A xxA

itd........

Rješavanje sistema linearnih jednačina – direktne metode


2. Riješi se nepozanta promjenljiva iz posljednje jednačine, njena vrijednost uvrsti u prethodnu jednačinu, pa se riješi sljedeća nepoznata, itd. ( zamjena unazad )

Primjer 1.

1 2 3

1 2 3

1 2 3

(1) 80 20 20 20(2) 20 40 20 20(3) 20 20 130 20

x x xx x xx x x

Metodom eliminacije riješiti sistem jednačina:

2 31

20 20 20iz (1) (*)

80x x

x

2 32 3

2 3

2 32 32 3

20 20 2020 40 20 20 (4) 35 25 2580(*) u (2) i (3)

(5) 25 125 2520 20 2020 20 130 20

80

x xx x x x

x xx xx x

Rješenje 1:

Metode eliminacije (Gaussova metoda)Rješavanje sistema linearnih jednačina – direktne metode


2 3

2 3

(4) 35 25 25(5) 25 125 25

x xx x

32

25 25iz (4) (**)

35x

x

33

25 25 750 300(**) u (5) 25 35 7 7

xx

1 2 3

1 2 3

1 2 3

80 20 20 20 20 40 20 20 20 20 130 20

x x xx x xx x x

1 2 3

2 3

3

(6) 80 20 20 20(7) 35 25 25

750 300(8) 7 7

x x xx x

x

3

32

2 33

iz (8) 0.4

25 25iz (7), tj. (**) 1.0

3520 20 20

iz (6), tj. (*) x 0.680

x

xx

x x



Rješenje 2:

80 20 20 20 20 40 20 20

20 20 130 20

Ax = b A b1 2 3

1 2 3

1 2 3

80 20 20 2020 40 20 2020 20 130 20

x x xx x xx x x

80 20 20 20 20 40 20 20

20 20 130 20

A b

(a) 80 20 20 20 ( 20 / 80) (b), ( 20 / 80) (c)(b) 20 40 20 20(c) 20 20 130 20

(a) 80 20 20 20(b) 0 35 25 25 ( 25 / 35) (c)(c) 0 25 125 25



1

2

3

(a) 80 20 20 20 0.6(b) 0 35 25 25 1.0(c) 750 300 0.40 0

7 7

xxx

(a) 80 20 20 20(b) 0 35 25 25 ( 25 / 35) (c)(c) 0 25 125 25



Problemi

• Prilikom izvođenja metode eliminacije može se desiti da je elemenat na glavnoj dijagonali modifikovane matrice A jednak nuli.

• U slučaju da su elementi po dijagonalama mnogo manji od ostalih elemenata u jednačinama koje sadrže glavni elemenat, može doći do značajne greške zaokruživanja, što, pak, može dovesti do pogrešnih rješenja.

Korisni alati:

• bilo koji red (jednačina) se može pomnožiti konstantom. Ova operacija se najčešće koristi za skaliranje jednačina, ako je to neophodno.

• redovi (jednačine) mogu zamijeniti mjesta. Operacija se koristi kako bi se izbjeglo dijeljenje s nulom i smanjile greške zaokruživanja.

• bilo koji red (jednačina) može se zamijeniti linearnom kombinacijom tog reda (jednačine) i bilo kojeg drugog reda (jednačine). Ova operacija se najčešće koristi kako bi se implementirao proces sistematske eliminacije.



Primjer 2.

Metodom eliminacije riješiti sistem jednačina:

1

2

3

0 2 1 54 1 1 32 3 3 5

xxx

0 2 1 5 4 1 1 34 1 1 3 0 2 1 52 3 3 5 2 3 3 5

a) 4 1 1 3 ( 0 / 4) (b), ( 2 / 4) (c)b) 0 2 1 5c) 2 3 3 5

4 1 1 3 4 1 1 30 2 1 5 0 7 / 2 7 / 2 7 / 20 7 / 2 7 / 2 7 / 2 0 2 1 5



a) 4 1 1 3b) 0 7 / 2 7 / 2 7 / 2 (4 / 7) (c)c) 0 2 1 5

3

2

3

4 1 1 3 10 7 / 2 7 / 2 7 / 2 20 0 3 3 1

xxx

Primjer 3.

Provjeriti prednosti procesa skaliranja na sistemu jednačina:

1

2

3

3 2 105 1042 3 103 981 1 3 3

xxx

pri čemu proračun izvršiti na tri značajne cifre. Rješenje sistema je x1 = – 1, x2 = 1 i x3 = 1



a) 3 2 105 104 (0.667) (b), (0.333) (c)b) 2 3 103 98c) 1 1 3 3

1

2

3

3 2 105 1042 3 103 981 1 3 3

xxx

a) 3 2 105 104b) 0 4.334 33 28.6 (0.077) (c)c) 0 0.334 32 31.6

3

2

1

a) 3 2 105 104 0.884b) 0 4.334 33 28.9 0.924c) 0 0 29.5 29.4 0.997

xxx

x1 = – 1, x2 = 1, x3 = 1



1

2

3

3 2 105 1042 3 103 981 1 3 3

xxx

x1= – 1, x2=1, x3=1

3 2 105 1 1 3 32 3 103 2 3 103 981 1 3 3 2 105 104

1

3 /105 0.02862 /103 0.01941/ 3 0.3333

a

a) 1 1 3 3 (2) (b), (3) (c)b) 2 3 103 98c) 3 2 105 104

1 1 3 30 5 97 920 1 96 95

2 5 / 97 0.05161/ 96 0.0104

a

1

2

3

a) 1 1 3 3 1 1 3 3 1b) 0 5 97 92 (1/ 5) (c) 0 5 97 92 1c) 0 1 96 95 0 0 76.6 76.6 1

xxx



Gaussova metoda

Opšti algoritam rješavanja:

1. Definisati koeficijente matrice A, vektora b(, i pomoćnog vektora o.)

2. Počevši od prve kolone, treba normalizovati kolone k (k=1,2,..., n-1) i tražiti po veličini najveći elemenat u koloni k te izmijeniti redove kako bi se taj koeficijent postavio u poziciju glavnog elementa akk.

3. Za kolonu k (k=1,2,...,n-1) se primijeni procedura eliminacije na redove i (i=k+1,k+2,...,n) kako bi se stvorile nule ispod glavnog elementa, akk. Na taj način se dobija:

Nakon što se primijeni ovaj korak na svih k kolona, originalna matrica A postaje gornja trougaona.

)...,2,1(

)...,2,1,(

nkkiaaabb

nkkjiaaaaa

kjkk

ikii

kjkk

ikijij



4. Riješiti nepoznanice x koristeći zamjenu unazad, tako da je:

ii

n

ijjiji

i

nn

nn

a

xabx

abx

1

Broj množenja i dijeljenja približno je jednak n3/3 – n/3 + n2 – za sistem od 10 jednačina to je 430, a sistem od 100 jednačina 343 000.

Gaussova metodaRješavanje sistema linearnih jednačina – direktne metode


• Varijacija Gaussove metode, pri čemu se i elementi iznad glavne dijagonale izjednačavaju s nulom. Matrica A se, na taj način, transformiše u dijagonalnu matricu.

• Skaliranjem matrica A se pretvara u jediničnu matricu.

• Pogodna za simultano rješavanje sistema jednačina s više vrijednosti vektora b.

• Broj množenja i dijeljenja je približno jednak n3/2 – n/2 + n2 – 50% više od Gaussovemetode.

Primjer

1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

Riješiti sistem jednačina koristeći Gauss-Jordanovom metodom:

Gauss-Jordanova metodaRješavanje sistema linearnih jednačina – direktne metode


(a) 80 20 20 20 / 80(b) 20 40 20 20(c) 20 20 130 20

1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

(a) 1 0.25 0.25 0.25 ( 20) (b), ( 20) (c)(b) 20 40 20 20(c) 20 20 130 20

(a) 1 0.25 0.25 0.25(b) 0 1 5 / 7 5 / 7 ( 0.25) (a), ( 25) (c)(c) 0 25 125 25

(a) 1 0.25 0.25 0.25(b) 0 35 25 25 / 35(c) 0 25 125 25



1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

(a) 1 0.25 0.25 0.25(b) 0 1 5 / 7 5 / 7 ( 0.25) (a), ( 25) (c)(c) 0 25 125 25

(a) 1 0 3/ 7 3/ 7(b) 0 1 5 / 7 5 / 7(c) 0 0 750 / 7 300 / 7 /(750 / 7)

(a) 1 0 3/ 7 3/ 7(b) 0 1 5 / 7 5 / 7(c) 0 0 1 2 / 5 ( 3 / 7) (a), ( 5 / 7) (b)

1

2

3

(a) 1 0 0 3/ 5 0.6(b) 0 1 0 1.0 1.0(c) 0 0 1 2 / 5 0.4

xxx



[A|I][I|A-1]Primjer

80 20 2020 40 2020 20 130

Koristeći Gauss-Jordanovu metodu, naći inverznu matricu matrice:

80 20 20 1 0 0 / 80 1 0.25 0.25 1/ 80 0 0 ( 20) (b), ( 20) (c)20 40 20 0 1 0 20 40 20 0 1 020 20 130 0 0 1 20 20 130 0 0 1

1 0.25 0.25 1/ 80 0 0 1 0.25 0.25 1/ 80 0 00 35 25 0.25 1 0 / 35 0 1 5 / 7 0 1/ 35 0 ( 0.25) (a), ( 25) (c)0 25 125 0.25 0 1 0 25 125 0 0 1

Ideja: Matricu A proširiti jediničnom matricom, te slično prethodnom postupku, lijevi dio transformisati u jediničnu matricu. Desni dio, onda, predstavlja inverznu matricu, tj.

Inverzija matrice Gauss-Jordanovom metodomRješavanje sistema linearnih jednačina – direktne metode


1 0.25 0.25 1/ 80 0 0 1 0.25 0.25 1/ 80 0 00 35 25 0.25 1 0 / 35 0 1 5 / 7 1/140 1/ 35 0 ( 0.25) (a), ( 25) (c)0 25 125 0.25 0 1 0 25 125 0.25 0 1

1 0 3/ 7 1/ 70 1/140 00 1 5 / 7 1/140 1/ 35 00 0 750 / 7 3/ 7 5 / 7 1 /(750 / 7)

1 0 3/ 7 1/ 70 1/140 00 1 5 / 7 1/140 1/ 35 00 0 1 1/ 250 1/150 7 / 750 ( 3 / 7) (a), ( 5 / 7) (b)

1

1 0 0 2 /125 1/100 1/ 250 2 /125 1/100 1/ 2500 1 0 1/100 1/ 30 1/150 1/100 1/ 30 1/1500 0 1 1/ 250 1/150 7 / 750 1/ 250 1/150 7 / 750

A

Inverzija matrice Gauss-Jordanovom metodomRješavanje sistema linearnih jednačina – direktne metode


Matrična metoda

-1 -1

-1

Ax = b

A Ax = 1x = x = A b

x = A b

Primjer

1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

1

80 20 20 20 20 40 20 20

20 20 130 20

Ax = b A b x A b

Riješiti sistem jednačina koristeći matričnu metodu:



1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

1

2 /125 1/100 1/ 2501/100 1/ 30 1/1501/ 250 1/150 7 / 750

A

1

2 /125 1/100 1/ 250 20 0.61/100 1/ 30 1/150 20 1.01/ 250 1/150 7 / 750 20 0.4

x A b

Matrična metoda



Ideja: Faktorizirati (razložiti) na neke dvije matrice u povoljnom obliku

Na primjer,

L – donja trougaona matrica

U – gornja trougaona matrica

Metoda Doolitle

Metoda Crouta

A = LU

11 12 1 11 12 1

21 22 2 21 22 2

1 2 1 2

1 0 01 0 0

1 0 0

n n

n n

n n nn n n nn

a a a u u ua a a l u u

a a a l l u

11 12 1 11 12 1

21 22 2 21 22 2

1 2 1 2

0 0 10 0 1

0 0 1

n n

n n

n n nn n n nn

a a a l u ua a a l l u

a a a l l l

Metode faktorizacije



Metoda Doolitle

Matrica U dobija se Gaussovom metodom eliminacije, a matrica L predstavlja zapis množitelja u procesu eliminacije. S poznatim U i L sistem se rješava prema:

A = LU

Lb' b b'

Ux b' x

Primjer

1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

Riješiti sistem jednačina koristeći matričnu metodu:




1

2

3

(a) 80 20 20 20 0.6(b) 0 35 25 25 1.0(c) 750 300 0.40 0

7 7

xxx

(a) 80 20 20 20(b) 0 35 25 25 ( 25 / 35) (c)(c) 0 25 125 25

(a) 80 20 20 20 ( 20 / 80) (b), ( 20 / 80) (c)(b) 20 40 20 20(c) 20 20 130 20

1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

80 20 200 35 25

7500 07

U

1 0 00.25 1 00.25 5 / 7 1

L



Unaprijed poznato!!!


80 20 200 35 250 0 750 / 7

U1 0 0

0.25 1 00.25 5 / 7 1

L

1

2

3

80 20 20 2020 40 20 2020 20 130 20

xxx

•Pogodna za simultano rješavanje sistema jednačina s više vrijednosti vektora b.

•Broj množenja i dijeljenja je približno jednak n3/2 – n/2 + n2 što je 50% više od Gaussovemetode.

Lb' b b'Ux b' x

1 1

2 2

3 3

1 0 0 ' 20 ' 200.25 1 0 ' 20 ' 250.25 5 / 7 1 ' 20 ' 300 / 7

b bb bb b

1 1

2 2

3 3

80 20 20 20 0.40 35 25 25 1.00 0 750 / 7 300 / 7 0.4

x xx xx x




Nedostaci metoda eliminacije

• Prisustvo grešaka zaokruživanja

- usljed aproksimacije brojevima konačne tačnosti

- moguće ih je smanjiti pogodnim razmještajem jednačina ili pomoću posebnog iterativnog postupka

• Podešenost sistema

1 2

1 2

1

2

21.0001 2.0001

(a) 1 1 2 ( 1) (b)(b) 1 1.0001 2.0001

1 1 2 11 0.0001 0.0001 1

x xx x

xx

1 2

1 2

1

2

20.9999 2.0001

(a) 1 1 2 ( 1) (b)(b) 1 0.9999 2.0001

1 1 2 31 0.0001 0.0001 1

x xx x

xx

Primjer



- korištenje beskonačnih brojeva

- skaliranje i zamjena redova

1 1 1

1 1

2

2

1 1

max

max

min

n

ijj n in

ijj n j

i

n n

ijei j

a

a

a

A

A

A

A

maksimalan zbir kolone

Norma i broj podešenosti sistema

maksimalan zbir reda

spektralna norma

Euklidska norma




Primjer

1 11 1.0001

A

Procijeniti podešenost sistema s matricom (matrica koeficijenata iz prethodnog primjera):

2 2 2 2 2

1 11 1 1 1.0001 2.0005

n n

ijei j

a

A

Euklidska norma za A

Inverzna matrica i Euklidska norma za A-1

1 10001 1000010000 10000

A 1 2 2 2 2 2

1 110001 ( 10000) ( 10000) 10000 20000.5

n n

ijei j

a

A

1( ) 40002 1e e

C A A A




11 12 1 1 1

21 22 2 2 2

1 2

n

n

n n nn n n

a a a x ba a a x b

a a a x b

S obzirom da je u većini velikih sistema linearnih jednačina matrica koeficijenata A rijetka, tj. većina elemenata jednaka nuli, mnogo je efikasnije koristiti iterativne metode.

Opšti algoritam iterativnih metoda:

1.Pretpostavi se početno rješenje x(0)

2.Rješenje x(0) se koristi za dobivanje novog, boljeg, rješenja x(1)

pomoću neke strategije smanjenja razlike između rješenja x(0) i stvarnog rješenja x

3.Postupak se ponavlja do postizanja željene tačnosti

Dovoljan uslov za konvergenciju iterativnih metoda je dijagonalna dominantnost.

1 ( 1,2,..., )

n

ii ijjj i

a a i n

Iterativne metodeRješavanje sistema linearnih jednačina – iterativne metode


11 12 1 1 1

21 22 2 2 2

1 2

n

n

n n nn n n

a a a x ba a a x b

a a a x b

Jacobijeva metoda

1

1

1 1

1(1) (0) (0)

1 1

1( 1) ( ) ( )

1 1

( 1, 2,..., )

1

1

1

n

ij j ij

i n

i i ij j ij jj j iii

i n

i i ij i ij ij j iii

i nk k k


a x b i n

x b a x a xa

x b a x a xa

x b a x a xa

( 1) ( ) ( )

1

( )( 1) ( )

( ) ( )

1

1 nk k k

i i i ij ijii

kk k i

i iii

nk k

i i ij ij

x x b a xa

Rx xa

R b a x

Rješavanje sistema linearnih jednačina – iterativne metode


11 12 1 1 1

21 22 2 2 2

1 2

n

n

n n nn n n

a a a x ba a a x b

a a a x b

Primjer

Jacobijevom metodom riješiti sljedeći sistem jednačina:

1

2

3

4

5

4 1 0 1 0 1001 4 1 0 1 100

0 1 4 1 0 1001 0 1 4 1 1000 1 0 1 4 100

xxxxx

1 2 4

1 2 3 5

2 3 4

1 3 4 5

2 4 5

4 1004 100

4 1004 100

4 100

x x xx x x x

x x xx x x x

x x x

1 2 4

2 1 3 5

3 2 4

4 1 3 5

5 2 4

25 0.25 0.2525 0.25 0.25 0.2525 0.25 0.2525 0.25 0.25 0.2525 0.25 0.25

x x xx x x xx x xx x x xx x x

Jacobijeva metoda



1 2 4

2 1 3 5

3 2 4

4 1 3 5

5 2 4

25 0.25 0.2525 0.25 0.25 0.2525 0.25 0.2525 0.25 0.25 0.2525 0.25 0.25

x x xx x x xx x xx x x xx x x

(0) (1) (2) (18)

0.0 25.0 25.00 25.0000000.0 25.0 31.25 35.714285

(*) (*) (*) ......0.0 25.0 37.50 42.8571430.0 25.0 31.25 35.7142850.0 25.0 25.00 25.000000

x x x x

(*)

Jacobijeva metoda



11 12 1 1 1

21 22 2 2 2

1 2

n

n

n n nn n n

a a a x ba a a x b

a a a x b

Gauss-Seidelova metoda

1

1( 1) ( 1) ( )

1 1

( )( 1) ( )

1( ) ( 1) ( )

1

( 1, 2,..., )

1

n

ij j ij

i nk k k


kk k i

i iii

i nk k k

i i ij i ij ij j i

a x b i n

x b a x a xa

Rx xa

R b a x a x



11 12 1 1 1

21 22 2 2 2

1 2

n

n

n n nn n n

a a a x ba a a x b

a a a x b

Primjer

Gauss-Seidelovom metodom riješiti sljedeći sistem jednačina:

1

2

3

4

5

4 1 0 1 0 1001 4 1 0 1 100

0 1 4 1 0 1001 0 1 4 1 1000 1 0 1 4 100

xxxxx

1 2 4

1 2 3 5

2 3 4

1 3 4 5

2 4 5

4 1004 100

4 1004 100

4 100

x x xx x x x

x x xx x x x

x x x

( 1) ( ) ( )1 2 4( 1) ( 1) ( ) ( )2 1 3 5( 1) ( 1) ( )3 2 4( 1) ( 1) ( 1) ( )4 1 3 5( 1) ( 1) ( 1)5 2 4

25 0.25 0.25

25 0.25 0.25 0.25

25 0.25 0.25

25 0.25 0.25 0.25

25 0.25 0.25

k k k

k k k k

k k k

k k k k

k k k

x x x

x x x x

x x x

x x x x

x x x




( 1) ( ) ( )1 2 4( 1) ( 1) ( ) ( )2 1 3 5( 1) ( 1) ( )3 2 4( 1) ( 1) ( 1) ( )4 1 3 5( 1) ( 1) ( 1)5 2 4

25 0.25 0.25

25 0.25 0.25 0.25

25 0.25 0.25

25 0.25 0.25 0.25

25 0.25 0.25

k k k

k k k k

k k k

k k k k

k k k

x x x

x x x x

x x x

x x x x

x x x

(0)

0.00.00.00.00.0

x

(1)1(1)2(1)3(1)4(1)5

25

25 31.25

31.25 32.81

25 0.25 0.25

25 0.25 0.25 0.25

25 0.25 0.25

25 0.25 0

25

25 32.8125 26.953125

31.25 2

.25 0.25

25 0.25 0.2

0 0

6.953125 23.925781

0 0

0

5

0

x

x

x

x

x

(1)1(1)2(1)3(1)4

26.074219

26.074219 33.740234

33.740

31.25 26.

234 40.173340

26.074219 40.173340

953125

32.8125 23.925781

26.95

25 0.25 0.25

25

3125

2

0.25 0.25 0.25

25 0.25 0.25

25 0.25 0.25 0 3.2 .5

x

x

x

x

(1)5

1 34.506225

33.25 0.25 0.25740234 34.506225 25.191498

92578

x

(15)

25.00000035.714286

... 42.85714335.71428625.000000

x


(1)

25.000031.250032.812526.953123.9258

x



11 12 1 1 1

21 22 2 2 2

1 2

n

n

n n nn n n

a a a x ba a a x b

a a a x b

Metode relaksacije – SOR metoda

( )( 1) ( )

( ) ( )

1

1( ) ( 1) ( )

1

0 2 sistem konvergira0 1 podrelaksacija1 2 nadrelaksacija

kk k i

i iii

nk k

i i ij jj

i nk k k

i i ij j ij jj j i

Rx xa

R b a x

R b a x a x

Gauss-Seidel

Jacobi



Primjer

SOR metodom (za Jacobijevu metodu) riješiti sljedeći sistem jednačina:

1

2

3

4

5

4 1 0 1 0 1001 4 1 0 1 100

0 1 4 1 0 1001 0 1 4 1 1000 1 0 1 4 100

xxxxx

1 2 4

1 2 3 5

2 3 4

1 3 4 5

2 4 5

4 1004 100

4 1004 100

4 100

x x xx x x x

x x xx x x x

x x x

1 1 2 4

2 1 2 3 5

3 2 3 4

4 1 3 4 5

5 2 4 5

100 4100 4100 4100 4100 4

R x x xR x x x xR x x xR x x x xR x x x

Uzeti =1.1.

Metode relaksacije – SOR metodaRješavanje sistema linearnih jednačina – iterativne metode


(0) (0) (1)

0.0 100.00 27.50.0 100.00 27.5

(*) (**)0.0 100.00 27.50.0 100.00 27.50.0 100.00 27.5

R

x x

( ) ( ) ( ) ( )1 1 2 4( ) ( ) ( ) ( ) ( )2 1 2 3 5( ) ( ) ( ) ( )3 2 3 4( ) ( ) ( ) ( ) ( )4 1 3 4 5( ) ( ) ( ) ( )5 2 4 5

100 4

100 4

100 4

100 4

100 4

k k k k

k k k k k

k k k k

k k k k k

k k k k

R x x x

R x x x x

R x x x

R x x x x

R x x x

(*)

( )( 1) ( ) 11 1

( )( 1) ( ) 22 2

( )( 1) ( ) 33 3

( )( 1) ( ) 44 4

( )( 1) ( ) 55 5

4

4

4

4

4

kk k

kk k

kk k

kk k

kk k

Rx x

Rx x

Rx x

Rx x

Rx x

(**)



(1) (1) (2)

27.5 10.00 24.7527.5 17.50 32.3125

(*) (**)27.5 45.00 39.87527.5 17.50 32.312527.5 10.00 24.75

R

x x

( ) ( ) ( ) ( )1 1 2 4( ) ( ) ( ) ( ) ( )2 1 2 3 5( ) ( ) ( ) ( )3 2 3 4( ) ( ) ( ) ( ) ( )4 1 3 4 5( ) ( ) ( ) ( )5 2 4 5

100 4

100 4

100 4

100 4

100 4

k k k k

k k k k k

k k k k

k k k k k

k k k k

R x x x

R x x x x

R x x x

R x x x x

R x x x

(*)

( )( 1) ( ) 11 1

( )( 1) ( ) 22 2

( )( 1) ( ) 33 3

( )( 1) ( ) 44 4

( )( 1) ( ) 55 5

4

4

4

4

4

kk k

kk k

kk k

kk k

kk k

Rx x

Rx x

Rx x

Rx x

Rx x

(**)(2) (2) (3)

24.75 1 25.02532.3125 10.625 35.2344

(*) (**)39.875 5.125 41.284432.3125 10.625 35.2344

24.75 1 25.025

R

x x

(23)

2535.714342.857135.7143

25

x



Problem optimiranja vrijednosti !!!

(13)

2535.714342.857135.7143

25

xSOR metodom (za Gauss-Seidelovu metodu)

0.6 0.8 1 1.2 1.40

10

20

30

40

50

0.6 0.8 1 1.2 1.410

20

30

40

50



Ostale metode

• Nestacionarne metode

- metoda konjugovanih gradijenata (za sisteme sa simetričnom matricom sistema)

- metoda bikonjugovanih gradijenata (za sisteme s asimetričnom matricom sistema)



Interpolacija i aproksimacija funkcija

U mnogim inženjerskim problemima, podaci koji se posmatraju su poznati samo za niz diskretnih taèaka, a ne kao kontinuirana funkcija, tj.

( )i iy f x

•Interpolacija

•Diferenciranje

•Integriranje

Vrste približnih funkcija

•Polinomi

•Trigonometrijske funkcije

•Eksponencijalne funkcije

Željene karakteristike

•Lako određivanje

•Lako izračunavanje

•Lako diferenciranje

•Lako integriranje


x

y

Diskretne tačke

x

y

Diskretne tačke

Pristupi u određivanju približnih funkcija

• Interpolacija – tačno poklapanje

• Aproksimacija – približno poklapanje



Interpolacija polinomima

21 2( ) ... n

n o nP x a a x a x a x

• Weierstrassov aproksimacioni polinom: Ako je funkcija f (x) neprekidna na intervalu [a,b], tada za svako proizvoljno malo > 0 postoji polinom Pn(x), kod kojeg vrijednost n zavisi od vrijednosti , tako da za svako x u intervalu [a,b] vrijedi

| Pn(x) – f (x) | <

• Teorem o jedinstvenosti rješenja: Polinom n-tog stepena koji prolazi kroz tacno n + 1 diskretnih tačaka je jedinstven.



20 1 0 2 0 0

21 1 1 2 1 1

22 1 2 2 2 2

21 2

...

...

............................................

...

no n

no n

no n

nn o n n n n

y a a x a x a x

y a a x a x a x

y a a x a x a x

y a a x a x a x

Problem: Naći interpolacioni polinom n-tog reda koji prolazi kroz n +1 tačaka [xi ,yi] (i = 0,1,...,n)

20 0 0

21 1 1

22 2 2

2

1 ...1 ...

01 ...

1 ...

n

n

n

nn n n

x x xx x x

D x x x

x x x

21 2( ) ... n

n o nP x a a x a x a x

Interpolacija polinomima

Direktna metoda



Primjer

Interpolirati vrijednost za x = 3.44, koristeći linearnu, kvadratnu i kubnu interpolaciju, za podatke

x f(x)

3.35 0.298507

3.40 0.294118

3.50 0.285714

3.60 0.277778

Napomena: Podaci predstavljaju vrijednosti funkcije f (x)=1/x

f (3.44)=1/3.44=0.290698

•Linearni polinom (dva podatka) – yi = a0 + a1xi

1

1

0.294118 3.400.285714 3.50

o

o

a aa a

1( ) 0.579854 0.08404P x x

Interpolacija polinomimaInterpolacija i aproksimacija funkcija


•Kvadratni polinom (tri podatka) – yi = a0 + a1xi + a2xi2

21 2

21 2

21 2

0.298507 3.35 3.35

0.294118 3.40 3.40

0.285714 3.50 3.50

o

o

o

a a a

a a a

a a a

22 ( ) 0.876561 0.256080 0.0249333P x x x

1(3.44) 0.579854 0.08404 3.44 0.290756P

Greška: f (3.44) – P1(3.44) = 0.000058

22 (3.44) 0.876561 0.256080 3.44 0.0249333 3.44 0.290697P

Greška: f (3.44) – P2(3.44) = –0.000001

x f(x)

3.35 0.298507

3.40 0.294118

3.50 0.285714

3.60 0.277778

f (3.44)=1/3.44=0.290698

Interpolacija i aproksimacija funkcijaInterpolacija polinomima


Primjer

•Kubni polinom (četiri podatka) – yi = a0 + a1xi + a2xi2+ a3xi

3

2 31 2 3

2 31 2 3

2 31 2 3

2 31 2 3

0.298507 3.35 3.35 3.35

0.294118 3.40 3.40 3.40

0.285714 3.50 3.50 3.50

0.277778 3.60 3.60 3.60

o

o

o

o

a a a a

a a a a

a a a a

a a a a

2 33 ( ) 1.121066 0.470839 0.0878 0.00613333P x x x x

Greška: f (3.44) – P3(3.44) = 0

2 33 (3.44) 1.121066 0.470839 3.44 0.0878 3.44 0.00613333 3.44 0.290698P

x f(x)

3.35 0.298507

3.40 0.294118

3.50 0.285714

3.60 0.277778

f (3.44)=1/3.44=0.290698



Lagrangeov interpolacioni polinom

1( ) ( ) ( )x b x aP x f a f ba b b a

2( )( ) ( )( ) ( )( )( ) ( ) ( ) ( )( )( ) ( )( ) ( )( )x b x c x a x c x a x bP x f a f b f ca b a c b a b c c a c b

( )( ) ( ) ( )( ) ( )( ) ( ) ( )( )( ) ( ) ( )( ) ( )

( )( ) ( ) ( )( )( ) ( )

nx b x c x k x a x c x kP x f a f ba b a c a k b a b c b k

x a x b x j f kk a k b k j

x f(x)

3.35 0.298507

3.40 0.294118

3.50 0.285714

3.60 0.277778

f (3.44)=1/3.44=0.290698



0 0 1 10

( ) ( ) ( ) ( ) ( ) ... ( ) ( ) ( ) ( )n

n n n k kk

P x L x f x L x f x L x f x L x f x

0 1 1

00 1 1

( ) ( )( ) ( )( )( ) ( )( ) ( )

nk k n i

kik k k k k k n k ii k

x x x x x x x x x xL xx x x x x x x x x x

Primjer

Interpolirati vrijednost za x = 3.44, koristeći linearnu, kvadratnu i kubnu interpolaciju, za podatke

x f(x)

3.35 0.298507

3.40 0.294118

3.50 0.285714

3.60 0.277778


f (3.44)=1/3.44=0.290698



•Linearni polinom (dva podatka) – yi = a0 + a1xi

1

1

3.50 3.40( ) 0.294118 0.2857143.40 3.50 3.50 3.40

( ) 0.579854 0.0840

x xP x

P x x

•Kvadratni polinom (tri podatka) – yi = a0 + a1xi + a2xi2

2

2

( 3.40)( 3.50) ( 3.35)( 3.50)( ) 0.298507 0.294118(3.35 3.40)(3.35 3.50) (3.40 3.35)(3.40 3.50)

( 3.35)( 3.40) 0.285714(3.50 3.35)(3.50 3.40)

( ) 2

=0.876561-0.256080x+0.0249333x

x x x xP x

x x

P x

x f(x)

3.35 0.298507

3.40 0.294118

3.50 0.285714

3.60 0.277778

f (3.44)=1/3.44=0.290698



Newtonovi interpolacioni polinomi

20 0 0 0 0

0

00

0 1 02

0 1 0 2 1 0

1 10 1 0

( )1 2

2..............................................

( 1)

nn k

nk

n n n i

s s s sP x f f f f f

n kx xs x x sh

hf f f

f f f f f f

nf f f

i

0

n

ii

f

xi fi(0) fi

(1) fi(2) fi

(3)

x1 f1(0)

f1(1)

x2 f2(0) f1

(2)

f2(1) f1

(3)

x3 f3(0) f2

(2)

f3(1)

x4 f4(0)

Prvi Newtonov interpolacioni polinom (za diferenciranje unaprijed)

Tabela podijeljenih razlika



Primjer (prvi Newtnonov interpolacioni polinom)

Interpolirati vrijednost za x = 3.44, koristeći linearnu, kvadratnu

i kubnu interpolaciju, za podatke



f (3.44)=1/3.44=0.290698

20 0 2 0 0

0

00

( )1 2

nn k

nk


n kx xs x x sh

h

2 3( 1) ( 1)( 2)(3.44) (3.4) (3.4) (3.4) (3.4)2 3!

s s s s sP f s f f f



f (3.44)=1/3.44=0.290698

2 3( 1) ( 1)( 2)(3.44) (3.4) (3.4) (3.4) (3.4)2 3!

s s s s sP f s f f f

0.4 (0.4 1)(3.44) 0.294118 0.4 ( 0.008404) (0.000468)2

0.4(0.4 1)(0.4 2) ( 0.0004)3!

P



f (3.44)=1/3.44=0.290698

20 0 2 0 0

0( )

1 2

( 1)( 2) [ ( 1)]!

nn k

nk


n k

s s s s s iii

Drugi Newtonov interpolacioni polinom (za diferenciranje unazad)



Primjer (drugi Newtnonov interpolacioni polinom)

Interpolirati vrijednost za x = 3.44, koristeći linearnu, kvadratnu

i kubnu interpolaciju, za podatke

i x0=3.5



0x xsh



Greška interpolacije



Aproksimacija funkcija

x

y(x)Yi(xi)

Diskretne tačke

y(x)Yi

xi

ei

i i ie Y y

Metoda najmanjih kvadrata

min( )S



21 2 ... n

o ny a a x a x a x

2 2 20 1 2 0 1 2

1 1( , , , , ) ( ) ( )

N Nn

n i i i i n ii i

S a a a a e Y a a x a x a x

i i ie Y y

min( )S

20 1 2 0 1 2

1( , , , , ) 2( )( ) 0

Nn k

n i i i n i iik

S S a a a a Y a a x a x a x xa

Aproksimacija funkcijaInterpolacija i aproksimacija funkcija


20 1 2 0 1 2

1( , , , , ) 2( )( ) 0

Nn k

n i i i n i iik




20 1 2 0 1 2

1( , , , , ) 2( )( ) 0

Nn k

n i i i n i iik




Primjer 1.

Za podatke u tabeli potrebno je odrediti aproksimacioni polinom prvog reda koristeći metodu najmanjih kvadrata u obliku:

Cp=a +bT





Primjer 2.

Za podatke u tabeli potrebno je odrediti aproksimacioni polinom drugog reda koristeći metodu najmanjih kvadrata u obliku:

Cp = a + bT + cT 2





Nelinearna aproksimacija

Stepena funkcija

ln( ) ln( ) ln( )

ln( ), ln( ), ln( )

/ln

i

b

b

y ax

y ax

y a b x

Y y A a X x B b

Y A BX



Eksponencijalna funkcija

ln( ) ln( )

ln( ), ln( ),

/ln

i

bx

bx

y a e

y a e

y a bx

Y y A a X x B b

Y A BX




Za podatke u tabeli potrebno je odrediti nelinearni aproksimacioni polinom oblika

y = ae b x

Primjer

/ln

bx

bx

y a e

y a e




ln( ) ln( )

ln( ), ln( ),

/ln

i

bx

bx

y a e

y a e

y a bx

Y y A a X x B b

Y A BX




1.09861

ln( ), ln( ),

30.69315

i

A

Y y A a X x B b

a e eb B

0.69315 0.693153 3 ( ) 3 2

3 2

bx x x x

x

y ae e e

y




Numeričko diferenciranje i integriranje funkcijaNumeričko diferenciranje

•Diferenciranje približnim funkcijama

•Formule za diferenciranje

Diferenciranje približnim funkcijama


Numeričko diferenciranjeNumeričko diferenciranje i integriranje funkcija


Za podatke u tabeli potrebno je odrediti vrijednost prvog izvoda u tački x = 3.5

Primjer


f ‘ (3.5)= -1/3.52 = -0.081633...



Formule za diferenciranje

x

f (x)

x x1 x2

f (xi-h) f (xi)

A

f (xi+h)

B

C t

tc

t-

t+





Za podatke u tabeli potrebno je odrediti vrijednost prvog izvoda u tački x = 3.5

Primjer


f ‘ (3.5)= -1/3.52 = -0.081633...

Diferenciranje unaprijed

Diferenciranje unazad



Centralno diferenciranje

f ‘ (3.44)= -1/3.442 = -0.081633...Numeričko diferenciranjeNumeričko diferenciranje i integriranje funkcija


•Integriranje približnim funkcijama

•Newton-Cotesove formule

•Gaussove kvadraturne formule

Integriranje približnim funkcijama x

f (x)

a b

b

a

f(x)dxI

Numeričko integriranjeNumeričko diferenciranje i integriranje funkcija


Izračunati vrijednost integrala:

Primjer

koristeći podatke iz tabele.





Newton-Cotesove formule



Newton-Cotesove formule – trapezno pravilo



Newton-Cotesove formule – trapezno pravilo




Primjer – trapezno pravilo


Za jedan interval:



Za dva intervala:

Za četiri intervala:



Newton-Cotesove formule – Simpsonovo 1/3 pravilo




Primjer


Primjer – Simpsonovo 1/3 pravilo

Za jedan interval:



Za dva intervala:



Gaussove kvadraturne formule

n = 2



1 1

1 1

2 2

( ) ( ) [ ]2

b

a

x mt cb a b am c

b aI f x dx f mt c m dt F t dt



1 1( )2 3 3

b

a

b aI f x dx F F

1 1

1 1( ) ( ) [ ]

2b

a

b aI f x dx f mt c m dt F t dt





Primjer – Gaussove kvadraturne formule

3.52 2

10.4 3.5 ( )0.4 3.5

=0.4

x mt cb a b am c

x t F tt

1 1 1( ) ( )2 3 3

b

a

b aI f x dx F F f xx



1

1

1 1 1( )2 3 3

0.22957092

b

a

b aI dx F t dt F Fx

I

Za dva intervala:



3.32 2

10.2 3.3 ( )0.2 3.3

=0.2

b a b am c

x t F tt



3.72 2

10.2 3.7 ( )0.2 3.7

=0.2

b a b am c

x t F tt



Rješavanje običnih diferencijalnih jednačinaO običnim diferencijalnim jednačinama (ODJ)

ODJ daju zavisnost između funkcije s jednom nezavisnom promjenljivom i njenih totalnih izvoda u odnosu na tu nezavisnu promjenljivu

• ODJ s početnim vrijednostima – Cauchijev problem

• ODJ s graničnim vrijednostima


Podjela fizičkih problema

• problemi širenja (ODJ s početnim vrijednostima)

• problemi ravnoteže (ODJ s graničnim vrijednostima)

• problemi sopstvenih vrijednosti (rješenje postoji samo za određene parametre)

O običnim diferencijalnim jednačinama (ODJ)Rješavanje običnih diferencijalnih jednačina


• jednokoračne metode – koriste podatke samo jedne tačke (koraka)

• višekoračne metode – koriste podatke više tačaka (koraka)

• ekstrapolacione metode

O običnim diferencijalnim jednačinama (ODJ)Rješavanje običnih diferencijalnih jednačina


Rješavanje problema s početnim vrijednostima

Taylorova metoda

Rješavanje običnih diferencijalnih jednačina


Primjer – Taylorova metoda

Prenos toplote zračenjem s tijela mase m u okolinu se može opisati jednačinom

Riješiti datu jednačinu za t = 0 do 10 s ako je = 410-12, Ta = 250 K, T (0) = 2500 K

Tačno rješenje

Rješavanje problema s početnim vrijednostimaRješavanje običnih diferencijalnih jednačina








Metoda konačnih razlika

Transformacija problema rješavanja diferencijalnih jednačina na algebarski problem.

1. Neprekidna oblast (domena rješavanja) se prekrije numeričkom mrežom

2. Tačni izvodi diferencijalne jednačine se aproksimiraju algebarskim aproksimacijama konačnih razlika

3. Algebarske aproksimacije konačnih razlika se smjenom uvrste u diferencijalnu jednačinu

4. Rješava se rezultujuća jednačina konačnih razlika



Eulerova metoda

• eksplicitna

• implicitna

Eksplicitna Eulerova metoda



Karakteristike eksplicitna Eulerova metode

• Metoda je eksplicitna, tj. funkcija f (x) ne zavisi od yn+1

• Potrebna je jedna čvorna tačka

• Samo jedno izračunavanje izvoda funkcije po iteraciji

• Lokalna greška je drugog, a globalna prvog reda

• Metoda je uslovno stabilna, tj. stabilnost zavisi od koraka h



Primjer – Eulerova eksplicitna metoda







Implicitna Eulerova metoda

Karakteristike implicitne Eulerova metode

• Metoda je implicitna, tj. funkcija f (x) zavisi od yn+1

• Potrebna je jedna čvorna tačka

• Samo jedno izračunavanje izvoda funkcije po iteraciji

• Lokalna greška je drugog, a globalna prvog reda

• Metoda je stabilna, tj. stabilnost ne zavisi od koraka h



Primjer – Eulerova implicitna metoda







O stabilnosti Eulerovih metoda

• eksplicitna

• implicitna





Runge-Kutta metode

Runge-Kutta metode drugog reda



Modifikovana Eulerova metoda

C1=C2=1/2 = =1



Primjer – modifikovana Eulerova metoda







Modifikovana metoda srednje vrijednosti

C1= 0, C2=1 = =1/2



Primjer – modifikovana metoda srednje vrijednosti









Runge-Kutta metode četvrtog reda (standardna)



• Aproksimirane jednačine su eksplicitne i zahtijevaju četiri izračunavanja izvoda funkcije u jednom koraku (iteraciji)

• Jednačine su konzistentne, s lokalnom greškom petog i globalnom četvrtog reda

• Jednačine su uslovno stabilne (npr. za y’+ y = 0,t 2.785)

• S obzirom da su jednačine konzistentne i uslovno stabilne, one su i konvergentne.

Karakteristike Runge-Kutta metode četvrtog reda



Primjer – Runge-Kutta 4. reda











Ostale metode

• višekoračne (Adamsova i njene varijacije, ...)

• ekstrapolacione



Rješavanje ODJ višeg reda s početnim vrijednostimaRješavanje običnih diferencijalnih jednačina


Primjer

Diferencijalnu jednačinu drugog reda koja opisuje vertikalni let rakete svesti na sistem dvije diferencijalne jednačine prvog reda.





Primjer

Riješiti diferencijalnu jednačinu drugog reda koja opisuje vertikalni let rakete.

Uzeti da je T = 10000 N, m 0= 100 kg, g = 9.8 m/s2, m =5 kg/s, t = 1 s.

Rješavanje sistema ODJ s početnim vrijednostimaRješavanje običnih diferencijalnih jednačina












Rješavanje problema s graničnim vrijednostima

Granični uslovi

• Dirichlet – y (x) = y0

• Neumann – y ‘(x) = y’0

• Mješoviti

Rješavanje običnih diferencijalnih jednačina


• Metoda gađanja

• Metoda ravnoteže

• Rezleigh-Ritz metoda

• metoda kolokacija

• Galerkinova metoda

• metoda konačnih elemenata

• metoda konačnih volumena

• ......................

Metode rješavanja

Rješavanje problema s graničnim vrijednostimaRješavanje običnih diferencijalnih jednačina


Metoda gađanja

1. Diferencijalna jednačina s graničnim uslovima se transformiše na sistem diferencijalnih jednačina prvog reda

2. Granični uslovi na jednoj strani se koriste kao početni uslovi

3. Pretpostavi se dodatni početni uslov

4. Riješi se sistem, a rješenje na drugoj granici se uporedi s drugim graničnim uslovom

5. Postupak 1-4 se ponavlja dok se ne dobije traženo rješenje



Primjer – metoda gađanja

Stacionarni problem jednodimenzionalnog prenosa toplote sastoji se od toplotne difuzije, odnosno kondukcije, uzduž šipke konstantnog poprečnog presjeka i toplotne konvekcije na okolinu. Može se pokazati da se ovaj problem opisuje sljedećom običnom diferencijalnom jednačinom drugog reda s graničnim vrijednostima:

Naći raspodjelu temperature u šipki, ako je zadato:L = 0.01 m, T1 = 0 °C, T2 = 100 °C, = 400 m-1, Ta = 0 °C, x = 0.0025 m



u1 (0) = T ’(0) = 1000 °C/m u2 (0) = T ’(0) = 2000 °C/m



u1 (0) = T ’(0) = 1487.4459 °C/m



Primjer – metoda gađanja

Stacionarni problem jednodimenzionalnog prenosa toplote sastoji se od toplotne difuzije, odnosno kondukcije, uzduž šipke s konstantnog poprečnog presjeka i toplotne konvekcije na okolinu. Može se pokazati da se ovaj problem opisuje sljedećom običnom diferencijalnom jednačinom drugog reda s graničnim vrijednostima:

Naći raspodjelu temperature u šipki, ako je zadato:L = 0.01 m, T1 = 100 °C, T’ (L) = 0, = 400 m-1, Ta = 0 °C, x = 0.0025 m



u1 (0) = T ’(0) = -40000 °C/m u2 (0) = T ’(0) = -35000 °C/m



u1 (0) = T ’(0) = -39970.6068 °C/m



Metoda ravnoteže

• Neprekidna oblast interesa (domena) se prekrije numeričkom mrežom, tj. podijeli na određeni broj pod-domena.

• Tačni izvodi diferencijalne jednačine s graničnim vrijednostima se aproksimiraju algebarskim aproksimacijama konačnih razlika.

• Algebarske aproksimacije konačnih razlika se smjenom uvrste u diferencijalnu jednačinu kako bi se dobila algebarska jednačina konačnih razlika.

• Rješava se rezultujuća jednačina konačnih razlika.



Primjer 1. – metoda ravnoteže


Naći raspodjelu temperature u šipki, ako je zadato:L = 0.01 m, T1 = 0 °C, T2 = 100 °C, = 400 m-1, Ta = 0 °C, x = 0.0025 m







Primjer 2. – metoda ravnoteže


Naći raspodjelu temperature u šipki, ako je zadato:L = 0.01 m, T1 = 100 °C, T ’ (L) = 0, = 400 m-1, Ta = 0 °C, x = 0.0025 m

Za unutrašnje tačke



Za graničnu čvornu tačku 5





O rješavanju parcijalnih diferencijalnih jednačina

• Eliptičke – Laplaceova jednačina; problemi ravnoteže

• Hiperboličke – talasna jednačina, problemi vibracija; nestacionarni problemi

• Paraboličke – nestacionarna toplotna kondukcija

Podjela PDJ drugog reda

Metode za numeričko rješavanje PDJ

• Metoda konačnih razlika

• Metoda konalnih volumena

• Metoda konačnih elemenata


S R E T N O !!!

Documents

Aleksandar Karač Denis Spahić - ptf.unze.ba