Rekursive Wurzelberechnung mit Intervallhalbierung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Dagon
User
Beiträge: 6
Registriert: Donnerstag 9. Februar 2006, 22:03

Sonntag 26. März 2006, 21:28

Hi Leute,
Ich habe folgendes Problem:
Ich will eine Funktion schreiben, die die Wurzel eines gegebenen Radikanten durch rekursive Intervallhalbierung berechnet. Dafür hab ich bisher folgendes:

Code: Alles auswählen

def Intervall(radikant,unten,oben):
    mitte=(unten+oben)/2.0
    print mitte
    if mitte**2 < radikant:              
       unten=Intervall(radikant,mitte,oben)
    else:
       oben=Intervall(radikant,unten,mitte)
Das Problem ist, dass ich keine vernünftige Abbruchbedingung zu Stande bekomme. Es wird zwar eine immer bessere Annäherung ausgegeben (später sogar der genaue Wert) aber irgendwann wiederholt sich das Ergebnis nurnoch bis ein Fehler kommt.
Kann mir da jemand weiterhelfen?
helmut
User
Beiträge: 57
Registriert: Mittwoch 2. November 2005, 07:45
Wohnort: Dormagen

Sonntag 26. März 2006, 22:36

Hallo Dagon,
nachfolgend 2 Loesungen, einmal iterativ und einmal rekursiv.

Code: Alles auswählen

from math import fabs

def iter_sqrt(q_zahl,curval):
	while fabs(q_zahl/curval-curval)>.0001:
		curval = (q_zahl/curval+curval)/2.
	return curval

def rec_sqrt(q_zahl,curval):
	if fabs(q_zahl/curval-curval)<.0001:
		res = curval
	else:
		res = rec_sqrt(q_zahl,(q_zahl/curval+curval)/2.)
	return res

print iter_sqrt(900,10)                      #30.000000014
print rec_sqrt(900, 10)                     #30.000000014
Gruss, Helmut
Dagon
User
Beiträge: 6
Registriert: Donnerstag 9. Februar 2006, 22:03

Montag 27. März 2006, 13:09

Danke auf jeden Fall für die Antwort, nur ist sie nicht ganz das, was ich gesucht habe. Gibt es keine Möglichkeit meiner Funktion noch eine Abbruchbedingung hinzuzufügen, dass sie einfach ab einer bestimmter Schrittzahl/Genauigkeit aufhört? Denn es werden ja die richtigen Näherungswerte ausgegeben, nur halt endlos.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Montag 27. März 2006, 13:24

Wie wäre es mit

Code: Alles auswählen

if abs(oben-unten)<1e-5
Diese Funktion solltest du aber nicht rekursiv schreiben, da du das jeweilige Ergebnis des rekursiven Aufrufs eh nicht benötigst. (Und du früher oder später einen Stack-overflow produzierst, wenn du zuviele Schritte brauchst)

Warum nicht einfach iterativ (was du praktisch ja eh schon machst)

Code: Alles auswählen

def Intervall(radikant, unten, oben):
  mitte = (unten+oben)/2.0
  while abs(unten-oben)>1e-5:
      mitte = (unten+oben)/2.
      if mitte*mitte < radikant:
        unten = mitte
      else:
        oben = mitte
  return mitte
Antworten