iteratives Verfahren zur Berechnung von Eigenwerten einer reellen symmetrischen Tridia gonalmatrix \begin{eqnarray}T=\left(\begin{array}{llll}{\alpha}_{1} & {\beta}_{1} & & \\ {\beta}_{2} & {\alpha}_{2} & \ddots & \\ & \ddots & \ddots & {\beta}_{n}\\ & & {\beta}_{n} & {\alpha}_{n}\end{array}\right),\end{eqnarray}

das auf der Regel von Sturm (Sturm, Regel von) beruht.

Ist p_i(x) das charakteristische Polynom der i-ten Hauptabschnittsmatrix von T − xI, so gilt \begin{eqnarray}\begin{array}{lll}{p}_{0}(x) & = & 1\\ {p}_{1}(x) & = & {\alpha}_{1}-x\\ {p}_{i}(x) & = & ({\alpha}_{i}-x){p}_{i-1}(x)-{\beta}_{1}^{2}{p}_{i-2}(x)\\ & & i=2,3,\ldots, n\end{array}\end{eqnarray}

Dabei ist p_n(x) = det(T − xI) das charakteristische Polynom von T, dessen Nullstellen gerade die Eigenwerte von T sind. Für β_i ≠ 0, i = 2, …, n bilden die Polynome \begin{eqnarray}{p}_{n}(x),{p}_{n-1},\ldots, {p}_{0}(x)\end{eqnarray}

eine Sturmsche Kette für p_n(x); darunter versteht man eine Folge von Polynomen q_n(x), q_n−1 (x), …, q₀(x) absteigenden Grades mit folgenden Eigenschaften:

1. q_n(x) besitzt nur einfache Nullstellen.
2. sgn(q_n−1 (ζ)) = − sgn(q′_n (x)) für alle reellen Nullstellen ζ von q_n(x).
3. Für i = n − 1, n − 2, …, 1 gilt \begin{eqnarray}{q}_{i+1}(\zeta){q}_{i-1}(\zeta)\lt 0,\end{eqnarray} falls ζ Nullstelle von q_i(x) ist.
4. Das letzte Polynom q₀(x) ändert sein Vorzeichen nicht.

Es gilt, daß die Anzahl der reellen Nullstellen von q_n(x) im Intervall a ≤ x< b gleich |w(b) − w(a)| ist, wobei w(x) die Anzahl der Vorzeichenwechsel der Sturmschen Kette q_n(x), q_n−1 (x), …, q₀(x) an der Stelle x ist (hierbei streicht man zunächst alle q_i(x) = 0 und zählt dann die Anzahl der Vorzeichenwechsel). Ein Beispiel für eine Sturmsche Kette ist \begin{eqnarray}\begin{array}{lll}{q}_{3}(x) & = & {x}^{3}-6{x}^{2}-11x-6\\ {q}_{2}(x) & = & 3{x}^{2}-12x+11\\ {q}_{1}(x) & = & \displaystyle\frac{2}{3}x-\displaystyle\frac{4}{3}\\ {q}_{0}(x) & = & 1\end{array}\end{eqnarray}

Die Anzahl der Nullstellen von q₃(x) im Intervall [0, 2.5] ist gleich |w(2.5) − w(0)| = |1 − 3| = 2, da \begin{eqnarray}\begin{array}{lll}{q}_{3}\left(\displaystyle\frac{5}{2}\right) & = & -\displaystyle\frac{-11}{4},\,{q}_{2}\left(\displaystyle\frac{5}{2}\right)=-\displaystyle\frac{1}{4},\\ {q}_{1}\left(\displaystyle\frac{5}{2}\right) & = & \displaystyle\frac{1}{3},\,{q}_{0}\left(\displaystyle\frac{5}{2}\right)=1\end{array}\end{eqnarray}

und \begin{eqnarray}{q}_{3}(0)=-6,\,{q}_{2}(0)=11,\,{q}_{1}(0)=-\frac{4}{3},\,{q}_{0}(0)=1.\end{eqnarray}

Eine einfache Rechnung ergibt \begin{eqnarray}{q}_{3}(x)\text{}=\text{}(x\text{}-\text{}3)(x\text{}-\text{}2)(x\text{}-\text{}1)\text{},\end{eqnarray}

sodaß q₃(x) tatsächlich zwei Nullstellen im Intervall [0, 2.5] besitzt.

Man kann nun diese Eigenschaft der charakteristischen Polynome p_j(x) der Hauptabschnittsmatrizen einer symmetrischen Tridiagonalmatrix T nutzen, um die Eigenwerte von T (bzw. die Nullstellen von p_n(x)) mittels Bisektion zu berechnen. T besitzt nur einfache reelle Eigenwerte \begin{eqnarray}{\zeta}_{1}\gt {\zeta}_{2}\gt \ldots \gt {\zeta}_{n}.\end{eqnarray}

Für x =−∞ besitzt die Sturmsche Kette \begin{eqnarray}{p}_{n}(x),\,{p}_{n-1}(x),\ldots, {p}_{0}(x)\end{eqnarray}

die Vorzeichenverteilung +, +, …, +, also gilt w(−∞) = 0. Daher gibt w(µ) gerade die Anzahl der Nullstellen ζ von p_n(x) mit ζ< µ an: w(µ) ≥ n + 1 − i genau dann, wenn ζ_i< µ. Um nun die i-te Nullstelle ζ_i von p_n(x) mittels Bisektion zu bestimmen, startet man mit einem Intervall [a₀, b₀ ], welches ζ_i sicher enthält. Dann halbiert man sukzessive dieses Intervall und testet, in welchem der beiden Teilintervalle ζ liegt. Man bildet also für j = 0, 1, 2, …: \begin{eqnarray}\begin{array}{l}{\mu}_{j}=({a}_{j}+{b}_{j})/2,\\ {a}_{j+1}=\left\{\begin{array}{lll}{a}_{j} & \text{falls} & w({\mu}_{j})\ge n+1-i\\ {\mu}_{j} & \text{falls} & w({\mu}_{j})\lt n+1-i\end{array}\\ {b}_{j+1}=\{\begin{array}{lll}{\mu}_{j} & \text{falls} & w({\mu}_{j})\ge n+1-i\\ {b}_{j} & \text{falls} & w({\mu}_{j})\lt n+1-i\end{array}\right.\end{array}\end{eqnarray}

Die a_j konvergieren monoton wachsend, die b_j monoton fallend gegen ζ_i. Die Konvergenz ist linear.