4. Algorithmus für die n-te Wurzel einer Zahl

Algorithmus für die n-te Wurzel einer Zahl

  • S

    Hallo,
    ich versuche gerade, die n-te Wurzel einer reellen Zahl zu berechnen. Allerdings habe ich keinen Ansatz für den zu verwendenden Algorithmus. Kann mir da jemand helfen? Oder zumindest ein gutes Stichwort geben?

    0
  • V

    Stiefel2000 schrieb:

    Hallo,
    ich versuche gerade, die n-te Wurzel einer reellen Zahl zu berechnen. Allerdings habe ich keinen Ansatz für den zu verwendenden Algorithmus. Kann mir da jemand helfen? Oder zumindest ein gutes Stichwort geben?

    direkt mit pow
    w3=pow(x,1.0/3.0);

    oder per eigener schleife mit "newtonsches näherungsverfahren"

    0
  • S

    Selbermachen ist die Devise ;).
    Das Newton-Raphson-Verfahren habe ich zufällig gerade programmiert, aber wenn ich den zugehörigen Wikipedia-Artikel lese, dann steht da nur was von der Quadratwurzel. Ich lese gleich mal weiter, hoffentlich habe ich was übersehen.

    EDIT: Ok, mir wird gerade klar, dass es einen Weg mit dem Newtonverfahren geben muss, es handelt sich ja um nichts weiteres als ein mageres Polynom. Aber was mache ich mit den nötigen Ableitungen? Wird das Verfahren für eine 10. Wurzel nicht ziemlich langsam? 😕

    EDIT 2: Jaja, das berühmte Brett vorm Kopf...
    Ginge es so?

    ....
while(fabs(f(x)) > precision)
{    x -= f(x) / (exponent * potenz(x , exponent -1));
}
....
    0
  • M

    das Newton-Verfahren kannst du auch für n-te Wurzel anwenden.
    Die Funktion für die du dann die Nullstelle suchst ist:

    a-x^n=0 wobei x dann deine n-te Wurzel von a ist.

    edit @edit: du brauchst bei dem Verfahren doch immer nur die erste Ableitung, und iterierst dich dann Schritt für Schritt an die Lösung ran.

    0
  • V

    anleitung zum 5. wurzel aus 18 berechnen:

    vorbereitung:

    vorzeichen prüfen und ablehnen oder positiv machen und im ergebnis wieder negativ

    gleichung bauen
    x^5=18

    nach 0 auflösen
    x^5-18=0

    funktion draus machen
    f(x)=x^5-18

    weil nämlich newtin nur sullstellen sucht.

    newton:

    x=18 //sicher größer als die wurzel
do
   x=x-f(x)/f'(x)
while x sinkt
ausgabe x

    das x=f(x)/f'(x) braucht natürlich
    f(x)=x^5-18
    und
    f'(x)=5*x^4

    0
  • V

    Stiefel2000 schrieb:

    Ginge es so?

    ....
while(fabs(f(x)) > precision)
{    x -= f(x) / (exponent * potenz(x , exponent -1));
}
....

    Jup.

    0
  • S

    Ok, erstmal vielen Dank für den Wink mit dem Zaunpfahl. Aber jetzt habe ich ein gewisses Problem:

    int main()
{    double x = 288;
     double rez_exponent = 5;
     double wurzel;
     ...
     wurzel = _super-wurzel-funktion_(x , rez_exponent);
     ...
}

double _super-wurzel-funktion_(double x , int rez_exponent)
{    double base = newton-NST-suchen(...);    //wie übergebe ich eine Funktion einer Variablen?
     return(base);     
}

    Normalerweise würde ich jetzt einen Funktionenpointer übergeben, aber das wäre in diesem Fall wohl etwas dämlich.

    0
  • V

    du willst f und f' an eine funktion übergeben? nee, das wird böse.
    newton-NST-suchen wird besser keine eigene funktion, sondern die
    _super-wurzel-funktion_ wird zu _super-wurzel-funktion-mit-newton-drin_

    0
  • S

    volkard schrieb:

    du willst f und f' an eine funktion übergeben? nee, das wird böse.
    newton-NST-suchen wird besser keine eigene funktion, sondern die
    _super-wurzel-funktion_ wird zu _super-wurzel-funktion-mit-newton-drin_

    Ok, das habe ich mir mittlerweile auch schon gedacht ;). Ich probier's gleich mal...

    EDIT:

    double _root(double x , unsigned int n)	//n-te Wurzel aus x soll berechnet werden
{	double base = 1;   //welcher Startwert bietet sich generell an?
	while()    //welche Abbruchbedingung sorgt fuer eine hohe Genauigkeit?
		base -= (_potenz_lu(base , n) - x) / (_potenz_lu(base , n - 1) * n);
	return(base);
}

    Soweit bin ich ersteinmal, jetzt versuche ich, durch Umformungen noch ein wenig Geschwindigkeit rauszukitzeln. Welche Hürden ich noch sehe, habe ich mal kommentiert :).

    EDIT2:
    So, das Programm läuft - also nochmal vielen Dank für eure Hilfe. Aber jetzt geht es gleich noch ein wenig in die Tiefe:

    Test: 42. Wurzel aus 73019

    while(_betrag(base - buffer) > 0.000000000001)
	{	buffer = base;
		base -= (_potenz_lu(base , n) - x) / (_potenz_lu(base , n - 1) * n);
	}

    Ergebnis: 1.3055577657875052644
    Time taken: 0.0000700950622558594

    while(_betrag(base - buffer) > 0.000000000001)
	{	buffer = base;
		base -= base / n - x / (_potenz_lu(base , n - 1) * n);
	}

    Ergebnis: 1.3055577657875052644
    Time taken: 0.0000090599060058594

    double summand = _potenz_lu(base , n - 1) * n;
	while(_betrag(base - buffer) > 0.000000000001)
	{	counter ++;
		buffer = base;
		if(counter % 2 == 0)
			summand = _potenz_lu(base , n - 1) * n;
		base -= base / n - x / summand;
	}

    Ergebnis: 1.3055577657865116148
    Time taken: c) 0.0002689361572265625

    Bei der letzten Version wollte ich ein paar Ableitungen einspaaren (und damit Potenzen), jedoch scheint das völlig daneben gegangen zu sein. Habt ihr noch Tipps, wo ich ein wenig Geschwindigkeit rausfeilschen kann?

    EDIT 3:
    Weiterer Test: 23. Wurzel aus 730193096092658018

    5.9795872242411514108
    Time taken: a) 0.0001971721649169922

    5.9795872242411514108
    Time taken: b) 0.0000779628753662109

    5.9795872242421372889
    Time taken: c) 0.0001778602600097656

    Dieses Mal hat Methode 3 gut aufgeholt, aber scheinbar ist die 2 noch immer am schnellsten. (Ja, es macht mir Spaß, an Algorithmen zu schrauben, bis sie möglichst schnell sind ;).)

    0
  • H

    als startwert ist 1 gut geeignet. Wenn du noch ein bisschen näher dran sein willst, kannst du aber auch x/n nehmen; ist aber im Grunde egal, Newton konvergiert quadratisch (also schnell), und bei dem Finden der n-ten Wurzel sogar immer, wenn man als startwert nicht gerade 0 nimmt 🙂

    Als abbruchbedingung: while(_potenz_lu(base , n) > epsilon), wobei epsilon in der Größenordnung 10^-10 sein sollte, schätze ich mal. Je nachdem, wie genau du das Ergebnis brauchst. Double kann zwar bis in den 10^-16er Bereich, aber wer weiß, was sich dann da für numerische Ungenauigkeiten abspielen, die dir vielleicht dein ganzes Ergebnis kaputtmachen...

    0
  • S

    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...

    0
  • H

    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 😉

    0
  • S

    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. 😕

    0
  • B

    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.

    0
  • V

    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.

    0
  • B

    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.

    0
  • S

    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?

    0
  • V

    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)
    0
  • V

    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.

    0
  • B

    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.

    0
Anmelden zum Antworten