## 3 Description of Numerical Algorithms
### Single Vector Iteration Methods  
The vector iteration or power method is the oldest and probably the simplest and most intuitive numerical method for solving an eigenvalue problem. Consider the LEP (8) with matrix pencil \(s\mathbf{I}_{r}-\mathbf{A}\). The main idea of the power method is that, if one starts with a vector \(\mathbf{b}\) and repeatedly multiplies by \(\mathbf{A}\), then the subsequence  
\[\mathbf{Ab},\mathbf{A}^{2}\mathbf{b},\mathbf{A}^{3}\mathbf{b},\ldots, \tag{11}\]  
converges to a multiple of the right eigenvector that corresponds to the eigenvalue of \(\mathbf{A}\) with LM. More strictly put, under the assumption that the magnitude of the largest eigenvalue \(\lambda_{\text{m}}\) is larger than that of all other eigenvalues, (11) linearly converges to a multiple of the corresponding right eigenvector \(\mathbf{u}_{\text{m}}\). In order to guarantee the convergence, it is also required that the initial vector is selected with a non-zero component in the direction of \(\lambda_{\text{m}}\). Applying the above idea, the method starts with an initial vector \(\mathbf{b}^{(0)}\), which is updated at each step of the iteration through multiplication with \(\mathbf{A}\) and normalization. The \(k\)-th step of the iteration is as follows:  
\[\mathbf{b}^{(k)}=\frac{\mathbf{Ab}^{(k-1)}}{||\mathbf{Ab}^{(k-1)}||}\,\ k=1,2,3,\ldots \tag{12}\]  
Finally, under the assumptions discussed above, \(\mathbf{b}^{(k)}\) converges to the vector \(\mathbf{u}_{\text{m}}\), which corresponds to the eigenvalue of LM \(\lambda_{\text{m}}\). Given \(\mathbf{u}_{\text{m}}\), an estimation of the eigenvalue \(\lambda_{\text{m}}\) is given by the Rayleigh quotient. In general, given a right eigenvector \(\mathbf{u}_{i}\), the Rayleigh quotient provides an estimate of the corresponding eigenvalue \(\lambda_{i}\), as follows:  
\[\tilde{\lambda}_{i}(\mathbf{A},\mathbf{u}_{i})=\frac{\mathbf{u}_{i}^{\text{H} }\mathbf{Au}_{i}}{\mathbf{u}_{i}^{\text{H}}\mathbf{u}_{i}}\, \tag{13}\]  
where \(\mathbf{u}_{i}^{\text{H}}\) is the conjugate transpose of \(\mathbf{u}_{i}\). The power method finds an eigenvector that corresponds to the eigenvalue of LM. However, the eigenvalue of LM is typically not of interest for SSSA. The inverse power method addresses this issue by using \((\mathbf{A}-\sigma\mathbf{I}_{r})^{-1}\) instead of \(\mathbf{A}\) in (12), where the spectral shift \(\sigma\) represents an initial guess of an eigenvalue \(\lambda_{i}\). The \(k\)-th step of the inverse power method is as follows:  
\[\mathbf{b}^{(k)}=\frac{(\mathbf{A}-\sigma\mathbf{I}_{r})^{-1}\mathbf{b}^{(k-1 )}}{||(\mathbf{A}-\sigma\mathbf{I}_{r})^{-1}\mathbf{b}^{(k-1)}||}\,\ k=1,2,3,\ldots \tag{14}\]  
Provided that \(\sigma\) is a good initial guess of \(\lambda_{i}\), \(\mathbf{b}^{(k)}\) converges to the corresponding right eigenvector \(\mathbf{u}_{i}\). Hence, the inverse power method is able to calculate the eigenvector that corresponds to any single eigenvalue, by computing the dominant eigenvector of \((\mathbf{A}-\sigma\mathbf{I}_{r})^{-1}\). Then, the eigenvalue \(\lambda_{i}\) is approximated by the Rayleigh quotient that is given by (13). A bad selection of the spectral shift \(\sigma\) leads to very slow convergence, or convergence to a different eigenvector than the one desired, despite the ability of the inverse power method to compute any eigenpair \((\lambda_{i},\mathbf{u}_{i})\). The Rayleigh quotient iteration method is an extension of the inverse power methodthat updates the applied spectral shift at each step of the iteration. Starting from an initial eigenpair guess (\(\sigma^{(0)}\), \(\mathbf{b}^{(0)}\)), the \(k\)-th step, \(k=1,2,3,\ldots\), of the Rayleigh quotient iteration is:  
\[ \begin{split}\mathbf{b}^{(k)}&=\frac{(\mathbf{A}- \sigma^{(k-1)}\mathbf{I}_{r})^{-1}\mathbf{b}^{(k-1)}}{||(\mathbf{A}-\sigma^{( k-1)}\mathbf{I}_{r})^{-1}\mathbf{b}^{(k-1)}||}\;,\\ \sigma^{(k)}&=\frac{(\mathbf{b}^{(k)})^{\mathrm{H}} \mathbf{A}\mathbf{b}^{(k)}}{(\mathbf{b}^{(k)})^{\mathrm{H}}\mathbf{b}^{(k)}} \;.\end{split}