001    package de.hska.java.aufgaben.suchen;
002    
003    
004    import de.hska.java.aufgaben.objekte.Polynom;
005    
006    /**
007     * Eine Implementierung des Newton-Verfahren zur Berechnung einer Nullstelle
008     * eines Polynoms f(x).
009     * Beim Newton-Verfahren wird ausgehend vom einem Startwert x<sub>0</sub> die
010     * Folge x<sub>n+1</sub> := x<sub>n</sub> - f(x<sub>n</sub>)/f<sup>'</sup>(x<sub>n</sub>)
011     * berechnet. Die Folge konvergiert (nicht immer) gegen eine Nullstelle.
012     * 
013     * <p>
014     *   <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/suchen.html#newtonverfahren">Zurück zum Aufgabentext</a>
015     * </p>
016     * 
017     * 
018     * @author Christian Pape
019     */
020    public class NewtonVerfahren {
021    
022            /**
023             * Ein reelwertiges (double) Polynom in einer Unbekannten.
024             */
025            private Polynom polynom;
026    
027            /**
028             * Die erste Ableitung des Polynoms.
029             */
030            private Polynom ableitung;
031            
032            /**
033             * Erzeugt ein neues NewtonVerfahren mit dem Nullstellen für das
034             * gegeben Polynom berechnet werden können.
035             */
036            public NewtonVerfahren(Polynom polynom) {
037                    this.polynom = polynom;
038                    this.ableitung = polynom.getErsteAbleitung();
039            }
040            
041            
042            /**
043             * Sucht und berechnet mit Hilfe des Newton-Verfahren eine Nullstelle.
044             * Startwert ist <code>x</code>. Es wird so lange gesucht, bis
045             * der Funktionswert kleiner oder gleich epsilon ist, dieser sollte 
046             * sehr nahe bei Null sein.
047             * Die Methode terminiert nicht notwendigerweise.
048             * Wenn Sie terminiert und das Ergebnis eine Zahl ist (und nicht infinity oder NaN),
049             * dann ist es eine Nullstelle .
050             */
051            public double sucheNullstelle(double x, final double epsilon) {
052                    double neuesX = x;
053                    
054                    do {
055                            x = neuesX;
056                            neuesX = x - polynom.f(x) / ableitung.f(x);
057                    } while ( Math.abs(polynom.f(neuesX)) > epsilon);
058                    
059                    return neuesX;
060            }
061    }
062