Sekantenverfahren

Sekantenverfahren

Bei dem Sekantenverfahren handelt es sich um ein schon seit dem Mittelalter bekanntes numerisches Verfahren zur näherungsweisen Lösung einer reellen Gleichung des Typs f(x) = 0. Es entspricht einer Vereinfachung des Newton-Verfahrens, da nicht die Ableitung der Funktion berechnet werden muss.

Inhaltsverzeichnis

Verfahren

Zwischen zwei Punkten P(x1 | f(x1)) und Q(x2 | f(x2)) der Funktion f wird eine Sekante gelegt. Der Schnittpunkt der Sekante mit der X-Achse wird als verbesserter Startwert x3 für die Iteration verwendet. Mithilfe von x3 wird der neue Funktionswert f(x3) berechnet. Mit f(x3) und dem alten Wert f(x2) wird dieser Schritt wiederholt und erneut eine Sekante angelegt. Man wiederholt diesen Schritt solange, bis eine ausreichende Näherung der gesuchten Nullstelle erreicht wurde. Die folgende Animation zeigt, wie mit den Startwerten x1 und x2 weitere Punkte konstruiert werden.

Konstruktion am Graphen

Animation zeigt mehrere Iterationsschritte des Sekantenverfahrens

Das Verfahren verwendet folgende Iterationsvorschrift:

 x_{n+1} = x_n - \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1}) } \cdot f(x_n)

Dabei wird mit zwei Näherungswerten  x_0, x_1 \, begonnen.

Herleitung aus dem Newton-Verfahren

Das Verfahren lässt sich aus dem Newtonschen Näherungsverfahren mit der Iterationsvorschrift

 x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}

herleiten, indem man die Ableitung f'(x) durch den Differenzenquotienten

 f'(x_i) \approx \frac{f(x_i)-f(x_{i-1})}{x_i - x_{i-1}}

ersetzt.

Konvergenz

Aufgrund der Verwandtschaft zum Newtonschen Verfahren gelten für die Konvergenz des Sekantenverfahrens ähnliche Bedingungen:

  • Das Sekantenverfahren konvergiert superlinear mit Konstanten 1,618, (dies entspricht dem Verhältnis des goldenen Schnittes), d.h. die Zahl der korrekten Stellen des Näherungswertes erhöht sich pro Durchgang um mehr als eine. Dies hängt damit zusammen, dass der Differenzenquotient nur eine Näherung für die Ableitung ist, entsprechend geringer ist die Konvergenz im Vergleich zum quadratisch konvergenten Newton-Verfahren.
  • Die Funktion f muss im Definitionsbereich stetig verlaufen und genau eine Nullstelle besitzen.
  • Das Verfahren verliert an Genauigkeit und Konvergenzgeschwindigkeit, wenn die Ableitung f'(x) an der Nullstelle 0 wird, da sich in der Berechnung ein Ausdruck der Form  x_{n+1} = x_n - \frac{0}{0} \cdot f(x_n) ergibt. Speziell bei Polynomen entspricht dies einer mehrfachen Nullstelle.
 \frac{f(x_i)-f(x_{i-1})}{x_i - x_{i-1}}
mit zunehmender Annäherung an die Nullstelle durch Auslöschung der Ziffern in die Form 0/0 übergeht. Während das Verfahren selbst die Abschätzung für die Nullstelle immer weiter verbessern könnte, wird in der tatsächlichen Berechnung dieser Gewinn in der Nähe der Nullstelle durch zunehmende Rundungsfehler überkompensiert. Dadurch lässt sich auf Rechnern mit endlicher Stellenzahl prinzipiell mit dem Sekantenverfahren nicht die Genauigkeit des Newtonschen Verfahrens erreichen.

Vorteile des Verfahrens

Gegenüber dem Newtonschen Verfahren ergeben sich mehrere Vorteile:

  • Es müssen nur die Funktionswerte berechnet werden. Im Gegensatz zur Newton-Iteration können damit die Nullstellen jeder beliebigen, hinreichend glatten Funktion auch ohne Kenntnis oder Berechnung der Ableitungen berechnet werden.
  • Je Iterationsschritt muss nur die Funktion f(x) einmal berechnet werden. Beim Newtonverfahren muss zusätzlich auch noch der Funktionswert der Ableitung f'(x) bestimmt werden.
  • Durch die Vorgabe von zwei Startwerten lässt sich das Verfahren besser auf ein bestimmtes Intervall fokussieren, da die Richtung der Sekante durch die beiden Startwerte vorgegeben wird. Die Konvergenz kann dadurch allerdings nicht erzwungen werden.

Das Sekantenverfahren im Mehrdimensionalen

Analog zum mehrdimensionalen Newton-Verfahren kann man auch ein mehrdimensionales Sekantenverfahren definieren, um Nullstellen von Funktionen f: D \subset \mathbb{R}^{n} \to \mathbb{R}^{n} zu bestimmen.

Wurde im eindimensionalen die Ableitung durch den Differenzenquotient approximiert, so wird im mehrdimensionalen die Jacobi-Matrix approximiert:

 J(x):=\frac{\partial f_i}{\partial x_j}
=\begin{pmatrix}
  \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \ldots & \frac{\partial f_1}{\partial x_n} \\
  \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \ldots & \frac{\partial f_2}{\partial x_n} \\
  \vdots & \vdots & \ddots & \vdots \\
  \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & \ldots & \frac{\partial f_n}{\partial x_n}\end{pmatrix}
\approx \tilde J(x,h)= (F(x,h)_{jk})_{j,k\in\{1,\ldots,n\}}

wobei F(x,h)jk zu einer gegebenen Schrittweitenmatrix h\in \R^{n \times n} definiert ist durch:

F(x,h)_{jk}:=\begin{cases}
  \frac{\partial f_j}{\partial x_k (x)},  & \text{falls }h_{jk}=0\\
  \frac{ f_j(x+h_{jk} e_{k}) - f_j (x)}{ h_{jk}}, & \text{sonst}
\end{cases} ,\quad sofern x, x+h_{jk} e_{k} \in D ist.

Nun ergibt sich analog zum Newtonverfahren folgende Iterationsvorschrift:

x_{n+1} = x_n - (\tilde J(x,h))^{-1} \cdot f(x_n)

Da das Lösen von

\Delta x_{n} := (\tilde J(x_{n},h))^{-1}f(x_{n})\;,

über die Berechnung der Inversen einer Matrix und anschließender Multiplikation mit f(xn) aufwändiger und numerisch ungünstiger ist, wird statt dessen das lineare Gleichungssystem

\tilde J(x_{n},h)\;\Delta x_n = f(x_{n})

gelöst. Danach erhält man xn + 1 aus:

xn + 1 = xn − Δxn.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sekantenverfahren — Sekạntenverfahren,   Mathematik: Regula Falsi. * * * Se|kạn|ten|ver|fah|ren, das <o. Pl.> (Math.): Regula Falsi …   Universal-Lexikon

  • Brent-Verfahren — Das Brent Verfahren ist ein Verfahren der numerischen Mathematik zur iterativen Bestimmung einer Nullstelle, welches die Bisektion, das Sekantenverfahren (bzw. Lineare Interpolation) und die inverse quadratische Interpolation miteinander… …   Deutsch Wikipedia

  • Regula Falsi — Das Regula Falsi Verfahren (lat. „Regel des falschen Ansatzes“) ist eine Methode zum numerischen Berechnen von Nullstellen reeller Funktionen. Es kombiniert Methoden vom Sekantenverfahren und der Bisektion. Inhaltsverzeichnis 1 Das Verfahren… …   Deutsch Wikipedia

  • Globale Optimierung — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • Optimierungsalgorithmus — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Optimierungstheorie — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Optimierungsverfahren — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Regula falsi — Das Regula falsi Verfahren (lateinisch: regula falsi = „Regel des Falschen“), auch: Regula duarum falsarum Posicionum (lateinisch: regula duarum falsarum posicionum = „Regel vom zweifachen falschen Ansatz“),[1][2] Falsirechnung rsp. Falsi… …   Deutsch Wikipedia

  • Zielfunktion — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”