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

Freitag 10. April 2009, 20:41

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

Freitag 10. April 2009, 20:52

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

Freitag 10. April 2009, 20:58

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

Freitag 10. April 2009, 21:07

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

Freitag 10. April 2009, 22:18

Bei ein paar print-Funktionen kannste Platz sparen:

Code: Alles auswählen

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

Freitag 10. April 2009, 22:22

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

Freitag 10. April 2009, 23:11

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

Montag 16. Juni 2014, 09:57

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: 768
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Montag 16. Juni 2014, 10:19

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

Montag 16. Juni 2014, 10:23

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

Montag 16. Juni 2014, 10:41

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

Montag 16. Juni 2014, 10:43

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

Montag 16. Juni 2014, 10:49

@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: 768
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Montag 16. Juni 2014, 10:54

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: 768
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Montag 16. Juni 2014, 11:07

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
Antworten