Oppervlakte onder een grafiek

[NetForce1]

Ik heb een algoritme dat het oppervlak onder een grafiek bepaald, het is alleen heeeeeeeeel erg traag

code:

TI-BASIC:
for (x, a, b, c)
  d + Y1(x) * c -> d
end
disp d

Waarbij
a de x(begin) is
b de x(eind) is
c de stapgrootte is (dx)
Y1 de functie is
d de totale opp is

Je kunt dus een functie invoeren, een beginpunt, een eindpunt en een stapgrootte. Het gedeelte van de grafiek dat je wilt hebben wordt in rechthoeken verdeelt, de opp van zo'n rechthoek wordt berekend, en die worden vervolgens allemaal bij elkaar opgeteld.

Nu is het alleen zo dat dit proggie vreselijk traag is, terwijl de functie van me GR het in no-time uitgerekend heeft.

Weet iemand hier toevallig een sneller algoritme voor? (Die van de rekendoos bijv.)

Het kan ook niet liggen aan het feit dat de functie van de GR in assembly geschreven is, want ik heb het ook al op me PC-tje geprobeerd (met JAVA), maar ook daar won m'n GR het van

[Verwijderd]

Wellicht hebben die rekenmachines voor standaard grafieken al voorgeintegreerde functies. Dan is het uiteraard vrij snel uitgerekend. Dus wellicht dat bij heel complexe functies je PC het just dik wint van je GR.

[Verwijderd]

Je kan het beste gewoon een standaard integralen tabel kunnen coden op de pc waardoor de standaar integralen veel sneller uitworden gerekent

[Thijsch]

waarom deel je het op ion rechthoeken? is er geen andere manier om dat te doen? zoveelste deel van circel ofzo?
dat je bijvoorbeeld de functie 2x² hebt, je de grafiek tekend, kijkt of het een deel van eer circel is (het buigt omhoog, dus het moet uit circels kunnen bestaan). er moet toch een snellere manier zijn ?

[Verwijderd]

Nee, je moet wel recht hoeken pakken, als je er een cirkel van maakt moet je de hoeken om die cirkel gaan uitrekenen en dat kan ook niet echt dus...

[Lord Daemon]

Uhm, jouw methode bepaalt helemaal niet de oppervlakte onder een grafiek, joue methode benadert de oppervlakte onder de grafiek. Bepalen zal echt alleen gaan met behulp van integreren.

[Diadem]

Tsja, wat jij doet is inderdaad de integraal van een grafiek benaderen. Dit is standaard calculus.

Ik weet niet zeker hoe je grafische rekenmachine het doet. volgens mij kan zo'n ding niet integreren, dus hij zou het haast ook wel op dezelfde manier doen. Misschien een snellere processor (moderne dedicated processors zijn tientallen malen zo snel in hun specifieke taak dan jouw PCtje), en waarschijnlijk ook een heel veel sneller algoritme.

Embedded systems ruled

[Diadem]

Op vrijdag 22 februari 2002 22:13 schreef Goedkoop het volgende:
waarom deel je het op ion rechthoeken? is er geen andere manier om dat te doen? zoveelste deel van circel ofzo?
dat je bijvoorbeeld de functie 2x² hebt, je de grafiek tekend, kijkt of het een deel van eer circel is (het buigt omhoog, dus het moet uit circels kunnen bestaan). er moet toch een snellere manier zijn ?

Deze functie bestaat toch echt niet uit cirkels hoor. Het is een parabool, dat is wel wat anders. Niet alles wat krom is is een cirkelbaan.

Bovendien, hoe wil je in godsnaam dan de oppervlakte onder zo'n grafiek gaan uitrekenen hiermee? Je kunt elke nette functie benaderen met rechthoeken, maar hoe wil je een functie benaderen met cirkels?

[Verwijderd]

Ander algoritme: niet veel efficienter, maar het wordt naukeuriger gedurende je langer wacht.

Waarbij
a de x(begin) is
b de x(eind) is
c de stapgrootte is (dx)
Y1 de functie is
d de totale opp is


c <- 1
ff <- 0
Do While key.pause {
R <- random.(uniform) getal tussen 0 en 1.
ff <- ff+ Y1 ((b-a)*R+a))
d <- (ff/c)*(b-a)
c <- c+1
Print d
}

[Lord Daemon]

Olav, hoe kan de stapgrootte nou negatief zijn? Ik snap niets van je algoritme?

[Verwijderd]

<- <=> = v snappie? (Overgehouden aan Splus)

[Lord Daemon]

Ah, niet 'is kleiner dan'.

Ok, ik snap het.

[RickN]

Euh, dat algoritme klopt volgens mij niet hoor. Als ik het goed begrijp (Ik ben niet bekend met dit vage GR taaltje) neemt ie op random plaatsen binnen het interval de functiewaarde en daar neemt ie dan het gemiddelde van. Dat gemiddelde is dan zogenaamd de opervlakte onder de grafiek. Dat lijkt me dus niet waar, je zult dat gemiddelde eerst nog moeten vermenigvuldigen met de lengte van het interval.

Dan over het nut van dit algoritme, het wordt idd steeds nauwkeuriger, maar het duurt wel verschrikkelijk lang, van het vorige algoritme weet je iig dat het eindigt en als je grotere nauwkeurigheid wilt voer je gewoon een kleinere stapgrootte in.

Oh, en daar komt natuurlijk nog bij dat je GF over ze nek gaat als je lang genoeg wacht, omdat ff dan een overflow krijgt...

[Confusion]

Ik geef hieronder enkele van de bekendste methoden voor het benaderen van een integraal. Stel dat je wilt integreren over het stuk tussen a en b, dan verdeel je het gebied in N gelijke stukken van lengte h. De te integreren functie noem ik f. Vervolgens heb je de volgende methoden:

de rechthoeksregel
Deze benadering wordt gegeven door

de som van i = 0 tot i = N-1 over f(a+i*h)*h.

Kortom, je neemt de waarde aan het begin van ieder interval, vermenigvuldigt dat met de lengte van het interval en sommeert dat over alle intervallen. De globale fout die je maakt is van orde h.

de middenpuntsregel
Deze benadering wordt gegeven door

de som van i = 0 tot i = N-1 over f(a+(i+1/2)*h)*h

Je neemt dus nu de waarde in het midden van ieder interval en vermenigvuldigt dat met de lengte van het interval. De globale fout is nu van orde h²

de regel van Simpson
Deze benadering wordt gegeven door

de som van i = 1 tot i = N-1 over
h/3*[f(a+(i-1)) + 3*f(a+(i-1/2)) + f(a+i*h)]

Je neemt dus de waarde aan het begin van het interval + 3 maal de waarde in het midden van het interval + de waarde aan het eind van het interval. De globale fout is nu van orde h⁴

De regel van Simpson geeft een betere benadering, waardoor je uiteindelijk veel minder functie-evaluaties nodig hebt om dezelfde nauwkeurigheid te bereiken; je kan N veel kleiner kiezen.

[wicher|IA]

je zal idd gewoon de functie moeten integreren

daarmee krijg je het vlot en exact

de rechthoekjes-methode heb ik maar een keer gehad op de middelbare school, als introductie en verheldering op integreren

maar integreren is vlotter, en exact

[RickN]

Op zaterdag 23 februari 2002 12:55 schreef Fused een hele hoop handige informatie:

Die wel wat kleine foutjes bevatte:

De rechthoeksregel, daar heb ik nog nooit van gehoord. Als je goed naar die regel kijkt is het gewoon de middenpuntsregel, met de evaluatie punten 1/2*h naar links verschoven. Wat nog meer opvalt is dat die methode volgens jouw een slechtere benadering geeft dan de middenpuntsregel. Dat lijkt me sterk, het is namelijk gewoon de zelfde methode.

Je methode van Simpson klopt ook niet helemaal. Ik neem aan dat je Simpson's 1/3 regel bedoelt, en niet zijn 3/8 regel (die heeft namelijk 4 evaluatie punten).
Het lijkt me duidelijk dat de som van de gewichten bij de evaluatie punten altijd 1 (in jouw geval 3 want je vermenigvuldigt met h/3) moet zijn. Bij jou is die som 5, dus iets klopt er niet. De correcte regel van Simpson ziet er zo uit: (gebruik makende van jouw notatie)

de som van i = 0 (waarom had jij 1?) tot i = N-1 over
h*[1/6*f(a+(i*h)) + 2/3*f(a+(i+1/2)*h) + 1/6*f(a+(i+1)*h)]

Daarnaast vergeet je nog 1 hele bekende regel (misschien bedoelde je deze met jouw rechthoeksregel?) nl. de trapeziumregel:

de som van i = 0 tot i = N-1 over
h*(1/2*[f(a+(i*h)) + f(a+(i+1)*h)])

Hierbij evalueer je in het begin en eindpunt van een subinterval. Van die functie waarden neem je het gemiddelde en dat vermenigvuldig je met h.

De regel van Simpson kun je trouwens uitbreidden, door meer evaluatiepunten en gewichten te nemen. Met de juiste evaluatie punten en gewichten kun je polynomen van hoge graad EXACT integreren. Deze functies heten Gauss, of ook wel Gauss-Legendre formules. In een GR kun je dan mooi een tabelletje stoppen met evaluatie punten en gewichten, en daarmee kun je dan lekker snel, lekker nauwkeurig integreren. Of dit ook de in de praktijk gebruikte methode is weet ik helaas niet.

[Confusion]

RickN schreef:
De rechthoeksregel, daar heb ik nog nooit van gehoord. Als je goed naar die regel kijkt is het gewoon de middenpuntsregel, met de evaluatie punten 1/2*h naar links verschoven. Wat nog meer opvalt is dat die methode volgens jouw een slechtere benadering geeft dan de middenpuntsregel. Dat lijkt me sterk, het is namelijk gewoon de zelfde methode.

Zie J. van Kan, Numerieke wiskunde voor technici, appendix A.2.1:

De laagste orde benadering is de rechthoeksregel. Deze wordt gegeven door:
integraal van x₀ tot x₀ + h over f(x)dx 'is ongeveer gelijk aan'
h*f(x₀)

Die laatste regel staat hier als formule natuurlijk.

De keuze van het steunpunt bij éénpuntsintegratie is van belang voor de nauwkeurigheid. Kiezen we het steunpunt in het midden van het interval, dan winnen we een orde van nauwkeurigheid. Dit heet om voor de hand liggende redenen de middenpuntsregel.
[..]
integraal van x₀ - h tot x₀ + h over f(x)dx = 2*h*f₀ + h³/3*f^''(x₀ + theta*h)

Op de rest kom ik later terug; die regel van Simpson heb ik inderdaad verprutst; de trapeziumregel had ik weggelaten omdat de middenpuntsregel dezelfde orde van nauwkeurigheid heeft, maar ik ben blij dat je die er nog even bij vermeldde. De middenpuntsregel zoals door mij vermeld klopte ook niet; ik heb daar ook met het aantal gekozen intervallen zitten prutsen tov. het boek (ik wilde het niet in die exacte notatie hier neerzetten).
Sorry, ik heb nogal een gestresste dag (vanavond huisfeest en er moet nog heel veel gebeuren) en niet voldoende tijd aan het opschrijven besteed.

Maar ach, bij gebruik op testfuncties ziet iemand het snel genoeg als het niet klopt

[RickN]

Op zaterdag 23 februari 2002 15:54 schreef Fused het volgende:

[..]

Zie J. van Kan, Numerieke wiskunde voor technici, appendix A.2.1:

Yep, ik heb em nu ook op google gevonden. En idd, als je naar een plaatje van de rechthoek regel en de middenpunt regel kijkt zie je duidelijk dat die tweede een betere benadering geeft.

Wat trouwens nog niet genoemd is, Adaptive Quadrature. Daar heb ik ooit een opdracht over moeten doen bij m'n numerieke wiskunde college. Ook best lache, hierbij hak je het interval niet meteen op in N evengrootte subintervallen, maar begin je met 1 groot interval en dan ga je iteratief telkens het interval dat voor de grootste fout zorgt in tweeen hakken. Op die manier leg je je evaluatie punten meestal op gunstigere plaatsen neer dan wanneer je ze gewoon uniform over het interval verdeelt.

Gaussian Quadrature, (Gauss-Legendre formules) doet het wat dat betreft natuurlijk nog beter, want daarbij reken je gewoon uit wat de meest gunstige plaats is voor je evaluatie punten.

[Diadem]

Toepasselijke signature van RickN hierbij:

<small>"A mathematician is a machine for converting coffee into theorems." - Alfréd Rényi</small>

Maar goed. Dit soort algoritmes is niets voor mij. Ik snap Riemann sommen, maar om daar nu ook nog eens verschillende types van te gaan onderscheiden, dat gaat mij wat te ver. Zolang de limiet naar oneindig van het aantal stappen maar altijd gelijk blijft ben ik tevreden

[FCA]

Op zaterdag 23 februari 2002 18:52 schreef Diadem het volgende:
Toepasselijke signature van RickN hierbij:
[..]

Maar goed. Dit soort algoritmes is niets voor mij. Ik snap Riemann sommen, maar om daar nu ook nog eens verschillende types van te gaan onderscheiden, dat gaat mij wat te ver. Zolang de limiet naar oneindig van het aantal stappen maar altijd gelijk blijft ben ik tevreden

Wacht maar af tot je Numerieke Wiskunde volgend jaar krijgt. Kun je je borst natmaken (is sowieso een rampenvak, maar goed).

Verder vergeten jullie allemaal dat in de foutschatting de waarde van de m-de afgeleide ook een rol speelt. Als je functie niet continue differentieerbaar is, convergeren de iteraties vaak heel slecht. Ook wel handig om mee te nemen.

[RickN]

Op zondag 24 februari 2002 20:50 schreef FCA het volgende:

[..]

Verder vergeten jullie allemaal dat in de foutschatting de waarde van de m-de afgeleide ook een rol speelt. Als je functie niet continue differentieerbaar is, convergeren de iteraties vaak heel slecht. Ook wel handig om mee te nemen.

Ik snap niet zo goed wat je hier bedoelt. De hier besproken methodes zijn in principe niet iteratief, dus convergentie lijkt me hier niet aan de orde.
Het is natuurlijk wel zo dat als de m-de afgeleide van je functie niet continue is, de fout die je maakt bij je benadering wel eens heel groot kan zijn. Dit omdat de fout zelf weer (ongeveer) de integraal is van de m-de afgeleide van de oorspronkelijke functie, vermenigvuldigd met een term die van h afhangt.

Maar het lijkt me dat dit voor alle hier besproken methodes geldt, en dus lijkt het me iets wat je niet KUNT meenemen.

BTW, ik vind het altijd leuk om te zien hoe veel van de wiskundige vragen die hier gepost worden na een tijdje totaal offtopic gaan (en dan pas echt interesant worden )
Zal er wel iets mee te maken hebben dat de mods hier ook wiskundigen zijn...

[FCA]

Op zondag 24 februari 2002 23:23 schreef RickN het volgende:

[..]

Ik snap niet zo goed wat je hier bedoelt. De hier besproken methodes zijn in principe niet iteratief, dus convergentie lijkt me hier niet aan de orde.
Het is natuurlijk wel zo dat als de m-de afgeleide van je functie niet continue is, de fout die je maakt bij je benadering wel eens heel groot kan zijn. Dit omdat de fout zelf weer (ongeveer) de integraal is van de m-de afgeleide van de oorspronkelijke functie, vermenigvuldigd met een term die van h afhangt.

Eigenlijk wel. Je kijkt voor steeds kleinere h hoeveel beter de benadering de werkelijkheid benadert, eigenlijk doe je het wel iteratief. Maar in principe heb je dat wel correct. Je kunt door meerdere stappen achter elkaar te doen, met behulp van een zogenaamde Romberg-schema nog nauwkeurigere benaderingen maken. Je verliest dan wel veel informatie over de grootte van de fout.

Maar het lijkt me dat dit voor alle hier besproken methodes geldt, en dus lijkt het me iets wat je niet KUNT meenemen.

Idd, maar misschien zijn er methodes waarvoor dat niet geldt? Niet dat ik ze ken ofzo, maar stel dat je een functie hebt die precies 1 keer continue differentieerbaar is. Dan kun je veel beter een simpele rechthoek benadering nemen, i.p.v. een Gauss-kwadratuur. Je weet dan tenminste een bovengrens voor de fout. En dan heb je altijd nog het probleem dat de absolute fout dan wel klein mag zijn, maar de relatieve fout gigantisch is, doordat de oppervlakte toevallig net zoveel positief als negatief is.

BTW, ik vind het altijd leuk om te zien hoe veel van de wiskundige vragen die hier gepost worden na een tijdje totaal offtopic gaan (en dan pas echt interesant worden )
Zal er wel iets mee te maken hebben dat de mods hier ook wiskundigen zijn...

Nou, LD is een natuurkundige (of sterrenkundige, zoiets iig), Morgoth doet iets heel anders, alleen Diadem is echt wiskundige (en dan nog gecombineerd met natuurkunde, maar dat zijn de besten )
Verder lopen er wel veel natuurkundigen en wiskundigen rond ja.

[NetForce1]

OK, kan misschien beter nog ff wachten tot ik integreren gehad heb.
iig bedankt