namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


numerik:bisektion

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

numerik:bisektion [2015-07-04 14:47] (aktuell)
Zeile 1: Zeile 1:
 +====== Bisektionsverfahren ======
 +Der Zwischenwertsatz besagt: Jede stetige Funktion $f$ nimmt im Intervall $[a,b]$ jeden Wert von $f(a)$ und $f(b)$ mindestens einmal an. 
 +Bei einem Vorzeichenwechsel im Intervall $[a,b]$ muss es also mindestens eine Nullstelle geben.
  
 +Nicht das schnellste, aber das robustete Verfahren ist die Intervallhalbierung. Untersucht wird das Vorzeichen in der Mitte $m$ der Intervalls. Je nachdem, ob der Vorzeichenwechsel in der Hälfte $[a,m]$ oder in der Hälfte $[m,b]$ stattfindet,​ wird dort weiter gesucht, bis die Genauigkeitsanforderungen erfüllt sind oder eine genügende Anzahl von Halbierungsschritten unternommen wurde. Am Ende wird ein (engeres) Intervall geliefert, das die Nullstelle sicher einschließt:​
 +<code cpp bisektion.cpp>​
 +#include <​cassert>​
 +#include <​cmath>​
 +#include <​iostream>​
 +#include <​utility>​
 +
 +template <​typename Domain>
 +auto midpoint(Domain a, Domain b) { return (a + b) / 2; }
 +
 +template <​typename Function, typename Domain>
 +std::​pair<​Domain,​ Domain> ​
 +root_bisection(Function f, Domain a, Domain b, int steps = 50)
 +{
 +  assert(f(a) * f(b) < 0);
 +  auto ya = f(a);
 +
 +  while (steps-- > 0)
 +  {
 +    auto m = midpoint(a, b);
 +    auto ym = f(m);
 +    if (ya * ym < 0) { b = m; }
 +    else { a = m; ya = ym; }
 +  }
 +  return {a, b};
 +}
 +
 +int main()
 +{
 +  auto f = [](double x) { return std::​sin(x);​ };
 +  auto x = root_bisection(f,​ 3.0, 4.0);
 +
 +  auto a = x.first, b = x.second;
 +  std::cout << a << " " << b << ​ " : " << f(a) << " " << f(b) << '​\n';​
 +  return 0;
 +}
 +</​code>​
 +
 +Die [[http://​www.boost.org/​doc/​libs/​1_57_0/​libs/​math/​doc/​html/​math_toolkit/​internals1/​roots2.html|Boost.Math]]-Bibliothek enthält ähnliche Routinen, setzt aber reellwertige Funktionen mit reellem Definitionsbereich voraus, während hier auch andere Grundbereiche (''​Domain''​) erlaubt sind. Template-Varianten mit vorgegebenem Abstand ''​distance(Domain a, Domain b)''​ sind leicht abzuleiten und durch Spezialisierung der Funktionen ''​midpoint(a,​b)''​ bzw. ''​distance(a,​b)''​ erweiterbar:​
 +
 +<code cpp bisektion.h>​
 +#include <​cassert>​
 +#include <​cmath>​
 +#include <​utility>​
 +
 +template <​typename Domain>
 +auto midpoint(Domain a, Domain b) { return (a + b) / 2; }
 +
 +template <​typename Domain>
 +auto distance(Domain a, Domain b) { using std::abs; return abs(a - b); }
 +
 +template <​typename Function, typename Domain, typename Distance>​
 +std::​pair<​Domain,​ Domain> ​
 +root_bisection(Function f, Domain a, Domain b, Distance epsilon, int steps = 50)
 +{
 +  assert(f(a) * f(b) < 0);
 +  auto ya = f(a);
 +
 +  while (distance(a,​ b) > epsilon && steps-- > 0)
 +  {
 +    auto m = midpoint(a, b);
 +    auto ym = f(m);
 +    if (ya * ym < 0) { b = m; }
 +    else { a = m; ya = ym; }
 +  }
 +  return {a, b};
 +}
 +</​code>​
numerik/bisektion.txt · Zuletzt geändert: 2015-07-04 14:47 (Externe Bearbeitung)