Nullstelle näherungsweise berechnen

[hallo97]

Hallo, ich habe als Eigenprojekt versucht ein Programm zu schreiben, mit dem es möglich ist, Nullstellen von Funktionen, welche sich nicht mit den elementaren Rechenoperationen lösen lassen, näherungsweise zu bestimmen (mal ganz davon abgesehen, dass es schon solche Programme gibt).
Meine Vorgehensweise ist relativ einfach, indem ich ein Intervall vorgebe - wo ich mir sicher seine kann, dass es dort Nullstellen gibt. Dieses Intervall wird dann in k-Schritte aufgeteilt. Dann soll mein Programm dieses Intervall durchlaufen und jedesmal testen, ob die if-Bedingung erfüllt ist. Falls sie erfüllt ist, soll das entsprechende i zu einer leeren Liste hinzugefügt werden. Nun können es hier auch mehrere Kandidaten sein, welche diese Bedingung erfüllen. Deshalb nehme ich nur das mittlere Element aus der Liste, im k-Schritt.

Nun tritt leider folgende Ereignis ein, was man ganz einfach schon bei einer quadratischen Gleichung y = i**2 merken kann, wenn man dieses Programm ausführt. Für die Eingabe u = -1 , o = 1 und y = 2 wird mir nur eine Lösung angeben, statt zwei. Warum? Wo ist in meinem Programm der Fehler. Ich finde ihn einfach nicht. :K

Code: Alles auswählen

from math import *

u = float(input('Untergrenze u = '))
o = float(input('Obergrenze o = '))
y0 = float(input('gewünschter Wert y = '))

L = [] # Kandidatenliste im k-ten Schritt

K = [] # Finale Kandidatenliste aller k-ten Schritte

k = 0
i = u+k

while i <= o:
	
	while i <= u+k+0.1:
		
		y = i**2
		
		
		if y < 0.00001+y0 and y > -0.00001+y0 or y == y0  :
			
			L.append(i)
			
			i = i+0.000001
			
			y = i**2
			
			
		else :
			
			i = i+0.000001
			
			y = i**2

		
        k = k+0.1
	i = u+k
	

K.append(L[len(L)//2])

print(K)

Würde mich sehr über eine ANtwort mit konstruktiven Tipps freuen.
Danke!

Gruß

hallo97

[narpfel]

Moin,

wie viele (und welche) Nullstellen hat denn `y = i**2 - y_0` deiner Meinung nach für `y_0 == 2` im Intervall [-1, 1]?

Zu deinem Code:

• Sternchenimporte sind nur sehr selten sinnvoll und sollten vermieden werden, weil man sich damit unkontrollierbar viele Namen in den globalen Namensraum schaufelt. Hier wird außerdem nichts aus `math` verwendet.
• Deine Variablennamen sind sehr wenig aussagekräftig. Einbuchstabige Namen führen dazu, dass Andere (und in zwei Wochen bist du selbst „andere“) das Programm nur noch schwer verstehen können.
• Leerzeilen sollten sparsam als Strukturierungsmittel eingesetzt werden. Ein oder zwei Leerzeilen zwischen jeder Zeile machen den Code schwerer lesbar.
• Wenn der selbe Code sowohl im `if`- als auch im `else`-Zweig steht, wird er in jedem Fall ausgeführt und man sollte ihn deswegen hinter die `if`-Anweisung schreiben.
• Anweisungen der Form `a = a ∘ b` (wobei `∘` ein beliebiger binärer Operator ist), lassen sich kürzer als `a ∘= b` schreiben, beispielsweise also `k = k + 0.1` → `k += 0.1`.
• Vergleichsoperatoren lassen sich verketten: `a < x and x < b` lässt sich schreiben als `a < x < b` (also wie man es aus der Mathematik vielleicht kennt).
• Um binäre Operatoren sollten Leerzeichen gesetzt werden. Siehe dazu auch PEP 8.

Ich komme ungefähr bei dem hier raus, wenn ich diese Tipps (teilweise) auf deinen Code anwende (ungetestet):

Code: Alles auswählen

lower = float(input('Untergrenze u = '))
upper = float(input('Obergrenze o = '))
y0 = float(input('gewünschter Wert y = '))

candidates = []

k = 0
i = lower + k

while i <= upper:
    while i <= lower + k + 0.1:
        y = i ** 2

        if abs(y - y0) < 0.00001:
            candidates.append(i)
            
        i += 0.000001
        k += 0.1
    i = lower + k

print(candidates[len(candidates) // 2])

Der Code macht das selbe wie deiner und ergibt auch nicht das richtige. Frage dazu: Wie oft wird die innere `while`-Schleife durchlaufen und wann wird sie verlassen?

In der Praxis würde man auch eher einen anderen Algorithmus (Sekantenverfahren, Regula falsi etc.) verwenden als alle Zahlen durchzuprobieren.

[hallo97]

Hallo, schonmal Danke für die schnelle Antwort.

Kurz vorab, ich programmiere selbst noch nicht so lange, aber mache mit Python gerne Programme zur Lösung von mathematischen Problemen.

Wie oft die innere While-Schleife durchlaufen wird, hängt davon ab, wie die Intervallgrenzen gesetzt sind. Das Intervall wird dann in k (hier 0.1) Schritten durchlaufen.
Die innere Schleife soll dann verlassen werden, wenn der jeweils k-te Schritt durch ist. Dann wird k um 0.1 erhöht und dann auch die Unterggrenze um einen k-ten Schritt erhöht.
Der Sinn bei k Schritten soll sein, zu verhinden, dass Python 'zu weit' geht. Es kann ja sein, dass in einem größeren Schritt als 0.1 noch eine Nullstelle existiert, sodass Python auch diesen Kandidaten mit in die Liste hinzugefügt, sodass sich die Mitte dieser Liste verschiebt. Dann würde Python das mittlere Element - und nur dieses mittlere - aufrufen und damit nur einen Kandidaten, statt zwei ausgeben. Das ganze könnte man natürlich auch in 0.01 Schritten, was ich aber besser nicht tun sollte, da es doch schon sehr sehr viel mehr Rechenaufwand wäre.

Wie gesagt, ist das für mich eine reine Übungssache, wie Python eben sagen soll, damit er genau das tut, was verlangt wird. Nur offenbar ist das noch nicht der Fall, weil er eben nicht alle Nullstellen ausgibt, welche im Intervall existieren. Dass, es bereits andere Algorithmen gibt, ist mir schon klar, z.B auch das Newtonverfahren. Aber wie gesagt, ich will wissen, wie ich Python sage, dass er genau das tut, was ich im oberen Absatz beschrieben habe.

[narpfel]

Die Frage war nicht, wie oft die innere `while`-Schleife durchlaufen werden soll, sondern wie oft sie durchlaufen wird. Guck’ dir nochmal genau die Updates von `i` und `k` am Schleifenende an.

Damit der Algorithmus so funktioniert, wie du ihn beschrieben hast, musst du für jedes Teilintervall alle Kandidaten sammeln und dann den „richtigen“ auswählen. In deinem Code passiert etwas anderes.

Stichwort Übungssache: Beim Programmieren ist es nicht nur wichtig, dass man übt, dem Computer genau zu sagen, was er tun soll, sondern auch, dass man übt, Algorithmen zu bewerten bzw. zu entscheiden, ob es Sinn macht, einen Algorithmus zu implementieren oder ob ein anderer Algorithmus mehr Sinn macht (etwa, weil er einfacher zu implementieren ist oder bessere Ergebnisse liefert). Aber wenn du dir dessen bewusst bist, dass es auch andere Algorithmen gibt, dann ist alles in Ordnung.

[hallo97]

Achso hier noch ein Nachtrag. Es kann bei diesem Algortihmus oft passieren, dass es im k-ten Schritt keinen Kandidaten gibt und somit die Liste leer bleibt. Folge: Indexerror, da die die Liste dennoch leer ist und nicht geteilt werden kann.

Mein vorheriges Programm besaß nur eine While-Schleife und hat gleich nur das Intervall durchgerechnet, ganz naiv, ohne Rücksicht darauf, dass es auch mehrere Nullstellen geben könnte. Das ist problematisch, gerade bei periodischen Funktionen, wo man sich nicht nur unbedingt für genau eine Stelle interessiert.
Ein Beispiel wäre y = i**2*exp(cos(i)) = 40 und man betrachtet das Intervall [-10,10], wo es sechs Kandidaten wären. Nur, wenn ich jetzt mein vorheriges Programm drauf loslasse, wird er mir nur einen Kandidaten zurückgeben, wobei hier die Laufzeit sehr groß ist. Ne Tasse Kaffee kann da schonmal drin sein.
Kleiner Spoiler, hier wäre es x = 5.140057796381149

Das vorherige Programm:

Code: Alles auswählen

from math import *

u = float(input('Untergrenze u = '))
o = float(input('Obergrenze o = '))
y0 = float(input('gewünschter Wert y = '))

i = u

L = []

while i <= o :
	
	y = i**2*exp(cos(i))
	
	i = i+0.0000001
	
	if y < 0.00001+y0 and y > -0.00001+y0 or y == 0  :
		
		L.append(i)	# Alle i-Werte, welche die if_Bedingung erfüllen, kommen in die Liste L.

print('\nMöglicher Kandidat x = ',L[len(L)//2]) # Das mittlere Element wird aus der Liste ausgegeben.

From math import * habe ich deshalb genommen, damit Python auch zum Beispiel mit trigonometrischen Funktionen rechnen kann.

[Sirius3]

@hallo97: Du hast noch nicht die Frage von narpfel beantwortet. Du kannst das auch mal mit print-Aufrufen einfach austesten. Es kann auch eine gute Übung sein, einen bewährten Algorithmus umzusetzen.

[hallo97]

Also.
Die innere Schleife wird in JEDEM k-ten Durchgang aufgerufen. Jetzt ist man in der inneren Schleife, mit den Grenzen des jeweiligen Teilintervalls (Schritt 0.1). Und innerhalb dieser Schleife läuft die Laufvariable i dieses Teilintervall mit einer Schrittweite von 0.000001 ab.

Frage beantwortet?

[kbr]

Frage beantwortet?

Nein. Denn die Frage war nicht, was geschehen soll, sondern was tatsächlich geschieht.

[hallo97]

Also was in der inneren While-Schleife passiert, vermute ich folgendes. Wenn der momentane Wert von i die if-Bedingung erfüllt, dann wird dieser Wert zur Liste L hinzugefügt. i wird um einen Schritt erhöht und y mit dem um einen Schritt erhöhten i berechnet. Aber dann wird das weitere Hochzählen von i und das Überprüfen, ob i die if-Bedingung erfüllt, nicht weiter fortgesetzt. Gleiches würde dann auch auch für else gelten, wo nur i einmal erhöht wird und mit diesem erhöhten i das y ausgerechnet wird.

Ich habe weiterhin am Programm gearbeitet und bin nun zum folgenden Ergebnis gekommen. Eins vorweg, es funktioniert so, wie ich es schon in meinen früheren Beiträgen gesagt habe.

Das Hochzählen von i habe ich aus der if-Bedingung genommen, damit i immer weiterhin erhöht wird, bis die Obergrenze o erreicht wird.
Außerdem soll nach jedem k-ten Schritt überprüft werden, ob L nicht leer ist. Wenn Ja, dann nur das mittlere Element nehmen. Dann wird dieses zur Liste K hinzugefügt. Danach wird die Liste L gelöscht und wieder neu als leere Liste definiert. Dann wird k um einen Schritt k erhöht, sowie die Untergrenze um einen k-ten Schritt. Und falls die Liste leer ist, dann wird auch sie entfernt und wieder leer definiert.

Wenn das komplette Intervall durchlaufen ist, werden alle finalen Kandidaten durchmummerriert untereinander ausgegeben.

Code: Alles auswählen

from math import *

u = float(input('Untergrenze u = '))
o = float(input('Obergrenze o = '))
y0 = float(input('gewünschter Wert y = '))
k_step = float(input('Intervallschritt k = '))
i_step = float(input('Laufschrittweite i = '))

k = 0
i = u+k

L = [] # Kandidateniste im k-ten Teilintervall
K = [] # finale Kandidatenliste

while i <= o:
	while i <= u+k+k_step:
		y = cos(exp(i)) # Argument <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
		
		if y < y0+0.0000001 and y > y0-0.0000001 or y == y0:
			L.append(i)
		i = i+i_step
	
	if L != []:
		K.append(L[len(L)//2]) # Wenn es im k-ten Schritt Kandidaten gibt, füge nur den Kandidaten aus der Mitte der Liste L zur finalen Liste K hinzu.
	
	del L # Kandidateniste im k-ten Teilintervall wegschmeißen.
	L = [] # leere Kandidateniste für k+1 ten Teilintervall neu definieren.	
	k = k+k_step # k nach k-ten Schritt erhöhen
	i = u+k # Untergrenze nach Durchlauf des k-ten Schtrittes aktualisieren.
	
	
#print(K)	# finale Kandidatenliste ausgeben


# Liste K durchlaufen und alle Kandidaten durchnummeriert ausgeben.
zahl = 1
print('\n\nDas sind die Kandidaten im Intervall [' + str(u) + ',' + str(o) + '] für y = ' + str(y0) + ':')
for nullstelle in K:
	print('\n\tx' + str(zahl) + ' = ' + str(nullstelle))
	zahl = zahl+1

[Sirius3]

@hallo97: den Sinn von zwei verschachtelten while-Schleifen verstehe ich überhaupt nicht, warum darf es pro k-Intervall nur eine Nullstelle geben?

Variablen sollte man erst initalisieren, wenn man sie braucht. `L` wird erst in der inneren while-Schleife gebraucht, also initalisiert man sie erst in der Zeile davor. Dann brauchst Du auch nicht dieses komische Konstrukt, `L` nach der while-Schleife wieder zu leeren. Das `del` in Zeile 26 ist absolut überflüssig, wenn Du in der Zeile danach `L` gleich wieder einen Wert zuweist. `del` an sich wird so gut wie nie gebraucht und dann in 99% der Fälle um ein Element aus einem Wörterbuch zu löschen.

Zeile 19: wenn y im Interval y0-0.0000001 und y0+0.00000001 liegt, dann ist der Fall y=y0 auch abgedeckt, wobei Gleichheit bei Floatingpoint selten erreicht wird. Kurz schreibt man das als `abs(y-y0) < 1e-7`.

Zeile 36ff: wenn Du eine Zählvariable brauchst, nimm `enumerate`. Statt Strings mit + zusammenzustückeln, nimm .format.

Code: Alles auswählen

print('\n\nDas sind die Kandidaten im Intervall [{}, {}] für y = {}:'.format(u, o, y1))
for zahl, nullstelle in enumerate(K, 1):
    print('\tx{} = {}'.format(zahl, nullstelle))

Die Zählung ist auch falsch, da Du absichtlich und unabsichtlich Nullstellen überspringst. Deine Prüfung, ob Du eine Nullstelle hast, ist nicht gut, da Du ja genau in dem 1e-7-Intervall landen mußt, um das zu wissen, bzw. auch Werte als Nullstelle genommen werden, die gar keine sind. Aber wie schon ganz am Anfang geschrieben, gibt es deutlich schnellere, einfachere und bessere Algorithmen, um Nullstellen zu suchen.

[hallo97]

Ich habe deswegen zwei Whileschleifen genommen, da mir sonst nur ein Kandidat(wen es ihn geben sollte) zurückgegeben wird. Das will ich aber nicht. Es sollen alle Kandidaten im vorgegebenen Intervall ausgegeben werden und nicht nur einer. Deshalb wird das Intervall in k-Schritten durchlaufen. Das es dort nur eine Nullstelle geben soll, sage ich nicht, es wäre nur gut, wenn es so ist.
Deshalb sollten die k-Schritte so gewählt werden, dass eben nur eine im k-ten Schritt vorkommt. Das habe ich auch schon weiter oben schon beschrieben, da sonst nur ein Kandidat (statt alle) ausgegeben wird.
Ja, es kann passieren, dass die k-Schritte blöd gewählt sind, aber da muss dann doch zunächst auf eine graphische Darstellung übergewechselt werden, um zu sehen, welche Schrittweite gut wäre. Das wäre halt eine kritische Stelle.

Wie gesagt, dass hier soll ein Anfang für mich sein, dem Computer zu sagen, was er tun soll. Das mache ich erst seit paar Monaten.