Algorithmus für die n-te Wurzel einer Zahl

[Stiefel2000]

Ich habe gerade zu meinem letzten Beispiel mit den Startwerten rumgespielt und es kam heraus, dass der Wert 10 mit ziemlichem Vorsprung gewonnen hat. Bleibt nur die Frage, ob das jetzt am spezifischen Problem lag...
Der Vorschlag deiner Abbruchbedingung gefällt mir eher weniger gut - das würde ja bedeuten, dass ich in jedem Schleifendurchlauf eine extra Potenz berechnen muss. Bei meinem letzten Beispiel wird das sicher Längen mehr Rechenzeit fressen, als die Differenzbildung der letzten beiden Werte.

10^-10 klingt aber sehr gut - ich bin eben mal an die Grenzen des doubles gegangen, allerdings ist dann Methode drei nicht mehr nutzbar (wird gar nicht fertig).

EDIT:

double _root(double x , unsigned int n)		//n-te Wurzel aus x soll berechnet werden
{	double base = 2;
	double buffer = 0;
	while(_betrag(base - buffer) > 0.00000000000001)
	{	buffer = base;
		base -= base / n - x / (_potenz_lu(base , n - 1) * n);
	}
	return(base);
}

Die Funktion ist Sieger geworden - ein letztes Dankeschön und ich mache mich an die nächste Aufgabe...

[Heinzelotto]

Stiefel2000 schrieb:

Der Vorschlag deiner Abbruchbedingung gefällt mir eher weniger gut - das würde ja bedeuten, dass ich in jedem Schleifendurchlauf eine extra Potenz berechnen muss. Bei meinem letzten Beispiel wird das sicher Längen mehr Rechenzeit fressen, als die Differenzbildung der letzten beiden Werte.

Jo, das stimmt
Du musst aber auch bedenken, dass -- besonders bei hohen Potenzen -- auch schon ein kleines x-delta in großen Differenzen resultiert:

octave:1> (10.00000000001)^42-10^42
ans =  4.1996e+31

Das heißt, angenommen, du berechnest die 42. Wurzel aus 10^42 (=10), es wird im schlechtesten Fall als ergebnis etwas um 10^21 verschiedenes herauskommen
Das sind aber auch sehr extreme Werte, bei deinem Beispiel mit der 42. Wurzel aus 73019 ist die genauigkeit ca. 2*10^-4, was ja im prinzip ausreichen sollte...

EDIT: alles klar

[Stiefel2000]

Mmh, jetzt hast du mich nachdenklich gestimmt. Ich habe vorher nicht daran gedacht, dass sich der Fehler potenziert. Was nun? Gibt es noch eine bessere Abbruchbedingung, die sowohl Genauigkeit als auch Geschwindigkeit liefert?

EDIT: Mir fällt gerade ein: Wenn ich als Differenz beider Werte nur 10^-12 zulasse...dann wäre es ja optimal, wenn ich exakt 10^-11 erreiche und dann einen weiteren Schritt durchführe, weil das Newton-Verfahren ja quadratisch konvergiert (die Genauigkeit des Doubles wäre damit also mehr als ausgereizt). Allerdings habe ich keine Idee, wie ich diesen Balance-Akt trotz der starken Konvergenz hinbekommen könnte.

[Bashar]

Es gibt aufgrund der quadratischen Konvergenzordnung beim Newton-Verfahren überhaupt keinen Grund*, sich mit einer Genauigkeit von 10^-10 o.ä. zufriedenzugeben. Überhaupt ist der absolute Fehler hier ein völlig uninteressantes Maß, wenn dann willst du den relativen Fehler reduzieren. Und zwar so weit, dass er im Rundungsfehler aufgeht.

[volkard]

Bashar schrieb:

Es gibt aufgrund der quadratischen Konvergenzordnung beim Newton-Verfahren überhaupt keinen Grund*, sich mit einer Genauigkeit von 10^-10 o.ä. zufriedenzugeben. Überhaupt ist der absolute Fehler hier ein völlig uninteressantes Maß, wenn dann willst du den relativen Fehler reduzieren. Und zwar so weit, dass er im Rundungsfehler aufgeht.

Jo.
Deswegen schlug ich vor

while x sinkt

also solange mathematisch alles in Ordnung ist. Die Schleife terminiert erst, wenn die Rechengenauigkeit erreicht ist und Mikrounfug passiert.

[Bashar]

Schönes Wort

Ich hab ja letztens hier eine Funktion zum Wurzelziehen gepostet, die bei Gleichheit zweier aufeinanderfolgender Folgenglieder abbricht. Das hat auch funktioniert, aber

volkard schrieb:

Mikrounfug

kann man wahrscheinlich nicht immer ausschließen.

[Stiefel2000]

volkard schrieb:

Deswegen schlug ich vor

while x sinkt

Was genau schlägst du damit vor? Etwa das, was ich auch umgesetzt habe? Oder beziehst du dich auf "f(x) sinkt"? Letzteres habe ich auf Grund der Rechenzeit weiter oben ja schon ausgeschlossen.

Bashar schrieb:

Es gibt aufgrund der quadratischen Konvergenzordnung beim Newton-Verfahren überhaupt keinen Grund*, sich mit einer Genauigkeit von 10^-10 o.ä. zufriedenzugeben. Überhaupt ist der absolute Fehler hier ein völlig uninteressantes Maß, wenn dann willst du den relativen Fehler reduzieren. Und zwar so weit, dass er im Rundungsfehler aufgeht.

Ich muss gestehen, dass ich nicht ganz verstehe, was du mir sagen willst. Wenn du mit absolutem Fehler die endgültige Abweichung von der wirklichen Nullstelle meinst, mit relativem Fehler die Differenz zweier aufeinanderfolgender Schätzungen, dann wäre das doch nicht richtig, oder? Wenn du nun mit relativem Fehler den Fehler relativ zur exakten Nullstelle meinst...was ist dann der absolute Fehler?
Was die Genauigkeit angeht, hast du natürlich Recht - dank quadratischer Konvergenz kann man da sehr einfach sehr viel rausholen. Aber die Frage nach einer Abbruchbedingung, die dies ohne großen Rechenaufwand ermöglicht, bleibt deshalb bestehen.

EDIT: Ich habe gerade überlegt, ob eine for-Schleife evt. die while-Schleife ersetzen sollte? Wieviele Schritte braucht denn das Newton-Verfahren im schlimmsten Fall, um die Nullstelle auf 10^-16 zu berechnen? Evt. könnte ich ja vom Standard-Startwert weggehen und für jede Funktion einen besseren Startwert ermitteln, damit ich im Laufe von höchstens 10 Schritten (o.ä.) meine Genauigkeit erreiche?

[volkard]

Stiefel2000 schrieb:

volkard schrieb:

Deswegen schlug ich vor

while x sinkt

Was genau schlägst du damit vor? Etwa das, was ich auch umgesetzt habe? Oder beziehst du dich auf "f(x) sinkt"? Letzteres habe ich auf Grund der Rechenzeit weiter oben ja schon ausgeschlossen.

Neun. Du machst

base=2
buffer=0
while(_betrag(base - buffer) > 0.00000000000001)

ich mache

base=x
buffer=0
while(base > buffer)

[volkard]

Stiefel2000 schrieb:

EDIT: Ich habe gerade überlegt, ob eine for-Schleife evt. die while-Schleife ersetzen sollte? Wieviele Schritte braucht denn das Newton-Verfahren im schlimmsten Fall, um die Nullstelle auf 10^-16 zu berechnen? Evt. könnte ich ja vom Standard-Startwert weggehen und für jede Funktion einen besseren Startwert ermitteln, damit ich im Laufe von höchstens 10 Schritten (o.ä.) meine Genauigkeit erreiche?

dann berechne mal die hundertste wurzel aus 2. sollte viel langsamer konvergieren als eine schnöde zweite wurzel.

[Bashar]

Stiefel2000 schrieb:

Ich muss gestehen, dass ich nicht ganz verstehe, was du mir sagen willst. Wenn du mit absolutem Fehler die endgültige Abweichung von der wirklichen Nullstelle meinst, mit relativem Fehler die Differenz zweier aufeinanderfolgender Schätzungen, dann wäre das doch nicht richtig, oder? Wenn du nun mit relativem Fehler den Fehler relativ zur exakten Nullstelle meinst...was ist dann der absolute Fehler?

Der absolute Fehler ist die Differenz zwischen Näherung und wahrem Wert, der relative Fehler ist der Quotient aus dem absoluten Fehler und dem wahren Wert.

[Stiefel2000]

volkard schrieb:

ich mache

base=x
buffer=0
while(base > buffer)

Dann müsste ich aber bei negativen x einen kleinen Sonderfall einbauen - und ich bin nicht ganz sicher, ob ich mich mit dem Newton-Verfahren auch garantiert von links der Nullstelle nähere. Das hängt im schlimmsten Fall von x ab, das kann ich allerdings a priori nur raten. (ich habe vorhin ein paar weitere Möglichkeiten ausprobiert, aber die Konvergenzgeschwindigkeit steigt immer nur für einen Teil von Zahlen)
EDIT: Vielleicht bietet sich x=1 an, 1 ist schließlich nur seine eigene Wurzel. Aber dann wären Zahlen zwischen 0 und 1 evt. problematisch...

Bashar schrieb:

Der absolute Fehler ist die Differenz zwischen Näherung und wahrem Wert, der relative Fehler ist der Quotient aus dem absoluten Fehler und dem wahren Wert.

Achso, jetzt wo du es sagst, ist es klar :). Ich bin mir nur gerade nicht sicher, was jetzt wirklich zu größerer Genauigkeit führt. Bei Zahlen zwischen 0 und 1 ist es wohl der relative Fehler, bei Zahlen größer 1 dann der absolute.

Gibt es denn keine Möglichkeit, die 15. Wurzel aus 20395820395409652 mit einer gaanz einfachen Regel so anzunähern, dass ich die Zahl der nötigen Iterationen zumindest ein wenig einschränken kann? Ich habe vorhin z.B. probiert x/n (x = Zahl, 1/n = Exponent), aber damit war kein Blumentopf zu gewinnen. Das Problem stellt sich übrigens bei allen möglichen Nullstellen-Berechnungen, die ich bisher durchgeführt habe - wie kommt man an Informationen über die Nullstelle, wenn man selbst noch gar nichts über die Funktion weiß?

[volkard]

Stiefel2000 schrieb:

Dann müsste ich aber bei negativen x einen kleinen Sonderfall einbauen

Dann erinnere Dich an mein zweites Posting.

- und ich bin nicht ganz sicher, ob ich mich mit dem Newton-Verfahren auch garantiert von links der Nullstelle nähere.

Ups, es sollte sich von rechts nähern.

Das hängt im schlimmsten Fall von x ab, das kann ich allerdings a priori nur raten.

Ich fange rechts an, dann bleibts auch rechts. Garantiert beim Wurzelsuchen.

(ich habe vorhin ein paar weitere Möglichkeiten ausprobiert, aber die Konvergenzgeschwindigkeit steigt immer nur für einen Teil von Zahlen)

Ich habe nicht abgeschätzt, welche Kosten es erzeugt, x als Startwert zu nehmen, statt einer besseren Abschätzung.

Gibt es denn keine Möglichkeit, die 15. Wurzel aus 20395820395409652 mit einer gaanz einfachen Regel so anzunähern, dass ich die Zahl der nötigen Iterationen zumindest ein wenig einschränken kann?

Mir fällt nur ein:
Schaust Dir die Bits im double mal genau an.
20395820395409652=0.566097735227579001993092333577812^55
Du dividierst frecherweise den Exponent durch 15
x=0.566097735227579001993092333577812^4=9.057563763641264031889477337232

[volkard]

Stiefel2000 schrieb:

Das Problem stellt sich übrigens bei allen möglichen Nullstellen-Berechnungen, die ich bisher durchgeführt habe - wie kommt man an Informationen über die Nullstelle, wenn man selbst noch gar nichts über die Funktion weiß?

Rumraten.
Aber hier beim Wurzelziehen wissen wir ja schon recht viel.

[volkard]

Übrigens brauchst Du die Abfrage eh, weil negative Zahlen nur bei ungeraden Wurzelexponenten gehen.

[Stiefel2000]

volkard schrieb:

- und ich bin nicht ganz sicher, ob ich mich mit dem Newton-Verfahren auch garantiert von links der Nullstelle nähere.

Ups, es sollte sich von rechts nähern.

Startwert sei jetzt 1 (weil die 1 so schön ist): Dann ist z.B. die Wurzel aus 2 bei 1,4, ich nähere mich der Lösung also sicher von links. Ich traue dem Verfahren mal zu, dass es nicht "um die Nullstelle herumhüpft".
Bei der Wurzel aus 0,25 nähere ich mich dann übrigens von rechts.

volkard schrieb:

Das hängt im schlimmsten Fall von x ab, das kann ich allerdings a priori nur raten.

Ich fange rechts an, dann bleibts auch rechts. Garantiert beim Wurzelsuchen.

Wenn du immer rechts anfangen wolltest, müsstest du dann nicht unendlich als Startwert nehmen?

volkard schrieb:

Gibt es denn keine Möglichkeit, die 15. Wurzel aus 20395820395409652 mit einer gaanz einfachen Regel so anzunähern, dass ich die Zahl der nötigen Iterationen zumindest ein wenig einschränken kann?

Mir fällt nur ein:
Schaust Dir die Bits im double mal genau an.
20395820395409652=0.566097735227579001993092333577812^55
Du dividierst frecherweise den Exponent durch 15
x=0.566097735227579001993092333577812^4=9.057563763641264031889477337232

Das ist gar keine schlechte Näherung, das sollte zumindest bei großen Zahlen eine gewisse Arbeitserleichterung mit sich bringen. Wie genau komme ich an diesen Teil des doubles?

volkard schrieb:

Übrigens brauchst Du die Abfrage eh, weil negative Zahlen nur bei ungeraden Wurzelexponenten gehen.

Das ist klar - aber ich denke, dass das Newton-Verfahren an sich da schon die richtige Lösung finden wird.

[volkard]

Stiefel2000 schrieb:

Startwert sei jetzt 1 (weil die 1 so schön ist): Dann ist z.B. die Wurzel aus 2 bei 1,4, ich nähere mich der Lösung also sicher von links. Ich traue dem Verfahren mal zu, dass es nicht "um die Nullstelle herumhüpft".

Suche wurzel aus 2:
1
1,5
1,416666666
1,414215686
1,414213562
Wenn x >wuzel, dann ist das auch das folgende x >wurzel. Das ist ab dem zweiten x so. Einsehen kann man das gut geometrisch, indem man schaut, wie x^n-zahl verläuft und bei irgendeinem x rechts von der Wurzel die Tangente anlegt.

Suche Wurzel aus 0.25
1
0,625
0,5125
0,500152439
0,5000000232
0,5

Bei der Wurzel aus 0,25 nähere ich mich dann übrigens von rechts.

Du näherst Dich eigentlich immer von rechts, außer dem einen ersten Schritt.

Wenn du immer rechts anfangen wolltest, müsstest du dann nicht unendlich als Startwert nehmen?

Es reicht irgend ein Wert, der größer als die Wurzel ist. Deswegen nahm ich die Zahl, aus der die Wurzel zu ziehen ist, unter der Annahme, daß die Zahl >1 ist.

Das ist gar keine schlechte Näherung, das sollte zumindest bei großen Zahlen eine gewisse Arbeitserleichterung mit sich bringen. Wie genau komme ich an diesen Teil des doubles?

Gefrickel mit Bits. Ich würde eine wohl union aus einem double und einer struct mit bitfield nehmen.

Mal wieder die 15. Wurzel aus 20395820395409652
x1=1
x2=1-(1^{15-20395820395409652)/(14*1}14)
x2=1456844313957833.21428571428571428571

x1=20395820395409652
x2=20395820395409652-(20395820395409652^{15-20395820395409652)/(14*20395820395409652}14)
x2=18938976081451819.71428571428571428571

Mir scheint, die 1 ist ein besser Startwert als meiner. Man müßte nur den ersten Schritt nicht in den Vergleich einbeziehen. Das würde sich dann auch fein damit vertragen, daß das Bitgefummle gelöst wird und man kaum noch AUssagen über den Startwert machen mag.

[volkard]

Stiefel2000 schrieb:

volkard schrieb:

Übrigens brauchst Du die Abfrage eh, weil negative Zahlen nur bei ungeraden Wurzelexponenten gehen.

Das ist klar - aber ich denke, dass das Newton-Verfahren an sich da schon die richtige Lösung finden wird.

Bei ungeradem Wurzelexponenten und negativer Zahl wird das Verfahren schon die Lösung finden. Aber der Schwung ins Negative kann weit ausschlagen. Die ganze Mühe um den besten Anfangsschätzwert wäre vergebens gewesen. Und bei geradem Wurzelexponent und negativer Zahl hast Du einen hübschen Zufallszahlengenerator, der leider nichts mit der Lösung zu tun hat. Es macht aber Spaß, ihm zuzuschauen und auf besonders große Ausshläge zu warten.

[ichnixplan]

Hi,

ich habe hier mal ein Programm für die n-te Wurzel geschrieben.

int wurzel;
          float wert2;

          printf("die wie vielte wurzel möchten sie ziehen?\n");
          fflush(stdin);
          scanf("%d", &wurzel);

          if(wurzel<0)
          casetwo();

         do{
              printf("welche zahl moechten sie wurzeln :d\n");
          fflush(stdin);
          scanf("%f", &wert2);
         }while(wert2<0);

    start=wert2;
    ergebnis=heron(wert2, start, wurzel);
    printf("die %d. wurzel aus %f ist %f \n", wurzel, wert2, ergebnis);

float heron(float wert, float start, int wurzel)
{
     int i=0;
     for(i=0;i<100;i++)
     {
          wert= ((wurzel-1)*potenz(wert, wurzel) + start)/(wurzel*potenz(wert, wurzel-1));
     }
     ergebnis=wert;
    return ergebnis;
}

float potenz(float wert, int wurzel)
{    int i=1;
     float pot=1;

     for(i=1;i<=wurzel;i++)
     {
     pot=pot*wert;
     }
     wert=pot;
return wert;
}