Universität Hamburg - Fachbereiche - Fachbereich Mathematik

Java-Kurs (2)

Numerische Mathematik, WiSe 99/00 und SoSe 00, Bodo Werner

Zurück zum Inhaltsverzeichnis.

Funktionen und Polynome

Das Kap.2 der Numerik befasst sich mit der Polynominterpolation. Parallel hierzu werden in Java eine abstrakte Klasse Funktion und Unterklassen hiervon eingeführt. Genauer soll es sich bei Funktionen nur um solche mit reellen Intervallen [xMin, xMax] als Definitionsbereich und mit reellen Funktionswerten handeln, kurz um reelle Funktionen. Klar, dass zu jeder "konkreten" Funktion auch eine Abbildungsvorschrift gehören muss. Diese wird durch die Methode getY() realisiert. Alle "konkreten" Funktionen werden durch eine zu definierende Unterklasse der abstrakten Klasse Funktion vereinbart. Hierzu gehören Polynome (besser Polynomfunktionen). Bei diesen bietet es sich an, das Horner Schema zur Realisierung der Methode getY() zu verwenden. Die Umsetzung dieses Schema in Java geschieht mit einer Methode namens Horner() der Klasse Polynom, die als Rückgabewert wieder ein Polynom hat!

Wir werden die Klasse Funktion noch in vielen Bereichen der Numerik verwenden. Insbesondere werden wir Graphen von Funktionen mit einer Black-box-Methode zeichnen.

Die abstrakte Klasse Funktion1 und eine Unterklasse

abstract als Eigenschaft einer Klasse und ihrer Methoden, Bildung von Unterklassen mit extends, Bezug auf einen Konstruktor der Oberklasse mit super(), Verwendung von verschiedenen Konstruktoren gleichen Namens (Überladung), die Methode Math.sqrt(), Verzweigung eines Programmablaufs durch if ... else , der Datentyp boolean, logische Operatoren
Die folgende Klasse Funktion1 ist eine einfachere Modifikation der späteren Klasse Funktion, wie sie für das Zeichnen von Graphen von Funktionen verwendet wird. Bei einem späteren Gebrauch sollte die Klasse Funktion verwendet werden, welche natürlich noch weiter angereichert werden kann.
 1 abstract class Funktion1{
 2  double xMin, xMax; //Grenzen des Definitionsbereichs
 3  Funktion1(){  //1.Konstruktor (maximaler Def.Bereich):
 4    xMax=Double.MAX_VALUE;
 5    xMin=-xMax;
 6  }
 7  Funktion1(double xMin, double xMax){  //2. Konstruktor:
 8    this.xMin=xMin;
 9    this.xMax=xMax;
10  }
11  //Methode: (muss in Unterklasse ueberlagert werden)
12  abstract double getY(double x);
13 }//Ende class Funktion1
Der Zusatz abstract in den Zeilen 1 und 12 ist hier der wesentliche Punkt. Von einer abstrakten Klasse soll keine Instanz (kein Exemplar) gebildet werden, d.h. es müssen Unterklassen erstellt werden, in denen dann auch die abstrakte, d.h. noch nicht implementierte Methode getY() (mit Wert double) konkretisiert wird. Der Sinn dieser "Abstraktion" wird besser wiedergegeben, wenn man abstract mit aufgeschoben übersetzt. Der Sinn in der Einführung solcher Klasse ist, dass deutlich wird, was zu einer Funktion gehört: ein Definitionsbereich in Form eines Intervalls und eine Zuordnungsvorschrift.

Ein weiterer neuer Punkt ist die Überladung von Konstruktoren durch zwei Varianten, die sich durch verschiedene Parameterlisten unterscheiden. Je nach Bedarf kann auf die erste (maximaler Definitionsbereich) oder auf die zweite Variante ([xMin,xMax] als Definitionsbereich) zugegriffen werden. Letzteres ist besonders wichtig beim Zeichnen von Graphen von Funktionen in einem Grafikfenster, dessen horizontale Ausmaße gerade durch das Intervall [xMin,xMax] gegeben ist. Eine solche Überladung ist generell von Methoden möglich und stellt einen ganz wesentliches Vorteil gegenüber anderen Programmiersprachen dar.

Da die Klasse Funktion1 abstrakt ist, sollen nie Instanzen von ihr gebildet werden. Daher spielen ihre Konstruktoren nur indirekt eine Rolle, indem auf diese in Unterklassen mittels des Schlüsselworts super() zugegriffen wird.

Unterklassen

Die Zeile 4 der Klasse Funktion1 möchte ich hier nicht erklären, weil das folgende Bilden von Unterklassen viel wichtiger ist:
 1 class Wurzel extends Funktion1{
 2  Wurzel(double xMin, double xMax){
 3    super(xMin,xMax);
 4  }
 5  //Die einfachere Konstruktor-Variante:
 6  Wurzel(){
 7   super();
 8   xMin=0;
 9  }
10  double getY(double x){
11    double y=Double.NaN;
12    if ((xMin<=x) & (x<=xMax)) y=Math.sqrt(x);
13    else System.out.println(x+" ist nicht im Def.Bereich");
14    return y;
15 }
16 }//Ende Wurzel
Diese Klasse Wurzel wird durch den Zusatz extends in Zeile 1 zu einer Unterklasse von Funktion1. Sie erbt damit alle Daten (hier xMin, xMax) und Methoden der Oberklasse. Hier sind letztere die beiden Konstruktoren in den Zeilen 3 und 7 der Klasse Funktion1, auf die mit super() in den Zeilen 3 und 7 der Klasse Wurzel zugegriffen wird. Durch die jeweils zwei Konstruktoren (mit verschiedenen Parameterlisten) werden unterschiedliche Fälle von Definitionsbereichen erfasst: einmal ist dieser maximal (nichtnegative reelle Zahlen), im anderen Fall kann er durch den "Konstrukteur" festgelegt werden. Hier kommt wieder das Prinzip der Überladung von Methoden vor: Man kann Methoden mit gleichen Bezeichnern, aber unterschiedlichen Parameterlisten vorsehen, allerdings müssen sie denselben Rückgabewert haben.

Noch ein Wort zu super() : Jeder Konstruktor einer Unterklasse muss mittels super als erste Anweisung auf einen Konstruktor der Superklasse zugegreifen. Wenn dies nicht geschieht, setzt der Compiler automatisch den Default-Befehl super().

In Zeile 10 wird durch Verwendung der Java-Bibliotheks-Methode Math.sqrt() die aufgeschobene Methode getY() mit Rückgabewert double realisiert (implementiert), wobei der Fall, dass das Argument nicht im Definitionsbereich liegt, durch den Funktionswert NaN (Not a Number) gekennzeichnet ist. Zum Hintergrund der "Wrapper-Klasse" Double, die die Konstanten NaN, MAX_VALUE bereitstellt, verweise ich auf die Literatur.

if ... else - Verzweigung

Die Zeilen 12-13 enthalten eine if ... else Verzweigung. Falls der nach if (stets in runden Klammern) stehende Boole'sche Ausdruck wahr (true) ist, werden die dahinter aufgeführten Anweisungen (bei mehreren durch Block-Klammern {...} zusammengefasst) ausgeführt, wenn nicht (false), wird der nach else stehende Block angesprungen. Dieser kann auch fehlen, d.h. dass if { ...} auch ohne else{...} einen Sinn macht. Java-Verzweigungen mit switch oder bedingte Ausdrücke der Form B ? w1 : w2 mit einem Boole'schen Ausdruck B und "Werten" w1, w2 sollten in Lehrbüchern nachgeschlagen werden. In Zeile 12 kommt der logische Operator & vor. Dieser und andere wie |, !, ==, !=, &&, || werden in allen Lehrbüchern erklärt. In diesem Zusammenhang sollte wenigstens erwähnt werden, dass es auch den Grunddatentyp boolean mit den beiden Werten true, false gibt. So hätte statt Zeile 12 auch
12a boolean b=(xMin<=x) & (x<=xMax);
12b if (b) y=Math.sqrt(x);
stehen können.

Eine Applikation

Jetzt fehlt noch eine Applikationsklasse, die ein Objekt der Klasse Wurzel bildet - wieder mit dem Schlüsselwort new (hier sogar zwei verschiedene Objekte namens f1, f2 mit Hilfe der zwei Konstruktoren) und an diese die "Nachricht sendet", sie möge einen Funktionswert an einer gewissen Stelle abliefern, indem ihre Methode getY() aufgerufen wird (Verwendung der Punktnotation!):
class Bsp4{
 1  static void main(String[] args){
 2  double x=5;
 3  Wurzel f1=new Wurzel();  //maximaler Def.Bereich
 4  System.out.println("Wurzel aus "+x+": ");
 5  System.out.println("f1: "+f1.getY(x));
 6  Wurzel f2=new Wurzel(0,1); //Def.Bereich [0,1]
 7  System.out.println("Wurzel aus "+x+": ");
 8  System.out.println("f2: "+f2.getY(x));
 9  }
10 }
Hier werden beide Konstruktoren verwendet (Zeilen 3 und 6), in letzterem Fall liegt x=5; in Zeile 2 außerhalb des vereinbarten Definitionsbereiches. In diesem Fall ergibt f2.getY(x) den "Wert" NaN (Zeile 8).

Die Klasse Polynom als Unterklasse von Funktion1 (Horner Schema, Umordnen)

Eindimensionale Felder double[], eine Methode (Horner()) der Klasse Polynom mit Wert Polynom,
Ein Polynom n-ten Grades kann durch ein Feld double[] a der Länge n+1 mit Komponenten a[0], ..., a[n] dargestellt werden: p(x)=a[0]+a[1]*x+....+a[n]*x^n. Wir wollen das Horner Schema zur Auswertung in der Methode getY() verwenden. Hierzu werden die im Horner Schema mit b[0],..., b[n-1] bezeichneten Koeffizienten berechnet und - aus Gründen, die durch die Vorlesung und die Methode Umordnen() klar werden - wieder zu einem Polynom (n-1)-ten Grades durch eine Methode Polynom Horner() mit Rückgabewert Polynom "gemacht" (Zeilen 12-18). Das ist schon recht komplex: Eine Methode der Klasse Polynom hat als Wert einen Typ eben dieser Klasse - eine Rekursion (Selbstbezug). Ist p ein Objekt der Klasse Polynom, so ist q=p.Horner() wieder ein Polynom, so dass q.Horner() oder p.Horner().Horner() einen Sinn gibt. Diese Struktur wird sehr schön in der Methode Umordnen() (Zeilen 26-36) benutzt, durch die eine andere Darstellung p(x)=c[0]+c[1](x-z)+...+c[n]*(x-z)^n zu vorgegebenem z berechnet wird, genauer: die Methode double[] Umordnen(double z) (Zeile 26) liefert als Rückgabewert das Feld c[]. In einer Schleife (Zeilen 31-34) wird Horner() auf das zuletzt berechnete Polynom angewendet (q=q.Horner(z) in Zeile 33), das Ergebnis wird wieder q genannt. Das ist schon eine relativ komplexe Rekursion: zum einen enthält die Klasse Polynom eine Methode, die als Rückgabewert ein Objekt eben dieser Klasse hat, zum anderen werden die "Hornerpolynome" p_{n-k} durch Zeile 34 rekursiv berechnet (p_{n-k-1}=p_{n-k}.Horner(z)). Man sollte sich nicht an der Methode Umordnen() die Zähne ausbeißen. Hier treffen sich mathematische und programmiersprachliche Schwierigkeiten.
 1 class Polynom extends Funktion1{
 2 //Attribute, Datenelemente, Mitgliedsvariable:
 3   int Grad;
 4   double a[];  //Koeffizienten (p=a[0]+a[1]*x+....+a[n]*x^n)
 5   //Konstruktor:
 6   Polynom(double[] a){
 7     super(); //max. Def.Bereich
 8     this.a=a;
 9     Grad=a.length-1;
10   }//Ende  Konstruktor
11   //Methoden:
12   Polynom Horner(double z){
13     double[] b = new double[Grad];
14     b[Grad-1]=a[Grad];
15     for (int j=Grad-2;j>=0;j--) 
         b[j]=b[j+1]*z+a[j+1];
16     Polynom q=new Polynom(b);
17     return q; //p_n(x)=p_{n-1}(x)*(x-z)+p_n(z), q=p_{n-1}
18   }//ende Horner

19   double getY(double x){
20     if (Grad==0) return a[0];
21     else{
22       Polynom q = Horner(x);
23       return q.a[0]*x+a[0];
24     }//Ende else
25   }//Ende getY

26   double[] Umordnen(double z){
27     double[] c = new double[Grad+1];
28     c[0] = getY(z);
29     c[Grad]=a[Grad];
30     Polynom q=Horner(z);//q_p_{n-1}
31     for (int k=1;k<Grad;k++){
32       c[k]=q.getY(z);//q=p_{n-k}
33       q=q.Horner(z);//q=p_{n-k-1}
34      }
35     return c;
36    }
37 }//ende class Polynom
Die Daten der Klasse Polynom sind zum einen der Koeffizientenvektor double[] a sowie ihr Grad int Grad. Dieser wird dem Konstruktor nicht mitgeteilt, sondern dort aus der Länge des Feldes a berechnet - was dann mathematisch nicht korrekt ist, wenn die letzte Komponente des Feldes a verschwinden sollte.

Da Polynom eine Unterklasse von Funktion1 ist, muss die dort als abstract aufgeführte Methode getY() implementiert werden (Zeilen 19-25).

In der for-Schleife werden die Koeffizienten c[k] des umgeordneten Polynoms mit Schleifenlaufvariable k berechnet. Man achte auf die fett (nicht farbig) hervorgehobenen Termini, die schon in früheren Beispielen erläutert wurden, aber sicher noch gewöhnungsbedürftig sind.

Weiter mit "Polynominterpolation"