QMR法求解线性方程组的原理

QMR（Quasi-Minimal Residual）算法是用于解决大规模非对称线性方程组的迭代方法之一。它是由Saad和Schultz在1986年提出的。

QMR算法的基本思想是利用CG（Conjugate Gradient）算法和GMRES（Generalized Minimal Residual）算法的优点，同时避免它们的缺点。与CG算法类似，QMR算法也是一种Krylov子空间迭代方法，但它不要求矩阵A是对称正定的。与GMRES算法类似，QMR算法也采用了Arnoldi过程来构造一个Krylov子空间，但是它使用了两个不同的基向量序列。

QMR算法的主要步骤如下：

1. 初始化：给定初始向量$x_0$，计算$r_0=b-Ax_0$，并选择两个初始基向量$v_0$和$w_0$，使得它们满足$r_0\perp v_0$和$Av_0\perp w_0$。

2. 迭代：对于$k=0,1,2,\cdots$，进行如下迭代：

- 计算$\beta_k=\|r_k\|$和$q_k=r_k/\beta_k$；
- 在Krylov子空间$K_{k+1}(A,q_k)$中，使用Arnoldi过程计算基向量$v_{k+1}$和$w_{k+1}$；
- 解一个小规模的上Hessenberg矩阵$H_k$的线性方程组$H_ky_k=\beta_ke_1$；
- 计算$x_{k+1}=x_k+V_ky_k$，其中$V_k=[v_0,v_1,\cdots,v_k]$。

3. 终止：如果满足收敛条件，停止迭代，否则返回步骤2。

QMR算法的收敛性与矩阵A的特征值分布密切相关。当矩阵A越接近对称正定，QMR算法的收敛速度越快。但是，即使矩阵A是不对称的，QMR算法仍然可以比其他迭代方法更快地收敛。