Собственные значения симметричной трехдиагональной матрицы можно находить без раскрытия характеристического определителя и непосредственного решения алгебраического уравнения высокой степени. Для этого применяют метод половинного деления, основанный на свойствах последовательности Штурма. Сначала строят последовательность многочленов, затем по изменениям знаков её членов определяют расположение искомого собственного значения, после чего постепенно сужают интервал, в котором оно находится.
Собственные Значения Симметричной Трехдиагональной Матрицы: Постановка Задачи
Пусть задана симметричная трехдиагональная матрица \( A \) порядка \( n \):
\[
A=
\begin{pmatrix}
a_1 & b_1 & 0 & \cdots & 0 & 0\\
b_1 & a_2 & b_2 & \cdots & 0 & 0\\
0 & b_2 & a_3 & \ddots & 0 & 0\\
\vdots & \vdots & \ddots & \ddots & b_{n-2} & 0\\
0 & 0 & 0 & b_{n-2} & a_{n-1} & b_{n-1}\\
0 & 0 & 0 & 0 & b_{n-1} & a_n
\end{pmatrix}.
\]
Элементы матрицы \( A \) в общем виде можно задать следующим образом:
\[
a_{ij}=
\begin{cases}
a_i, & i=j,\\[4pt]
b_i, & j=i+1,\\[4pt]
b_j, & i=j+1,\\[4pt]
0, & |i-j|>1.
\end{cases}
\]
Ненулевые элементы такой матрицы расположены только на главной диагонали и двух соседних с ней диагоналях. Её симметричность означает, что
\[
a_{ij}=a_{ji}.
\]
Поэтому каждый элемент \( b_i \), расположенный над главной диагональю, равен соответствующему элементу под ней.
Симметричные трёхдиагональные матрицы возникают во многих прикладных задачах численных методов. Кроме того, нахождение собственных значений произвольной симметричной матрицы часто сводят к аналогичной задаче для симметричной трёхдиагональной матрицы. Благодаря её особой структуре объём необходимых вычислений значительно уменьшается.
Далее будем считать, что все внедиагональные элементы \( b_i \) отличны от нуля:
\[
b_i\neq 0,
\qquad
i=1,2,\dots,n-1.
\]
При этом условии матрица является неразложимой, а все её собственные значения действительны и попарно различны. Упорядочим их по убыванию:
\[
\lambda_1>\lambda_2>\dots>\lambda_n.
\]
Если некоторый элемент \( b_i \) равен нулю, матрица распадается на отдельные симметричные трёхдиагональные блоки. В таком случае собственные значения можно находить отдельно для каждого блока.
Последовательность Штурма: Построение Главных Миноров
Для построения последовательности Штурма рассмотрим главные подматрицы матрицы \( A \). Обозначим через \( A_i \) главную подматрицу порядка \( i \):
\[
A_i=
\begin{pmatrix}
a_1 & b_1 & 0 & \cdots & 0\\
b_1 & a_2 & b_2 & \cdots & 0\\
0 & b_2 & a_3 & \ddots & \vdots\\
\vdots & \vdots & \ddots & \ddots & b_{i-1}\\
0 & 0 & \cdots & b_{i-1} & a_i
\end{pmatrix},
\qquad
i=1,2,\dots,n.
\]
Для каждой подматрицы \( A_i \) введем многочлен
\[
p_i(\lambda)
=
\det\left(A_i-\lambda\cdot I_i\right),
\qquad
i=1,2,\dots,n,
\]
где \( I_i \) — единичная матрица порядка \( i \). Дополнительно положим
\[
p_0(\lambda)=1.
\]
Для главной подматрицы первого порядка имеем
\[
p_1(\lambda)=a_1-\lambda.
\]
Рассмотрим главную подматрицу второго порядка. Для неё получим:
\[
p_2(\lambda)
=
\det
\begin{pmatrix}
a_1-\lambda & b_1\\
b_1 & a_2-\lambda
\end{pmatrix}
=
(a_1-\lambda)\cdot(a_2-\lambda)-b_1^2.
\]
Поскольку
\[
p_0(\lambda)=1,
\qquad
p_1(\lambda)=a_1-\lambda,
\]
последнее равенство можно представить в виде
\[
p_2(\lambda)
=
(a_2-\lambda)\cdot p_1(\lambda)-b_1^2\cdot p_0(\lambda).
\]
Аналогично для главных подматриц более высоких порядков получаем рекуррентную формулу
\[
p_i(\lambda)
=
(a_i-\lambda)\cdot p_{i-1}(\lambda)-b_{i-1}^{2}\cdot p_{i-2}(\lambda),
\qquad
i=2,3,\dots,n.
\]
Таким образом, последовательно вычисляются многочлены
\[
p_0(\lambda),
p_1(\lambda),
p_2(\lambda),\dots,
p_n(\lambda).
\]
Поскольку \( A_n=A \), последний многочлен этой последовательности является характеристическим многочленом матрицы:
\[
p_n(\lambda)
=
\det\left(A-\lambda\cdot I\right).
\]
Поэтому собственные значения матрицы являются корнями уравнения
\[
p_n(\lambda)=0.
\]
Многочлены \( p_0(\lambda),p_1(\lambda),p_2(\lambda),\dots,p_n(\lambda) \) образуют последовательность Штурма. Для их вычисления не нужно отдельно раскрывать каждый определитель. Достаточно последовательно применять рекуррентную формулу, используя только два предыдущих значения.
Свойство Последовательности Штурма: Подсчет Собственных Значений
Пусть задано некоторое число \( \mu \). Подставим его вместо параметра ( \lambda ) и вычислим числовую последовательность
\[
p_0(\mu),
p_1(\mu),
p_2(\mu),\dots,
p_n(\mu).
\]
Обозначим через \( \nu(\mu) \) количество изменений знаков между соседними ненулевыми членами этой последовательности. Свойство последовательности Штурма состоит в том, что число \( \nu(\mu) \) равно количеству собственных значений матрицы, строго меньших \( \mu \).
Поскольку матрица имеет \( n \) собственных значений, количество собственных значений, строго больших \( \mu \), определяется по формуле
\[
s(\mu)=n-\nu(\mu).
\]
Таким образом, число \( s(\mu) \) показывает, сколько собственных значений удовлетворяют неравенству
\[
\lambda_i>\mu.
\]
Это свойство позволяет определить положение \( k \)-го собственного значения, не вычисляя его непосредственно. Если \( s(\mu)\geq k \), то справа от числа \( \mu \) расположено как минимум \( k \) собственных значений. Поэтому для \( k \)-го собственного значения, упорядоченного по убыванию, выполняется неравенство
\[
\lambda_k>\mu.
\]
Если же \( s(\mu)<k \), то справа от числа \( \mu \) расположено меньше \( k \) собственных значений. В этом случае
\[
\lambda_k\leq\mu.
\]
При подсчете изменений знаков некоторое промежуточное значение \( p_i(\mu) \) может оказаться равным нулю. Тогда его условный знак считают противоположным знаку предыдущего члена \( p_{i-1}(\mu) \). Это правило применяют только для правильного определения количества изменений знаков, и оно не изменяет самого значения многочлена.
При условии \( b_i\neq 0 \) два соседних члена последовательности Штурма не могут одновременно быть равны нулю.
Если \( p_n(\mu)=0 \), то число \( \mu \) является точным собственным значением матрицы.
Метод Половинного Деления: Вычислительная Схема
Для применения метода половинного деления сначала необходимо определить интервал, содержащий все собственные значения матрицы. Если его границы заранее неизвестны, можно воспользоваться бесконечной нормой матрицы:
\[
\lVert A\rVert_{\infty}
=
\max_{1\leq i\leq n}
\left(
|b_{i-1}|+|a_i|+|b_i|
\right),
\qquad
b_0=b_n=0.
\]
Все собственные значения симметричной матрицы \( A \) принадлежат интервалу
\[
-\lVert A\rVert_{\infty}
\leq
\lambda_i
\leq
\lVert A\rVert_{\infty}.
\]
Поэтому начальные границы можно выбрать следующим образом:
\[
\alpha_0=-\lVert A\rVert_{\infty},
\qquad
\beta_0=\lVert A\rVert_{\infty}.
\]
Для нахождения \( k \)-го собственного значения, где \( k=1,2,\dots,n \), на \( r \)-й итерации вычисляют середину текущего интервала:
\[
c_r=
\frac{\alpha_{r-1}+\beta_{r-1}}{2},
\qquad
r=1,2,3,\dots.
\]
Для числа \( c_r \) по рекуррентной формуле находят значения
\[
p_0(c_r),
p_1(c_r),
p_2(c_r),\dots,
p_n(c_r).
\]
После этого определяют количество изменений знаков \( \nu(c_r) \), а затем вычисляют количество собственных значений, больших \( c_r \):
\[
s(c_r)=n-\nu(c_r).
\]
Если \( p_n(c_r)=0 \), то число \( c_r \) является собственным значением матрицы, поэтому вычисления завершают.
Если \( s(c_r)\geq k \), то выполняется неравенство
\[
\lambda_k>c_r.
\]
Следовательно, искомое собственное значение находится в правой половине текущего интервала. Новые границы задают следующим образом:
\[
\alpha_r=c_r,
\qquad
\beta_r=\beta_{r-1}.
\]
Если \( s(c_r)<k \), то выполняется неравенство
\[
\lambda_k\leq c_r.
\]
В этом случае искомое собственное значение находится в левой половине текущего интервала, поэтому полагают
\[
\alpha_r=\alpha_{r-1},
\qquad
\beta_r=c_r.
\]
После каждой итерации сохраняется включение
\[
\lambda_k\in[\alpha_r,\beta_r],
\]
а длина интервала уменьшается вдвое.
Итерационный процесс продолжают до тех пор, пока не выполнится условие
\[
\frac{\beta_r-\alpha_r}{2}\leq\varepsilon,
\]
где \( \varepsilon \) — заданная точность вычислений.
После завершения итераций приближённое значение \( k \)-го собственного значения определяют как середину последнего интервала:
\[
\lambda_k
\approx
\frac{\alpha_r+\beta_r}{2}.
\]
Погрешность полученного приближения не превышает половины длины этого интервала:
\[
\left|
\lambda_k-
\frac{\alpha_r+\beta_r}{2}
\right|
\leq
\frac{\beta_r-\alpha_r}{2}.
\]
Таким образом, после завершения итераций получаем приближённое значение \( \lambda_k \), абсолютная погрешность которого не превышает половины длины последнего интервала.
Собственные Значения Симметричной Трехдиагональной Матрицы: Практика Метода Половинного Деления
Рассмотрим, как метод половинного деления применяют к симметричным трехдиагональным матрицам разных порядков. В каждом примере найдём одно заданное собственное значение, используя последовательность Штурма для выбора нужной половины текущего интервала.
Пример 1. Найти первое собственное значение симметричной трехдиагональной матрицы
\[
A=
\begin{pmatrix}
2 & 0.5\\
0.5 & 1
\end{pmatrix}
\]
методом половинного деления с точностью \( \varepsilon=0.1 \)
Матрица имеет два собственных значения. Упорядочим их по убыванию:
\[
\lambda_1>\lambda_2.
\]
Необходимо найти первое собственное значение \( \lambda_1 \).
Сначала вычислим бесконечную норму матрицы:
\[
\lVert A\rVert_{\infty}
=
\max
\left\{
|2|+|0.5|,
|0.5|+|1|
\right\}
=
\max\left\{2.5,1.5\right\}
=
2.5.
\]
Следовательно, все собственные значения матрицы находятся в интервале
\[
[\alpha_0,\beta_0]=[-2.5,2.5].
\]
Построим последовательность Штурма:
\[
\begin{gathered}
p_0(\mu)=1,\\[4pt]
p_1(\mu)=2-\mu,\\[4pt]
p_2(\mu)=(1-\mu)\cdot p_1(\mu)-0.5^2\cdot p_0(\mu).
\end{gathered}
\]
На первой итерации найдём середину начального интервала:
\[
c_1=
\frac{-2.5+2.5}{2}=0.
\]
Вычислим члены последовательности Штурма:
\[
\begin{gathered}
p_0(0)=1,\\[4pt]
p_1(0)=2-0=2,\\[4pt]
p_2(0)=(1-0)\cdot 2-0.5^2\cdot 1=1\cdot 2-0.25\cdot 1=1.75.
\end{gathered}
\]
Получаем последовательность знаков
\[
+,\ +,\ +.
\]
Количество изменений знаков равно \( \nu(0)=0 \). Поэтому количество собственных значений, больших \( 0 \), составляет
\[
s(0)=2-\nu(0)=2-0=2.
\]
Поскольку \( s(0)\geq 1 \), первое собственное значение находится в правой половине начального интервала:
\[
\lambda_1\in[0,2.5].
\]
Последующие итерации выполним аналогично:
| \( r \) | \( c_r \) | \( \bigl(p_0(c_r),p_1(c_r),p_2(c_r)\bigr) \) | \( \nu(c_r) \) | \( s(c_r) \) | Новый интервал |
|---|---|---|---|---|---|
| 1 | \( 0 \) | \( (1, 2, 1.75) \) | 0 | 2 | \( [0,2.5] \) |
| 2 | \( 1.25 \) | \( (1, 0.75, -0.438) \) | 1 | 1 | \( [1.25,2.5] \) |
| 3 | \( 1.875 \) | \( (1, 0.125, -0.359) \) | 1 | 1 | \( [1.875,2.5] \) |
| 4 | \( 2.188 \) | \( (1, -0.188, -0.027) \) | 1 | 1 | \( [2.188,2.5] \) |
| 5 | \( 2.344 \) | \( (1, -0.344, 0.212) \) | 2 | 0 | \( [2.188,2.344] \) |
После пятой итерации искомое собственное значение находится в интервале
\[
\lambda_1\in[2.188,2.344].
\]
Проверим условие завершения:
\[
\frac{\beta_5-\alpha_5}{2}
\approx
\frac{2.344-2.188}{2}
=
0.078.
\]
Поскольку
\[
0.078\leq 0.1,
\]
итерационный процесс останавливаем.
В качестве приближённого значения \( \lambda_1 \) возьмем середину последнего интервала:
\[
\lambda_1
\approx
\frac{2.188+2.344}{2}
=
2.266.
\]
Таким образом, первое собственное значение матрицы приближенно равно
\[
\lambda_1\approx 2.266.
\]
Пример 2. Найти второе собственное значение симметричной трехдиагональной матрицы
\[
A=
\begin{pmatrix}
3 & 1 & 0\\
1 & 2 & 1\\
0 & 1 & 0
\end{pmatrix}
\]
методом половинного деления с точностью \( \varepsilon=0.1 \)
Матрица имеет три собственных значения. Упорядочим их по убыванию:
\[
\lambda_1>\lambda_2>\lambda_3.
\]
Необходимо найти второе собственное значение \( \lambda_2 \).
Вычислим бесконечную норму матрицы:
\[
\lVert A\rVert_{\infty}
=
\max
\left\{
|3|+|1|,
|1|+|2|+|1|,
|1|+|0|
\right\}
=
\max\left\{4,4,1\right\}=4.
\]
Следовательно, начальный интервал имеет вид
\[
[\alpha_0,\beta_0]=[-4,4].
\]
Для заданной матрицы последовательность Штурма определяется формулами
\[
\begin{gathered}
p_0(\mu)=1,\\[4pt]
p_1(\mu)=3-\mu,\\[4pt]
p_2(\mu)=(2-\mu)\cdot p_1(\mu)-p_0(\mu),\\[4pt]
p_3(\mu)=(-\mu)\cdot p_2(\mu)-p_1(\mu).
\end{gathered}
\]
На первой итерации середина начального интервала равна
\[
c_1=
\frac{-4+4}{2}=0.
\]
Вычислим члены последовательности Штурма:
\[
\begin{gathered}
p_0(0)=1,\\[4pt]
p_1(0)=3-0=3,\\[4pt]
p_2(0)=(2-0)\cdot 3-1=5,\\[4pt]
p_3(0)=(-0)\cdot 5-3=-3.
\end{gathered}
\]
Последовательность знаков имеет вид
\[
+,\ +,\ +,\ -.
\]
Количество изменений знаков составляет \( \nu(0)=1 \). Поэтому количество собственных значений, больших \( 0 \), равно
\[
s(0)=3-\nu(0)=3-1=2.
\]
Поскольку \( s(0)\geq 2 \), второе собственное значение находится в правой половине начального интервала:
\[
\lambda_2\in[0,4].
\]
Последующие вычисления приведём в таблице:
| \( r \) | \( c_r \) | \( \bigl(p_0(c_r),p_1(c_r),p_2(c_r),p_3(c_r)\bigr) \) | \( \nu(c_r) \) | \( s(c_r) \) | Новый интервал |
|---|---|---|---|---|---|
| 1 | \( 0 \) | \( (1, 3, 5, -3) \) | 1 | 2 | \( [0,4] \) |
| 2 | \( 2 \) | \( (1, 1, -1, 1) \) | 2 | 1 | \( [0,2] \) |
| 3 | \( 1 \) | \( (1, 2, 1, -3) \) | 1 | 2 | \( [1,2] \) |
| 4 | \( 1.5 \) | \( (1, 1.5, -0.25, -1.125) \) | 1 | 2 | \( [1.5,2] \) |
| 5 | \( 1.75 \) | \( (1, 1.25, -0.688, -0.047) \) | 1 | 2 | \( [1.75,2] \) |
| 6 | \( 1.875 \) | \( (1, 1.125, -0.859, 0.486) \) | 2 | 1 | \( [1.75,1.875] \) |
После шестой итерации получаем
\[
\lambda_2\in[1.75,1.875].
\]
Проверим условие завершения:
\[
\frac{\beta_6-\alpha_6}{2}
\approx
\frac{1.875-1.75}{2}
=
0.063.
\]
Поскольку
\[
0.063\leq 0.1,
\]
итерационный процесс останавливаем.
Приближенное значение второго собственного значения равно
\[
\lambda_2
\approx
\frac{1.75+1.875}{2}
=
1.813.
\]
Таким образом, второе собственное значение матрицы приближенно равно
\[
\lambda_2\approx 1.813.
\]
Пример 3. Найти третье собственное значение симметричной трехдиагональной матрицы
\[
A=
\begin{pmatrix}
6 & 1 & 0 & 0\\
1 & 4 & 1 & 0\\
0 & 1 & 2 & 1\\
0 & 0 & 1 & 1
\end{pmatrix}
\]
методом половинного деления с точностью \( \varepsilon=0.1 \)
Матрица имеет четыре собственных значения. Упорядочим их по убыванию:
\[
\lambda_1>\lambda_2>\lambda_3>\lambda_4.
\]
Необходимо найти третье собственное значение \( \lambda_3 \).
Вычислим бесконечную норму матрицы:
\[
\lVert A\rVert_{\infty}
=
\max
\left\{
|6|+|1|,
|1|+|4|+|1|,
|1|+|2|+|1|,
|1|+|1|
\right\}
=
\max\left\{7,6,4,2\right\}
=7.
\]
Следовательно, все собственные значения матрицы находятся в интервале
\[
[\alpha_0,\beta_0]=[-7,7].
\]
Построим последовательность Штурма:
\[
\begin{gathered}
p_0(\mu)=1,\\[4pt]
p_1(\mu)=6-\mu,\\[4pt]
p_2(\mu)=(4-\mu)\cdot p_1(\mu)-p_0(\mu),\\[4pt]
p_3(\mu)=(2-\mu)\cdot p_2(\mu)-p_1(\mu),\\[4pt]
p_4(\mu)=(1-\mu)\cdot p_3(\mu)-p_2(\mu).
\end{gathered}
\]
На первой итерации середина начального интервала равна
\[
c_1=
\frac{-7+7}{2}=0.
\]
Вычислим члены последовательности Штурма:
\[
\begin{gathered}
p_0(0)=1,\\[4pt]
p_1(0)=6-0=6,\\[4pt]
p_2(0)=(4-0)\cdot 6-1=23,\\[4pt]
p_3(0)=(2-0)\cdot 23-6=40,\\[4pt]
p_4(0)=(1-0)\cdot 40-23=17.
\end{gathered}
\]
Получаем последовательность знаков
\[
+,\ +,\ +,\ +,\ +.
\]
Количество изменений знаков равно \( \nu(0)=0 \). Поэтому количество собственных значений, больших \( 0 \), составляет
\[
s(0)=4-\nu(0)=4-0=4.
\]
Поскольку \( s(0)\geq 3 \), третье собственное значение находится в правой половине начального интервала:
\[
\lambda_3\in[0,7].
\]
Последующие итерации приведены в таблице:
| \( r \) | \( c_r \) | \( \bigl(p_0(c_r),p_1(c_r),p_2(c_r),p_3(c_r),p_4(c_r)\bigr) \) | \( \nu(c_r) \) | \( s(c_r) \) | Новый интервал |
|---|---|---|---|---|---|
| 1 | \( 0 \) | \( (1, 6, 23, 40, 17) \) | 0 | 4 | \( [0,7] \) |
| 2 | \( 3.5 \) | \( (1, 2.5, 0.25, -2.875, 6.938) \) | 2 | 2 | \( [0,3.5] \) |
| 3 | \( 1.75 \) | \( (1, 4.25, 8.563, -2.109, -6.98) \) | 1 | 3 | \( [1.75,3.5] \) |
| 4 | \( 2.625 \) | \( (1, 3.375, 3.641, -5.65, 5.541) \) | 2 | 2 | \( [1.75,2.625] \) |
| 5 | \( 2.188 \) | \( (1, 3.813, 5.91, -4.921, -0.067) \) | 1 | 3 | \( [2.188,2.625] \) |
| 6 | \( 2.406 \) | \( (1, 3.594, 4.728, -5.514, 3.027) \) | 2 | 2 | \( [2.188,2.406] \) |
| 7 | \( 2.297 \) | \( (1, 3.703, 5.307, -5.279, 1.539) \) | 2 | 2 | \( [2.188,2.297] \) |
После седьмой итерации получаем интервал
\[
\lambda_3\in[2.188,2.297].
\]
Проверим условие завершения:
\[
\frac{\beta_7-\alpha_7}{2}
\approx
\frac{2.297-2.188}{2}
=
0.055.
\]
Поскольку
\[
0.055\leq 0.1,
\]
итерационный процесс останавливаем.
В качестве приближенного значения третьего собственного значения возьмем середину последнего интервала:
\[
\lambda_3
\approx
\frac{2.188+2.297}{2}
=
2.242.
\]
Таким образом, третье собственное значение матрицы приближенно равно
\[
\lambda_3\approx 2.242.
\]
Что Читать Дальше: Другие Способы Вычисления Собственных Значений
Метод половинного деления — лишь один из способов исследования спектра матрицы. Далее можно перейти к другим алгоритмам и сравнить, какие задачи удобнее решать с помощью каждого из них.
- Метод вращения: Собственные значения симметричной матрицы — Узнайте, как последовательные вращения обнуляют внедиагональные элементы и помогают вычислить все собственные значения симметричной матрицы.
- Степенной метод: Наибольшее по модулю собственное значение — Рассмотрите, как с помощью последовательных умножений матрицы на вектор приближённо найти наибольшее по модулю собственное значение и соответствующий собственный вектор.
- Метод исчерпывания: Второе собственное значение матрицы — Узнайте, как после нахождения первого собственного значения изменить матрицу и вычислить следующее.
Собственные Значения Симметричной Трехдиагональной Матрицы: Реализация Алгоритма в Коде
Если вам нравится программирование, самое время перейти от теории к собственной реализации. Блок-схема уже содержит готовую логику вычислений, поэтому её можно перенести в Pascal, Python, C++, JavaScript или любой другой язык, с которым вам удобно работать.
Это хорошая возможность не только закрепить метод половинного деления, но и увидеть, как математический алгоритм превращается в полноценную программу. Такая программа находит собственные значения симметричной трехдиагональной матрицы и помогает лучше понять связь между численными методами и практическим программированием.
