\myAddDate{06}{03}{09} Обозначим через \(x_{n+1}^{(i)}\) \(i\)-ую координату вектора \(x_{n+1}\). Тогда: \[x_{n+1}^{(i)}=c_1\lambda_1^{n+1}e_1^{(i)} + c_2\lambda_2^{n+1}e_2^{(i)} + \dots + c_m \lambda_m^{n+1} e_m^{(i)}\] \[x_n^{(i)}=c_1 \lambda_{1}^n e_1^{(i)} + c_2\lambda_2^n e_2^{(i)} + \dots + c_m\lambda_m^n e_m^{(i)}\] Поделим \(x_{n+1}^{(i)}\) на \(x_{n}^{(i)}\): \[\frac{x_{n+1}^{(i)}}{x_{n}^{(i)}}=\frac{c_m\lambda_m^{n+1}e_m^{(i)}\left(1 + \frac{c_{m-1}}{c_m}\frac{e_{m-1}^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^{n+1} + \dots + \frac{c_1}{c_m}\frac{e_1^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_1}{\lambda_m}\right)^{n+1}\right)} {c_m\lambda_m^n e_m^{(i)}\left(1 + \frac{c_{m-1}}{c_m}\frac{e_{m-1}^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^n + \dots + \frac{c_1}{c_m}\frac{e_1^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_1}{\lambda_m}\right)^n\right)} =\] \[= \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right) = \lambda_m^{(n)}\] Таким образом, \(\lambda_m^{(n)} - \lambda_m = O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\), то есть мы решили задачу нахождения максимального по модулю собственного значения. Сформулируем соответсвующее утверждение: \begin{myUnnumberedStatement} Пусть выполнены следующие предположения: \begin{enumerate} \item (A) Матрица A имеет базис из собственных векторов \(\left\{e_i \right\}_{i=1}^{i=m}\) \item (B) \(|\frac{\lambda_{m-1}}{\lambda_m}| < 1\) \item (С) \(x_0 = c_1e_1 + c_2e_2 + \dots + c_me_m\), где \(c_m \neq 0\) \end{enumerate} Тогда \(x_n \rightarrow e_m\) (по направлению) при \(n \rightarrow \infty \), где \(e_m\) - собственный вектор, отвечающий наибольшему по модулю собственному значению \(\lambda_m\), а \(\lambda_m^{(n)} = \frac{x_{n+1}^{(i)}}{x_{n}^{(i)}} = \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\). \end{myUnnumberedStatement} \begin{myUnnumberedNote} Условия (A) и (B) несколько ограничивают класс задач, к которым применим этот метод, хотя он все равно остается достаточно широким. \end{myUnnumberedNote} \begin{myUnnumberedNote} Найти \(\lambda_m^{(n)}\) можно также по формуле: \[\lambda_m^{(n)} = \frac{\left(x_{n+1}, x_n\right)}{\left(x_n, x_n\right)} = \frac{\left(Ax_n, x_n\right)}{\left(x_n, x_n\right)}\]. \end{myUnnumberedNote} Рассмотрим два случая: 1. Пусть \(A = A^*\). Тогда \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - ортонормированный базис из собственных векторов матрицы A: \[Ae_k = \lambda_k e_k, \quad k = 1, \dots, m,\quad e_k \neq 0\] \[\left(e_i, e_j\right) = \delta_{ij}\] \[x_{n+1}=c_1\lambda_1^{n+1}e_1 + c_2\lambda_2^{n+1}e_2 + \dots + c_m \lambda_m^{n+1} e_m\] \[x_n=c_1 \lambda_{1}^n e_1 + c_2\lambda_2^n e_2 + \dots + c_m\lambda_m^n e_m\] Найдем \(\lambda_m^{(n)}\): \[\lambda_m^{(n)} = \frac{\left(x_{n+1}, x_n\right)}{\left(x_n, x_n\right)} = \frac{c_1^2\lambda_1^{2n+1} + c_2^2\lambda_2^{2n+1} + \dots + c_m^2\lambda_m^{2n+1}}{c_1^2\lambda_1^{2n} + c_2^2\lambda_2^{2n} + \dots + c_m^2\lambda_m^{2n}} =\] \[= \frac{c_m^2\lambda_m^{2n+1}\left(1 + \left(\frac{c_{m-1}}{c_m}\right)^2\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^{2n+1} + \dots + \left(\frac{c_1}{c_m}\right)^2\left(\frac{\lambda_1}{\lambda_m}\right)^{2n+1}\right)} {c_m^2\lambda_m^{2n}\left(1 + \left(\frac{c_{m-1}}{c_m}\right)^2\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^{2n} + \dots + \left(\frac{c_1}{c_m}\right)^2\left(\frac{\lambda_1}{\lambda_m}\right)^{2n}\right)} = \] \[= \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^{2n}\right)\] Таким образом, при \(A = A^*\) получили более быструю сходимость. 2. Пусть \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - базис из собственных векторов (ортонормированность не предполагается). Тогда: \[\lambda_m^{(n)} = \frac{\left(x_{n+1}, x_n\right)}{\left(x_n, x_n\right)} = \frac{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^{n+1}\lambda_j^n\left(e_i, e_j\right)}{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^n\lambda_j^n\left(e_i, e_j\right)} = \] \[= \frac{c_m^2\lambda_m^{2n+1}\left(e_m, e_m\right)\left(1 + \frac{c_{m-1}}{c_m}\frac{\left(e_m, e_{m-1}\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^n + \dots + \left(\frac{c_1}{c_m}\right)^2\frac{\left(e_1, e_1\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_1}{\lambda_m}\right)^{2n+1}\right)} {c_m^2\lambda_m^{2n}\left(e_m, e_m\right)\left(1 + \frac{c_{m-1}}{c_m}\frac{\left(e_m, e_{m-1}\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^n + \dots + \left(\frac{c_1}{c_m}\right)^2\frac{\left(e_1, e_1\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_1}{\lambda_m}\right)^{2n}\right)} = \] \[= \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\] \[\lambda_m^{(n)} - \lambda_m = O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\] \subsection{Метод обратных итераций} Пусть матрица \(A\) (m x m) такова, что \(\exists A^{-1}\). Рассмотрим итерационный степенной метод решения частичной проблемы собственных значений: \[Ax_{n+1} = x_n, \quad n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\] Домножим обе части слева на \(A^{-1}\): \[x_{n+1} = A^{-1}x_n, \quad n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\] Получили степенной метод для обратной матрицы. Пусть верны следующие предположения: \begin{enumerate} \item (A) Матрица A имеет базис из собственных векторов \(\left\{e_i \right\}_{i=1}^{i=m}\) \item (B) \(|\frac{\lambda_1}{\lambda_2}| < 1\) \item (С) \(x_0 = c_1e_1 + c_2e_2 + \dots + c_me_m\), где \(c_1 \neq 0\) \end{enumerate} Тогда: \[x_n=c_1 \lambda_{1}^{-n} e_1 + c_2\lambda_2^{-n} e_2 + \dots + c_m\lambda_m^{-n} e_m\] \[\lambda_1^n x_n=c_1 e_1 + c_2 \left(\frac{\lambda_1}{\lambda_2}\right)^n e_2 + \dots + c_m \left(\frac{\lambda_1}{\lambda_m}\right)^n e_m\] Таким образом, \(x_n \rightarrow e_1 \) (по направлению) при \(n \rightarrow \infty\). \begin{myUnnumberedTask} Пусть выполнены условия (A), (B) и (C). Тогда метод обратных итераций позволяет найти собственное значение \(\lambda_1^{(n)} = \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\), где \(\lambda_1^{(n)} = \frac{x_n^{(i)}}{x_{n+1}^{(i)}}\). \end{myUnnumberedTask} \begin{proof} Выпишем выражения для \(x_{n}^{(i)}\) и \(x_{n+1}^{(i)}\): \[x_n^{(i)}=c_1 \lambda_{1}^{-n} e_1^{(i)} + c_2\lambda_2^{-n} e_2^{(i)} + \dots + c_m\lambda_m^{-n} e_m^{(i)}\] \[x_{n+1}^{(i)}=c_1 \lambda_{1}^{-n-1} e_1^{(i)} + c_2\lambda_2^{-n-1} e_2^{(i)} + \dots + c_m\lambda_m^{-n-1} e_m^{(i)}\] Теперь поделим \(x_{n}^{(i)}\) на \(x_{n+1}^{(i)}\): \[\frac{x_{n}^{(i)}}{x_{n+1}^{(i)}}=\frac{c_1\lambda_1^{-n}e_1^{(i)}\left(1 + \frac{c_2}{c_1}\frac{e_2^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n} + \dots + \frac{c_m}{c_1}\frac{e_m^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_m}{\lambda_1}\right)^{-n}\right)} {c_1\lambda_1^{-n-1} e_1^{(i)}\left(1 + \frac{c_2}{c_1}\frac{e_2^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n-1} + \dots + \frac{c_m}{c_1}\frac{e_m^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_m}{\lambda_1}\right)^{-n-1}\right)} =\] \[= \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right) = \lambda_1^{(n)}\] \end{proof} Пусть теперь \(A = A^*\). Тогда \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - ортонормированный базис из собственных векторов матрицы A. Найдем \(\lambda_1^{(n)}\): \[\lambda_m^{(n)} = \frac{\left(x_n, x_n\right)}{\left(x_{n+1}, x_n\right)} = \frac{c_1^2\lambda_1^{-2n} + c_2^2\lambda_2^{-2n} + \dots + c_m^2\lambda_m^{-2n}}{c_1^2\lambda_1^{-2n+1} + c_2^2\lambda_2^{-2n-1} + \dots + c_m^2\lambda_m^{-2n-1}} =\] \[= \frac{c_1^2\lambda_1^{-2n}\left(1 + \left(\frac{c_2}{c_1}\right)^2\left(\frac{\lambda_2}{\lambda_1}\right)^{-2n} + \dots + \left(\frac{c_m}{c_1}\right)^2\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n}\right)} {c_1^2\lambda_1^{-2n-1}\left(1 + \left(\frac{c_2}{c_1}\right)^2\left(\frac{\lambda_2}{\lambda_1}\right)^{-2n-1} + \dots + \left(\frac{c_m}{c_1}\right)^2\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n-1}\right)} = \] \[= \lambda_1 + O\left(\left(\frac{\lambda_{1}}{\lambda_{2}}\right)^{2n}\right)\] Таким образом, при \(A = A^*\) снова имеем более быструю сходимость. \begin{myUnnumberedTask} Пусть \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - базис из собственных векторов матрицы A. Тогда \(\lambda_1^{(n)} = \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\). \end{myUnnumberedTask} \begin{proof} \[\lambda_1^{(n)} = \frac{\left(x_n, x_n\right)}{\left(x_{n+1}, x_n\right)} = \frac{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^{-n}\lambda_j^{-n}\left(e_i, e_j\right)}{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^{-n-1}\lambda_j^{-n}\left(e_i, e_j\right)} = \] \[= \frac{c_1^2\lambda_1^{-2n}\left(e_1, e_1\right)\left(1 + \frac{c_2}{c_1}\frac{\left(e_1, e_2\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n} + \dots + \left(\frac{c_m}{c_1}\right)^2\frac{\left(e_m, e_m\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n}\right)} {c_1^2\lambda_1^{-2n-1}\left(e_1, e_1\right)\left(1 + \frac{c_2}{c_1}\frac{\left(e_1, e_2\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n} + \dots + \left(\frac{c_m}{c_1}\right)^2\frac{\left(e_m, e_m\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n-1}\right)} = \] \[= \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\] \[\lambda_1^{(n)} - \lambda_1 = O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\] \end{proof} Сформулируем еще одно утверждение: \begin{myUnnumberedStatement} Если есть хотя бы одно комплексное собственное значение \(\lambda_k = \lambda_0 + i\lambda_1\), \(\lambda_1 \neq 0\), то и отвечающий ему собственный вектор должен быть комплексным, и начальное приближение для него должно быть комплексным. \end{myUnnumberedStatement} \begin{proof} Пусть \(x_k = \mu_0 + i\mu_1\) - собственный вектор матрицы A, отвечающий собственному значению \(\lambda_k = \lambda_0 + i\lambda_1\). Тогда: \[Ax_k = A(\mu_0 + i\mu_1) = (\lambda_0 + i\lambda_1)(\mu_0 + i\mu_1) = \lambda_0\mu_0 - \lambda_1\mu_1 + i(\lambda_0\mu_1 + \lambda_1\mu_0)\] В силу линейности: \[A\mu_0 = \lambda_0\mu_0 - \lambda_1\mu_1\] \[A\mu_1 = \lambda_0\mu_1 + \lambda_1\mu_0\] Предположим, что \(\mu_1 = 0\). Тогда \(\lambda_1\mu_0 = 0\), \(\mu_0 = 0\), откуда следует, что \(x_k = 0\), а это противоречит тому, что x - ненулевой вектор. \end{proof} \subsection{Метод обратных итераций со сдвигом} Иногда бывает нужно найти собственное значение из внутренней части спектра. Рассмотрим метод обратных итераций со сдвигом: \[(A - \alpha E)x_{n+1} = x_n, \alpha \in \mathbb{R}, n \in \mathbb{N}\] \[n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\] Пусть существует \((A - \alpha E)^{-1} = B\), тогда получим степенной метод для матрицы B: \[x_{n+1} = Bx_n, \quad n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\] Собственные значения матрицы B: \[\lambda_k^B = \frac{1}{\lambda_k^{A} - \alpha}\] Тогда \(x_n \rightarrow e_l\) (по направлению), где l таково, что: \[\lambda_l^B = \max_{k = 1, \dots, m} \frac{1}{\lambda_k^A - \alpha} = \frac{1}{\lambda_l^{A} - \alpha}\] \begin{myUnnumberedNote} Если известно приближенное значение какого-то собственного значения, а мы хотим его уточнить, то можно использовать этот метод. Найти весь спектр этим методом практически невозможно. \end{myUnnumberedNote} \section{Приведение матрицы к верхней почти треугольной форме (ВПТФ)} Легче всего найти собственные значения у диагональной или треугольной матрицы. Наша задача - привести матрицу A (m x m) к треугольной. Однако, приведение матрицы A к треугольной форме методом Гаусса не сохраняет спектр матрицы. Спектр матрицы сохраняется при преобразовании подобия: \[C = Q^{-1}AQ\] Если матрица Q - ортогональна (унитарна), то сохраняется симметрия. \begin{myUnnumberedDefinition} Матрица находится в верхней почти треугольной форме (ВПТФ), если она имеет вид (ненулевые элементы обозначены через x): \[ A = \begin{pmatrix} x & x & x & \cdots & x & x & x \\ x & x & x & \cdots & x & x & x \\ 0 & x & x & \cdots & x & x & x \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & x & x & x \\ 0 & 0 & 0 & \cdots & 0 & x & x \end{pmatrix} \] \end{myUnnumberedDefinition} Рассмотрим вектор-столбец \(\nu\): \[\nu = (\nu_1, \nu_2, \dots, \nu_m)^T\] \[\nu^T = (\nu_1, \nu_2, \dots, \nu_m)\] \begin{myUnnumberedDefinition} Элементарным отражением, соответствующим вектору \(\nu\), называется преобразование, задаваемое матрицей: \[H = E - 2\frac{\nu \nu^T}{||\nu||^2}\] \end{myUnnumberedDefinition} \begin{myUnnumberedNote} \[\nu^T \nu = \nu_1^2 + \nu_2^2 + \dots + \nu_m^2 = ||\nu||^2\] \[\nu \nu^T = \begin{pmatrix} \nu_1^2 & \nu_1 \nu_2 & \cdots & \nu_1 \nu_m \\ \nu_2 \nu_1 & \nu_2^2 & \cdots & \nu_2 \nu_m \\ \vdots & \vdots & \ddots & \vdots \\ \nu_m \nu_1 & \nu_m \nu_2 & \cdots & \nu_m^2 \end{pmatrix} \] Матрица \(\nu \nu^T\) - симметричная. \end{myUnnumberedNote}