Участник:Stanis-morozov/Алгоритм Тренча вычисления спектра симметрической теплицевой матрицы
Задача нахождения собственных значений и собственных векторов для матрицы [math]A[/math] заключается в поиске таких соответствующих друг другу чисел [math]\lambda[/math] и ненулевых векторов [math]x[/math], которые удовлетворяют уравнению [math]Ax=\lambda x[/math]. Числа [math]\lambda[/math] называются собственными значениями, а вектора [math]x[/math] - соответствующими им собственными векторами[1]
Теплицевой матрицей называется матрица, в которой на всех диагоналях, параллельных главной, стоят равные элементы.[2]
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Задача эффективного вычисления собственных значений матриц является одной из основных задач линейной алгебры. Известно, что собственные значения произвольной матрицы невозможно вычислить за конечное число операций, однако существует множество итерационных методов, позволяющих решать эту задачу, например, QR-алгоритм. Однако, для некоторых специальных классов матриц можно предложить более эффективные методы, чем QR-алгоритм. Так, в 1989 была опубликована работа В. Тренча [3], в которой был предложен метод вычисления собственных значений симметрической теплицевой матрицы, учитывающий особенности структуры таких матриц, и допускающий эффективную параллельную реализацию [4][5][6].
1.2 Математическое описание алгоритма
Пусть имеется матрица [math]T_{n}[/math] порядка [math]n\times n[/math] следующего вида:
- [math] T_{n} = \begin{bmatrix} t_{0} & t_{1} & t_{2} & \cdots & t_{n-2} & t_{n-1} \\ t_{1} & t_{0} & t_{1}& \cdots & t_{n-3} & t_{n-2} \\ t_{2} & t_{1} & t_{0} & \cdots & t_{n-4} & t_{n-3} \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ t_{n-2} & \cdots & \cdots & t_{1} & t_{0} & t_{1} \\ t_{n-1} & \cdots & \cdots & t_{2} & t_{1} & t_{0} \\ \end{bmatrix} [/math]
2 Литература
- ↑ Е.Е. Тыртышников Основы алгебры. М.: Физматлит, 2017.
- ↑ Е.Е. Тыртышников Методы численного анализа. М.: Издательский центр "Академия", 2007, 320 с.
- ↑ Trench, W. F. (1989). Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices. SIAM J. Matrix Anal. Appl., 10(2): 135-146
- ↑ F. Noor and S.D. Morgera, Recursive and iterative algorithms for computing eigenvalues of Hermitian Toeplitz matrices, IEEE Trans. Signal Process. 41 (1993) 1272–1280.
- ↑ J. M. Badía and A. M. Vidal, Parallel Algorithms to Compute the Eigenvalues and Eigenvectors of Symmetric Toeplitz Matrices, Parallel Algorithms and Applications, Vol. 13, pp. 75-93. (2000).
- ↑ Noor F., Misbahuddin S. (2010) Using MPI on PC Cluster to Compute Eigenvalues of Hermitian Toeplitz Matrices. In: Hsu CH., Yang L.T., Park J.H., Yeo SS. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2010. Lecture Notes in Computer Science, vol 6081. Springer, Berlin, Heidelberg
