Induktiver Algorithmenentwurf: Wo ist mein Fehler?



  • War n ziemlicher Aufwand den Post hier zu erstellen, also hoffe ich mal jemand liest das ganze und kann mir helfen :).

    Der induktive Algorithmenentwurf nutzt die Prinzipien der vollständigen Induktion beim Algorithmenentwurf. Natürlich wird die vollständige Induktion nicht direkt angewendet (es interessiert hier ja nicht irgendwas zu beweisen), aber man lehnt sich daran an.

    Gegeben ist die Reihe zum Annähern von ln :

    k=022k+1(x1x+1)2k+1\sum_{k=0}^{\infty} \frac{2}{2k+1} (\frac{x-1}{x+1})^{2k+1}

    mit

    22k+1(x1x+1)2k+1=ak\frac{2}{2k+1} (\frac{x-1}{x+1})^{2k+1} = a_k

    Der Induktionsanfang ist demnach:

    a0=220+1(x1x+1)20+1=2x2x+1a_0 = \frac{2}{2 \cdot 0 + 1} (\frac{x-1}{x+1})^{2 \cdot 0 + 1} = \frac{2x-2}{x+1}

    Dieser gibt später die Startwerte meiner Variablen im Algorithmus an.

    a_k+1 ist demnach:

    ak+1=22k+3(x1x+1)2k+2a_{k+1} = \frac{2}{2k+3} (\frac{x-1}{x+1})^{2k+2}

    Das Ziel ist es nun, sozusagen eine "Differenz" zwischen a_k+1 und a_k zu finden, welche man in einem Algorithmus abbilden kann.

    a_k+1 lässt sich somit (durch ein wenig ausklammern usw.) umschreiben in:

    22k+111+22k+1(x1x+1)(x1x+1)2k+1\frac{2}{2k+1} \frac{1}{1+\frac{2}{2k+1}} (\frac{x-1}{x+1}) (\frac{x-1}{x+1})^{2k+1}

    Was ja nichts anderes ist als

    11+22k+1(x1x+1)ak\frac{1}{1+\frac{2}{2k+1}} (\frac{x-1}{x+1}) \cdot a_k

    Und jetzt kommt mein Problem: Ich habe mit dieser Vorarbeit diesen Algorithmus (hier in Pseudocode, zum ausprobieren hab ich ihn in Java gegossen) abgeleitet:

    ALGORITHMUS lnIT( x   ,   delta )   //delta ist die Genauigkeit
    k=1                       //fängt bei 1 an, da wir glied k=0 schon haben
    ln = (2*x -2)/(x+1)       //Induktionsanfang, Summe besteht nur aus erstem Glied
    ak = {2*x -2)/(x+1)       //erstes Glied
    
    WHILE abs(ak) > delta
       DO
          ak = ak * (1/(1+(2/(2k + 1)))) * ((x-1)/(x+1)) //ak = ak * differenz
          ln = ln+ak
          k = k+1
       END
    
    RETURN ln
    END
    

    Das Problem: Für immer größere Werte weicht mein Algorithmus immer mehr vom korrekten Wert für ln ab. Bei x = 2.0 und delta = 0.0000000000001 ist es noch 0.66666666 (was bei nem richtigen ln von ~0.63 noch ganz ok ist), bei x=25 und gleichem delta bekomme ich aber z.B. (soweit ich mich erinnern kann) einen ln von ~1.3 wobei der richtige irgendwo bei 3 liegt.

    Weiß jemand woran das liegt? Habe ich hier einen Leichtsinnsfehler gemacht oder besteht gar ein grundlegendes Missverständnis des ganzen Ansatzes?



  • Kann es sein, dass der Fehler bei der Division durch 2k+1 entsteht? Falls das ein int ist, und du das nicht in double castest, ist das in Java eine Ganzzahldivision, und dann kommt murx raus.



  • Nein, sicherheitshalber habe ich alles in doubles angegeben. Ich hab zwar mittlerweile einen Fehler in der Herleitung entdeckt (die Potenz rechts oben ist für k+1 nicht 2k+2 sondern 2k+2),aber auch nach der berichtigung sind die werte noch falsch (vor allem für große testwerte)

    Das ist übrigens der java-code der funktion:

    public class iterativ {
    	public static double lnIt(double x, double delta) 
    	{
    		double k = 1.0;
    		double ln = 2*((x-1)/(x+1));
    		double ak = ln;
    
    		while(Math.abs(ak)> delta)
    		{
    			ak = ak*(
    					(1/(1+(2/(2*k+1)))) * ((x-1)/(x+1))* ((x-1)/(x+1))) ;
    			ln = ln + ak;
    			k = k+1.0;
    		}
    
    		return ln;
    	}
    }
    


  • Du gehst also von folgendem ak+1 aus (der erste Bruch lässt sich noch vereinfachen):

    ak+1=ak(2k+1)(x1)2(2k+3)(x+1)2a_{k+1}=a_k\cdot\frac{(2k+1)(x-1)^2}{(2k+3)(x+1)^2}

    Zum Problem: getestet habe ich es nicht, aber ich vermute, das Problem ist die Ungenauigkeit von double. Jedesmal wird eine Nachkommastelle abgeschnitten und bei Multiplikationen kommt das irgendwann sichtbar zum Tragen, mehr als mit Additionen.

    Mit Java kenne ich mich nicht so gut aus, aber wenn du es so belassen willst, solltest du eine genauere Gleitkommazahlendarstellung auswählen (in C/C++ long double) oder (wäre noch genauer) jeweils den Zähler und Nenner seperat auszurechnen und abzuspeichern, dann treten keine Rundungsfehler auf.

    Übrigens:

    ak = ak*((1/(1+(2/(2*k+1)))) * ((x-1)/(x+1))* ((x-1)/(x+1))) ;
    ln = ln + ak;
    k = k+1.0;
    

    heisst kürzer

    ak *= (1/(1+(2/(2*k+1)))) * ((x-1)/(x+1))* ((x-1)/(x+1))) ;
    ln += ak;
    k++;
    


  • Kannst du mal die Quelle der ursprünglichen Formel angeben?
    Am besten, du implementierst die Summe auch mal und schaust, ob das dann funktioniert. Ich habe es mal kurz in Matlab ausprobiert und komme da bei x=25 auch schon auf einen Wert von 3.2 (nur die ursprüngliche Summenformel, die du als gegeben betrachtest).
    Vielleicht ist die Reihe ja eine Approximation für kleine x oder sie beruht auf irgendwelchen Annahmen, die hier nicht erfüllt sind.


Anmelden zum Antworten