Lexikon der Mathematik: Bisektion
Verfahren zur iterativen Berechnung einer Nullstelle ζ eines Polynoms p(x) durch Intervallschachtelung.
Man startet mit einem Intervall [a0, b0], welches ζ sicher enthält. Dann halbiert man sukzessive dieses Intervall und testet, in welchem der beiden sich ergebenden Teilintervalle ζ liegt. Man bildet also
\begin{eqnarray}\text{f}\mathop{\text{u}}\limits^{\mathrm{..}}\text{r}\text{\hspace{0.17em}}j=0,1,2,\ldots :\\ {\mu }_{j}=({a}_{j}+{b}_{j})/2,\\ {a}_{j+1}=\{{a}_{j}\text{\hspace{0.17em}}\text{falls}\text{\hspace{0.17em}}\zeta \in [{a}_{j},{\mu }_{j}],\\ {\mu }_{j}\text{\hspace{0.17em}}\text{falls}\text{\hspace{0.17em}}\zeta \in [{\mu }_{j},{b}_{j}]\\ {b}_{j+1}=\{{\mu }_{j}\text{\hspace{0.17em}}\text{falls}\text{\hspace{0.17em}}\zeta \in [{a}_{j},{\mu }_{j}]\\ {b}_{j}\text{\hspace{0.17em}}\text{falls}\text{\hspace{0.17em}}\zeta \in [{\mu }_{j},{b}_{j}].\end{eqnarray}
\begin{eqnarray}\zeta \in [{a}_{j+1},{b}_{j+1}]\subset [{a}_{j},{b}_{j}]\end{eqnarray}
und\begin{eqnarray}|{b}_{j+1}-{a}_{j+1}|=|{b}_{j}-{a}_{j}|/2.\end{eqnarray}
Die aj konvergieren monoton wachsend, die bj monoton fallend gegen ζ. Die Konvergenz ist linear.Beginnt man z. B. mit einem Intervall I = \([{a}_{0},{b}_{0}]\), so daß
\begin{eqnarray}P({a}_{0})\cdot p({b}_{0})\lt 0\end{eqnarray}
gilt, dann existiert aus Stetigkeitsgründen eine Nullstelle ζ im Inneren von I.Der Test, in welchem Teilintervall ζ liegt, ist hier sehr einfach: \(\zeta \in [{a}_{j},{\mu }_{j}]\), falls \(p(a)p({\mu }_{j})\lt 0\), andernfalls \(\zeta \in [{\mu }_{j},{b}_{j}]\).
Bisektion wird auch zur Eigenwertberechnung reeller, symmetrischer Tridiagonalmatrizen mittels Sturmscher Ketten verwendet. Dabei ist der Test, in welchem Teilintervall ζ sich befindet, ebenfalls einfach.
Schreiben Sie uns!