为了解决作为主要方法的最小二乘问题，一般有（具有满秩$A$

• 求解正规方程组$A^{T}Ax = A^{T}b$
• 使用 QR 分解
• 使用 SVD 分解

一般来说，QR分解是一种在准确性和计算成本之间取得良好平衡的方法。

使用正规方程是可能的，但由于条件数，它经常被避免。系统的矩阵是，它有 其中是条件数。因此，如果您的矩阵有一个好的，那么正规方程就可以了。$A^{T}A$

$$K_{A^{T}A} = (K_{A})^{2}$$ $K$$K$

请注意，矩阵是对称且正的（特征值是和 奇异值）所以要直接求解系统，您可以使用 Cholesky 分解。$A^{T}A$$\sigma^{2}_{i} > 0$$\sigma_{i}$$A$

在评论中，您声明正常方程系统的条件数与一样小。对于这样一个条件良好的问题，尝试共轭梯度迭代法可能是一个好主意。根据众所周知的共轭梯度误差估计，该方法应该快速收敛 其中不是您的，而是来自正规方程的矩阵（条件编号为 5 的矩阵）。注意 1.9e-17 。$\kappa=5$

$$||x_*-x_m||_A \le 2 \left[ \frac{\sqrt \kappa -1}{\sqrt \kappa +1} \right]^m ||x_*-x_0||_A \, ,$$ $A$$A$$A^*A$$\left[ \frac{\sqrt 5 -1}{\sqrt 5 +1} \right]^{40}=$

共轭梯度法的一个优点是，不需要显式计算形式的矩阵向量积。这些计算为 。 $A^* A$$q_i=A^* Ap_i$$q_i=A^* (Ap_i)$

另见 Saad 的书：稀疏线性系统的迭代方法，第 6 章和第 8 章。

其他答案已经给出了很好的建议，所以我想猜测一下意外加速的原因。

求解正规方程应该花费 flops（形成，然后用 Cholesky 分解求解），并且做 QR 应该花费 flops（例如：https://seas.ucla .edu/~vandenbe/103/lectures/qr.pdf），这让我们期望正规方程会快 2 倍。$\sim mn^2+13n^3$$A^*A$$2mn^2$

由于您说您使用numpy.dot, 并且numpy.dot自动并行化 ( https://scipy.github.io/old-wiki/pages/ParallelProgramming )，因此如果 QR未并行化，您可能会看到，因此加速 10 可能是合理的。但是这种多线程加速通常不会被提及，因为平方条件数的问题更为重要。$2\times \text{number-of-threads}$

要检查，您需要找出您的 numpy 正在使用的 BLAS/LAPACK 库numpy.show_config（OMP_NUM_THREADSStackOverflow 上已经有很多关于如何做到这一点的问题。