Seite 1 von 2
Newton Iteration
Verfasst: Freitag 10. April 2009, 20:41
von mzh
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
schreibe, dann kommt zweimal Null.
Verfasst: Freitag 10. April 2009, 20:52
von KingZero
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.
Verfasst: Freitag 10. April 2009, 20:58
von mzh
Aha, dann wird in der "Start value"- Zeile gar nicht der Startwert ausgegeben, sondern der auf Null gerundete Endwert.
Verfasst: Freitag 10. April 2009, 21:07
von KingZero
Richtig. Aber da du beim Start- und Finalvalue beides mal x ausgibst, wirst du immer die gleiche Zahl bekommen.
Verfasst: Freitag 10. April 2009, 22:18
von derdon
Bei ein paar print-Funktionen kannste Platz sparen:
Code: Alles auswählen
>>> print("********************")
********************
>>> print("*" * 20)
********************
Verfasst: Freitag 10. April 2009, 22:22
von EyDu
Verfasst: Freitag 10. April 2009, 23:11
von mzh
Besten Dank allen.
String formatting ist irgendwie schwieriger als das eigentliche Programmieren.
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 09:57
von Justifiez
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?
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 10:19
von MagBen
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:
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 10:23
von DaftWullie
Das könnte daran liege, dass Deine Funktion keine (reellen) Nullstellen hat. *Ewig* wäre in diesem Fall 20000 Zeilen...
Edit: MagBen war schneller
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 10:41
von Justifiez
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?
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 10:43
von Justifiez
Es müssten ja sogar zwei Ergebnisse rauskommen. Das macht es aber auch nicht.
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 10:49
von 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…
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 10:54
von MagBen
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()
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 11:07
von MagBen
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.
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 11:16
von 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.
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 11:22
von Justifiez
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))
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 11:25
von MagBen
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!
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 11:40
von BlackJack
@MagBen: Häh? :K
Re: Newton Iteration
Verfasst: Montag 16. Juni 2014, 11:53
von Justifiez
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.