07 - húrmódszer

Ismét tail rekurziót és paraméterként átadott függvényt gyakorlunk: ezúttal egy függvény zérushelyét szeretnénk megkeresni egy intervallumon, méghozzá az úgynevezett húrmódszert használva, ami szintén egy numerikus módszer, tehát elég hozzá, ha ki tudjuk értékelgetni a függvényünket.

Persze nem találunk feltétlenül olyan pontot, ahol pontosan 0 a függvény értéke, de ha ,,majdnem nulla'', akkor visszajövünk azzal.

a módszer

A módszer inputként kap

• egy f függvényt,
• egy a és egy b pontot, méghozzá úgy, hogy az egyikben negatív, a másikban pozitív a függvény,
• meg egy e > 0 valós szám, ennyi hibát megengedünk,
• és a következőt csinálja ciklusban:
  • kiszámolja az aktuális pontjai közt félúton lévő x pontot,
  • ha |f(x)| < e, akkor leállunk, ez jó lesz zérushelynek, elég közel van nullához,
  • különben ha f(x) negatív, akkor x-szel és a két eredeti pontunk közül a pozitívval,
  • ha pedig pozitív, akkor x-szel és a két eredeti pontunk közül a negatívval haladunk tovább.

Ha a függvény nem túl ronda (mondjuk folytonos és ráadásul ,,egyenletesen'', van valami felső korlát arra h mennyire meredek ezen az intervallumon), akkor ez a módszer előbb-utóbb talál egy zérushelyet.

példa

Nézzük ezt a képet példaként: a kék a függvény, megkapjuk az a és b pontokat, melyek naranccsal vannak jelölve, f(a) pozitív, f(b) pedig negatív.

Ekkor

• a és b közt félúton ott az x1 pont, ahol az érték negatív. Messze van a nullától, ezért most a-val és x1-gyel megyünk tovább, mert ha f(x1) negatív, akkor x1 mellé at visszük tovább, mert f(a) volt a pozitív a két eredeti pontunk közül.
• a és x1 közt félúton x2 van, ott is mondjuk f(x2) negatív és mondjuk még messze a nullától. Akkor x2 mellé a-t visszük tovább, mert f(a) volt a pozitív az f(x1) és az f(a) közül.
• a és x2 közt félúton van x3, itt mondjuk f(x3) pozitív, de messze van a nullától, így x3 mellé x2-t visszük tovább, mert az aktuális két pontunk közül f(x2)<0 és f(a)>0 volt.
• x2 és x3 közt félúton van x4˙, ahol a függvény értéke elég közel van nullához, visszaadjukx4`-et.

a feladat

Implementáljuk a húrmódszert: kapja meg a hurmodszer függvény magát a függvényt, aminek keressük a zérushelyét, valamint két pontot, a-t és bt azzal az ígérettel, hogy az egyikben f pozitív, a másikban pedig negatív (ha nem így lenne, mondjuk egyelőre adjunk vissza ???-et), és egy e valós hibakorlátot (mondjuk ha e negatív, akkor állítsuk be inkább 0.001-re)!

a megoldás

Hogy nézzen ki a függvényünk fejléce?

def hurmodszer( f: Double=>Double, a: Double, b: Double, e: Double ): Double = ???

Válasz mutatása

Kezdetnek mondjuk érdemes lenne úgy rendezni az a és b értékeket, hogy f(a) <= f(b) mindig igaz legyen; ha nem így jön be az input, cseréljük meg! Ezt hogy érhetjük el?

@tailrec
def hurmodszer( f: Double=>Double, a: Double, b: Double, e: Double ): Double = {
  if( f(a) > f(b) ) hurmodszer(f, b, a, e)
  else ???
}

Mivel a paraméterek is értékek, ezért nem adunk nekik új értéket; ehelyett pl. a korrigálást el tudjuk végezni rekurzív hívással, amit a fordító úgyis kioptimalizál, hiszen tail rekurzív. Ezt a biztonság kedvéért jelezzük annotációval is.

Válasz mutatása

A következő logikus lépés talán az e hibatag korrekciója lenne a leírt módon. Ezt hogy érhetjük el?

@tailrec
def hurmodszer( f: Double=>Double, a: Double, b: Double, e: Double ): Double = {
  if ( f(a) > f(b) ) hurmodszer(f, b, a, e)
  else if( e <= 0.0 ) hurmodszer(f, a, b, 0.001 )
  else ???
}

Ne essünk copypaste hibába: a második ágon **nem** `(f,b,a,0.001)`-gyel hívjuk a függvényt, hiszen ott `a` és `b` elvileg jó sorrendben vannak már.

Válasz mutatása

Most, hogy f(a) <= f(b), talán ez az a pont, ahol jó ötlet lenne ellenőrizni, vajon f(a) <= 0 és f(b) >= 0 is teljesül-e (nyilván ez kell legyen a sorrendjük). Ha nem, akkor jöjjünk vissza mondjuk a ??? értékkel, egyébként pedig most már, hogy minden argumentumot ellenőriztünk, hívhatjuk a módszernek egy checked változatát (lehetne persze úgy is megoldani ezt, hogy minden hívásnál ellenőrizzük a paramétereket, de fölösleges időpocsékolás: ha mi csináljuk a rekurzív hívást a saját függvényünkből, azt jól fogjuk tenni). Hogyan ellenőrzünk negatív - pozitívot?

@tailrec
def hurmodszer( f: Double=>Double, a: Double, b: Double, e: Double ): Double = {

  def hurmodszerChecked( x: Double, y: Double ): Double = ???

  if ( f(a) > f(b) ) hurmodszer(f, b, a, e)
  else if( e <= 0.0 ) hurmodszer(f, a, b, 0.001 )
  else if ( f(a) > 0.0 || f(b) < 0.0 ) ???
  else hurmodszerChecked( a, b )
}

Figyeljük meg: a checked függvény már csak a két aktuális pontot kapja meg, hiszen a függvényen belül deklaráltuk, így rálát az `f` függvényre is és az `e` hibatagra is, ráadásul mire ideérünk, már a korrigált változatra.

Válasz mutatása

Menjünk rá a checked függvényre: először is jó ötletnek tűnik kiszámolni a felezőpontot, mondjuk egy z értékbe. Hogyan?

@tailrec
def hurmodszer( f: Double=>Double, a: Double, b: Double, e: Double ): Double = {

  def hurmodszerChecked( x: Double, y: Double ): Double = {
    val z = (x+y)/2.0  //nem kell megadjuk a típust, kikövetkezteti a fordító
  }

  if ( f(a) > f(b) ) hurmodszer(f, b, a, e)
  else if( e <= 0.0 ) hurmodszer(f, a, b, 0.001 )
  else if ( f(a) > 0.0 || f(b) < 0.0 ) ???
  else hurmodszerChecked( a, b )
}

Válasz mutatása

Mi van még hátra? Ha f(z) már jó, akkor visszaadhatjuk z-t, ha meg nem, akkor ha pozitív, y-t kell z-re cserélni, ha negatív, akkor meg x-et. Implementáljuk le! Ehhez érdemes lehet felhasználni a Math.abs függvényt, ami az input (mondjuk) Double szám abszolútértékét adja vissza.

@tailrec
def hurmodszer( f: Double=>Double, a: Double, b: Double, e: Double ): Double = {

  @tailrec //lett benne rekurzív hívás, annotáljuk
  def hurmodszerChecked( x: Double, y: Double ): Double = {
    val z = (x+y)/2.0  
    if( Math.abs(f(z)) <= e ) z                     //ha f(z) szinte nulla, z-t jelentjük le zérushelynek
    else if( f(z) < 0.0 ) hurmodszerChecked( z, y ) //f(z) negatív, f(y) pozitív
    else hurmodszerChecked( x, z )                  //f(x) negatív, f(z) pozitív
  }

  if ( f(a) > f(b) ) hurmodszer(f, b, a, e)
  else if( e <= 0.0 ) hurmodszer(f, a, b, 0.001 )
  else if ( f(a) > 0.0 || f(b) < 0.0 ) ???
  else hurmodszerChecked( a, b )
}

Válasz mutatása

Tudunk valamit javítani a fenti kódon, hogy kevesebbet számoljon?

Tudunk: `f(z)`-t kétszer is kiszámoljuk, egyszer a hibatag miatt, egyszer meg mikor az előjelét teszteljük negatívra. Tegyük ki értékbe:

@tailrec
def hurmodszer( f: Double=>Double, a: Double, b: Double, e: Double ): Double = {

  @tailrec //lett benne rekurzív hívás, annotáljuk
  def hurmodszerChecked( x: Double, y: Double ): Double = {
    val z = (x+y)/2.0  
    val fz = f(z)
    if( Math.abs(fz) <= e ) z                     //ha f(z) szinte nulla, z-t jelentjük le zérushelynek
    else if( fz < 0.0 ) hurmodszerChecked( z, y ) //f(z) negatív, f(y) pozitív
    else hurmodszerChecked( x, z )                  //f(x) negatív, f(z) pozitív
  }

  if ( f(a) > f(b) ) hurmodszer(f, b, a, e)
  else if( e <= 0.0 ) hurmodszer(f, a, b, 0.001 )
  else if ( f(a) > 0.0 || f(b) < 0.0 ) ???
  else hurmodszerChecked( a, b )
}

Inicializáláskor is persze eltehetjük az `f(a)` és `f(b)` értékeket valba úgy, hogy csak egyszer kelljen kiszámolni őket; ugyanakkor talán nem fontos, mert a checked függvényben plusz egy `f` kiértékelés az lényegében meg fogja kétszerezni a kiértékelések számát, hiszen azt minden iterációban futtatjuk, a lenti inicializálós kód tényleg csak plugy két hívást jelent. De megtehetjük, hogy ugyanígy kimentjük `f(a)`-t és `f(b)`-t.

Válasz mutatása

Ha mondjuk az x^2=2 egyenletet akarjuk megoldani numerikusan, azaz az x*x-2 függvény zérushelyét keressük, mondjuk 1e-10 pontossággal (ez ugye a 0.0000000001 érték), azt hogy tehetjük meg? A húrmódszer alkalmazásához persze kell egy olyan pont, ahol ez a függvény negatív (erre pl x=0 jó lesz, mert ott -2), és egy olyan, ahol pozitív (erre meg akár x=10 is jó lesz, mert ott 98). Hogy futtatjuk a húrmódszert erre a függvényre ezekből a pontokból ezzel a pontossággal?

println( hurmodszer( x => x*x - 2, 0, 10, 1e-10) ) //prints 1.4142135623842478

Amint látjuk, szépen megtalálta a gyökkettőt mint zérushelyet, ahogy kell. Futtassuk azért le a teszteket is, ott más függvények zérushelyeit keresgetjük.

Válasz mutatása

Persze ??? hagyása a kódban az nem az idiomatikus megoldás, majd később látni fogjuk, hogy ilyenkor mit illik inkább tenni.

---

Utolsó frissítés: 2020-12-31 18:15:23