LOGIN | NEU REGISTRIEREN

Schule > Mathematik > Algebra und Funktionen > Numerische Verfahren zur Berechnung der n-ten Wurzel

Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
EINLEITUNG DAS VERFAHREN DURCH INTERVALLSCHACHTELUNG Beweis Programm DAS VERFAHREN VON HERON Programm 1.) Scheitelpunkt n r 2.) Monotonie 3.) Differenzsumme Wir stellen fest: Graphische Interpretation Erweitern des Definitionsbereichs VERGLEICH DER ALGORITHMEN VERGLEICH DER ALGORITHMEN Fazit QUELLEN ANLAGEN
3 4 5 5 7 7 8 9 9 10 11 12 12 13 13 14 14
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r

Einleitung
Heutzutage wundert sich niemand darüber, wie der Taschenrechner die numerische (nicht algebraisch ausgedrückte) Lösung der Gleichung x n - r = 0 ausspuckt, denn genaugenommen ist das ja die n-te Wurzel aus r. Doch wie hätten es die Griechen der Antike vor 2000 Jahren gemacht? Welche Algorithmen hätten sie dabei verwendet können? Diese Frage möchte ich nun in meiner Hausarbeit beantworten. Sicherlich gibt es unzählige Methoden zur Ermittlung der Lösung dieser Gleichung, doch ich möchte mich auf zwei Methoden, der Intervallschachtelungsmethode und der Methode von Heron, beschränken. Ich werde sie jeweils vorstellen, beweisen, sie in einem Programm anwenden, Überlegungen zur Definitionsmenge machen und schließlich diese beiden Algorithmen vergleichen. Da in beiden Methoden konvergierende Folgen unverzichtbar sind, werden in den Beweisen Wissen über Grenzwertrechnung vorausgesetzt. Für die beiden Programme sind Pascal-Kenntnisse nicht unbedingt notwendig, doch um diese ausprobieren zu können, sind ein PC und ein Pascal-Compiler erforderlich. Die beiden Programme bergen zu Gunsten besseren Verständnisses kleinere Mängel, die aber leicht ausgebügelt werden können. Ob diese Methoden tatsächlich auch in den Taschenrechner eingesetzt werden, das weiß ich nicht, hängt es doch von der Chiparchitektur ab, worüber ich nicht recherchiert habe. Dank noch an Jan Leike, der diese Hausarbeit auf Fehler untersucht hat.
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
Das Verfahren durch Intervallschachtelung
Bei dieser Methode nähert man sich durch geschicktes Einsetzen von Schätzwerten der Nullstelle der Funktion f : x a x n - r im Intervall [0; [ . Dabei wählt man die zwei Startwerte so, dass die Nullstelle x dazwischen liegt, d.h. ein f (a0 ) < 0 und ein f (b0 ) > 0 . Da die Funktion f im
100 80 60 40 20
1 -20
Intervall [0; [ stetig und streng monoton steigend ist (Abb.1), gilt der Nullstellensatz: Aus f (ai ) < 0 < f (bi ) folgt a i < x < bi
Abb.1
1 Definitionsbereich: n N { } ; r R0+ ; x := n r
Ein Beispiel wäre a0 = 0 und b0 = r + 1 , denn für ein positives r gilt immer: 0<r 1. für 0 < r < 1 : 2. für r > 1 : r
n -1 n n n
>1
-1 n 1 n
0 < rn <1
r r
>1

0 < x < r +1
r>r r +1 > x Es ist also x ]a0 ;b0 [ größer als x, also liegt x im Intervall ]a0 ; m[ . Ist umgekehrt f (m) kleiner als 0, so ist m und erhalten das halb so lange Intervall ]a1;b1[ . Im zweiten Fall setzen wir stattdessen a1 = m und b1 = b0 . Wenn man diesen Vorgang beliebig wiederholt, erhält man x mit Nun bildet man aus a0 und b0 den Arithmetischen Mittel m. Ist f (m) größer als 0, so ist m
kleiner als x, also liegt x im Intervall ]m;b0 [ . Im ersten Fall setzen wir a1 = a0 und b1 = m
beliebiger Genauigkeit. Für den Fall jedoch, im dem f (m ) = 0 ist, gilt m = x , und weitere Wiederholungen erübrigen sich.
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r

Beweis
Das Startintervall ]a0 ;b0 [ hat die Länge a0 - b0 = 0 - (r + 1) = r + 1 . Bei jedem weiteren Intervall halbiert sich also die Intervalllänge l. Ein Intervall ]ai ; bi [ hat daher die Länge
1 (r + 1) . Da x sich in diesem Intervall befindet, ist also ]ai ; x[ kürzer als ]ai ; bi [ . Nun 2 findet man für jede noch so kleine Zahl e einen Intervall ]ai ; bi [ , dessen Länge l kleiner ist
e als e, nämlich für alle i > log 1 . Wenn die Länge des Intervalls ]ai ; bi [ kleiner als e r +1 2 ist, so ist gewiss auch die Länge des Intervalls ]ai ; x[ kleiner als e. Daher gilt
lim a
=x=n r.
Dasselbe gilt auch für bi . q.e.d.

Programm
program Intervall_Methode; const e = 0.00000001; {Genauigkeit} var a, b, m, r: real; n, z: integer; function f(x, r: real; n: integer): real; var i: integer; p: real; begin p := 1; for i := 1 to n do p := p * x; f := p - r; end; begin z := 0; {Iterationszähler} write('Radiant : '); readln(r); write('Exponent: '); readln(n); a := 0; b := r + 1; repeat inc(z); m := (a + b) / 2.0; if f(m, r, n) > 0 then b := m else a := m; writeln('] ',a:15:8,' ; ',b:15:8,' [' ); until (abs(a-b) < e); writeln('========================================'); writeln('Endergebnis: ', a:15:8); writeln(z, ' Durchläufe'); readln; end.
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
Erweitern des Definitionsbereichs
1 Wir rufen in Erinnerung, wie wir anfangs r und n definiert haben: n N { } ; r R0+
Würden wir nun für n alle Zahlen R0+ einsetzen, so ist die Bedingung, dass der Graph stetig und streng monoton steigend ist, immer noch erfüllt. D.h. das Verfahren würde immer noch funktionieren. Gehen wir einen Schritt weiter, und nehmen R0- auch noch dazu, so müssen wir beachten, dass für R0- ein f (a 0 ) = f (0) nicht definiert ist. Daher müssen wir ein a 0 wählen, der eben nahe genug bei Null ist und kleiner als x ist. Außerdem müssen wir die Rolle von ai und bi vertauschen, da der Graph eine Hyperbel und deshalb streng monoton Abb.2 fallend ist (Abb.2): Für f (ai ) < 0 < f (bi ) gilt nun. Daher funktioniert die ursprünglich beschriebene Methode nicht mehr. Für n = 0 erhalten wir ohnehin nur eine Parallele zur x-Achse. Würden wir für r eine negative Zahl einsetzen, so hätte die Funktion f : x a x n - r keine Nullstelle im positiven Bereich(Abb.3), und f (a 0 ) und f (b0 ) wären beide größer als Null. Eine nicht vorhandene Nullstelle lässt sich nicht finden. Es sei denn, n wäre eine ungerade Abb.3 Zahl und a 0 und b0 sind so gewählt, dass die Nullstelle dazwischen liegt. Diese negative Nullstelle wäre allerdings nicht mehr die ,n-te Wurzel aus r".
8 6 4 2 5 10 15 20 -2
-6
-4
-2
-2
-4
Wir definieren also neu: n R + ; r R0+ ;
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r

Das Verfahren von Heron
Dieses Verfahren wurde ursprünglich von Heron (griechischer Mathematiker und Physiker, 60 v.Chr. Alexandria) für die Berechnung der Quadratwurzel entwickelt. Jedoch lässt sich dieses Verfahren auf Berechnung n-ter Wurzeln erweitern. Ähnlich wie bei der ersten Methode wiederholt man solange, bis die gewünschte Genauigkeit erreicht ist.
1 Definitionsbereich: n N { } ; r , x0 R + ; x 0 sei ein beliebiger Schätzwert Dabei befolgt man die folgende Iterationsvorschrift: r + (n - 1) x n -1 und xi +1 = f ( xi ) ; f :xa x n r Das kann man sich so erklären: ist x > n r , so ist n -1 < n r , also bildet man aus den x beiden Zahlen den Arithmetischen Mittel, wobei, man x mehr gewichtet ( (n - 1)x ). Je öfter man das macht, je näher kommt man an die Nullstelle des Terms x n - r .

Programm
program Heron_Methode; const e = 0.00000001; {Genauigkeit} var x, r, ergebnis: real; n, z: integer; function potenzieren(a: real; b: integer): real; var i: integer; c: real; begin c := 1; for i := 1 to abs(b) do c := c * a; if (b < 0) and (c <> 0) then c := 1/c; {für negative n} potenzieren := c; end; function f(x, r: real; var n, z: integer): real; begin inc(z); x := ((r / potenzieren(x, n-1)) + (n - 1) * x) / (n * 1.0); writeln(x:15:8); if (abs(r - potenzieren(x, n)) < e) then f := x else f := f(x, r, n, z); end; begin write('Radiant : '); readln(r); write('Exponent : '); readln(n); write('Schätzwert: '); readln(x); z := 0; {Iterationszähler} ergebnis := f(x, r, n, z); writeln('====================') ; writeln('Endergebnis: ', ergebnis:15:8); writeln(z, ' Durchläufe'); readln; end.
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
Beweis
1.) Scheitelpunkt

Für x0 < n r gilt:

r >1 x0 wegen n > 1 gilt des Weiteren:
1 1 1 rn rn rn + + ... > n x0 x0 x0 da von den n Summanden auf der linken Seite n-1 Summanden größer als 1 sind und ein Summand gleich 1 ist. 1 rn Nun multipliziert man auf beiden Seiten -1 , das größer als 0 ist und deswegen die x0 Ungleichheitszeichen nicht umkehrt. 1 rn x0 1 rn x0 1 rn n - 1 n -1 > x -1 1 rn +1 > n x0
n n n -1 n-2 n-n
1 n

r + n - 1 x0 1 x n 0 > rn n r + (n - 1)x0 n -1 1 x0 > rn n Für x0 > n r gilt:

rn <1 x0
1 1 1 rn rn rn + + ... < n x0 x0 x0 da von den n Summanden auf der linken Seite n-1 Summanden kleiner als 1 sind und ein Summand gleich 1 ist.
n -1 n-2 n-n
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
1 rn Nun multipliziert man auf beiden Seiten -1 , das kleiner als 0 ist und deswegen die x0 Ungleichheitszeichen umkehrt. 1 rn x0 r 1 rn n - 1 n -1 > x
x0
n -1
+ (n - 1)x0 n
> rn

gilt f (x0 ) = n r .
Das heißt, für alle x 0 R + und x0 n r gilt f (x0 ) > n r . Nur für Scheitelpunkt x0 = n r Das heißt wiederum, dass x1 = f ( x0 ) immer größer ist als
r , wenn wir ausschließen,
dass die erste Schätzung schon ins Schwarze trifft und x0 = r .
2.) Monotonie

Für i 1 gilt also aus 1.) xi > r und daraus folgt:
1 n
xi > r r xi > n -1 xi
(n - 1)xi + xi
r xi > xi
n -1
r xi
n -1
+ (n - 1)xi
+ (n - 1)xi n
x i > f ( xi )
xi > xi +1 > xi + 2 > ... > n r
3.) Differenzsumme
a)
r xi - xi +1 = xi - xi
n -1
+ (n - 1)xi n = xi - xi -
r xi
n -1
- xi =-
r xi
n -1
- xi
Erstellt von Yang Guo
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
b) Aus 2.) xi > xi +1 folgt: r r + xi +1 < + xi n -1 n -1 xi xi +1 r r - xi < - xi +1 n -1 n -1 xi xi +1 r r - xi - xi +1 n -1 n -1 xi xi +1 - >- n n xi - xi +1 > xi +1 - xi + 2 > xi + 2 - xi + 3 > ... c) Die Summe der Differenzen ist (x1 - x2 ) + (x2 - x3 ) + ... = x1 - x
Das heißt, die Folge (x1 - x2 ) , ( x2 - x3 ) , ... konvergiert gegen 0, da xi - xi +1 > xi +1 - xi + 2 > ... . Würde die Folge divergieren oder gegen eine Zahl ungleich 0 konvergieren, müsste die Folgensumme unendlich sein, was aber nicht der Fall ist ( x1 - x ist endlich). Das heißt wiederum, dass für ein i gilt xi - xi +1 = 0 .

Wir stellen fest:
lim( xi - xi +1 ) = 0
r lim-
xi
n -1
- xi =0
lim
r xi
n -1
= xi
lim xi = r
lim x
=nr
q.e.d.
Erstellt von Yang Guo
10
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
Graphische Interpretation
Der Graph (Abb.4) für die Funktion f : x a x
n -1
+ (n - 1) x
bereits festgestellt haben, einen Scheitelpunkt bei sich der Graph an die Gerade n -1 x und je näher x bei 0 n ist, je mehr schmiegt sich der Graph an die y-Achse: r + (n - 1)x n -1 x n -1 lim = x x n n r + (n - 1)x x n -1 lim = x 0 n
hat, wie wir im Beweis n r . Je größer x ist, je mehr schmiegt

Abb.4
Um zu erreichen, dass der Funktionswert f ( xi ) immer wieder zurück auf die x-Achse kommt, um erneut das f ( xi +1 ) zu bilden, werden die Funktionswerte einfach am Graph x a x gespiegelt: Dabei ist immer gewährleistet, dass xi +1 = f ( xi ) . Die waagerechten Streckenzüge sind die Differenzen x0 - x1 , x1 - x2 , usw., die gegen 0 strebt, wie man am Graph (Abb.5) sieht. Da (fast) alle f ( x ) > n r , ist spätestens x1 auf der rechten Seite vom Schnittpunkt der Graphen f x a x . Deutlich sieht man, wie sich xi durch die ,Zickzackkurve" dem Schnittpunkt der beiden Graphen nähert. Der Schnittpunkt ist: r + (n - 1) x r x n -1 x= nx - (n - 1) x = n -1 x = n r n x n Also nähert sich xi an r
Abb.5
Erstellt von Yang Guo
11
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r
Erweitern des Definitionsbereichs
1 Wir rufen in Erinnerung, wie wir anfangs definiert haben: n N { } ; r , x0 R0+ Ich werde nun nur graphisch argumentieren, da ein Beweis doch ziemlich aufwändig wäre. - Würden wir nun für n alle Zahlen R0+ einsetzen, so ändert sich für n > 1 nichts, aber für 0 < n < 1 ist der Faktor (n - 1) negativ. Obwohl dann im Beweis vieles nicht mehr 1 stimmt, zeigt der Graph (Abb.6) für n = 3 doch, dass es funktioniert. Allerdings muss dazu x 0 zwischen 0 und der Nullstelle von f sein, da sonst die Iteration divergieren würde. - Gehen wir einen Schritt weiter, und nehmen R0- auch noch dazu, so schneiden sich die Graphen immer noch an der richtigen Stelle und die Iteration (Zickzackkurve) strebt dagegen(Abb.6). Auch hier muss aber x 0 zwischen 0 und der Nullstelle von f sein, um ein Divergieren zu verhindern. - Für n = 0 wäre f(x) nicht definiert, aber eine Gleichung x 0 = r mit r 1 hat sowieso keine Nullstelle. - Bei einem negativen r schneiden sich die Graphen f(x) und x a x nicht (Abb.8) - Den Schätzwert x kann auch negativ sein, für ein gerades n strebt die Iteration aber gegen die negative Lösung (Abb.9, n = 2), für ein ungerades n jedoch geht alles gut (Abb.10, n = 3). Nur für die Zahl 0 ist f ( x ) nicht definiert.
60 40 20 -30 -20 -10 10 20 -20 -40 -60 -80
Abb.6
Abb.7

30
Also können wir neu definieren: zu Sicherheit n R + ]0;1[ ; r R0+ ; x0 R {0} Dabei müssen wir beachten: lim xi = n r ;
Abb.8
Abb.9
Abb.10
Erstellt von Yang Guo
12
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r

Vergleich der Algorithmen
Der wichtigste Aspekt im Vergleich zwischen den beiden Algorithmen ist wohl das Verhältnis zwischen Anzahl der Wiederholungen (Iterationen) und die Genauigkeit. Dafür lassen wir beide Algorithmen jeweils Wurzeln auf 8 Stellen genau ausrechnen und vergleichen dann die Anzahl der Wiederholungen: Intervallschachtelung 37 35 32 29 Heron mit Schätzwert 10 6 12 46 82
4 6
1000 200 20 30
35
Wir sehen, dass mit zunehmendem Exponenten die Methode von Heron länger braucht und mit zunehmendem Radianten die Intervallschachtelungsmethode länger braucht. Besonders eindrucksvoll ist natürlich die Heron-Methode bei 4 1000 , die er mit 6 Iterationen schon auf 8 Stellen genau berechnet. Der Grund für die Effizienz bzw. Ineffizienz liegt darin, dass die Iteration der HeronMethode im Grunde nur im ,Korridor" zwischen dem Graphen von f und dem Graphen x a x abspielt, wie wir in der Abb.5 sehen. Je größer der Exponent n, je steiler wird die n -1 Schrankenfunktion x und somit auch f im Bereich [ n r ; [ . Damit wird mit n zunehmenden n auch der ,Korridor" schmaler und steiler. Deshalb werden mehr ,Zickzacks" gebraucht, um sich n r zu nähern. Beim Intervallschachtelungsmethode hängt die Anzahl der Wiederholungen hauptsächlich davon ab, wie groß das Intervall ]a 0 ;b0 [ ist, da diese mit jeder Wiederholung halbiert wird und damit die Genauigkeit erreicht. Da nun a0 = 0 und b0 = r + 1 , hängt es nun letztendlich von r ab.

Fazit
Bei kleineren Exponenten und großen Radianten sollte man sich für die Methode von Heron entscheiden und bei großen Exponenten und kleinen Radianten bevorzugt die Methode der Intervallschachtelung anwenden. Wenn aber die Operationen sowieso vom Computer durchgeführt werden, ist es meist egal. Generell gilt aber, dass bei großen Exponenten die Rechnung länger dauert als bei kleinen, da die Potenzen bei beiden Methoden gebildet werden. Würde man alles mit Stift und Papier machen wollen, würde ich eher die Heronsche Methode empfehlen, da bei kleinen Exponenten, die ja in diesem Fall zu erwarten ist, nur wenige Iterationen erfordert. Natürlich verkürzt eine gute Wahl des Schätzwertes x 0 , a 0 und b0 die Rechnung noch erheblich.
Erstellt von Yang Guo
13
Hausarbeit Mathematik 2002/2003 : Berechnung der n-ten Wurzel aus r

Quellen
Das World Wide Web Das Buch ,Infinitesimalrechnung 1" vom Bayerischen Schulbuch-Verlag Eigene Überlegungen
Anlagen
Die beiliegende CD enthält diese Hausarbeit, Programmbeispiele und ein PascalCompiler.
Erstellt von Yang Guo
14

Download: PDF, PDF