Nächste Seite: A.2.11 Einen String in Aufwärts: A.2 Lösungen Vorherige Seite: A.2.9 Einfache Integration Inhalt
Sowohl die Java- als auch die C++-Lösung arbeiten nach folgendem Prinzip: beim Aufruf zur Suche der Nullstelle wird eine Funktion angegeben (in Java als Funktionsobjekt, in C++ als Zeiger auf eine Funktion), deren Nullstelle gesucht ist, weiterhin die Grenzen des zu durchsuchenden Intervalls, eine gewünschte Genauigkeit, und eine Anfangsschrittweite. Daraufhin wird das angegebene Intervall gemäß letzterer in Streifen zerlegt, und für jedes dieser Teilintervalle der Funktionswert bestimmt. Der höchste vorkommende Funktionswert und der zugehörige Abszissenwert sind eine erste Näherung für das Maximum; der tatsächliche Wert wird in einem der beiden benachbarten Streifen vermutet. Dementsprechend wird das Intervall auf diese beiden Streifen verkleinert, und mit 100 Teilintervallen darin die Suche analog fortgesetzt (durch einen rekursiven Aufruf). Diese weitere Unterteilung setzt sich fort, bis durch das Verkleinern des Intervalls die Breite kleiner wird als die geforderte Genauigkeit; die Mitte des letzten Intervalls wird dann als Näherung für den Abszissenwert des Maximums geliefert.
Das Interface FunktObj aus der Musterlösung Java: Verwendung eines funktionalen Objekts zur Aufgabe Einfache Integration zur Deklaration einer Funktion mit einer Veränderlichen wird hier noch einmal verwendet:
// Time-stamp: "30.05.02 13:49 FunktObj.java klaus@lap2.wachtler.de"
//
// Interface eines funktionalen Objekts zur Lösung der
// Übungsaufgabe "Einfache Integration" und anderer ähnlicher Probleme.
interface FunktObj
{
double f( double x );
}
Die eigentliche Musterlösung ist folgende:
// Time-stamp: "30.05.02 14:56 maxfun.java klaus@lap2.wachtler.de"
//
// Musterlösung der Aufgabe "Maximum einer Funktion"
//
class maxfun
{
private FunktObj f;
// Konstruktor
// Eingabeparameter:
//
// f: Funktionsobjekt (die Nullstelle dessen Methode f()
// ist gesucht)
public maxfun( FunktObj funktion )
{
f = funktion;
}
// Sucht im Intervall [a,b] nach dem Maximum einer Funktion f(x).
//
// Eingabeparameter:
//
// a: linke Intervallgrenze
// b; rechte Intervallgrenze
// Genauigkeit: gewünschte Genauigkeit (in x-Richtung)
// Schrittweite: anfängliche Schrittweite, in der das Intervall
// unterteilt wird
//
// Rückgabe:
// Abszissenwert der gefundenen Nullstelle
//
// Vorgehensweise:
// Beim anfänglichen Aufruf wird das Intervall mit der angegebenen
// Schrittweite unterteilt, und der größte aller Funktionswerte gesucht.
// Daraufhin wird das gesuchte Maximum im Intervall vermutet, das um
// Schrittweite vor dem gefundenen Höchstwert beginnt, und um
// Schrittweite hinter dem gefundenen Höchstwert endet.
// maxfun ruft sich dann für dieses Intervall wieder selbst auf mit den
// neuen Grenzen, der ursprünglichen Genauigkeit, und einer Schrittweite,
// die als 1/100 der neuen Intervalllänge berechnet wird.
//
// Die Rekursion endet, wenn die Intervalllänge kleiner als die
// gewünschte Genauigkeit ist.
double max( double a,
double b,
double Genauigkeit,
double Schrittweite
)
{
// a und b ggf. richtig sortieren:
if( a>b )
{
double temp = a; a = b; b = temp;
}
// Wenn die Genauigkeit bereits erreicht ist, dann einfach
// die Mitte des Intervalls liefern:
if( b-a < Genauigkeit )
{
return ( b + a )/2.0;
}
else
{
// den jeweils größten gefundenen Funktionswert in maxy und
// den zugehörigen Abszissenwert in maxx merken!
// Weil möglicherweise in der Schleife der Endwert des
// Intervalls nicht genau getroffen wird, ist es am geschicktesten
// den Maximalwert gleich mit der rechten Grenze zu initialisieren.
// Damit ist diese auch gleich berücksichtigt!
double maxx = b;
double maxy = f.f( b );
// Schleife über alle Schritte:
for( ; a<b; a+=Schrittweite )
{
if( f.f( a )>maxy )
{
// größeren Wert als bisher gefunden!
maxy = f.f( a );
maxx = a;
}
}
// der bisherige Maximalwert liegt bei (maxx,maxy).
// Das darum liegende Intervall genauer durchsuchen:
return max( maxx-Schrittweite, // neues a
maxx+Schrittweite, // neues b
Genauigkeit, // bleibt
2*Schrittweite/100.0 // feiner unterteilt
);
}
}
} // class Maxfun
Das zugehörige Testprogramm:
// Time-stamp: "30.05.02 14:29 test_maxfun.java klaus@lap2.wachtler.de"
//
// Testprogramm zur Musterlösung der Aufgabe "Maximum einer Funktion"
//
// javac test_maxfun.java FunktObj.java maxfun.java
// java test_maxfun
// Die geforderte Funktion:
class f1 implements FunktObj
{
public double f( double x )
{
return 15.0 + 13.0*x - 0.5*x*x;
}
}
public class test_maxfun
{
public static void main( String[] args )
{
// Maximum von f() in f1 suchen:
f1 meinefunktion = new f1();
maxfun meinmax = new maxfun( meinefunktion );
double x = meinmax.max( -1000.0, // Intervall von
+1000.0, // Intervall bis
0.0001, // Genauigkeit
1.0 // Anfangsabstand
);
System.out.println( "Maximum f(" + x + ") = "
+
meinefunktion.f( x )
);
}
}
// Time-stamp: "01.06.02 18:11 maxfun.cpp klaus@lap2.wachtler.de"
//
// Musterlösung der Aufgabe "Maximum einer Funktion"
//
// Kompilieren und starten unter Linux:
// g++ -Wall -DTESTPROGRAMM maxfun.cpp -o maxfun && maxfun
//
// Kompilieren und starten unter Win32/VC++ 6.0:
// cl /Zi /GX -DTESTPROGRAMM maxfun.cpp
// .\maxfun
#include <iostream>
using namespace std;
// Sucht im Intervall [a,b] nach dem Maximum einer Funktion f(x).
//
// Eingabeparameter:
//
// f: (Adresse der) Funktion, deren Nullstelle gesucht ist
// a: linke Intervallgrenze
// b; rechte Intervallgrenze
// Genauigkeit: gewünschte Genauigkeit (in x-Richtung)
// Schrittweite: anfängliche Schrittweite, in der das Intervall
// unterteilt wird
//
// Rückgabe:
// Abszissenwert der gefundenen Nullstelle
//
// Vorgehensweise:
// Beim anfänglichen Aufruf wird das Intervall mit der angegebenen
// Schrittweite unterteilt, und der größte aller Funktionswerte gesucht.
// Daraufhin wird das gesuchte Maximum im Intervall vermutet, das um
// Schrittweite vor dem gefundenen Höchstwert beginnt, und um
// Schrittweite hinter dem gefundenen Höchstwert endet.
// maxfun ruft sich dann für dieses Intervall wieder selbst auf mit den
// neuen Grenzen, der ursprünglichen Genauigkeit, und einer Schrittweite,
// die als 1/100 der neuen Intervalllänge berechnet wird.
//
// Die Rekursion endet, wenn die Intervalllänge kleiner als die
// gewünschte Genauigkeit ist.
double maxfun( double( *f )( double x ),
double a,
double b,
double Genauigkeit,
double Schrittweite
)
{
// a und b ggf. richtig sortieren:
if( a>b )
{
double temp = a; a = b; b = temp;
}
// Wenn die Genauigkeit bereits erreicht ist, dann einfach
// die Mitte des Intervalls liefern:
if( b-a < Genauigkeit )
{
return ( b + a )/2.0;
}
else
{
// den jeweils größten gefundenen Funktionswert in maxy und
// den zugehörigen Abszissenwert in maxx merken!
// Weil möglicherweise in der Schleife der Endwert des
// Intervalls nicht genau getroffen wird, ist es am geschicktesten
// den Maximalwert gleich mit der rechten Grenze zu initialisieren.
// Damit ist diese auch gleich berücksichtigt!
double maxx = b;
double maxy = f( b );
// Schleife über alle Schritte:
for( ; a<b; a+=Schrittweite )
{
if( f( a )>maxy )
{
// größeren Wert als bisher gefunden!
maxy = f( a );
maxx = a;
}
}
// der bisherige Maximalwert liegt bei (maxx,maxy).
// Das darum liegende Intervall genauer durchsuchen:
return maxfun( f, // Funktion weiterreichen
maxx-Schrittweite, // neues a
maxx+Schrittweite, // neues b
Genauigkeit, // bleibt
2*Schrittweite/100.0 // feiner unterteilt
);
}
}
//////////////////////////////////////////////////////////////////////////
//
// Testprogramm:
//
#ifdef TESTPROGRAMM
double f1( double x )
{
return 15.0 + 13.0*x - 0.5*x*x;
}
int main( int nargs, char **args )
{
double Nullstelle = maxfun( f1, -1000.0, +1000.0, 0.0001, 1.0 );
cout << " f(" << Nullstelle << ")=" << f1( Nullstelle ) << endl;
return 0;
} // main( int nargs, char **args )
#endif // ifdef TESTPROGRAMM