Jacobi和Gauss-Seidel都是用于求解线性方程组的迭代方法。Jacobi迭代很容易实现在GPU上并行的版本，但是收敛速度很慢甚至有可能发散。Gauss-Seidel迭代并不能用类似Jacobi的方法并行，因为它是一个依赖于顺序的迭代方法。但是Gauss-Seidel迭代的收敛速度比Jacobi快很多。因此出现了用图论的图着色算法加速Gauss-Seidel迭代的研究。

Understading the Geometry of \(A\in \mathbb{R}^{m\times n}\)

\[ A\in \mathbb{R}^{m\times n} \\ x\in \mathbb{R}^n \mapsto Ax \in \mathbb{R}^m \]

Assumption: \(A \in \mathbb{R}^{n \times n}\) is symmetric, no repeated eigenvalues \(\lambda\)s.

Two basic Properties

Lemma: Every matrix \(A \in \mathbb{R}^{n \times n}\) has at least one (complex) eigenvalue.

很多时候需要把已有问题转化为特征值问题。

1. 有一个对称矩阵（有时候是对称半正定矩阵），我们想要找一个方便的基。
2. 具体的优化问题。

High-Level Idea

Why QR?

\[ \begin{aligned} cond A^T A &= ||A^T A|| \cdot ||(A^T A)^{-1}||\\ &\approx ||A^T|| \cdot ||A|| \cdot ||A^{-1}|| \cdot ||A^{-T}|| &= cond A^2 \end{aligned} \]

为了避免计算\(A^T A\)，我们可以使用QR分解。

Sensitivity and Conditioning

Gaussian elimination works in theory, but what about floating point precision?

How much can we trust \(x_0\) if \(0<||Ax_0 - b||_2 \ll 1\)(backwards error)?

Structured Linear Systems

Gaussian elimination and/or LU can solve all the example problems above. But these systems can have special properties that make them easier or stabler to solve.

Today's example: Positive definite, sparsity.

Linear Systems

\[ \begin{aligned} Ax &= b \\ A &\in \mathbb{R}^{n \times n} \\ x &\in \mathbb{R}^n \\ b &\in \mathbb{R}^n \end{aligned} \]

Mathematically correct != numerically sound. Using Tolerance:

1
2
3
4
5
6
7

double x = 1.0;
double y = x / 3.0;
if(fabs(x-y*3.0) < numeric_limits<double>::epsilon()){
    cout << "They are equal" << endl;
}
else
    cout << "They are not equal" << endl;