Algorithmus für die n-te Wurzel einer Zahl

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;
}