Finden Sie Nullstellen einer stetigen Funktion.

Schwierigkeit 2

Wenn eine stetige, reelwertige Funktion f: R -> R eine Nullstelle besitzt, dann gibt es mindestens zwei reele Zahlen a und b, so dass f(a)f(b) < 0 ist. Das heisst, einer der Funktionswerte ist negativ (unterhalb der x-Achse), der andere ist positiv (oberhalb der x-Achse): da f stetig ist, muss die Funktionskurve von f die x-Achse schneiden.

Implementieren Sie ein Halbierungsverfahren, das für eine Funktion f eine Nullstelle auf einem Intervall [a,b] näherungsweise findet, falls dort eine Nullstelle existiert. Die Genauigkeit der Lösung sollte bei Ihrer Lösung mit angegeben werden. f soll einfach als Java-Funktion implementiert sein. Testen Sie Ihre Implementierung mit dem Polynom f(x) = 2x3 - 5x2 + 7x + 2. Es gilt f(1) = 2 - 5 + 7 = 6 und f(-1) = -2 - 5 - 7 = -14.

Lösung. Damit der Algorithmus für alle mögliche Implementierungen von Funktionen verwendet werden kann, ist eine Funktion als abstrakter Datentyp gegeben.

Finden Sie Nullstellen mit dem Newtonverfahren.

Schwierigkeit 2

Berechnen Sie die Nullstelle einer stetige, differenzierbaren Funktion f mit Hilfe des Newton-Verfahrens.

Beim Newton-Verfahren wird ausgehend vom einem Startwert x0 die Folge xn+1 := xn - f(xn)/f'(xn) berechnet. Die Folge konvergiert (nicht immer) gegen eine Nullstelle.

Wenn Sie schon Polynome implementiert haben, dann können Sie diese dazu verwenden. Wenn nicht, dann definieren Sie sich eine Klasse (oder besser ein Interface) mit zwei Methoden: eine zur Berechnung des Funktionswerts f(x) und eine für den Wert der ersten Ableitung in x.

Lösung.

Berechnen Sie an mit einem Halbierungsverfahren

Schwierigkeit 2

Berechnen Sie die Potenz an für einen double-Wert a und einem int-Wert n >= 0 mit einem rekursiven Halbierungsverfahren. Der Zeitaufwand Ihrer Implementierung darf O(log2n) nicht überschreiten.

Betrachten Sie folgendes Beispiel, um einen Idee für die Unterteilung zu bekommen:

a7 = a a3 a3

Lösung.