5. Aлгебраїчна проблема власних значень

Нехай задано матрицю $A \in \RR^{n \times n}$. Тоді задача на власні значення ставиться так: знайти число $\lambda$ та вектор $x \ne 0$, що задовольняють рівнянню

\begin{equation} \label{eq:5.1} A x - \lambda x. \end{equation}

Означення: $\lambda$ називається власним значенням $A$, а $x$ — власним вектором.

З \eqref{eq:5.1}

\begin{equation} \det (A - \lambda E) = P_n(\lambda) = (-1)^n \lambda^n + a_n \lambda^{n - 1} + \ldots + a_0 = 0. \end{equation}

Тут $P_n(\lambda)$ — характеристичний багаточлен.

Для розв’язання багатьох задач механіки, фізики, хімії потрібне знаходження всіх власних значень $\lambda_i$, $i = \overline{1,n}$, а іноді й всіх власних векторів $x_i$, що відповідають $\lambda_i$.

Означення: Цю задачу називають повною проблемою власних значень.

В багатьох випадках потрібно знайти лише максимальне або мінімальне за модулем власне значення матриці. При дослідженні стійкості коливальних процесів іноді потрібно знайти два максимальних за модулем власних значення матриці.

Означення: Останні дві задачі називають частковими проблемами власних значень.

5.1. Степеневий метод

1. Знаходження $\lambda_\max$: $\lambda_\max \equiv \vert \lambda_1 \vert \ge \vert \lambda_2 \vert \ge \vert \lambda_3 \vert \ge \ldots$.

   Нехай $x^{(0)}$ — заданий вектор, будемо послідовно обчислювати вектори

   \begin{equation} \label{eq:5.1.2} x^{(k + 1)} = A x^{(k)}, \quad k = 0, 1, \ldots \end{equation}

   Тоді $x^{(k)} = A^k x^{(0)}$. Нехай $\{e_i\}^n_{i=1}$ — система власних векторів. Представимо $x^{(0)}$ у вигляді:

   \begin{equation} x^{(0)} = \Sum_{i=1}^n c_i e_i. \end{equation}

   Оскільки $A e_i = \lambda_i e_i$, то $x^{(k)} = \Sum_{i=1}^n c_i \lambda_i^k e_i$. При великах $k$: $x^{(k)} \approx c_1 \lambda_1^k e_1$. Тому

   \begin{equation} \mu_1^{(k)} = \frac{x_m^{(k+1)}}{x_m^{(k)}} = \lambda_1 + O \left( \left| \frac{\lambda_2}{\lambda_1} \right|^k \right). \end{equation}

   Значить $\mu_1^{(k)} \xrightarrow[k \to \infty]{} \lambda_1$.

   Якщо матриця $A = A^\intercal$ симетрична, то існує ортонормована система векторів $\langle e_i, e_j \rangle = \delta_{ij}$. Тому

   \begin{equation} \begin{aligned} \mu_1^{(k)} &= \frac{\left\langle x^{(k + 1)}, x^{(k)} \right\rangle}{\left\langle x^{(k)}, x^{(k)}\right\rangle} = \frac{\left\langle \Sum_i c_i \lambda_i^{k + 1} e_i, \Sum_j c_j \lambda_j^k e_j \right\rangle}{\left\langle \Sum_i c_i \lambda_i^k e_i, \Sum_j c_j \lambda_j^k e_j \right\rangle} = \frac{\Sum_i c_i^2 \lambda_i^{2k + 1}}{\Sum_i c_i^2 \lambda_i^{2k}} = \newline &= \frac{c_1^2 \lambda_1^{2 k + 1} + c_2^2 \lambda_2^{2 k + 1} + \ldots }{c_1^2 \lambda_1^{2 k} + c_2^2 \lambda_2^{2 k} + \ldots } = \lambda_1 + O \left( \left| \frac{\lambda_2}{\lambda_1} \right|^{2k} \right) \xrightarrow[k \to \infty]{} \lambda_1. \end{aligned} \end{equation}

   Це означає збіжність до максимального за модулем власного значення з квадратичною швидкістю.

   Якщо $\vert \lambda_1 \vert > 1$, то при проведенні ітерацій відбувається зріст компонент вектора $x^{(k)}$, що приводить до «переповнення» (overflow). Якщо ж $\vert \lambda_1 \vert < 1$, то це приводить до зменшення компонент (underflow). Позбутися негативу такого явища можна нормуючи вектори $x^{(k)}$ на кожній ітерації.

   Aлгоритм степеневого методу знаходження максимального за модулем власного значення з точністю $\varepsilon$ виглядає так:

    e[0] = x[0] / norm(x[0])
   
    k = 0
    while True:
        k += 1
   
        x[k + 1] = A * x[k]
        μ[k][1] = scalar_product(x[k + 1], e[k])
        e[k + 1] = x[k + 1] / norm(x[k + 1])
   
        if abs(μ[k + 1][1] - μ[k][1]) < ε:
            break
   
    λ[1] = μ[k + 1][1]
   

   За цим алгоритмом для симетричної матриці $A^\intercal = A$ швидкість прямування $\mu_1^{(k)}$ до $\lambda_\max$ — квадратична.

2. Знаходження $\lambda_2$: $\vert \lambda_1 \vert \ge \vert \lambda_2 \vert \ge \vert \lambda_3 \vert \ge \ldots$. Нехай $\lambda_1$, $e_1$ відомі.

   Задача 10: Довести, що якщо \(\vert \lambda_1 \vert \ge \vert \lambda_2 \vert \ge \vert \lambda_3 \vert \ge \ldots\) то \begin{equation} \mu_2^{(k)} = \frac{x_m^{(k+1)} - \lambda_1 x_m^{(k)}}{x_m^{(k)} - \lambda_1 x_m^{(k - 1)}} \xrightarrow[k \to \infty]{} \lambda_2, \end{equation} де \(x^{(k + 1)} = A x^{(k)}\), \(x_m^{(k)}\) — \(m\)-та компонента \(x^{(k)}\).

   Задача 11: Побудувати алгоритм обчислення $\lambda_2$, $e_2$, використовуючи нормування векторів та скалярні добутки для обчислення $\mu_2^{(k)}$.

3. Знаходження мінімального власного числа $\lambda_\min(A) = \min_i \vert \lambda_i(A) \vert$.

   Припустимо , що $\lambda_i(a) > 0$ то відоме $\lambda_\max$. Розглянемо матрицю $B = \lambda_\max E - A$. Маємо

   \begin{equation} \forall i: \quad \lambda_i(B) = \lambda_\max - \lambda_i(A). \end{equation}

   Тому $\lambda_\max(B) = \lambda_\max(A) - \lambda_\min(A)$. Звідси $\lambda_\min(A) = \lambda_\max(A) - \lambda_\max(B)$.

   Якщо $\exists i$: $\lambda_i(A) < 0$, то будуємо матрицю $\overline{A} = \sigma E + A$, $\sigma > 0$: $\overline{A} > 0$ і для неї попередній розгляд дає необхідний результат. Замість $\lambda_max$ в матриці $B$ можна використовувати $\|A\|$.

   Ще один спосіб обчислення мінімального власного значення полягає в використання обернених ітерацій:

   \begin{equation} \label{eq:5.1.3} A x^{(k + 1)} = x^{(k)}, \quad k = 0, 1, \ldots \end{equation}

   Aле цей метод вимагає більшої кількості арифметичних операцій: складність методу на основі формули \eqref{eq:5.1.2}: $Q = O(n^2)$, а на основі \eqref{eq:5.1.3} — $Q = O(n^3)$, оскільки треба розв’язувати СЛAР, але збігається метод \eqref{eq:5.1.3} швидше.

5.2. Ітераційний метод обертання

Це метод розв’язання повної проблеми власних значень для симетричних матриць $A^\intercal = A$. Існує матриця $U$, що приводить матрицю $А$ до діагонального виду:

\begin{equation} A = U \Lambda U^\intercal, \end{equation}

де $\Lambda$ — діагональна матриця, по діагоналі якої стоять власні значення $\lambda_i$; $U$ — унітарна матриця, тобто: $U^{-1} = U^\intercal$.

З \eqref{eq:5.1} маємо

\begin{equation} \Lambda = U^\intercal A U. \end{equation}

Нехай $\exists \tilde U$ — матриця, така що $\tilde \Lambda = \tilde U^\intercal A \tilde U$ і $\tilde \Lambda = \left(\tilde \lambda_{ij}\right)^n_{i,j=1}$, $\left\vert \tilde \lambda_{ij} \right\vert < \delta \ll 1$, $i \ne j$.

Тоді діагональні елементи мало відрізняються від власних значень

\begin{equation} \left| \tilde \lambda_{ij} - \lambda_i (A) \right| < \varepsilon = \varepsilon(\delta). \end{equation}

Введемо

\begin{equation} t(A) = \Sum_{\substack{i, j = 1 \\ i \ne j}}^n a_{ij}^2. \end{equation}

З малості величини $t(A)$ випливає, що діагональні елементи малі. По $A = A_0$ за допомогою матриць обертання $U_k$:

\begin{equation} U_k = \begin{pmatrix} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & \cos \phi & \cdots & -\sin \phi & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & \sin \phi & \cdots & \cos \phi & \cdots & 0 \newline \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \newline 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \end{pmatrix}. \end{equation}

що повертають систему векторів на кут $\varphi$, побудуємо послідовність $\{A_k\}$ таку, що $A_k \xrightarrow[k \to \infty]{} \Lambda$.

Задача 12: Показати, що матриця обертання $U_k$ є унітарною: $U_k^{-1} = U_k^\intercal$.

Послідовно будуємо:

\begin{equation} \label{eq:5.2.3} A_{k+1} = U_K^T A_k U_k, \end{equation}

Означення: Процес \eqref{eq:5.2.3} називається монотонним, якщо: $t(A_{k+1}) < t(A_k)$.

Задача 13: Довести, що для матриці \eqref{eq:5.2.3} виконується:

\begin{equation} \label{eq:5.2.4} a_{i,j}^{(k+1)} = a_{i,j}^{(k)} \cos (2 \varphi) + \frac{1}{2} \left(a_{j,j}^{(k)} - a_{i,i}^{(k)}\right) \sin (2 \varphi), \end{equation}

Показати, що

\begin{equation} t(A_{k + 1}) = t(A_k) - 2\left(a_{i,j}^{(k)}\right)^2 \end{equation}

якщо вибирати $\varphi$ з умови $a_{i,j}^{(k+1)} = 0$.

Звідси

\begin{equation} \varphi = \varphi_k = \frac{1}{2} \arctan \left(p^{(k)}\right), \end{equation}

тобто

\begin{equation} p^{(k)} = \frac{2a_{i,j}^{(k)}}{a_{i,i}^{(k)}-a_{j,j}^{(k)}}, \end{equation}

де

\begin{equation} \left|a_{i,j}^{(k)}\right| = \Max_{\substack{m, l \\ m \ne l}} \left|a_{m,l}^{(k)}\right|. \end{equation}

Тоді $t(A_k) \xrightarrow[k\to\infty]{} 0$. Чим більше $n$ тим більше ітерацій необхідно для зведення $A$ до $\Lambda$.

Якщо матриця несиметрична, то застосовують QR- або QL-методи.