Návrat na detail prednášky / Stiahnuť prednášku / Technická Univerzita Košice / Fakulta Elektrotechniky a Informatiky / Numericka matematika

vypracovane_otazkynm.doc (vypracovane_otazkynm.doc)

NUMERIKA

1.Chyby pri numerických výpočtoch.

Nech x je presná hodnota a xˇ približná hodnota čísla, potom chyba E približnej hodnoty xˇ je E = x-xˇ. Ak nepoznáme presnú hod. x, nevieme vypočítat E.

Absolutnou chybou približného čísla xˇ rozumieme cis. |E|=|x-xˇ|.

Každé nezáporne číslo (xˇ), pre kt. platí  |x-xˇ| ≤ (xˇ), naz. Odhad absolútnej chyby, xˇ-(xˇ)≤ x ≤ xˇ+(xˇ) zapisujeme ako xi = xiˇ+-(xiˇ).

Relativnou chybou priblizneho cis. x nazývame nezáporné číslo R=|E| / |x|;

Teoretickym odhadom relativnej ch. približného čísla x rozumieme každé nezáporné číslo (xˇ), pre kt. plati R≤(xˇ); V prípade úpravy presného čísla x zaokruhľovaním na n desatinných miest je (xˇ) = 0,5.10-k.          

Ak poznáme chybu aproximácie čísla x číslom xˇ hovoríme že k-te desatinné miesto aproximácie x je platné, ak |x-xˇ|≤0,5.10-k.

CHYBA PRI VÝPOČTE HODNOT. Nech funkcia f je diferencovateľná v oblsti G, x = (x1,x2..xn); xˇ=(xˇ1,xˇ2,...,xˇn) a (xˇi)≥|xi-xˇi|, pre i=1,2...n;

Odhad absolútnej chyby funkčnej hodnoty (uˇ), kde uˇ= f(xˇ),za predpokladu že poznáme horné ohraničenia parciálnych derivácií |f(x)/ xi|≤ki, pre každé x z G, i=1,2…n môžeme urobiť pomocou lagrangeovej vety :     |u-uˇ| = |f(x1,x2..xn)-f(xˇ1,xˇ2..xˇn)| ≤ ni=1 ki (xˇi) = (uˇ).

Pre odhad relativnej chyby funkčnej hodnoty dostávame (uˇ) = (uˇ) / |u| =1/|u|  ki (xˇi)

2.Riešenie rovnice  metódou bisekcie. Intervaly separácie, grafický odhad koreňov.

f(x) = 0, kde f je reálna funkcia reálnej premennej číslo , pre kt. f() = 0, nazývame koreňom rovnice f(x)=0. Ak je funkcia f je polynóm, naz. rovnicu f(x)=0 alegebraickou rovnicou.

Ak f() = f‘()=...= f (k-1)  = 0 a f k() ≠ 0, potom hovoríme, že  je k-nasob. koreňom rovnice.

Postup:1.určíme interval (a,b), v kt. ležia jej reálne korene

            2.určíme počet koreňov ležiacich v (a,b)

            3.nájdeme intervaly (ai,bi) také, že f(i) = 0 (separujeme korene) pričom i(ai,bi) a pre každé      

                     x(ai,bi), f(x)≠0 pre x≠i

            4. použijeme približné metódy na výpočet koreňov

            5. urobíme odhad absol.chyby vypočítaného koreňa  

Veta: Neh funkcia f:RA->R je spojitá na <a,b> A a plati f(a).f(b)<0. Potom exist. aspoň jedno číslo c(a,b) také že f(c)=0 ; rovnica f(x)=0 môže mať v (a,b) nulový bod aj v prípade, keď f(a)f(b)>0;;

Veta na odhad absolútnej chyby: Nech  je presná hodnota a xk približná hodnota koreňa rovnice. Nech obe tieto hodnoty ležia v (a,b) a |f‘(x)| ≥ m>0 pre všetky x<a,b>, potom platí odhad |- xk| ≤ |f(xk) /m|.

Grafické riešenie rovníc - reálne korene rov. f(x)=0 môžeme približne určiť graficky ako x-ove súradnice priesečníka grafu funkcie y = f(x) s osou x. Ak rov. f(x)=0 nahradíme ekvivalenou rov. g(x)=h(x), kde g(x) a h(x) su jednoduchšie funkcie ako je f(x), potom približné hodnoty real. koreňov rov. f(x) = 0 nájdeme ako x-ove súradnice priesečníkov grafov funkcií y = g(x) a y = h(x)

BISEKCIA- predpokladáme, že f(x)=0 má práve jeden koreň x v (a,b). Definujeme postupnosť intervalov <an,bn>, n=1,2...predpisom

1.<a1,b1> = <a,b>

2.nech je def. <an,bn>, pričom f(an)f(bn)<0. Nech cn =( an + bn)/2

3. - Ak je f(cn) = 0,potom je cn koreňom rov.

   - Ak je f(cn)≠0 a f(an)f(cn)<0 položíme an+1=an, bn+1=cn,

   - Ak platí opačná nerovnosť, t.j. f(an).f(cn)>0 položíme an+1=cn, bn+1=bn.

   - Ak má postup. (cn) konečný počet členov, je posledný člen  koreňom rov. f(x)=0;

    -Ak je postup. (cn) nekonečná, potom má n->lim cn=.

Pre odhad abs.chyby korena  platí |cn-|<(b-a)/2n+1.

Ak máme vypočítať koreň  s nepresnosťou >0, ukončíme proces delenia intervalu, ak |bn-an|< 2 a za aproximovaný koreň  vezmeme číslo ( an + bn)/2

3.Riešenie rovnice  Newtonovou metódou. Podmienky konvergencie a odhad chyby

NEWTON-túto metódu môžeme použiť pri f(x)=0, ak funkcia je 2x diferencovateľná a funkcie f‘,f‘‘ v <a,b> nemenia znamienko, pričom f(a).f(b)<0.

Nech xn je aproximácia koreňa  rovnice f(x)=0 a f(xn).f‘‘(xn)>0, potom koreň  = n->lim xn,

pričom xn+1 = xn+hn, kde hn určíme nasledovným spôsobom:

Použitím Taylorovej vety dostávame f(x) = f(xn) + f ‘(xn)/1! (x- xn) +f‘‘(xn)/2! (x- xn)2, kde c leží medzi bodmi x a xn. Pretože xn je dobrá aproximácia kor. , dalsiu aproximáciu  xn+1 kor.  dostaneme riešením rovnice 0=f(xn)+ f ‘(xn) / 1!(xn+1- xn), t.j. 0 = f(xn) + f ‘(xn).hn a teda hn= -f(xn)/ f ‘(xn), to znamená že na výpočet členov postupnosti n=1(xn) dostávame rekuretný vzorec xn+1= xn-f(xn)/ f ‘(xn), n=1,2...

4. Banachova veta o pevnom bode. Konvergencia iteračnej postupnosti a odhad chyby.

Riešenie rovnice T (p0) = p, kde T: P-> P, Pje úplný normovaný LP

Pevný bod: bod p*  P, pre kt. platí T (p*) = p*

Predpokladáme, že T: P  A -> P. p0  A – začiatočná hodnota aproximácie, postupne nájdeme hodnoty

p1 = T (p0), p2 = T (p1)....pn+1 = T(pn), ....., ak postupnosť (pn) n=1 konverguje k p* a T je spojité na A tak z pn+1 = T(pn), n=0,1... pre n->  dostaneme T (p*) = p*

Kontraktívne zobrazenie: Nech (P,ρ) je metrický priestor. Hovoríme, že zobrazenie  T: P-> P je kontraktívne na množine A   P, ak exist. λ  (0,1) také, že p, ρ  A => ρ(T (p), T(ρ)) ≤ λ ρ(p, ρ)

Banachova veta o pevnom bode: Nech (P,ρ) je úplný metrický priestor a nech T: P-> P je na P kontraktívne. Potom exist. práve jeden pevný bod p*  P vzorcom pn+1 = T(pn), potom n->  lim pn = p*

Ak T je kontraktívne s λ  (0,1), platí odhad ρ(p*, pn) ≤ λn . ρ(p0, p1) / (1- λ)

5.Riešenie rovnice   iteračnou metódou. Postačujúce podmienky konvergencie a odhad chyby.

ITERACIA-tato metoda je založená na konštrukcii postupnosti iteracií. Hľadá sa koreň  rovnice f(x)=0, kt. leží v <a,b>. Funkcia f(x) = 0 má tvar x = (x), aby :<a,b>->R bola kontraktívna funkcia na <a,b> t.j.

((x)(y))=|(x)- (y)| ≤ |x-y|=(x,y); x,y<a,b> a zároveň (x),(x)<a,b>.

Nech funkcia je diferenciálna,  potom podľa Lagrangeovej  vety o strednej hodnote exist.  (a,b) také že (x)-(y)= ‘()(x-y). Ak exis. kladné číslo M také, že M = sup|‘(x)| pre x<a,b>, |(x)-(y)|<=M|x-y| .Ak M<1,tak je koeficient kontraktívnosti, =M.

Veta: Nech :<a,b>-> <a,b> je spojitá funkcia na <a,b>. Nech exist. spojitá derivácia ‘v (a,b) a číslo ,0≤ <1 také, že |‘(x)| ≤   pre ľubovoľné x(a,b). Potom iteračný proces xi+1=(xi), i=1,2.. konverguje k jedinému koreňu  rovnice x=(x) a platia odhady |xn-|<=n/1- |x1-x0|, n=1,2.... ;;|xn-|<=/1- |xn-xn-1|, n=1,2...

Ak koeficient konktrakt. (0;0.5) potom dostávame |xn-|≤ /1- |xn-xn-1|≤ |xn-xn-1|. Teda iteračný proces možno ukončiť, ak abs. hodnota z rozdielu po sebe idúcich aproximácií je menšia než presnosť, s akou máme vypočítať hodnotu koreňa  rovnice x=(x).

6.Rieš. sústav lineár. algebrických rovníc Gaussovou eliminačnou metódou, s výberom hlavného prvku. Riešenie sústav lineárnych rovníc v zmysle metódy najmenších štvorcov.

GAUSS – a11x1+ a12x2+ a13x3+a14x4= a15,.......,a41x1+ a42x2+ a43x3+a44x4= a45. Ak a11≠0, aii≠0.

V 1.časti zapíšeme koeficienty, ďalej vypočítame ki =j=15aij, i=1,2,3,4,  mi1= ai1/a11, i=2,3,4.

V 2.časti riadok 2(1) dostaneme tak, že k i-temu riadku v prvej časti pripočítame mi1 násobok prvého riadku,. a(1)i1= ai1+mi1a11= a11- a11=0 a ostatné prvky sú a(1)ij=aij+mi1a1j, i=2,3,4, j=2,3,4

Podobne k(1)i=ki+mi1k1, i=2,3,4. ak nenastala chyba pri výpočte tak ui(1)= Ki(1), pričom ui(1)= j=25aij(1), i=2,3,4.

Ak uk, potom je potrebné prekontrolovať správnosť výpočtov v tejto časti v i-tom riadku. Ak sme sa dopustili chyby so zaokrúhľovania, zistíme rozdiel u-k. Podobne vyplníme tretiu a štvrtú časť s príslušnou kontrolou. Namiesto pôvodnej sústavy riešime:a11x1+a12x2+a13x3+a14x4=a15 ,

                                                             a22x2 + a23x3 + a24x4 =a25 ,

                                                                         a33x3 + a34x4 =a35 ,

                                                                                     a44x4 =a45 .

Odkiaľ postupne vypočítame x´4, x´3, x´2 ,x´1 . Predpoklad nenulovosti koeficientov a11,aii(k) (k=1,2,3;i=2,3,4) môžeme u regurálnej matice sústavy vždy splniť, pretože v nutnom prípade zameníme navzájom rovnice. Získané riešenie  x´=(x´1,x´2,x´3,x´4) nemusí byť riešením danej sústavy.

Nech x=(x1,x2,x3,x4) je presné riešenie sústavy, potom x = x´+. Vektor   - spresnenie získaného riešenia  x´ môžeme nájsť takto : Dosadením x´+  za x  do sústavy Ax=b dostávame : A(x´+)=b    A=b-Ax´ . Výber hlavného prvku : metóda výberu hlavného prvku spočíva v nasledujúcom postupe. V časti I..z koeficientov pri neznámych  xi zvolíme najväčší v absolútnej hodnote za tzv. Hlavný prvok.

MNS – budeme predpokladať, že reál. funkcia je definovaná v n+1 bodoch x0, x1, x2...xn. Nech namerané tabuľkové hodn. (xi, yi) sú vyjadrením závislosti x a y. Úlohou aproximácie je nájsť v triede τ takú funkciu φ τ, kt. je najbližšie k funkcii v zmysle aporoximácií min i=0n(φ(xi) - yi)2

Sústava normálnych rovníc pre výpočet koeficientov: a0(n+1) + a1 i=0n xi = i=0nyi

                                                                                     a0 i=0n xi + a1 i=0n xi2 = i=0n xiyi

7.Riešenie sústav lineárnych algebrických rovníc metódou LU rozkladu matice sústavy.

LU ROZKLAD - nech A(aij) i,j=1,2..,n n je štvorcová matica

A=LU, kde L je matica, v kt. na hl.diagonále sú jednotky a pod nimi L21, L31,.. Ln1,

U je mat.(vyzerá ako po úprave gausovky).

Vynásobením matíc LU a porovnaním s maticou A dostávame n2 podmienok na výpočet koeficientov aij, lijs. Postupujeme tak, že vypočítame pvky 1.riadku matice U, potom 1.stĺpec matice L, ďalej 2.riadok matice U a 2. stĺpec matice L atd.

LU rozklad matice A. Dostavame LUx = b, položíme Ux = y, potom Ly = b. Dostávame tak trojuholníkovú sústavu Ly = b, z ktorej určíme vektor y. Ten použijeme ako pravú stranu sústavy Ux = y, z kt. určíme vektor x. Táto sústava je tiež trojuholníková.

8.Riešenie sústav lineárnych algebrických rovníc iteračnými metódami. Podmienky konvergencie iteračných metód.

JACOBIOVA - nech koeficienty aii≠0, i=1,2,..,n, prepíšeme sústavu Ax = b na tvar x = x+ = (x) nasledujúcim spôsobom.

Nech D = diagonála (a11, a22,.. ann),  (A-D+D)x = b, odtiaľ dostávame x = D-1(D-A)x+ D-1b,teda = D-1(D-A),  = D-1b. Riešením  rovnice je pevný bod zobrazenia  : L*-> L*.  Ak pre xL*, yL*, (x,y)=||x-y||, potom zobrazenie  bude kontraktívne ak:

((x),(y)) ≤ (x,y), (0,1) teda ((x),(y))=||(x+)-(y+)|| ≤ ||||.||x-y||≤ ||||(x,y), to znamená, že zobrazenie =x+ bude kontrakívne, ak ||||<1. Pre postupnosť aproximácií x(k+1)=x(k)+ platí :

VETA : Nech ||||<1.Potom sústava rovníc x=x+ má prave 1.riešenie xˇ, pre kt. platí

a)iteračný proces x(k+1)=x(k)+ konverguje ku xˇ nezávisle od voľby začiatočnej aproximácie x(0)

b) ak x(k) je k-ta aproximácia riešenia, potom ||xˇ-x(k)|| ≤ ||||/(1-||||)*||x(k)- x(k-1)||, k=1,2...

GAUSS-SEIDLO- x1(k+1)=11x1(k)+ 12x2(k)+...+1nxn(k)+1............ xn(k+1)=n1x1(k+1)+ n2x2(k)+... ...+nnxn(k)+n Ak ii=0 pre i=1,2,..n potom dostaneme Gauss-Seidlovu metodu. Nech matica M je matica, kt. dostaneme z matice A, ak vsetky prvky hlavnej diagonále a nad hlavnou diagonálou nahradíme nulami. Potom vytvorime z matice A hornú trojuholmékovú maticu N. Potom A = M+D+N a po dosadení do sústavy Ax = b dostávame (M+D+N)x=b. Za predpokladu, že aii0,i=1,2..n a existuje (M+D)-1, je x = -(M+D)D-1Nx+(M+D)-1b. Ak si označíme = -(M+D)-1N, potom postačújuca podmienka konvergencie daného procesu je ||||<1.

9. Riešenie sústavy nelineárnych rovníc Newtonovou metódou. Grafický odhad štartovacieho bodu.

NELINEAR NEWTON-máme sústavu rovníc, f(x)=0, predpokladáme že x(k) je aproximácia riešenia x rovnice f(x)=0. Ak pre každé xD, je determinant (f ‘(x))≠0, má daná sústava rovníc jediné riešenie. Ďalšiu aproximáciu môžeme  vypočítať podľa vzorca x(k+1)=x(k)-[f‘(x(k))]-1f(x(k))= x(k)+x(k).

Je teda metoda,kde g(x)=x-[f‘(x(k))]-1f(x).

Postup riešenia g(x) pre n=2, f1(x1,x2) = 0, f2(x1,x2) = 0.Nech x(k)= (x1(k) ,x2(k)). Použitím Taylorovho  vzorca, dostaneme fi(x1(k+1),x2(k+1))= fi(x1(k),x2(k))+  fi(x1(k),x2(k))/ x1*( x1(k+1)-x1(k))+  fi(x1(k),x2(k))/ x2*( x2(k+1)-x2(k))+Ri, kde i=1,2. Ďalšie aproximácie dostaneme riešením sústavy lineárnych rovníc

 f1(x(k))/ x1*( x1(k+1)-x1(k))+  f1(x(k))/ x2*( x2(k+1)-x2(k))= -f1(x(k))

 f2(x(k))/ x1*( x1(k+1)-x1(k))+  f2(x(k))/ x2*( x2(k+1)-x2(k))= -f2(x(k)),

odkiaľ x1(k+1)= x1(k)-W-1| f1x(k)   f1x(k)/ x2 | (ešte v determinante je |f1x(k)  f1x(k)/ x2|),

          x2(k+1)= x2(k)-W-1|f1x(k)/ x1   f1x(k)|  (ešte v determinante je  |f2x(k)/ x1   f2x(k)|)

kde W=|f1x(k)/ x1 f1x(k)/ x2 | a  |f2x(k)/ x1  f2x(k)/ x2|

V prípade n>2 je vyhodnejšie pri riešení sústav lineárnych algebraických rovníc v Newtonovej metóde namiesto Cramerovho pravidla použit eliminačnú metódu. Vektor x(k) dostaneme riešením sústavy f ‘(x(k)x(k)= -f(x(k))

10.Iteračná metóda pre riešenie sústavy nelineárnych rovníc, podmienky konvergencie.

Interačná metóda- nelineárna - sústava f(x)=0, kde f=(f1,f2,...,fn)T je vektorová funkcia n nezávislých premenných x1,x2,..,xn, upravíme na ekvivaletnú sústavu tvaru x=g(x), kde g=(g1,g2,...,gn)T. Vektorový zápis zodpovedá zápisu v zložkách xi= gi(x1,x2,...,xn),i=1,2...n;

Metóda je založená na konštrukcii postupnosti (x(k)), kde x(0)DG a ďalšie členy postupnosti vypočítame podľa x(k+1)= g(x(k)),k=1,2.., t.j. x1(k+1)= g1(x1(k),x2(k)... xn(k)),

                                       x2(k+1)= g2(x1(k),x2(k).... xn(k)),

                                       x2(k+1)= g2(x1(k),x2(k).... xn(k))........

                                       xn(k+1)= gn(x1(k),x2(k).... xn(k)).

Nech množina D je konvexná t.j. pre ľubovoľné x,yD patria do D všetky vektory x+t(y-z), t(0,1).  Označenie g‘ tzv.JACOBIOvu maticu zobrazenia g, potom g‘(x)=(.....g1(x)/ g1 ........) (matica), nasledujúce normy matice a vektora pre: A=(aij), i,j=1,2,...n je ||A||=max j=1n|aij|, x=(xi), i=1,2,..n je ||x||=max|xi| a plati

VETA: Nech DEn je neprázdna uzavretá, ohraničená a konvexná množina. Nech vektorová funkcia g:D->D a gi: D->D,pre i=1,2...n majú v D spojité parciálne derivácie 1.rádu podľa všetkých premenných x1,x2,...,xn. Nech ďalej exist. konštanta q, 0≤q<1 taká, že ||g‘(x)|| ≤q,xD. Potom sústava rovníc má práve jedno riešenie xˇD a pri ľubovoľnej voľbe x(0)D postupnosť  aproximácií (x(k)), získaná pomocou vzťahov x(k+1)=g(x(k)), konverguje k presnému riešeniu xˇ sústavy t.j. k->lim x(k)= xˇ a platia odhady ||xˇ- x(k)|| ≤q/(1-q)*||x(k)- x(k-1)||, k=1,2... ,

                                                                                                        ||xˇ- x(k)|| ≤qk/(1-q)*||x(1)- x(0)||, k=1,2..

11.Aproximácia funkcie pomocou Lagrangeovho interpolačného polynómu (tiež pre rovnaký krok). Odhad chyby aproximácie. Newtonov interpolačný polynóm pre tabuľku s nerovnakým krokom a Newtonove iterpolačné polynómy  pre tabuľku s rovnakým krokom.

Aproximácia, t.j náhrada funkcie f: A->R pomocou funkcie g: AB->R. Funkciu g zvolíme podľa funkcie f. Funkcia f môže byť zadaná napríklad funkčnýni hodnotami v n+1 bodoch alebo je príliš zložitá a na riešenie danej úlohy nevhodná.

Funkciu g hľadáme v tvare g = i=0ncigi. Za funkciu gi, i=0,1,...n berieme vačšinou funkcie 1,x, x2,x3..... alebo 1,cos(x),sin(x),cos(2x)....Koeficient ci určujeme na základe nejakého vhodného kritéria. Podľa voľby kritéria dostávame určitý typ aproximácie

INTERPOLACIA - Nech f. f je zadaná svojími funkčnými hodnotami v n+1 bodoch, t.j. tabuľkou hodnôt x|f(x),x0|f(x0),..... xn|f(xn).

Základnou úlohou interpolácie pomocou polynómov je nájsť polynóm P najmenšieho možného stupňa tak, aby pre i=0,1...n platilo f(j)(xi)= P(j)(xi), j=0,1,... xi-1. Zaoberá sa aproximáciami, kde ri=1 pre i=0,1..n, t.j hladáme polynóm P najviac n-tého stupňa s vlastnosťami f(xi)= P(xi), i=0,1..n.

LAGRANGEOV INTERPOLAČNÝ POLYNÓM - Funkciu f, zadanú v n+1, bodoch aproximujeme pomocou polynómu tvaru Ln(x)= i=0ngi(x).f(xi), tak aby Ln(xi)=f(xi), i=0,1,...n. Body xi nazývame uzlovými bodmi (graf). Funkciu gi zvolíme tak, aby spĺňali podmienku gi(xj)={  a)1, pre i=j;

                                                                                         b)0, pre i≠j.

Polynómy gi nadobúdajú nulové hodnoty v bodoch x0,x1,x2,....xi-1, xi+1,...,xn a preto ich môžeme zapísať v tvare gi(x)= Ci(x-x0)(x-x1)...(x-xi-1) (x-xi+1)... (x-xn), kde Ci je reálna konštanta. Ci vypočítame z podmienky gi(xi)=1, t.j. gi(x)=((x-x0) (x-x1)..... (x-xi-1) (x-xi+1)... (x-xn)) / ((xi-x0) (xi-x1)..... (xi-xi-1) (xi-xi+1)... (xi-xn)), i=0,1..n. Potom polynóm Ln(x) má tvar Ln(x)=i=0n((x-x0)..... (x-xi-1) (x-xi+1)... (x-xn)) / ((xi-x0)..... (xi-xi-1) (xi-xi+1)... (xi-xn))*f(xi), čo sa dá zapísať ako Ln(x)=i=0n i=0,ij n(x- xj)/(xi-xj)*f(xi).

CHYBA aproximacie – Nech x0<x1<...<xn sú uzlové body interpolácie v intervale I a funkcia f:I->R má v každom bode intervalu I deriváciu n+1-ho rádu. Odhad rozdielu f(x)- Ln(x), x(xo,xn), kde Ln je Lagrang. interpol. polynóm, odpovedajúci funkcii f a uzlovým bodom xi, i=0,1,...n;;

Rn(x)=f(x)- Ln(x), n+1(x)= i=0 n(x-xi). Z vlastností polynómu Rn(xi)=f(xi)-Ln(xi)=0, i=0,1,..n.

Určme K(x) tak, aby Rn(x)=K(x)n+1(x). Nech funkcia F:I->R je zadaná vzťahom F(t)=f(t)- Ln(t)- K(x)n+1(t). Polynóm Ln(t) je najviac n-tého stupňa, teda Ln(n+1)(t)=0. Polynóm n+1(t) je n+1-ho stupňa s koeficientom 1 pri najvyššej mocnine, teda n(n+1)(t)=(n+1)! a ďalej dostávame F(n+1)(t)=f(n+1)(t)-K(x)(n+1)! Pretože F(xi)=0, i=0,1...,n exist. taký bod (x0,xn),že F(n+1)()=0,t.j. 0= f(n+1)()-K(x)(n+1)!, odtiaľ K(x)= f(n+1)()/(n+1)!

Potom f(x)-Ln(x)= f(n+1)()/(n+1)!* n+1(x). Nech f(n+1)(x) je ohraničená na I, t.j. exit. konštanta Mn+1R taká, že Mn+1=xImax|f(n+1)(x)|. Potom odhadnúť veľkosť absolútnej chyby, ak nahradíme funkčnú hodnotu f v bode x hodnotou interpol. pol. V tom istom bode pre ľubovoľné x(x0,xn) takto:|f(x)-Ln(x)| ≤Mn+1/(n+1)!*|n+1(x)|. Lang .interpol. polynom s rovnakým krokom - ak exist.hR také, že xi= x0+ih, i=1,2..n,hovoríme, že funkcia je zadaná pomocou tabuľky s rovnakým krokom alebo tzv. Ekvidištatnými hodnodnotami

Ln(x)= n+1(x) i=0nf(xi)/Di(x), kde n+1(x)=(x-x0)(x-x1)...(x-xn),, Di(x)=(xi-x0)...(xi-xi-1) (x-xi)(xi-xi+1)...(xi-xn)

12.Interpolácia kvadratickými a  kubickými spline-funkciami. Sústava rovníc na určenie koeficientov spline-funkcie.

+ začiatok z 11. otázky

ITERPOLÁCIA KUBICKYMI SPLAJN - rozdeľme interval <a,b> na diely, tak aby a= x0< x1<...< xn-1< xn=b. Zostrojíme interpolačnú funkciu P, kt. bude mať vlastnosti: a)PC2<a,b>, t.j P a jej prvé 2 derivácie sú spojité na <a,b>

b) na každom čiastočnom intervale <xi,xi+1>, i=0,1..,n-1 je funkcia P totožná s nejakým polynómom tretieho stupňa. Aproximacii funkcie f pomocou funkcie P s danými vlastnosťami hovoríme prirodzená splajnová interpolácia kubickými polynómami.

Na <xi,xi+1> hľadáme funkcie Pi v tvare Pi(x)= ai+bi(x-xi)+ci(x-xi)2+di(x-xi)3  

Predpokladáme, že v bodoch xi, i=0,1..,n máme zadané hodnoty f(xi), i=0,1...,n  a potom platí                            Pi(xi)= f(xi),Pi(xi+1)=Pi+1(xi+1)=f(xi+1), i=0,1..,n-1.

Ďalšia prirodzená požiadavka na funkciu P je spojitost jej 1. a 2. derivácie t.j. P’i (xi)= P‘i-1(xi)=P‘‘i-1(xi), i=1,2,...,n-1. Ak doplníme ešte 2.podmienky v bodoch x0 a xn P’‘0(x0)=0, P’‘n-1(xn)=0, potom v každom čiastočnom intervale < xi,xi+1>, i=0,1..,n-1 na výpočet koeficientov ai,bi,ci  a di sú dané 4 podmienky.

Ak označíme xi+1-xi= hi dostaneme pre koeficienty ai,bi,ci ,di rovnice yi=f(xi)=ai,

                                                                                                            yi+1=f(xi+1)=ai+bihi+cihi2+dihi3, i=1,2,..n-1

                                                 bi+1 = bi + 2cihi + 3dihi2,

                                                 ci+1 = ci + 3dihi,      i=1,2,...n-1

                                                 c0 = 0,

                                                 cn-1+3dn-1hn-1 = 0.

Porovnaním posledných 2 rovníc pre i=n-1 je zrejmé, že cn= 0 a z 3.vzťahu je di=(ci+1-ci)/3hi, i=1,2,..,n-1.         Po dosadení do yi+1=f(xi+1)=ai+bihi+cihi2+dihi3 dostávame bi=(f(xi+1)- f(xi))/(hi)- hi/3*(ci+1+2ci), i=0,1..,n-1 a cn=0. Dosadením koeficientov ai,bi,di a po úprave dostávame sústavu rovníc pre koeficient ci:

cihi+2ci+1(hi+hi+1)+ ci+2hi+1=Ri,    Ri=3[(yi+2- yi+1)/(hi+1)-(yi+1- yi)/ (hi)], i=0,1,...,n-1 a položíme cn+1=0

13.Aproximácia funkcie metódou najmenších štvorcov. Zostavenie sústavy lineárnych algebraických rovníc v prípade lineárnej MNŠ.

MNŠ predpokladajme, že hodnoty f(xi), i=0,1,...,n boli namerané s „približne“ rovnakou presnosťou.

Koeficienty a0*,ai* vypočítame tak, aby súčet štvorcov di2, i=0,1,...,n bol najmenší, t.j.

S(a0*,ai*)= i=0 n∑(a0*+a1*xi-yi)2=minS(a0,a1), kde S(a0,a1)= i=0n∑(a0+a1xi+yi). Ostré lokálne minimum funkcie S(a0,a1) môže nastať v bode (a0,a1), v ktorom sú nulové parciálne derivácie ∂S/∂a0, ∂S/∂a1, t.j.

2i=0n∑(a0+a1xi-yi)*1=0, 2i=0n∑(a0+a1xi-yi)xi=0. Po úprave dostávame sústavu rovníc, ktorej riešením sú a0*,a1*, t.j. a0(n+1)+a1 i=0n∑xi=i=0n∑yi,  a0 i=0n∑xi+a1 i=0n∑xi2=i=0n∑xiyi. Dá sa dokázať, že v bode a0*,a1* funkcia S(a0,a1) nadobúda ostré lokálne minimum.

Predpokladajme, že presnosť experimentu pre všetky hodnoty xi, i=0,1,...,n nie je rovnaká. Každej hodnote yi priradíme v závislosti na presnosti určitú váhu vi>0,i=0,1,...,n.

Označme M={x0,x1,…,xn}a nech táto množina obsahuje práve m+1 navzájom rôznych bodov. Nech k je celé číslo 0≤ k ≥m a φ0,φ1,...,φk je systém lineárne nezávislých funkcií na množine M, t.j. nech je lineárne nezávislá (k+1)-tica vektorov (φ0(x0), φ0(x1),...,φ0(xn)), (φ1(x0), φ1(x1),...,φ1(xn)), (φk(x0), φk(x1),...,φk(xn)). Za triedu V aproximujúcich funkcií vezmeme množinu ich lineárnych kombinácii, v={a0φ0+ a1φ1+... akφk/ R, i=0,1,..,k}

14.Diskrétna Fourierova aproximácia. Rýchla Fourierova aproximácia (FFA).

Furierova analýza- rýchly algoritmus pre výpočet koeficientov ck=1/(m+1)* s=0 m∑f(xs)*e-ikXs k=0,1,...predpokladajme že sú dané hodnoty funkcie f v N bodoch  xs=2πs/N  s= 0,1,....,N-1 . Vzhľadom na prvý vzorec dostávame Ck=1/N *  s=0 N-1∑f(xs)*e-ik2πs/N k=0,1,2..,N-1 .

Zavedieme si nasledujúce označenie  Fs=f(xs)/N , w= e-2πi/N .

Po dosadení do predchádzajúceho vzťahu Ck=s=0N-1∑Fs*wks k=0,1,..,N-1 Uvažujeme jednoduchší prípad, keď

N= 2M . Ďalej položíme pre s párne s1=s/2 pre s neparne s1=(s-1)/2, potom 0≤s1≤N/2-1. Ak pri použití prechádzajúceho vzťahu rozdelíme sčítance s párnymi a nepárnymi indexami , dostaneme  

Ck=s1=0N/2-1∑F2s1*(w2)ks1 + w k *s1=0 N/2-1∑F2s1+1*(w2)ks1 . Ak vydelíme číslom N/2 dostaneme k=q(N/2)+k1. , kde q je podiel a k1 je zvyšok delenia.  

Označme : Rk1= s1=0 N/2-1∑F2s1*(w2)ks1  , Sk1= s1=0 N/2-1∑F2s1+1*(w2)ks1 , pre k=0,1,...N-1, potom po zavedení máme Ck= Rk1 + wk * Sk1 , k= 0,1,...N-1. Výpočet Rk1 a Sk1 predstavuje dve Furierove analýzy z N/2=2m-1 hodnôt funkcie. Pri výpočte Ck z Rk a Sk je potrebne najviac 2*2M operácií.

15.Približný výpočet integrálov lichobežníkovou metódou. Odhad chyby pri zadanom počte delení a odhad počtu delení pri zadaní nepresnosti.

Lichobežníková metóda - zaoberá sa výpočtom ∫a b f(x)dx   ,kde a<b sú reálne čísla a f:<a,b>-> je integrovateľná. Interval <a,b> rozdelíme na menšie intervaly, n intervalov  s konštantným krokom h, h=(a+b)/n, potom  ∫x0 xn f(x)dx ~ h[y0+yn/2 + y1+y2+….yn-1], čiže počítame čiastkové integrály na daných intervaloch.  

Pre chybu aproximácie  Rl potom platí: |Rl|<=((xn-x0)/12)*M2*1/n2, pričom M2 je M2=max |f’’(x)|, pričom x patrí do intervalu <a,b>.

Ak máme vyrátať spätne počet krokov ak máme zadanú presnosť , postupujeme takto :

|Rl|≤ ((xn-x0)/12)*M2*1/n2 < ε

vypočítame si M2 ,a s toho vypočítame  n ,n≥√ {(b-a)3*M2/(12*ε)},  pričom n sa zaokrúhľuje smerom nahor na celé párne číslo. (napr. n=2,24 , potom n musí byť  4 a nie 3 alebo az 6)

16.Približný výpočet integrálov Simpsonovou metódou. Odhad chyby pri zadanom počte delení a odhad počtu delení pri zadaní nepresnosti.

Simpsonová metóda - zaoberá sa výpočtom ∫a b f(x)dx   ,kde a<b sú reálne čísla a f:<a,b>-> je integrovateľná. Interval <a,b> rozdelíme na menšie intervaly, n intervalov  s konštantným krokom h, h=(a+b)/n,

potom  ∫x0 x2m f(x)dx≈1/3*h[y0+y2m + 4(y1+y3+y5+….y2m-1)+2(y2+y4+…+y2m-2)]=S(f,h),

čiže počítame čiastkové integrály na daných intervaloch.  

Pre chybu aproximácie  Rs potom platí: |Rs|<=((x2n-x0)/180)*M4*1/n4, pričom M4 je M4=max |f4(x)|, x <a,b>

Ak máme vyrátať spätne počet krokov ak máme zadanú presnosť , postupujeme takto :  

|Rs|≤((x2n-x0)/180)*M4*1/n4 < ε   vypočítame si M4 ,a s toho vypočítame  n , n≥4√ {(b-a)5*M4/(180*ε)},

pričom n sa zaokrúhľuje smerom nahor (napr. n=2,24 , potom n musí byť  3 )

17.Riešenie Cauchyho úlohy pre diferenciálnu rovnicu 1.rádu. Eulerove metódy. Pojem prediktora a korektora.

Eulerova metóda- jednokroková metóda, y’=f(x,y) – diferenciálna rovnica 1 . rádu s počiatočnými podmienkami y(x0) = y0, hľadáme tzv. prírastkové zobrazenie φ, ktoré závisí na premenných x <x0,b>,

y  R, h>0 a na funkcii f ,kde  yi+1= yi + hiφ(xi,yi,hi). Za smernicu úsečky vezmeme smernicu dotyčnice k integrálnej krivke prechádzajúcu bodom (xi,yi), teda ki =φ(xi,yi,hi)=y’(xi)=f(xi,yi)

potom dostávame yi+1= yi + hif(xi,yi). – to je rekurentný vzťah,

Ak pracujem s pevným krokom tak potom xi+1= xi+h , a yi+1= yi + hif(xi,yi) pre i=0,1,2…

Implicitná metóda- integrujme diferenciálnu rovnicu  y’=f(x,,y) na intervale <xi,xi+1>.

Dostávame y(xi+1)-y(xi) = ∫xixi+1f(x,y)dx.

Použitím lichobežníkového pravidla y(xi+1)=y(xi)+ h/2[f(xi,yi) + f(xi+1,yi+1) ] + di  , pričom y(xi)=yi.

Ak hodnotu yi+1 vo vzťahu  y(xi+1)=y(xi)+ h/2[f(xi,yi) + f(xi+1,yi+1) ] + di nahradíme hodnotou  y(xi+1) vypočítanú pomocou eulerovej metódy  y(xi+1)=yi + hf(xi,yi) ,

plati y(xi+1)=y(xi)+ h/2[f(xi,yi) + f(xi + h, yi + h*f(xi+1,yi+1) ] pre i =0,1,2,…V každom výpočtovom kroku od ym do ym+1 používame dve vhodné k-krokové metódy.

1.Explicitnú metódu, ktorou nájdeme začiatočnú aproximáciu (tiež označenie ym+1pred) pre ym+1, nazývame prediktor.

Implicitnú metódu, ktorou určíme ďalšie aproximácie y(j)m+1 nazývame korektor.

Aditivny vyber kroku :-dobry algoritmus (má v sebe myšlienku zahustenia ale aj zriedeniakroku), avšak nemusí to byť vždy efektívne. yn+1 = krok(h,xn,yn)

18.Riešenie Cauchyho úlohy pre diferenciálnu rovnicu 1.rádu metódou Rungeho-Kutta. Adaptívny výber kroku.

Metóda Rungeho-Kutta : vid 17, základom skupiny jednokrokových metód, ktoré sa často používajú, je vyjadrenie aproximácie yn+1 v tvare yn+1=yn+ ∑i=1s wiki ,kde wi sú vhodné končtanty a ki sú  k1 = h*f(xn,yn) , ki=h*f(xn+αih,yn +∑βijkj) i=2,3,…s, . Hodnoty ki sú získané z funkčných hodnôt funkcie f vo vhodne zvolených bodoch , pričom metóda nevyžaduje konštantný krok. Konštanty wi,αi,βi,j pre  i=1,2,3,…s , j=1,2,….i-1,. určujeme tak že požadujeme rovnosť medzi prvými p+1 členmi Taylorovho rozvoja ľavej a pravej strany  prvého vzťahu.

Najpoužívanejšou metódou je metóda Rungeho-kutta 4-teho rádu. Pričom : yn+1= yn+ 1/6 (k1+2k2 +2k3 + k4), k0=h*f(xn,yn),

k1=h*f(xn+1/2*h,yn + 1/2*k0),

k2= h*f(xn+1/2*h,yn+1/2k1),

k3= h*f(xn+1/2*h,yn+1/2k2),

k4= h*f(xn+h,yn+k3),

pomocou vzťahu |(k2-k3)/(k1-k2)|≈0.05 môžeme zistiť či je krok pomerne „dobrý“ ak je táto hodnota oveľa vačšia tak zmenšíme krok. , na odhad aproximácie  použijeme metódu  polovičného kroku :

e(x,h/2)≈1/15[y(x,h/2)-y(x,h)].

19. Riešenie Cauchyho úlohy pre sústavu diferenciálnych rovníc 1.rádu metódou Rungeho-Kutta.

Sústava dif. rovníc : y1´=f1 (x,y1,...,yn) y2´=f2(x,y1,...,yn) yn´=fn(x,y1,...,yn) <a,b>  takouto úlohou pre sústavu n diferenciálnych rovníc prvého rádu budeme rozumieť hľadanie n funkcii y1,y2,...,yn premennej x definovaných a spojite diferencovateľných v intervale <a,b>, ktoré vyhovujú rovniciam a doplňujúcim začiatočným podmienkam y1(x0)=y10, y2(x0)=y20,..., yn(x0)=yn0, kde y=(y10,y20,...,yn0)T je daný n - rozmerný vektor a x0 je pevne zvolený bod y intervalu.

Metóda Rungeho-Kutta: y´= f(x,y,z,) , z´= g(x,y,z) a začiatočné podmienky  y(xi)=yi, z(xi)=zi,

dostávame yi+1=yi + 1/6(k1y +2*k2y +2*k3y + k4y)  a zi+1=zi+1/6(k1z+2*k2z+2*k3z+k4z) kde k1y=.... k2y=....,k3y.....,k4y....,k1z=.....,k2z=.....,k3z=.....,k4z=....., (napísané v 18. otázke),  metóda rádu vyššieho ako 4.tého sa nepoužívajú  veľmi často.

Pomocou vzťahu |(k2-k3)/(k1-k2)|~0.05 môžeme zistiť či je krok pomerne „dobry“ ak je tato hodnota oveľa väčšia tak zmenšime krok. , na odhad aproximácie  použijeme metódu  polovičného kroku e(x,h/2)~1/15[y(x,h/2)-y(x,h)].

20.Viackrokové metódy riešenia diferenciálnych rovníc 1. rádu. Metódy typu prediktor-korektor.

Viackrokové metódy:  využívajú informácie získané v predchádzajúcich bodoch  xn,xn+1,xn+2....xn+k-1, t.j hodnoty yn,yn+1,yn+2....yn+k-1  fi = f(xi,yi), viackrokové metódy vyžadujú  na rozdiel od jednokrokových k začiatočných podmienok ktoré môžeme vypočítať pomocou rôznych metód..(Runge-Kutta , Eulerovej a pod.) Túto množinu bodov nazývame štartovací úsek. Viackrokovou alebo k-krokovou metódou budeme nazývať metódu danú vzorcom : j=0 k∑akyn+j = j=0 k ∑bkfn+j  n=0,1,.... , kde ai a bi sú konštanty a fi  stručný zápis hodnoty f(xi,yi).

Budeme predpokladať ,že ak >=1 a |ak|  + |bk|  >0 . V prípade ak bk=0 ide o tzv. Explicitnú metódu

ak bk≠0 ide o tzv. implicitnú metódu.

Adamsove metódy: predpokladajme, že poznáme približné hodnoty ym=y(xm), ym-1=y(xm-1),..., ym-k=y(xm-k) riešenia Cauchyho úlohy y´=f(x,y),y(x0)=y0 a hľadáme hodnotu riešenia ym+1 v bode xm+1. Potom dostávame y(xm+1)=ym+xmxm+1∫f(x,y)dx. Funkciu F(x)=f(x,y(x)) nahradíme pomocou druhého Newtonovho interpolačného polynómu v uzlových bodoch xm-k,...,xm-1,xm, kde t=x-xm/h

dostaneme F(x)≈F+t∆Fm-1+t(t+1)/2!*∆2Fm-2+t(t+1)(t+2)/3!*∆3Fm-3+...+ t(t+1)...(t+k-1)/k!*∆kFm-k