numerik:bisektion
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | numerik:bisektion [2015-07-04 14:47] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
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, | ||
+ | <code cpp bisektion.cpp> | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | template < | ||
+ | auto midpoint(Domain a, Domain b) { return (a + b) / 2; } | ||
+ | |||
+ | template < | ||
+ | std:: | ||
+ | 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:: | ||
+ | auto x = root_bisection(f, | ||
+ | |||
+ | auto a = x.first, b = x.second; | ||
+ | std::cout << a << " " << b << | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Die [[http:// | ||
+ | |||
+ | <code cpp bisektion.h> | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | template < | ||
+ | auto midpoint(Domain a, Domain b) { return (a + b) / 2; } | ||
+ | |||
+ | template < | ||
+ | auto distance(Domain a, Domain b) { using std::abs; return abs(a - b); } | ||
+ | |||
+ | template < | ||
+ | std:: | ||
+ | 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, | ||
+ | { | ||
+ | auto m = midpoint(a, b); | ||
+ | auto ym = f(m); | ||
+ | if (ya * ym < 0) { b = m; } | ||
+ | else { a = m; ya = ym; } | ||
+ | } | ||
+ | return {a, b}; | ||
+ | } | ||
+ | </ |
numerik/bisektion.txt · Zuletzt geändert: 2015-07-04 14:47 von 127.0.0.1