|
>als auch mit Mathematica 3.0 tritt bei langsam konvergenten >Fixpunktiterationsverfahren Stellenverlust ein. Es ist klar, warum: >bei langen Rechnungen geht Mathematica davon aus, dass die hinteren >Dezimal-Stellen nach und nach unzuverlaessig werden, und druckt >diese dann gar nicht mehr aus. Diese Formulierung ist nicht ganz zutreffend. Mathematica "geht nicht davon aus, dass die hinteren Dezimal-Stellen nach und nach unzuverlaessig werden", sondern es berechnet explizit wieviele Stellen zuverlaessing sind (basierend auf der Precision der Input-Zahlen und dem lokalen Anstieg der Funktion). Manchmal verliert man Stellen In[1]:= N[10^-1, 50]^100//Precision Out[1]= 48 und manchmal gewinnt man Stellen. In[2]:= Cos[N[10^-10,30]]//Precision Out[2]= 50 Und manchmal gewinnt man sogar sehr viele Stellen. In[3]:= Erf[N[12,30]]//Precision Out[3]= 93 All das gilt nur fuer bignum Arithmetik, Maschinenarithmetik kuemmert sich ja nicht darum wieviele Stellen korrekt sind. Sehen wir uns das Verhalten in Iterationen von Mathematica am Beispiel x->(x^2-1)/(x-1)+1 an. In[4]:= i = -1; Nest[(* print out current precision of the result *) (Print[i = i + 1; "Iteration: ", i, " Precision: ", Precision[#]]; (#^2 - 1)/(# - 1) - 1)&, N[2, 200], 20] Iteration: 0 Precision: 200 Iteration: 1 Precision: 199 Iteration: 2 Precision: 198 Iteration: 3 Precision: 197 Iteration: 4 Precision: 197 Iteration: 5 Precision: 196 Iteration: 6 Precision: 195 Iteration: 7 Precision: 194 Iteration: 8 Precision: 193 Iteration: 9 Precision: 192 Iteration: 10 Precision: 192 Iteration: 11 Precision: 191 Iteration: 12 Precision: 190 Iteration: 13 Precision: 189 Iteration: 14 Precision: 188 Iteration: 15 Precision: 187 Iteration: 16 Precision: 186 Iteration: 17 Precision: 186 Iteration: 18 Precision: 185 Iteration: 19 Precision: 184 Out[5]= 2.0000000000000000000000000000000000000000000000000000000000000000000\0000000000000000000000000000000000000000000000000000000000000000000000\000000000000000000000000000000000000000000000 In jedem Rechenschritt wird etwas an Precision verloren und dann kommt der Punkt wo nicht mehr uebrig ist. In[6]:= Nest[(#^2 - 1)/(# - 1) - 1&, N[2, 200], 236] Out[6]= 0. In[7]:= Precision[%] Out[7]= 1 In[8]:= Nest[(#^2 - 1)/(# - 1) - 1&, N[2, 200], 237] // Precision Precision::mnprec: Value 0 would be inconsistent with $MinPrecision; bounding by $MinPrecision instead. Out[8]= 0. Wenn wir strikt nach aussen rundende Intervalarithmetik benutzen sieht man, dass Mathematica's bignum Arithmetik den Fehler per Iteration sehr genau abgeschaetzt hat: In[9]:= ListPlot[(* log in Basis 10 *) Log[10, -N[Subtract @@ #[[1]]]]& /@ NestList[(* die Funktion *) (#^2 - 1)/(# - 1) - 1&, (* Startinterval: N[{2 - 10^-200, 2 + 10^-200}, 500] *) Interval[N[{2 - 10^-200, 2 + 10^-200}, 500]], 237], FrameLabel -> {"iteration", "log(interval width)"}, RotateLabel -> True, Frame -> True, PlotStyle -> {PointSize[0.001]}]; Um die genaue (nicht ganzzahlige) Precision zu sehen setzten wir SetPrecision[Round, False]. In[10]:= SetPrecision[Round, False]; In[11]:= Precision /@ NestList[(#^2 - 1)/(# - 1) - 1&, N[2, 200], 20] Out[11]= {200., 199.155, 198.31, 197.465, 196.62, 195.775, 194.929, 194.084, 193.239, 192.394, 191.549, 190.704, 189.859, 189.014, 188.169, 187.324, 186.478, 185.633, 184.788, 183.943, 183.098} Andererseits liefert die Intervalarithmetik: In[13]:= (* Definition von Precision *) N[-Log[10, Abs[Subtract @@ #[[1]]]]]& /@ NestList[(#^2 - 1)/(# - 1) - 1&, (* Startinterval equivalent zu N[2, 200] *) Interval[{SetPrecision[2 - 5 10^-201, 500], SetPrecision[2 + 5 10^-201, 500]}], 20] Out[13]= {200., 199.155, 198.31, 197.465, 196.62, 195.775, 194.929, 194.084, 193.239, 192.394, 191.549, 190.704, 189.859, 189.014, 188.169, 187.324, 186.478, 185.633, 184.788, 183.943, 183.098} Mathematica's bignum Arithmetik liefert also das gleiche Ergebnis wie Intervalarithmetik (nur viel schneller). Es gibt aber auch Iterationen die ein anderes Verhalten zeigen, z.B. die beiden folgenden Methoden um GoldenRatio auf k Stellen zu berechnen. In[14]:= g1[k_] := FixedPoint[N[Sqrt[1 + #], k]&, 1] In[15]:= g2[k_] := 1 + FixedPoint[N[1/(1 + #), k]&, 1] Da die Startzahlen Precision k haben sollte man denken, dass das Ergebnis eine kleinere Precision haette. Aber das ist nicht der Fall: In[16]:= {g1[1000] - GoldenRatio, g2[1000] - GoldenRatio} -1000 -1000 Out[16]= {0. 10 , 0. 10 } Benutzen wir wieder Interval zum checken: In[17]:= g2I[l_] := 1 + NestList[1/(1 + #)&, Interval[{1 - 10^-100, 1 + 10^-100}], l] In[18]:= Abs[Apply[Subtract, First /@ g2I[120], {1}]] // N -100 -101 -101 -102 -102 Out[18]= {2. 10 , 5. 10 , 2.22222 10 , 8. 10 , 3.125 10 , -102 -103 -103 -104 > 1.18343 10 , 4.53515 10 , 1.7301 10 , 6.61157 10 , -104 -105 -105 -105 > 2.52493 10 , 9.64506 10 , 3.68399 10 , 1.40717 10 , -106 -106 -107 -107 > 5.3749 10 , 2.05303 10 , 7.84188 10 , 2.99533 10 , -107 -108 -108 -109 > 1.14411 10 , 4.37013 10 , 1.66924 10 , 6.37593 10 , -109 -110 -110 -110 > 2.43539 10 , 9.30236 10 , 3.55319 10 , 1.3572 10 , -111 -111 -112 -112 > 5.18403 10 , 1.98012 10 , 7.5634 10 , 2.88896 10 , -112 -113 -113 -114 > 1.10348 10 , 4.21494 10 , 1.60996 10 , 6.14951 10 , -114 -115 -115 -115 > 2.3489 10 , 8.97201 10 , 3.427 10 , 1.309 10 , -116 -116 -117 -117 > 4.99993 10 , 1.9098 10 , 7.2948 10 , 2.78637 10 , -117 -118 -118 -119 > 1.0643 10 , 4.06525 10 , 1.55279 10 , 5.93113 10 , -119 -120 -120 -120 > 2.26549 10 , 8.6534 10 , 3.3053 10 , 1.26251 10 , -121 -121 -122 -122 > 4.82237 10 , 1.84198 10 , 7.03575 10 , 2.68742 10 , -122 -123 -123 -124 > 1.0265 10 , 3.92089 10 , 1.49765 10 , 5.7205 10 , -124 -125 -125 -125 > 2.18504 10 , 8.34609 10 , 3.18792 10 , 1.21768 10 , -126 -126 -127 -127 > 4.65112 10 , 1.77657 10 , 6.78589 10 , 2.59198 10 , -128 -128 -128 -129 > 9.90048 10 , 3.78165 10 , 1.44446 10 , 5.51735 10 , -129 -130 -130 -130 > 2.10744 10 , 8.0497 10 , 3.07471 10 , 1.17444 10 , -131 -131 -132 -132 > 4.48595 10 , 1.71348 10 , 6.54491 10 , 2.49993 10 , -133 -133 -133 -134 > 9.54889 10 , 3.64735 10 , 1.39316 10 , 5.32141 10 , -134 -135 -135 -135 > 2.0326 10 , 7.76384 10 , 2.96552 10 , 1.13273 10 , -136 -136 -137 -137 > 4.32664 10 , 1.65263 10 , 6.31248 10 , 2.41115 10 , -138 -138 -138 -139 > 9.20978 10 , 3.51782 10 , 1.34369 10 , 5.13244 10 , -139 -140 -140 -140 > 1.96042 10 , 7.48812 10 , 2.86021 10 , 1.0925 10 , -141 -141 -142 -142 > 4.17299 10 , 1.59394 10 , 6.08831 10 , 2.32553 10 , -143 -143 -143 -144 > 8.88272 10 , 3.3929 10 , 1.29597 10 , 4.95017 10 , -144 -145 -145 -145 > 1.8908 10 , 7.2222 10 , 2.75864 10 , 1.05371 10 , -146 -146 -147 -147 > 4.0248 10 , 1.53734 10 , 5.8721 10 , 2.24294 10 , -148 -148 -148 -149 > 8.56728 10 , 3.27241 10 , 1.24995 10 , 4.77438 10 , -149 -150 -150 -150 > 1.82365 10 , 6.96573 10 , 2.66067 10 , 1.01629 10 } Die Intervalle werden diesmal kleiner, d.h. der Fehler wird gedaempft. Das wird ersichtlich wenn man sich anschaut wie sich ein deltax fortpflanzt: In[19]:= stab2[x_] = Abs[x D[1/(1 + x),x]/(1/(1 + x))] x Out[19]= Abs[-----] 1 + x In[20]:= Plot[Evaluate[stab2[x]],{x,1,2}]; Dasselbe gilt fuer g1: In[21]:= stab1[x_] = x D[Sqrt[1 + x], x]/Sqrt[1 + x] x Out[21]= --------- 2 (1 + x) In[22]:= Plot[Evaluate[stab1[x]],{x,1,2}]; Wenn wir iterieren und nicht N[...,k] benutzen sehen wir ein Anwachsen der Precision. In[23]:= SetPrecision[Round, False]; In[24]:= ListPlot[Precision /@ NestList[Sqrt[1 + #]&, N[1, 50], 100]]; In[25]:= ListPlot[Precision /@ NestList[1/(1 + #)&, N[1, 50], 100]]; >Wie kann man diesen Stellenverlust vermeiden oder wenigstens an die >unterdrueckten Stellen wieder herankommen? Mit SetPrecision kann man einer Zahl einer hoehere Precision zuweisen. Dabei werden die intern gespeicherten guard digits (sichtbar mit $NumberBits genutzt). Im folgenden wird SetPrecision benutzt um jedesmal nach der Berechnung die Precision wieder auf 200 zu setzten. In[26]:= i = -1; Nest[(* print out current precision of the result *) (Print[i = i + 1; "Iteration: ", i, " Precision: ", Precision[#]]; SetPrecision[(#^2 - 1)/(# - 1) - 1, 200])&, N[2, 200], 20] Iteration: 0 Precision: 200. Iteration: 1 Precision: 200. Iteration: 2 Precision: 200. Iteration: 3 Precision: 200. Iteration: 4 Precision: 200. Iteration: 5 Precision: 200. Iteration: 6 Precision: 200. Iteration: 7 Precision: 200. Iteration: 8 Precision: 200. Iteration: 9 Precision: 200. Iteration: 10 Precision: 200. Iteration: 11 Precision: 200. Iteration: 12 Precision: 200. Iteration: 13 Precision: 200. Iteration: 14 Precision: 200. Iteration: 15 Precision: 200. Iteration: 16 Precision: 200. Iteration: 17 Precision: 200. Iteration: 18 Precision: 200. Iteration: 19 Precision: 200. Out[27]= 2.000000000000000000000000000000000000000000000000000000000000000000\ 000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000 In[28]:= Precision[%] Out[28]= 200. Die Stellen sind nicht alle 'verloren'. Mathematica weiss nur nicht ob sie noch sicher sind. Man sieht die expliziten Stellen (in base 2) mit $NumberBits. In[29]:= ?$NumberBits $NumberBits[x] gives a list containing the sign, a list of the bits thought to be correct, a list of the bits not thought to be correct, and the binary exponent. The number x must have a head of Real. Ob man SetPrecision verwendet in der obigen Iteration spielt fuer den Wert der Bits keine Rolle, nut ob sie als sichere oder guard digits angesehen werden wird dadurch beeinflusst: In[30]:= Nest[(#^2 - 1)/(# - 1) - 1&, N[2, 200], 20] Out[30]= 2.000000000000000000000000000000000000000000000000000000000000000000\ 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 In[31]:= $NumberBits[%] // InputForm Out[31]//InputForm= {1, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 16} In[32]:= Length /@ % Out[32]= {0, 623, 49, 0} In[33]:= Nest[ SetPrecision[(#^2 - 1)/(# - 1) - 1, 200]&, N[2, 200], 20] Out[33]= 2.000000000000000000000000000000000000000000000000000000000000000000\ 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 In[34]:= $NumberBits[%] // InputForm Out[34]//InputForm= {1, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 16} In[35]:= Length /@ % Out[35]= {0, 679, 41, 0} Wenn man einen groessere Rechnung mit fixierter Precision machen will, so ist es oft am guenstigsten diese Rechnung innerhalb eines Blocks auszufauehren und lokal die Variablen $MinPrecision und $MaxPrecision zu aendern: In[36]:= Block[{$MinPrecision=200,$MaxPrecision=200}, Nest[(#^2 - 1)/(# - 1) - 1&, N[2], 20]] Out[36]= 2.000000000000000000000000000000000000000000000000000000000000000000\ 000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000 In[37]:= Precision[%] Out[37]= 200. Michael Trott Wolfram Research |