Algoritmy numerickej aproximácie (riešené príklady) - História úprav

Juraj na 20:31, 16. august 2010

2010-08-16T20:31:25Z

Amonatrix: /* Modifikácia zdrojového kódu */

2010-05-27T09:43:48Z

Modifikácia zdrojového kódu

Amonatrix: /* Modifikácia zdrojového kódu */

2010-05-27T09:33:54Z

Modifikácia zdrojového kódu

Amonatrix: /* Riešenie v jazyku C */

2010-05-27T09:18:27Z

Riešenie v jazyku C

Amonatrix: /* Riešenie v jazyku C */

2010-05-27T08:45:44Z

Riešenie v jazyku C

Amonatrix: /* Vzorový výstup */

2010-04-23T14:20:42Z

Vzorový výstup

Amonatrix na 12:42, 19. apríl 2010

2010-04-19T12:42:01Z

Juraj na 14:47, 18. apríl 2010

2010-04-18T14:47:24Z

Juraj: /* Návrh dátových štruktúr */

2010-04-18T12:39:02Z

Návrh dátových štruktúr

Fajzen: /* Overenie vypočítaných hodnôt */

2010-04-17T19:52:22Z

Overenie vypočítaných hodnôt

← Staršia verzia		Verzia zo dňa a času 20:31, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:jazyk C]]~~
	{{Draft}}		{{Draft}}
	{{Skripta programovanie (zbierka úloh)}}		{{Skripta programovanie (zbierka úloh)}}

@@ Riadok 509: / Riadok 509: @@
 	};
 	Aprox B;
 	cout<<"Najvhodnejsia: ";
 	vypisRovnicuKrivky(zistiOptimum(body, n, B));

← Staršia verzia		Verzia zo dňa a času 09:33, 27. máj 2010
Riadok 516:		Riadok 516:
	}		}
	</source>		</source>
		+
		+	===Vzorový Príklad===
		+	Program vypočítal, že pre uvedené vstupné body je navhodnejšia Mocninová aproximácia.
		+	{\| class=datatable
		+	\|-
		+	!<math>x_i</math>
		+	!<math>y_i</math>
		+	\|-
		+	\|1.50
		+	\|0.58
		+	\|-
		+	\|2.00
		+	\|8.61
		+	\|-
		+	\|3.00
		+	\|60.91
		+	\|-
		+	\|4.00
		+	\|201.40
		+	\|-
		+	\|5.00
		+	\|476.59
		+	\|-
		+	\|6.00
		+	\|892.57
		+	\|-
		+	\|7.00
		+	\|1304.37
		+	\|-
		+	\|8.00
		+	\|2715.04
		+	\|}
		+
		+	[[Súbor:Vzor_graf.jpg\|center\|framed]]

← Staršia verzia		Verzia zo dňa a času 09:18, 27. máj 2010
Riadok 336:		Riadok 336:
	===Riešenie v jazyku C===		===Riešenie v jazyku C===
	Kriteriom na vyhodnotenie najlepšej aproximovanej krivky bude hľadanie minimálych hodnôt a vzdialeností uzlových (vstupných) bodov od aproximujúcej krivky.		Kriteriom na vyhodnotenie najlepšej aproximovanej krivky bude hľadanie minimálych hodnôt a vzdialeností uzlových (vstupných) bodov od aproximujúcej krivky.
		+
		+	Definovanie štruktúr potrebných pre spracovanie súradníc:
		+	<source lang="c" line>
		+	struct Bod{
		+	double x,y;
		+	};
		+
		+	enum TYP_KRIVKY{
		+	LIN, LOG, EXP, MOC
		+	};
		+
		+	struct Krivka{
		+	TYP_KRIVKY typ;
		+	double a,b;
		+	};
		+	</source>
		+
		+	Táto štruktúra pre zjednodušenie poslúži na uloženie všetkých typov aproximácie do jednej premennej typu Aprox:
		+	<source lang="c" line>
		+	struct Aprox{
		+	Krivka Lin, Log, Exp, Moc;
		+	};
		+	</source>
		+
		+	Funkcia aproximacie vypočíta všetky 4 typy aproximácií. Návratová hodnota funkcie je typu Aprox:
		+	<source lang="c" line>
		+	Aprox aproximacie(Bod *body, int n, Aprox B) //vypocita vsetky
		+	//aproximacie
		+	{
		+	double sx=0,sxx=0,sy=0,sxy=0,slxly;
		+	double slx=0,slxx=0,sly=0,slxy=0,sxly=0;
		+	for(int i=0;i<n;i++)
		+	{ sx+=body[i].x;
		+	slx+=log(body[i].x);
		+	sy+=body[i].y;
		+	sly+=log(body[i].y);
		+	sxy+=body[i].x * body[i].y;
		+	slxy+=log(body[i].x) * body[i].y;
		+	sxly+=body[i].x * log(body[i].y);
		+	slxly+=log(body[i].x) *log(body[i].y);
		+	sxx+=body[i].x * body[i].x;
		+	slxx+=log(body[i].x) * log(body[i].x);
		+	}
		+
		+	B.Lin.a=(nsxy-sysx)/(nsxx-sxsx);
		+	B.Lin.b=(sy-B.Lin.a*sx)/n;
		+
		+	B.Log.a=(nslxy-syslx)/(nslxx-slxslx);
		+	B.Log.b=(sy-B.Log.a*slx)/n;
		+
		+	B.Exp.a=(nsxly-slysx)/(nsxx-sxsx);
		+	B.Exp.b=(sly-B.Exp.a*sx)/n;
		+	B.Exp.b=exp(B.Exp.b);
		+
		+	B.Moc.a=(nslxly-slyslx)/(nslxx-slxslx);
		+	B.Moc.b=(sly-B.Moc.a*slx)/n;
		+	B.Moc.b=exp(B.Moc.b);
		+
		+	return B;
		+	}
		+	</source>
		+
		+	Na vypísanie najvhodnejšieho typu rovnice je použitá funkcia vypisRovnicuKrivky:
		+	<source lang="c" line>
		+	void vypisRovnicuKrivky(Krivka k) //vypise rovnicu urciteho typu
		+	{
		+	cout<<"y = ";
		+	switch(k.typ)
		+	{
		+	case LIN:
		+	cout<<k.a<<" x";
		+	if(k.b>0) cout<<"+";
		+	cout<<k.b<<" -> LINEARNA"<<endl;
		+	break;
		+	case LOG:
		+	cout<<k.a<<" ln x";
		+	if(k.b>0) cout<<"+";
		+	cout<<k.b<<" -> LOGARITMICKA"<<endl;
		+	break;
		+	case EXP:
		+	cout<<k.b<<" e^(";
		+	cout<<k.a<<" x)"<<" -> EXPONENCIALNA"<<endl;
		+	break;
		+	case MOC:
		+	cout<<k.b<<" x^(";
		+	cout<<k.a<<" )"<<" -> MOCNINOVA"<<endl;
		+	break;
		+	}
		+	}
		+	</source>
		+
		+	Pre zistenie optimálnej aproximovanej krivky pre dané vstupné body je použitý jednoduchý algoritmus daný vo funkcii zistiOptimum.
		+	*Postup riešenia algoritmu spočíva v zistení vzdialenosti y-onovej súradnice vstupného bodu od aproximovanej y-onovej súradnice, ktorú musíme najskôr vypočítať, a porovnaním ako sú tieto body vzdialené od jednotlivých bodov kriviky pre každý typ, zistíme optimum.
		+	*Dosadením x-ových súradníc vstupných bodov do príslušnej rovnice krivky sa vypočíta aproximovaná y-onová súradnica. Absolútnu hodnotu rozdielu vzdialenosti medzi y-onovými súradnicami(vypočítanými a vstupnými) sčíta a uloží túto sumu do premennej sumLin (pre každý ďalší jeden typ aproximácie do - sumLog, sumExp, sumMoc ). Toto sa opakuje pre každý jeden vstupný bod a pre každú rovnicu krivky.
		+	*Na záver sa sumy všetkých typov aproximácií porovnajú. Najmenšia suma predstavuje najmenšie odchýlky pre danú krivku v porovnaní so vstupnými bodmi. Funkcia vráti Optimálnu krivku aproximácie s najmenšou sumou:
		+	<source lang="c" line>
		+	Krivka zistiOptimum(Bod *body, int n, Aprox B)
		+	{
		+	double sumLin=0, sumLog=0, sumExp=0, sumMoc=0, y1=0,y2=0,y3=0,y4=0, Naj=0;
		+	Krivka Optim;
		+	for(int i=0; i < n; i++)
		+	{
		+	y1=((B.Lin.a*body[i].x)+B.Lin.b)-body[i].y;
		+	if(y1<0) y1=-y1;
		+	sumLin+=y1;
		+
		+	y2=((B.Log.a*(log(body[i].x)))+B.Log.b)-body[i].y;
		+	if(y2<0) y2=-y2;
		+	sumLog+=y2;
		+
		+	y3=(B.Exp.b(exp(B.Exp.abody[i].x)));
		+	y3=log(y3);
		+	if(y3<0) y3=-y3;
		+	sumExp+=y3;
		+
		+	y4=(B.Moc.b*(pow(body[i].x, B.Moc.a)))-body[i].y;
		+	if(y4<0) y4=-y4;
		+	sumMoc+=y4;
		+
		+	}
		+	Naj=min(sumLin,sumLog);
		+	Naj=min(Naj,sumExp);
		+	Naj=min(Naj,sumMoc);
		+
		+	if(Naj==sumLin) {B.Lin.typ=LIN; return B.Lin;}
		+	if(Naj==sumLog) {B.Log.typ=LOG; return B.Log;}
		+	if(Naj==sumExp) {B.Exp.typ=EXP; return B.Exp;}
		+
		+	B.Moc.typ=MOC;
		+	return B.Moc;
		+	}
		+	</source>
		+
		+	===Modifikácia zdrojového kódu===
		+	Pre názornosť nebudeme v programe dáta načítavať z klávesnice, ale vstupné údaje budú zadané priamo v zdrojovom kóde
		+	<source lang="c" line>
		+	#include <iostream.h>
		+	#include <conio.h>
		+	#include <math.h>
		+	#include <cmath>
		+
		+	struct Bod{
		+	double x,y;
		+	};
		+	enum TYP_KRIVKY{
		+	LIN, LOG, EXP, MOC
		+	};
		+	struct Krivka{
		+	TYP_KRIVKY typ;
		+	double a,b;
		+	};
		+	struct Aprox{
		+	Krivka Lin, Log, Exp, Moc;
		+	};
		+
		+	//Aprox aproximacie(Bod *body, int n, Aprox B)
		+	//void vypisRovnicuKrivky(Krivka k)
		+	//Krivka zistiOptimum(Bod *body, int n, Aprox B)
		+
		+	int main(int argc, char* argv[])
		+	{
		+	const int n=8;
		+	Bod body[n]={
		+	{1.50,0.58},
		+	{2.00,8.61},
		+	{3.00,60.91},
		+	{4.00,201.40},
		+	{5.00,476.59},
		+	{6.00,892.57},
		+	{7.00,1304.37},
		+	{8.00,2715.04}
		+	};
		+	Aprox B;
		+	cout<<"Najvhodnejsia: ";
		+	vypisRovnicuKrivky(zistiOptimum(body, n, B));
		+
		+	getch();
		+	return 0;
		+	}
		+	</source>

← Staršia verzia		Verzia zo dňa a času 08:45, 27. máj 2010
Riadok 335:		Riadok 335:

	===Riešenie v jazyku C===		===Riešenie v jazyku C===
−	~~Vytvoríme funkciu ''Krivka najlepsiaAproximacia~~(~~Bod *body, int n~~)'', ktorá bude mať ako parameter pole štruktúr Bod reprezentujúce vstupné body. Návratová hodnota funkcie bude štruktúra typu ''Krivka''. Údaje tejto štruktúry budú obsahovať informácie o krivke, ktorá je vhodná ako aproximačná krivka pre takéto vstupné body.	+	Kriteriom na vyhodnotenie najlepšej aproximovanej krivky bude hľadanie minimálych hodnôt a vzdialeností uzlových (vstupných) bodov od aproximujúcej krivky.

@@ Riadok 50: / Riadok 50: @@
 #y = 213.634 x - 467.195
 #y = 784.982 ln x - 572.83
-#y = 6.9628 e^(1.054x)
+#y = 0.9628 e^(1.054x)
 #y = 0.2609 x^(4.443)

@@ Riadok 203: / Riadok 203: @@
      Krivka k;
      k.a=(n*sxy-sy*sx)/(n*sxx-sx*sx);
-     k.b=(sy-a*sx)/n;
+     k.b=(sy-k.a*sx)/n;
      k.typ=LIN;
      return k;

@@ Riadok 5: / Riadok 5: @@
 {{Skripta programovanie (zbierka úloh)}}
-==Zadanie==
+==Zadanie 1==
 Riešte problém aproximácie dát. K dispozícii máme ''n'' bodov v rovine (ich súradnice ''x'' a ''y''). Úlohou bude vypočítať rovnicu aproximujúcej krivky metódou najmenších štvorcov pre:
 #Lineárnu aproximáciu v tvare <math>y=ax+b</math>
@@ Riadok 14: / Riadok 14: @@
 Porovnajte výsledok funkcie s výsledkom v tabuľkovom procesore, kde do (bodového) grafu zo vstupných bodov pridáte spojnicu trendu typu lineárna, resp. logaritmická, mocninová exponenciálna.
-==Vstupné údaje==
+===Vstupné údaje===
 Ako vzorku vstupných bodov budeme uvažovať body z intervalu <1,8>.
 ''Pre generovanie vstupných hodnôt použijem funkciu <math>f(x)=x^4-exp(x)</math>''
-===Vzorový vstup===
+====Vzorový vstup====
 {| class=datatable
 |-
@@ Riadok 47: / Riadok 47: @@
 |1115.04
 |}
-===Vzorový výstup===
+====Vzorový výstup====
 #y = 213.634 x - 467.195
 #y = 784.982 ln x - 572.83
@@ Riadok 53: / Riadok 53: @@
 #y = 0.2609 x^(4.443)
-==Analýza matematických vzťahov==
+===Analýza matematických vzťahov===
 Poznámka: v tomto texte nie sú uvádzané celé postupy výpočtu, nakoľko v tomto predmete nie sú primárnym cieľom matematické dôkazy. Študent si postup môže ľahko overiť sám.
-===Lineárna aproximácia: y=ax+b===
+====Lineárna aproximácia: y=ax+b====
 Pre lineárnu aproximáciu platia vzťahy:
 :<math>\begin{align}
@@ Riadok 81: / Riadok 81: @@
 \end{align}</math>
-===Logaritmická  aproximácia: <math>y=a*\ln x + b</math>===
+====Logaritmická  aproximácia: <math>y=a*\ln x + b</math>====
 Hľadáme najlepšiu aproximáciu pre logaritmickú rovnicu:  <math>y=a*\ln x + b</math>. Postup výpočtu je rovnaký ako v prvom prípade.
 Jediná zmena v riešení je tá, že os x je v logaritmickej mierke. Dostávame teda sústavu 2 rovníc:
@@ Riadok 102: / Riadok 102: @@
 \end{align}</math>
-===Exponenciálna  aproximácia: <math>y=b{{e}^{ax}}</math>===
+====Exponenciálna  aproximácia: <math>y=b{{e}^{ax}}</math>====
 Rovnicu <math>y=b{{e}^{ax}}</math> si upravíme tak, že ju zapíšeme v logaritmickom tvare:
 :<math>\begin{align}
@@ Riadok 132: / Riadok 132: @@
 kde <math>B=\ln b</math>.
-===Mocnimová  aproximácia: <math>y=b{{x}^{a}}</math>===
+====Mocnimová  aproximácia: <math>y=b{{x}^{a}}</math>====
 Rovnicu <math>y=b{{x}^{a}}</math>  si upravíme tak, že ju zapíšeme v logaritmickom tvare:
 :<math>\begin{align}
@@ Riadok 161: / Riadok 161: @@
 kde <math>B=\ln b</math>.
-==Analýza programátorského riešenia==
+===Analýza programátorského riešenia===
-===Návrh dátových štruktúr===
+====Návrh dátových štruktúr====
 V úlohe budeme pracovať s bodmi v rovine, ktoré sú charakterizované x a y súradnicou. Preto si vytvoríme štruktúru Bod, ktorá bude takýto bod reprezentovať:
 <source lang="c">
@@ Riadok 188: / Riadok 188: @@
 </source>
-==Riešenie v jazyku C==
+===Riešenie v jazyku C===
 Vytvoríme funkciu ''Krivka minSq(Bod *body, int n)'' kde v poli body sú vstupné údaje, n je počet bodov. Funkcia bude vracať dátovú struktúru typu Krivka, kde budú informácie o tvare aproximujúcej krivky.
@@ Riadok 254: / Riadok 254: @@
+}
 </source>
-===Použitie v programe===
+====Použitie v programe====
 Pre názornosť nebudeme v programe dáta načítavať z klávesnice, ale vstupné údaje budú zadané priamo v zdrojovom kóde. Modifikácia zdrojového kódu s načítaním vstupných hodnôt je jednoduchá a určite ju každý zvládne sám.
@@ Riadok 316: / Riadok 316: @@
 </source>
-==Overenie vypočítaných hodnôt==
+===Overenie vypočítaných hodnôt===
 Na nasledujúcich obrázkoch sú vstupné body z príkladu znázornené v tabuľkovom procesore a je vypočítaná najlepšia aproximujúca krivka (MS Excel ju nazýva spojnica trendu).
 <gallery heights=220px widths=400px perrow=2>
@@ Riadok 324: / Riadok 324: @@
 Súbor:min SQ moc.png
 </gallery>

@@ Riadok 176: / Riadok 176: @@
 </source>
 Význam týchto skratiek si zadefinujme nasledovne:
-*LIN - lineárna krivka s rovnicou <math>y=ax+b</math>
+*LIN - lineárna krivka (polynóm 1 stupňa) s rovnicou <math>y=ax+b</math>
-*LOG - lineárna krivka s rovnicou <math>y=a \ln{x} + b</math>
+*LOG - logaritmická krivka s rovnicou <math>y=a \ln{x} + b</math>
-*EXP - lineárna krivka s rovnicou <math>y=b e^{ax}</math>
+*EXP - exponenciálna krivka s rovnicou <math>y=b e^{ax}</math>
-*MOC - lineárna krivka s rovnicou <math>y=bx^a</math>
+*MOC - mocninová krivka s rovnicou <math>y=bx^a</math>
 Teraz si môžeme zadefinovať štruktúru Krivka ako trojicu: ''typ'' (TYP_KRIVKY), koeficient ''a''  a koeficient ''b''.
 <source lang="c">