Abou-Zahra
[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Sekantenverfahren

In Kapitel 10.2 wurde das Sekantenverfahren für nichtlineare Skalare als Vereinfachung des Newtonverfahrens vorgestellt. Dabei wurde mit der Diskretisierungsschrittweite h die bisher notwendige Ableitung durch eine Näherung ersetzt. Grafisch kann man sich das als eine Sekante des Funktionsgraphen an den Stellen F(x(k)) und F(x(k-1)) statt einer Tangente vorstellen. Die linearisierte Modellfunktion

l(k) = f(x(k)) + (x - x(k)) ( f(x(k) + h(k)) - f(x(k) ) / h(k) = 0

kann man auf zwei Arten interpretieren:

  1. Näherung der Tangentengleichung

    l(k) = f(x(k)) + (x - x(k)) f '(x(k)) = 0

    Auf Systeme nichtlinearer Gleichungen übertragen wird die Näherung A(x,h) für F'(x) gebildet, wobei jede Spalte S(i) der n mal n Matrix A(x,h) durch eine Diskretisierungsschrittweitenfunktion h(i)(x) errechnet wird:

    S(i) = A(x,h)e(i) = [ F(x + h(i)e(i)) - F(x) ] / h(k)

    i = 1,2,3... n
    e(i) ist der i-te Einheitsvektor
    Die Diskretisierungsschrittweite wird je nach Methode anders errechnet; eine Möglichkeit:

    h(i) = { e|x(i)| falls x(i) = 0; sonst e}.

  2. Lineare Interpolation:
    Bei Systemen nichtlinearer Gleichungen werden n Hyperebenen ermittelt (aus n + 1 Punkten x(k,j), j = 0,1,...n aus der Umgebung von x(k)). Die Ebenen haben folgenede Gestallt:

    L(x) = a(i)Tx + ci.

    Der Schnittpunkt aller Ebenen mit der Hyperebene y = 0 ist der Vektor für den nächsten Iterationsschritt x(k+1).

    Beispiel: Wir nehmen ein eindimensoinales Problem (n = 1), also eine Funktion im zweidimensionalen Raum:

    f(x) = x3 - x2 - x - 1; x0 = 1,5; x0,0 = 1; x0,1 = 2

    X hoch 3 Kurve mit 2 Sekanten

    l0 wurde durch die Punkte (x0,0; f(x0,0)) und (x0,1; f(x0,1)) errechnet:

    l0 = 3x - 5.

    Der Schnittpunkt von l0 mit y = 0 ergibt dann den Vektor für den nächsten Iterationsschritt. Also x1 = 5/3.
    Daraus nehmen wir die Punkte x1,0 = 7/6 und x1,1 = 13/6 und berechnen l2 aus (x1,0; f(x1,0)) und (x1,1; f(x1,1)).
    So enger die Punkte x(k,j) zu einander sind, um so genauer ist die Nährung.

    Beispiel: Wir nehmen ein zweidimensoinales Problem (n = 2), also eine Funktion im dreidimensionalen Raum.

    X hoch 3 Ebene geschnitten mit flacher Ebene

    Ausgehend von einen Punkt P ermitteln wir drei Punkte A,B,C aus der Umgebung von P. (P = x(k); A = x(k,0); B = x(k,1); C = x(k,2);) Die Punkte a,b,c sind jeweils (A,F(A)), (B,F(B)), (C,F(C)).
    Aus diese drei Punkte koennen wir eine neue Ebene L(x) erzeugen. Deren Schnittpunkt mit der y=0 Hyperebene für die ermittlung von x(k+1) notwendig ist.

Modifikationsverfahren

Eine Erweiterung des diskretisierten Newton Verfahrens zur Veringerung des Aufwandes bei der Bestimmung der Ableitung F'(x) ist das Modifikationsverfahren. Das Prinzip ist, nur mit einer groben Schätzung A(k) für F'(x) zu arbeiten, die dafür besonders schnell zu errechnen ist. Dies wird durch Addition einer Rang-1 Matrix zu A(k-1) erreicht:

A(k+1) := A(k) + u(k)[v(k)]T

u(k),v(k) $\in \BbbR ^n$
k = 0,1,..

Je nach Methode wird u,v anders berechnet. Beim Broyden- Verfahren werden u,v so gewählt, daß sie sich der Sekantenschrittweite h nähern. Diese Sekantenapproximation verringert den Rechenaufwand des Newtonverfahrens von O(n3) statt O(n2).


[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]