Die Mathe-Redaktion - 23.08.2019 13:22 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 458 Gäste und 22 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Python: Bisektions-Verfahren
Druckversion
Druckversion
Autor
Universität/Hochschule J Python: Bisektions-Verfahren
Physics
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 29.04.2018
Mitteilungen: 367
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-18


Abend,

hätte noch eine Aufgabe, deren Lösung - da leider nicht vorhanden - ich mir gerne hier erarbeiten würde. Folgender Grundstock:
Python
def bisect(f,a,b, eps, xstar):
    '''
    Nullstelle der Funktion f im Intervall [a,b] mit Toleranz eps 
    bestimmen. Die exakte Loesung xstar dient hier nur zur Berechnung 
    und Ausgabe des Fehlers bei jedem Iterationsschritt.
    Voraussetzung: f(a) und f(b) muessen verschiedene Vorzeichen haben 
    - falls nicht bereits a oder b Nullstelle ist/sind.
    '''
    a, b = min(a,b), max(a,b)
    fa, fb = f(a), f(b)
    eps=0.01
    fx=f(x)
    if fa * fb > 0:
        raise ValueError('Punkte ungeeignet.')
    x = (a+b) / 2
    i = 0
    text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
    print ( text % ( i, x, i, abs(fx), i, abs(x-xstar) ) )
    #
    #  Obige Zeilen dienen als Hinweis, welche Ausgaben erwartet werden.
    #  Es folgt eine Schleife, in der die Bisektion ausgefuehrt
    #  und die naechste Naeherung nach obigem Muster ausgegeben wird.
    #  Sie duerfen aber gerne auch weitere notwendige Ergaenzungen    vornehmen!
    #
 
    while (b-a) > eps:
 
       if fx == 0:
           break
       elif fx*fa < 0:
           b=x
       else:
           if fx*fa > 0:
               a=x
       b-a
       text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
       print ( text % ( i, x, i, abs(fx), i, abs(x-xstar) ) )
       i=i+1
 
    return x

Die while-Schleife habe ich so mal eingefügt. Passt das soweit? Hilfe wird dringend benötigt, danke :)

VG



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2105
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-18


Die Position der Zeilen
Python
fx=f(x)
...
x = (a+b) / 2
 

ist falsch.
Das soll vermutlich zu Beginn der Schleife passieren und natürlich in umgekehrter Reihenfolge.
Bei dir ist $x$ zum Zeitpunkt der Berechnung von $f(x)$ noch nicht definiert.

Zudem hast du die Ausgabe zweimal drin.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Physics
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 29.04.2018
Mitteilungen: 367
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-07-18


Servus DerEinfaeltige,

def bisect(f,a,b, eps, xstar):

    a, b = min(a,b), max(a,b)
    x = (a+b) / 2
    fa, fb, fx = f(a), f(b), f(x)

    eps=0.01
    i = 0
    control=0

    if fa * fb > 0:
        raise ValueError('Punkte ungeeignet.')
        control=1

    while (b-a)&&control=0 > eps:
       
       if fx == 0:
           break
       elif fx*fa < 0:
           b=x
       else:
           if fx*fa > 0:
               a=x
       b-a
       text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
       print ( text % ( i, x, i, abs(fx), i, abs(x-xstar) ) )
       i=i+1

    return x

So hier noch etwas sauber gemacht, jetzt sollte es passen, oder?
Du hilfst mir übrigens gerade ungemein! Die Prüfung kommt näher und mit dem Programmieren konnte ich mich noch nie wirklich anfreunden.

VG



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2105
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-07-18


Der Code sieht übrigens besser aus, wenn du ihn in eine Quelltextumgebung kopierst/schreibst.
Ich habe das mal gemacht und zwei Kommentare zugefügt an Stellen, die mir spontan auffielen.
Python
def bisect(f,a,b, eps, xstar):
 
    a, b = min(a,b), max(a,b)
    x = (a+b) / 2
    fa, fb, fx = f(a), f(b), f(x)
 
    eps=0.01
    i = 0
    control=0
 
    if fa * fb > 0:
        raise ValueError('Punkte ungeeignet.')
        control=1
 
    while (b-a)&;&;control=0 > eps: # Hier stimmt etwas nicht
 
       if fx == 0:
           break
       elif fx*fa < 0:
           b=x
       else:
           if fx*fa > 0: # Warum hier kein elif?
               a=x
       b-a    # Ergibt keinen Sinn
       text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
       print ( text % ( i, x, i, abs(fx), i, abs(x-xstar) ) )
       i=i+1
 
    return x
 



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Physics
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 29.04.2018
Mitteilungen: 367
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-07-18


So, danke für die Tipps! :) Jetzt hoffe ich passt es.
Python
def bisect(f,a,b, eps, xstar):
 
    a,b=min(a,b),max(a,b)
    x=(a+b)/2
    fa,fb,fx=f(a),f(b),f(x)
    eps=0.01
    i=0
 
    if fa*fb > 0:
        raise ValueError('Punkte ungeeignet.')
    else:
        while b-a > eps:
           if fx == 0:
              break
           elif fx*fa < 0:
              b=x
           elif fx*fa > 0:
              a=x
        text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
        print ( text % ( i, x, i, abs(fx), i, abs(x-xstar) ) )
        i=i+1
 
    return x
 

VG



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2105
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-07-19


Die Funktionswerte bleiben in deiner Schleife unverändert.
Das ist wohl nicht sinnvoll.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Physics
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 29.04.2018
Mitteilungen: 367
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-07-19


Morgen,

ist mir natürlich wieder entgangen:
Python
def bisect(f,a,b, eps, xstar):
 
    a,b=min(a,b),max(a,b)
    x=(a+b)/2
    fa,fb,fx=f(a),f(b),f(x)
    eps=0.01
    i=0
 
    if fa*fb > 0:
        raise ValueError('Punkte ungeeignet.')
    else:
        while b-a > eps:
           if fx == 0:
              break
           elif fx*fa < 0:
              b=x
           elif fx*fa > 0:
              a=x
 
           text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
           print ( text % ( i, x, i, abs(fx), i, abs(x-xstar) ) )
           i=i+1
           x=(a+b)/2
 
    return x
 
 



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2105
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-07-19


Du vergisst, $f(x)$ zu updaten.
Außerdem überschreibst du die Fehlertoleranz.

Hier mal ein Beispiel, das du in einem beliebigen Onlineinterpreter (bspw. hier) testen kannst.
Python
def bisect(f,a,b, eps, xstar):
  a,b=min(a,b),max(a,b)
  fa,fb=f(a),f(b)
  i=0 
  if fa*fb > 0:
    raise ValueError('Punkte ungeeignet.')
  while 1:
    x = (a+b)/2
    fx = f(x)
    if b-a<eps or fx == 0 or i>20:
      return x
    elif fx*fa < 0:
      b=x
    elif fx*fa > 0:
      a=x
    text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
    print(text % (i,x,i,abs(fx),i,abs(x-xstar)))
    i=i+1
  raise RuntimeError("Something went terribly wrong ...")
 
g = lambda x: x**2-2
bisect(g,1,2,0.01,2**.5)
print("\n\n")
 
h = lambda x: (x-1)*(x+2)*(x+3)
bisect(h,-12,10,0.01,1)
 
 



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Physics
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 29.04.2018
Mitteilungen: 367
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-07-20


DerEinfaeltige,

vielen Dank für deine Mühen!! :) Habs ausprobiert und funktioniert, wobei ich ein paar Dinge dann scheinbar doch noch nicht verstehe:
Das while 1 agiert einfach als immer true, und innerhalb dieser Schleife schaffst du dann eben die Abbruchbedingung?
Eine andere Sache: du schreibst ja um fx einen neuen Wert zuzuordnen fx=f(x), das ist dann quasi der Funktionsaufruf der Funktion f, die ja als Eingabeparameter der Funktion bisect beigegeben wurde oder?
Und eins noch: Wir geben ja den text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) aus. %2d steht für den Datentyp double, richtig? Wofür steht die 2?

EDIT: Wenn man das Bisektionsverfahren umbaut zum Regula Falsi-Verfahren (Hierbei muss nur das berechnete x=(a+b)/2 ausgetauscht werden durch x = (a*f(b)-b*f(a))/(f(b)-f(a))) bin ich etwas stutzig geworden. Denn eig. sollte das Regula-Falsi-Verfahren weniger Schritte benötigen. Und in der Tat ist der Fehler auch viel schneller geringer als beim Bisektionsverfahren, aber das Intervall schrumpft langsamer. Wäre es in diesem Fall sinnvoller, wenn man hier statt der Intervall-Länge den Funktionswert mit < eps ansetzt?

EDIT EDIT:
Python
def regula(f,a,b, eps, xstar):
  a,b=min(a,b),max(a,b)
  fa,fb=f(a),f(b)
  i=0 
  if fa*fb > 0:
    raise ValueError('Punkte ungeeignet.')
  while 1:
    x = (a*f(b)-b*f(a))/(f(b)-f(a))
    fx = f(x)
    if abs(fx) < 0.00001 or i>20:
      return x
    elif fx*fa < 0:
      b=x
    elif fx*fa > 0:
      a=x
    text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
    print(text % (i,x,i,abs(fx),i,abs(x-xstar)))
    i=i+1
  raise RuntimeError("Something went terribly wrong ...")
 
def bisect(f,a,b, eps, xstar):
  a,b=min(a,b),max(a,b)
  fa,fb=f(a),f(b)
  i=0 
  if fa*fb > 0:
    raise ValueError('Punkte ungeeignet.')
  while 1:
    x = (a+b)/2
    fx = f(x)
    if abs(fx) < 0.00001 or i>20:
      return x
    elif fx*fa < 0:
      b=x
    elif fx*fa > 0:
      a=x
    text = 'x^(%2d) = %.16f\tf^(%2d) = %.16f\te^(%2d) = %.16f'
    print(text % (i,x,i,abs(fx),i,abs(x-xstar)))
    i=i+1
  raise RuntimeError("Something went terribly wrong ...")
 
g = lambda x: x**2-2
bisect(g,1,2,0.01,2**.5)
print("\n\n")
 
regula(g,1,2,0.01,2**.5)
print("\n\n")
 

Wenn ich folgenden Code-Aufbau habe und beides Vergleiche komme ich in der Tat mit dem Regula nach nur 5 Schritten auf einen sehr genauen approximierten Wert, wohingegen ich beim Bisektionsverfahren 13 Schritte benötige!


VG




  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26822
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-07-20


2019-07-18 21:38 - DerEinfaeltige in Beitrag No. 3 schreibt:
Der Code sieht übrigens besser aus, wenn du ihn in eine Quelltextumgebung kopierst/schreibst.
Es wäre schön, wenn du auch noch den Themenstart und Beitrag #2 entsprechend ändern würdest wink


-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2105
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-07-20


%2d => d bedeutet Ganzzahl in Dezimaldarstellung und die 2 bedeutet mindestens 2 Stellen ohne führende Nullen.

"%2d" % 1 ergibt bspw. ' 1'


Fließkommazahlen werden mit %f ausgegeben.

"%5.2f" % 1.234 ergibt bspw. ' 1.23'
(mind. 5 Zeichen lang und 2 Nachkommastellen)



Zur Regula Falsi:
Diese nähert die Nullstelle nicht zwangsweise von der weiter entfernten Intervallgrenze aus an.
Im Gegensatz zur Bisektion macht es hier keinen Sinn, die Intervallgröße als Abbruchkriterium zu betrachten. Insbesondere muss diese auch gar nicht konvergieren und tut es hier wohl nur aufgrund numerischer Fehler.


PS.: Du überschreibst weiterhin in deinem Code das eps-Argument.
So etwas solltest du unbedingt vermeiden, da du damit gegen den "Vertrag" der Funktion verstößt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Physics
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 29.04.2018
Mitteilungen: 367
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2019-08-04 10:12


Morgen DerEinfaeltige,

danke dir für deine Hilfe bei diversen Fragen! Hatte Prüfungen, deswegen die späte Antwort.

VG
Physics



  Profil  Quote  Link auf diesen Beitrag Link
Physics hat die Antworten auf ihre/seine Frage gesehen.
Physics hat selbst das Ok-Häkchen gesetzt.
Physics wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]