[WS] Grundlegende Algorithmen in der Numerik

27.08.2008, 16:44

[WS] Grundlegende Algorithmen in der Numerik

Hallo,
ich möchte euch heute ein paar grundlegenden numerische Algorithmen vorstellen. Dieser Artikel soll weniger die Theorie behandeln, sonder eher wie man diese konrekt Umsetz. Dazu wird hier Java verwendet, sollte aber einem leicht fallen dieses in eine andere Sprache zu portieren.

Dieser Workshop ist nur als kleine, praxisnahe Einführung gedacht. Außergewöhnliches Hochschulwissen braucht man nicht, nur etwas programmieren sollte man können.

Nullstellen finden per Binärteilung
Nullstellen spielen einen zentrale Rolle. Wenn man einen Algorithmus findet, der Effektiv die Nullstellen einer beliebigen Funktion findet, lassen sich damit sehr viele Probleme lösen.
Möchte man dann z.B. die Wurzel 2 ziehen, muss man nur die Nullstelle von x^2 - 2 finden.

Mit Binärteilung kann man relativ effizient eine Nullstelle finden, sofern die Funktion bestimmte Voraussetzungen erfüllt.
Zuerst einmal sollte es eine stetige (reelle) Funkion sein. Für die Binärteilung müssen wir einen negativen und einen positiven Funktionswert finden, nach dem Zwischenwertsatz weiß man dann, dass zwischen diesen beiden Stellen min. eine Nullstelle liegt.
Sollten mehr als eine Nullstelle in dem Abschnitt existieren, so findet unsere Binärteilung eine Nullstelle, wir wissen aber nicht welche.

Was mit der Binärteilung nicht funktioniert, ist nur 'Berührungspunkte' des Graphen mit der x Achse zu finden.

Algorihmus - Abstrakt:
Man hat ein Intervall [a,b] gegeben, wobei f(a) und f(b) verschiedene Vorzeichen haben müssen.
Dann berechnet man die Mitte des Intervalls, also $\begin{eqnarray*} m = \frac{a+b}{2} \end{eqnarray*}$ und berechnet dann f(m).

Haben f(a) und f(m) das selbe Vorzeichen, so verschiebt man die linke Seite, also a, nach m, denn wir wissen, dass die Nullstelle im Intervall [m, b] liegen muss.
Haben die verschiedene Vorzeichen, ist das neue Intervall indem die Nullstelle liegt [a, m].
Dies kann man nun beliebig oft wiederhohlen, mit jedem Schritt halbiert sich die größe unserer Intervalls, weswegen wir sehr schnell eine guten Wert für die Nullstelle erhalten.

Algorithmus - Java:

In Java sieht das ganze so aus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:

class Binaerteilung {
   
      //Dieser Variable enthält die Konstante die für die Funktion f
      //verwendet wird. Also die gefundene Nullstelle
      //ist gleich der Wurzel aus dieser Zahl.
      public static double zahl = 2;
      
      public static void main(String[] args){         
         System.out.println("Nullstelle von f bei: "+findeNST(0,zahl));
         System.out.println("Sqrt von "+zahl+": "+Math.sqrt(zahl));
      }
   
      //eine Funktion f, fuer die die NST bestimmt werden soll
      static double f(double x) {
           return x*x - zahl; //hier x^2 - zahl;
      }
    
      static double findeNST(double a, double b) {
          double fa, fb, fm;
          double m = 0;
          fa = f(a);
          fb = f(b);
          if(fa == 0)
              return a;
          if(fb == 0)
              return b;


          //Hier lässt sich die Genauigkeit regeln
          for(int i=0; i<50; i++) {
              m = (a+b)/2;
            fm = f(m);

            if(fm == 0)
               return m;

            //haben f(a) und f(m) gleiches Vorzeichen
            if(fa * fm > 0) {
                 a = m;
                 fa = fm;
            } else {
                 b = m;
                 fb = fm;
            }
          }

          return m;
     }
}

Mit diesem kleinen Code lässt sich z.B. die Wurzel (sqrt) aus einer beliebigen Zahl bestimmen.
Denn die Wurzel aus c, ist einfach die Nullstelle von x^2 - c. Man weiß, dass die Nullstelle von x^2 - c im Intervall [0, c] liegen muss.

Maximum per Dreiteilung finden
Hier gehen wir davon aus, dass in dem Intervall [a,b] ein lokales Maximum liegt, welches wir finden möchten.
Sind mehrere lokale Maxima enthalten, wird nur eins gefunden, wovon wir aber nicht sagen können welches.
Deswegen ist es ratsam, wenn nur eins in [a,b] enthalten ist Augenzwinkern

Algorithmus - Abstrakt:
Man unterteil das Intervall [a, b] in drei gleichgoße Teile.
Dazu berechnet man den Abstand dx von a und b und drittelt diesen, also $\begin{eqnarray*} dx = \frac{b-a}{3} \end{eqnarray*}$ .
Anschließend berechnet man die Funktionswerte f(a+dx) und f(b-dx).

Ist f(a+h) größer als f(b-h), so zieht man die rechte Grenze des Intervalls, also b, dran, also b bekommt dann den Wert b-h.
Ist es anderes herum, zieht man a dran.

Dies kann man sich am besten mal bei einer umgedrehten Parabel (z.B. -x^2 + 10) veranschaulichen.

Algorithmus - Java:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:

public class max {

	public static void main(String[] args){		
		System.out.println("Findet das Maximum von Sinus zwischen 0 und 3");
		System.out.println("Max:" + maximum(0, 3) + " mit Funktionswert: "+f(maximum(0, 3)));
	}
		

	
	//Von dieser Funktion soll das Maximum gefunden werden
	public static double f(double x){
		return Math.sin(x);
	}
	
	
	public static double maximum(double left, double right) {		
		double varL, varR;
		double iL, iR;
		double dx;
		
		for(int i=0;i<50;i++){
			dx = (right-left)/3;
			iL = left + dx;
			iR = right - dx;
			
			varL = f(iL);
			varR = f(iR);
			
			if(varL < varR) 
				left = iL;
			else
				right = iR;
		}
		
		
		return (left+right)/2;
	}
	
}

numerische Integration
Sicher kennt jeder noch die Verfahren, bei denen man diese kleinen Rechtecke oder Trapeze unter einen Graphen einzeichnet und ausmisst, um so Näherungsweise den Flächeninhalt zu bekommen.

Da ich momentan keine Lust mehr habe dazu viel zu schreiben, hier nur der Code:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:

public class Integration {
	
	public static void main(String[] args){
		System.out.println("Von -5 bis 5, korrektes Ergebnis:"+(250/3.0));
		System.out.println("Von -5 bis 5 per Rechtecke:"+rechtecke(-5,5,100));
		System.out.println("Von -5 bis 5 per Trapez:"+trapez(-5,5,100));
	}
	
	//Die Funktion die integriert werden soll, hier x^2
	public static double f(double x) {
		return x*x; 
	}

	//Integriert die Funktion f über [a,b], mit n+1 Unterteilungen

        //Zeichnet kleine Rechtecke darunter, wobei hier
        // eine Kombination aus Ober- und Untersumme genutzt wird
	public static double rechtecke(double a, double b, double n){
		double sum = 0;
		double h = (b-a)/n;
		
		for(int i=0;i<=n;i++) {
			sum += f(a+i*h) * h;			
		}		
		
		
		return sum;		
	}
	
        //Zeichnet Trapeze ein und rechnet deren Flächeninhalt mit der Formel
        // A = (a+c)/2 * h aus.
        // a und c sind entsprechend zwei Funktionswerte.
	public static double trapez(double a, double b, double n){
		double sum = 0;
		double h = (b-a)/n;
		double f_alt = f(a);
		double f_neu;
		
		for(int i=1;i<=n;i++) {
			f_neu = f(a+i*h);			
			sum += (f_alt + f_neu)/2 * h;	
			
			f_alt = f_neu;
		}
		
		
		
		return sum;		
	}
}

Vielleicht kann ich das später noch ergänzen.

Neue Frage »

Antworten »

[WS] Grundlegende Algorithmen in der Numerik

Verwandte Themen