arnoldi算法步骤

Arnoldi算法是一种用于求解大规模稀疏矩阵的特征值和特征向量的迭代算法。它的基本思想是通过迭代构造一个Krylov子空间，然后在该空间上进行计算。下面是Arnoldi算法的步骤：

1. 首先选择一个初始向量$v_1$，并将其进行单位化，即$\Vert v_1\Vert=1$。

2. 对于$k=1,2,\cdots,m$，执行以下操作：

a. 计算$v_{k+1}=Av_k-\sum\limits_{j=1}^k h_{j,k}v_j$，其中$h_{j,k}=(v_{j},Av_k)$，$(\cdot,\cdot)$表示内积。

b. 对新向量$v_{k+1}$进行正交化，即$v_{k+1}=\operatorname{proj}_{\mathcal{K}_{k+1}}v_{k+1}$，其中$\mathcal{K}_{k+1}$表示由$\{v_1,v_2,\cdots,v_{k+1}\}$张成的Krylov子空间。

c. 计算$h_{k+1,k}=\Vert v_{k+1}\Vert$，并将$v_{k+1}$进行单位化$v_{k+1}=v_{k+1}/h_{k+1,k}$。

3. 将得到的向量$v_1,v_2,\cdots,v_m$组成一个正交矩阵$V_m=[v_1,v_2,\cdots,v_m]$，将得到的上Hessenberg矩阵$H_m=[h_{i,j}]_{m\times m}$。

4. 对矩阵$H_m$进行特征值分解，得到其特征值$\lambda_1,\lambda_2,\cdots,\lambda_m$和特征向量$x_1,x_2,\cdots,x_m$。则$Ax_j=\lambda_jx_j$。

5. 如果所求特征值和特征向量的个数为$\ell$，则取$H_m$的前$\ell$列组成一个$\ell\times m$的矩阵$H_{m,\ell}$，取$V_m$的前$\ell$列组成一个$n\times\ell$的矩阵$V_{n,\ell}$，对矩阵$H_{m,\ell}$进行特征值分解，得到其特征值$\mu_1,\mu_2,\cdots,\mu_\ell$和特征向量$y_1,y_2,\cdots,y_\ell$。则$Ay_j=\mu_jy_j$。

6. 返回所求的特征值$\mu_1,\mu_2,\cdots,\mu_\ell$和特征向量$y_1,y_2,\cdots,y_\ell$。