[摘记]数值方法01——线性代数方程组求解

注：以下来自《C++数值算法一书》，仅对章节内容做摘要，为的是给自己扫盲，不涉及算法。

以下是线性代数方程组：

当N=M时，则可能可以求得x的唯一解集。如果是行退化（某些方程是其他方程的线性组合）或者列退化（某些变量是其他变量的线性组合），则称这个方程组是奇异的。

方程组一般可以写成Ax=b的形式。A是M*N的矩阵，b是M维向量。若M<=N，则方程组是退化的，或者无解，或者不止一个解。若M>N，方程组是超限定的，这是一个线性最小二乘问题。

1. Gauss-Jordan消去法

思想：将A化为单位矩阵，然后得到的右端项即为方程组的解集。

2. 具有回代过程的高斯消去法

思想：将A化为三角矩阵，然后通过简单代入法得到解集。

3. LU分解法及其应用

思想：由于A=LU，则根据LUx=b，得到两个方程Ly=b和Ux=y。优点在于，L和U分别是下三角和上三角矩阵，因此一次求解所有要解的右端项。有一个算法称为Crout算法，能够相当容易地进行LU分解。

以上方法还可以用来求矩阵的逆。经过LU分解的行列式仅为对角线上元素的积。

4. 奇异值分解(SVD)

SVD用于处理高斯消去法和LU分解法无法给出满意情况的替换方法。也可以用来处理线性最小二乘问题。SVD分解，就是将A分解为A=U diag(w) V^T。

5. 稀疏线性方程组

这种情况往往有特定的算法，比如三对角矩阵等等。

一个通用的方法是共轭梯度法。（至今没看懂）这是一个迭代算法，要求A是对称正定矩阵。

6. Vandermonde矩阵和Toeplitz矩阵

两种特殊情况下的矩阵，可以在N*N阶运算内求解。

7. Cholesky分解

将A转换成一个下三角矩阵与其转置的积——A=LL^T。要求A是对称正定的。

8. QR分解

将A转化为上三角矩阵R与正交矩阵Q的积——A=QR，其中Q^TQ=I。于是对Ax=b有，Rx=Q^Tb。

这种方法运算操作是LU分解的两倍，只有在一些特殊情况下，才是合适的方法。

本文原创，转载请注明出处

http://www.cnblogs.com/luluathena/