Власні Значення Симетричної Тридіагональної Матриці: Метод Половинного Ділення

Власні значення симетричної тридіагональної матриці можна знаходити без розкриття характеристичного визначника та без безпосереднього розв’язування алгебраїчного рівняння високого степеня. Для цього застосовують метод половинного ділення, який грунтується на властивостях послідовності Штурма. Спочатку будують послідовність многочленів, далі за змінами знаків її членів визначають розташування шуканого власного значення, а потім поступово звужують інтервал, у якому воно міститься.

Власні Значення Симетричної Тридіагональної Матриці: Постановка Задачі

Нехай задано симетричну тридіагональну матрицю \( 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.
\]

Що Читати Далі: Інші Способи Обчислення Власних Значень

Метод половинного ділення — лише один зі способів дослідження спектра матриці. Далі можна перейти до інших алгоритмів і порівняти, які задачі зручніше розв’язувати кожним із них.

1. Метод обертання: Власні значення симетричної матриці — Дізнайтеся, як послідовні обертання зануляють позадіагональні елементи та допомагають обчислити всі власні значення симетричної матриці.
2. Степеневий метод: Найбільше за модулем власне значення — Розгляньте, як за допомогою послідовних множень матриці на вектор наближено знайти найбільше за модулем власне значення та власний вектор.
3. Метод вичерпування: Друге власне значення матриці — Дізнайтеся, як після знаходження першого власного значення змінити матрицю та обчислити наступне.

Власні Значення Симетричної Тридіагональної Матриці: Реалізація Алгоритму в Коді

Якщо вам подобається програмування, саме час перейти від теорії до власної реалізації: блок-схема вже містить готову логіку обчислень, тож її можна перенести у Pascal, Python, C++, JavaScript або будь-яку іншу мову, з якою вам зручно працювати. Це гарна нагода не лише закріпити метод половинного ділення, а й побачити, як математичний алгоритм перетворюється на повноцінну програму, що знаходить власні значення симетричної тридіагональної матриці та допомагає краще відчути зв’язок між чисельними методами й практичним програмуванням.