Newton Iteration

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.
mzh
User
Beiträge: 295
Registriert: Dienstag 3. März 2009, 15:27
Wohnort: ZH

Hallo zusammen

Ich hab ein kleines Skript zur Berechnung einer Nullstelle geschrieben:

Code: Alles auswählen

import math

def F(x):
    f = math.exp(x) + x
    df = math.exp(x) + 1
    return (f, df)

def zero(F, x0 = 0, eps = 1.0e-08, n = 2000):
    return x0 - F[0]/F[1]
    
if __name__ == '__main__':
    
    #Smallest deviation.
    eps = 1.0e-08
    
    #"x0" starting value.
    x = 0
    print("Iteration Nr.:      ", "Root value:    ", "Value of f(x):")
    for i in range(20000):
        if F(x)[0] < eps:
            break
        x = zero(F(x), x)
        print(("I " + str(i).rjust(3) +  ":              " + "%-3.8f" + ",      " + "%-3.8f")% (x, F(x)[0]))
    print("**********************")
    #I absolutly dont understand, why x has two different values here!!!
    print("Start value: %d" % x)
    print("Final value: " + str(x))
    print("**********************")
Die Ausgabe lautet nun:
Iteration Nr.: Root value: Value of f(x):
I 0: -0.50000000, 0.10653066
I 1: -0.56631100, 0.00130451
I 2: -0.56714317, 0.00000020
I 3: -0.56714329, 0.00000000
**********************
Start value: 0
Final value: -0.56714329041
**********************

Was ich allerdings überhaupt nicht seh, ist wieso 'x' am Schluss für zwei verschiedene Werte stehen kann!?! Zusätzlich: Wenn ich in der Ausgabe am Schluss das zweite print-statement als

Code: Alles auswählen

print("Final value: %d" %x)
schreibe, dann kommt zweimal Null.
[url=http://www.proandkon.com]proandkon.com[/url]
KingZero
User
Beiträge: 5
Registriert: Samstag 17. Januar 2009, 15:27

Code: Alles auswählen

>>> x = 0.56345
>>> print("x =  %d" %x)
x =  0
>>> print("x =  %f" %x)
x =  0.563450
"%d" -> integer
"%f" -> decimal
Und mit str(x) wandelst du die komplette Zahl in einen String um.
mzh
User
Beiträge: 295
Registriert: Dienstag 3. März 2009, 15:27
Wohnort: ZH

Aha, dann wird in der "Start value"- Zeile gar nicht der Startwert ausgegeben, sondern der auf Null gerundete Endwert.
[url=http://www.proandkon.com]proandkon.com[/url]
KingZero
User
Beiträge: 5
Registriert: Samstag 17. Januar 2009, 15:27

Richtig. Aber da du beim Start- und Finalvalue beides mal x ausgibst, wirst du immer die gleiche Zahl bekommen.
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Bei ein paar print-Funktionen kannste Platz sparen:

Code: Alles auswählen

>>> print("********************")
********************
>>> print("*" * 20)
********************
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Code: Alles auswählen

print(("I  %3d:              %-3.8f,      %-3.8f")% (i, x, F(x)[0])) 
Das Leben ist wie ein Tennisball.
mzh
User
Beiträge: 295
Registriert: Dienstag 3. März 2009, 15:27
Wohnort: ZH

Besten Dank allen.
String formatting ist irgendwie schwieriger als das eigentliche Programmieren.
[url=http://www.proandkon.com]proandkon.com[/url]
Justifiez
User
Beiträge: 13
Registriert: Montag 26. Mai 2014, 19:48

Hi Leute,

ich habe mir das Programm mal angeschaut, weil ich zurzeit auch damit arbeiten muss.
Wenn ich die Nullstellen von quadratischen Funktionen oder höher berechnen will, funktioniert das Programm nicht.
Bei quadratischen Funktionen wird bis ins "unendliche" iteriert. Ich habe hier mal die Nullstellen von 4*x**2 + 10 genommen, die entsprechende Ableitung wäre 8*x:

Code: Alles auswählen

def F(x):
    f = math.exp(x) + 4*x**2 + 10
    df = math.exp(x) + 8*x
    return (f, df)
Nach 50 Schritten habe ich bei der Ausgabe nur aufgehört zu kopieren, das geht wie gesagt noch ewig so weiter:

Code: Alles auswählen

Iteration Nr.:       Root value:     Value of f(x):
I    0:              -11.00000000,      494.00001670
I    1:              -5.38636238,      126.05617740
I    2:              -2.46069651,      34.30548466
I    3:              -0.71043423,      12.51029795
I    4:              1.69907927,      27.01639111
I    5:              0.28175487,      11.64299700
I    6:              -2.97093981,      45.35718865
I    7:              -1.05844678,      14.82823267
I    8:              0.76755985,      14.51109505
I    9:              -0.98182262,      14.23053033
I   10:              0.92066657,      15.90147125
I   11:              -0.68939769,      12.40295494
I   12:              1.78461085,      28.69660470
I   13:              0.36638435,      11.97945955
I   14:              -2.37266408,      32.61137144
I   15:              -0.64610584,      12.19389368
I   16:              1.97919302,      32.90572070
I   17:              0.55287806,      12.96094518
I   18:              -1.55073674,      19.83122946
I   19:              0.07560006,      11.10139262
I   20:              -6.51929334,      180.00621754
I   21:              -3.06778223,      47.69167544
I   22:              -1.12084420,      15.35117131
I   23:              0.65575771,      13.64667447
I   24:              -1.24683741,      16.50582641
I   25:              0.45702731,      12.41486787
I   26:              -1.91421770,      24.80437476
I   27:              -0.27872320,      11.06749584
I   28:              7.23466657,      1606.04006290
I   29:              6.12287839,      616.13441584
I   30:              4.90319398,      240.88462828
I   31:              3.51836131,      93.24457693
I   32:              2.01140266,      33.65675577
I   33:              0.58315164,      13.15193962
I   34:              -1.45373312,      18.68705613
I   35:              0.18603343,      11.34289627
I   36:              -4.02638167,      74.86483621
I   37:              -1.70089672,      21.75471835
I   38:              -0.08039175,      10.94860612
I   39:              -39.23559141,      6167.72653189
I   40:              -19.58593687,      1544.43569292
I   41:              -9.72914713,      388.62527537
I   42:              -4.73608907,      99.73093155
I   43:              -2.10327253,      27.81707771
I   44:              -0.43799048,      11.41267457
I   45:              3.55442077,      95.50318767
I   46:              2.04813085,      34.53275530
I   47:              0.61751843,      13.37963673
I   48:              -1.35167717,      17.56693057
I   49:              0.31270720,      11.75826435
I   50:              -2.72656308,      39.80202864
Woran könnte das liegen?
Benutzeravatar
MagBen
User
Beiträge: 799
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Justifiez hat geschrieben:Woran könnte das liegen?
Es werden keine Nullstellen gefunden, weil Deine Funktion keine Nullstellen hat.

Außerdem sollte in Zeile 20 math.fabs benutzt werden:
if math.fabs(F(x)[0]) < eps:
a fool with a tool is still a fool, www.magben.de, YouTube
DaftWullie
User
Beiträge: 37
Registriert: Donnerstag 17. Mai 2012, 21:28

Das könnte daran liege, dass Deine Funktion keine (reellen) Nullstellen hat. *Ewig* wäre in diesem Fall 20000 Zeilen...

Edit: MagBen war schneller
Justifiez
User
Beiträge: 13
Registriert: Montag 26. Mai 2014, 19:48

Danke für die schnellen Antworten :)

Das mit der quadratischen Funktion war natürlich blöd von mir.
Ich hab das jetzt nochmal mit der hier probiert:

Code: Alles auswählen

def F(x):
    f = math.exp(x) + x**2 - 7
    df = math.exp(x) + 2*x
    return (f, df)
Ergebnis:

Code: Alles auswählen

Iteration Nr.:       Root value:     Value of f(x):
I    0:              6.00000000,      432.42879349
I    1:              4.95907843,      160.05490457
I    2:              3.90871570,      58.11296653
I    3:              2.90072597,      19.60155512
I    4:              2.08361305,      5.37488505
I    5:              1.64307281,      0.87072300
I    6:              1.54011616,      0.03708990
I    7:              1.53532750,      0.00007633
I    8:              1.53531760,      0.00000000
I    9:              1.53531760,      -0.00000000
********************
Final value: 1.5353176023437658
********************
Normalerweise müsste aber sqrt(7) = 2,64575... rauskommen.
Kann man mit diesem Code keine besseren Ergebnisse erwarten?
Justifiez
User
Beiträge: 13
Registriert: Montag 26. Mai 2014, 19:48

Es müssten ja sogar zwei Ergebnisse rauskommen. Das macht es aber auch nicht.
BlackJack

@Justifiez: Natürlich kann da nur 1 Ergebnis heraus kommen. Vielleicht solltest Du Dir erst mal klar machen wie dieser Algorithmus funktioniert, dann ist es wesentlich einfacher das Ergebnis zu deuten.

Du bekommst hier halt den anderen 0-Punkt. Der den Du erwartet hast liegt übrigens bei -2,6…
Benutzeravatar
MagBen
User
Beiträge: 799
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Justifiez hat geschrieben:Normalerweise müsste aber sqrt(7) = 2,64575... rauskommen.
Das stimmt so für
f = x**2 - 7
aber nicht für:
f = math.exp(x) + x**2 - 7

Aber ohne math.exp(x) funktioniert der Algorithmus nicht, dann musst Du nämlich 0/0 abfangen.
Justifiez hat geschrieben:Es müssten ja sogar zwei Ergebnisse rauskommen. Das macht es aber auch nicht.
Newton liefert eine Nullstelle. Die zweite Nullstelle bekommst Du mit einem anderen Startwert.

Plotte doch einfach zwischendurch mal das, was Du versuchst zu analysieren:

Code: Alles auswählen

import numpy as N
from matplotlib import pyplot as P
x = N.linspace(-10,10,1000)
P.plot(x, N.exp(x)+x**2-7)
P.grid(True)
P.ylim(-10,10) 
P.show()
a fool with a tool is still a fool, www.magben.de, YouTube
Benutzeravatar
MagBen
User
Beiträge: 799
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

BlackJack hat geschrieben: Vielleicht solltest Du Dir erst mal klar machen wie dieser Algorithmus funktioniert
Das tut er doch gerade, indem er den Algorithmus in Python implementiert und mit uns diskutiert.
a fool with a tool is still a fool, www.magben.de, YouTube
BlackJack

@MagBen: Ich sehe nicht das er da irgendeinen Algorithmus *selbst* implementiert hat. Fremden Quelltext hernehmen und an einer Stelle eine Funktion ändern kann man auch ohne vorher verstanden zu haben was der Rest macht.
Justifiez
User
Beiträge: 13
Registriert: Montag 26. Mai 2014, 19:48

Ok, inwieweit verändert denn das math.exp(x) die letztendliche Lösung? Kann man das überhaupt in einer Zahl ausdrücken?

Ich habe auch gesehen, dass bei Linearen Funktionen das math.exp(x) die Lösung leicht verändert. Je größer der Anstieg der Funktion wird, desto niedriger wird der Fehler, ist aber trotzdem meisten noch zu hoch:

Code: Alles auswählen

def F(x):
    f = math.exp(x) + 100*x + 1
    df = math.exp(x) + 100
    return (f, df)

Code: Alles auswählen

Iteration Nr.:       Root value:     Value of f(x):
I    0:              -0.01980198,       0.00019477
I    1:              -0.01980391,       0.00000000
----------
Ungefähre Nullstelle:-0.019803909002865445
Auch wenn sich das "n" (bei einer linearen Funktion: y = m*x + n) ändert, sinkt der Fehler. Vielleicht ist das aber auch zu subjektiv

Code: Alles auswählen

def F(x):
    f = math.exp(x) + 100*x + 100
    df = math.exp(x) + 100
    return (f, df)

Code: Alles auswählen

Iteration Nr.:       Root value:     Value of f(x):
I    0:              -1.00000000,       0.36787944
I    1:              -1.00366531,       0.00000247
I    2:              -1.00366534,       0.00000000
----------
Ungefähre Nullstelle:-1.0036653350790592

@Blackjack: Korrigiere mich bitte, wenn ich falsch liege. Ich war aber der Meinung, dass das Tangentenverfahren von Newton zur Nullstellenberechnung war.
Mit dieser entscheidenden Formel:

x(n+1) = x(n) - f(x(n))/f'(x(n))
Benutzeravatar
MagBen
User
Beiträge: 799
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

BlackJack hat geschrieben: Fremden Quelltext hernehmen und an einer Stelle eine Funktion ändern kann man auch ohne vorher verstanden zu haben was der Rest macht.
Eben!
a fool with a tool is still a fool, www.magben.de, YouTube
Justifiez
User
Beiträge: 13
Registriert: Montag 26. Mai 2014, 19:48

Heißt das math.exp(x) , das in die Nullstellenberechnung jedesmal ein e^x einfließt?

Das kann ich mir irgendwie nicht vorstellen, würde aber Sinn machen, weil es in der Ableitung wieder vorkommt.
Antworten