Introdunction to Linear Algebra-第11章-Numerical Linear Algebra

[TOC]
《Introdunction to Linear Algebra》的第11章：Numerical Linear Algebra.

1. The goals of numerical linear algebra are speed and accuracy and stability: $n>10^{3} $ or $ 10^{6} $.
2. Matrices can be full or sparse or banded or structured : special algorithms for each.
3. Accuracy of elimination is controlled by the condition number $ |A|\left|A^{-1}\right| $.
4. Gram-Schmidt is often computed by using Householder reflections $ H=I-2 \boldsymbol{u} \boldsymbol{u}^{T} $ to find $Q $.
5. Eigenvalues use $ \boldsymbol{Q} \boldsymbol{R} $ iterations $ \boldsymbol{A}_{\mathbf{0}}=Q_{0} R_{0} \rightarrow R_{0} Q_{0}=\boldsymbol{A}_{\mathbf{1}}=Q_{1} R_{1} \rightarrow \rightarrow \boldsymbol{A}_{\boldsymbol{n}} $.
6. Shifted $ \boldsymbol{Q} \boldsymbol{R} $ is even better: Shift to $ A_{k}-c_{k} I=Q_{k} R_{k} $, shift back $ A_{k+1}=R_{k} Q_{k}+c_{k} I $.
7. Iteration $ S \boldsymbol{x}_{k+1}=\boldsymbol{b}-T \boldsymbol{x}_{k} $ solves $ (S+T) \boldsymbol{x}=\boldsymbol{b} $ if all eigenvalues of $ S^{-1} T $ have $ |\lambda|<1 $.
8. Iterative methods often use preconditioners $ P $. Change $ A \boldsymbol{x}=\boldsymbol{b} $ to $P A \boldsymbol{x}=P \boldsymbol{b}$ with $ P A \approx I $.
9. Conjugate gradients and GMRES are Krylov methods; see Trefethen-Bau (and other texts).

11.1 Gaussian Elimination in Practice

Roundoff Error and Partial Pivoting

Small pivots bring numerical instability, and the remedy is partial pivoting.

Multiplying a row or column by a scaling constant can also be very
worthwhile.

例子如下:

$.0001 u+v=1 \\- u + v = 0$

starts with coefficient matrix

$
A=\left[\begin{array}{cc}.0001 & 1 \\ -1 & 1\end{array}\right]
$

导致的结果:
$10,000v = 10,000$ instead of $10,001v = 10,000 \Rightarrow u = 0$.

$.0001 u+1=1 \text{ instead of } .0001 u+.9999=1 \Rightarrow u = 1$.

但是交换行后结果就不同了:
$$
\begin{aligned}
-u+v &=0 & & \longrightarrow & -u+v &=0 & \longrightarrow & u &=1 \\
.0001 u+v &=1 & & \longrightarrow & v &=1 & \longrightarrow & v &=1
\end{aligned}
$$

how a computer actually solves $A \boldsymbol{x} = \boldsymbol{b}$ –by elimination with partial pivoting.

Operation Counts: Full Matrices

对于较满的矩阵求解 $A \boldsymbol{x} = \boldsymbol{b}$ 的复杂度如何计算?

使用 Gaussian elimination:

• regard multiplying by£ and subtracting from the existing entry as a single operation.
• 对于每一个 pivot 需要 $n^2-n$ operations.
• 整个过程复杂度如下:
  $$
  \left(1^{2}+\cdots+n^{2}\right)-(1+\cdots+n)=\frac{n(n+1)(2 n+1)}{6}-\frac{n(n+1)}{2}=\frac{n^{3}-n}{3}
  $$

相比于通过求逆矩阵的方式求解 $A \boldsymbol{x} = \boldsymbol{b}$, Gaussian elimination 的好处在于:

1. Elimination requires $1⁄2n^3$ multiply-subtracts, compared to $n^3$ for $A^{-1}$.
2. If $A$ is banded so are $L$ and $U$: by comparison $A^{ - 1}$ is full of nonzeros.

TBC…