高斯消去
约 2005 个字 8 张图片 预计阅读时间 7 分钟
线性方程组的直接解法
经过有限步算数计算,得到了方程组的精确解法
如果在计算过程中没有舍入误差
但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解
迭代法主要是用某种极限过程去逐步逼近线性方程组的精确解的方法
雅可比（Jacobi)迭代法、高斯-赛德尔（Gauss-Seidel)迭 代法。
迭代法具有需要计算机的存贮单元较少、程序设计简单、原始系数矩阵在 计算过程中始终不变等优点
对角矩阵,下三角矩阵和上三角矩阵我们可以直接解出解
对角矩阵 \(\(A=diag(a_{11},a_{22},a_{33}...,a_{nn})=>x_i=\frac{b_i}{a_{ii}},i=1...n\)\) 下三角矩阵 \(\(x_i=\frac{b_i-\Sigma^{i-1}_{j=1}l_{ij}x_j}{l_{ii}}\)\) 对方程组,作如下的变换 1. 交换两个方程的次序 2. 一个方程的两边同时乘以一个非0的数 3. 一个方程的两边同时乘以一个非0数,加到另外一个方程,得到的增广矩阵 1. 交换两行 2. 一行乘以一个非0的数字 3. 某一个乘以一个非0的数,加到另一行
高斯消元法
设第一轮\(a_{11}!=0\),计算乘数\(m_{i1}=-\frac{a_{i1}}{a_{11}}\)
用\(m_{i1}\)乘上第1个方程,加都第i个方程上去
得到第二轮的矩阵,消去第2个方程搭到第n个方程的\(x_1\)
从而得到等价方程组
第二步:对得到的第二轮方程重新进行第一步的处理,消去x2,得到x3
...
第k步:进行第k步消元.设\(\(a_{kk}^{(k)}\neq0\)\) 计算乘数\(\(m_{ik}=-\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}\)\) 用\((m_{ik})\)乘以第k个方程加到第i个方程,消去第i个方程的未知数\(x_k\)
得到了如下的方程组
然后回代
第一步:在方程\((3,4)\)的最后一个方程中解出\(x_n\)
得到\(\(x_n=\frac{b_n^{(n)}}{a_{nn}^{(n)}}\)\)
然后把\(x_n\)代入倒数第二个方程
得到\(\(x_{n_1}=\frac{b_{n-1}^{(n-1)}-a_{n-1,n-1}^{(n-1)}}{a_{n-1,n-1}^{(n-1)}}\)\)
以此继续下去,可以得到\(x_k\)的计算公式
k=1的时候完成了回代过程,求得所求的解
由消元过程和回代过程求解线性方程组的方法称为高斯消去法
定理1:设线性方程组\(Ax=b\),其中A是一个n行n列的集合
- 如果有\(a_{kk}\neq 0\),则可以用高消去的方法求等价的上三角方程组,且有计算公式
- 消元计算一个公式
- 回代计算得到x
- 如果A是非奇异矩阵,则可能有某\(a_{kk}^{(k)}\neq 0\)
- 于是可能通过交换（A，b）的第k 行和第i k 行元素， 将 调到（k，k）位置，然后再进行消元计算
- 于是，在A 为非奇异矩阵时，只要引进行交换，则 高斯消去法可将Ax=b 化为上三角方程组，且通过回代即可求得方程组解
- 高斯消去法要求第k步消元的主元素不等于0,也就是\(\(a_{kk}^{(k)}\neq 0\)\)
定理2:对矩阵\(\(A=(a_{ij})_{n\times n}\)\) 主元素\(\(a_{kk}^{(k)}\neq 0\)\)的一个充分必要条件是矩阵的各阶顺序主子式不等于0
高斯消去法的计算量分析:
消元过程的计算量,高斯消去法消去过程分n-1步 第k步的计算工作量 1. 计算乘数,需要做(n-k)次除法运算 2. 消元:需要\((n-k)^2\),和\((n-k)^2\)次加减法运算 3. 计算\(b^{k+1}\).需要(n-k)次乘法运算和\((n-k)\)次加减法运算
于是完成全部消元一共需要做
\(\(\frac{n^3}{3}+n^2-\frac{n}{3}\)\) 次乘除法运算
高斯消去法的矩阵解释 1. 二维数组存放矩阵A的元素,用一维数组b(n)存放常数项b份分量 2. 需要输入的数据就是AB 3. 约化中间结果\(A^(k)\)元素冲掉A元素,\(b^{k}\)冲掉 4. 在高斯消去法中一般要进行行交换
列主元高斯消去法:
用高斯消去法姐Ax=b时其中设A是非奇异矩阵,可能出现\(a_{kk}^{(k)}=0\) 的情况,这是必须进行带行交换的高斯消去法
实际计算中如果\(a_{kk}^{(k)}\)很小的时候,会导致中间结果\(A^{(k)}\)元素数量级严重增长和舍入误差的扩散,使得最后的计算结果变得不可靠 $$ \begin{cases} 0.0001x + y = 1 \ x + y = 2 \end{cases} $$
具有行交换的高斯消去法(避免小主元) $$ \left( \begin{array}{cc|c} 0.1\times 10^1 & 0.1\times 10^1 & 0.2\times 10^1 \ 0.1\times 10^{-3} & 0.1\times 10^1 & 0.1 \times 10^1 \
\end{array} \right) $$
其中公式就是
此时我们需要得到的\(m_{21}=0.0001\),而之前得到的\(m_{21}=10000\)
主元还是\(0.00001x+1=1\),这样\(x=1,y=0\),这就是一个坏结果
而我们换元之后得到的\(\(x=1,y=1\)\) 比较接近实际解
所以,小主元可能导致计算失败,所以在消去法中应该避免采用绝对值很小的主元素
对一般矩阵方程组,需要引进选主元的技巧,在\高斯消去法的每一步都应该选取矩阵或者消元之后的低阶矩阵中绝对值的最大元素作为主元素,保持乘数\(|m_{ik}|<1\),以便于减少在计算过程中舍入误差对计算解的影响
完全主元消去法是在解低阶稠密矩阵的有效方法,但是在完全主元素消去法时选取主元需要花费一定的计算时间
现在介绍的是列主元消去法,在每次选主元的时候,以此按列选取绝对值最大的元素作为主元素,且仅仅交换两行.再进行消元计算
设有线性方程组\(\(Ax=b\)\)
首先在A的第一行中选取绝对值最大的元素\(a_{l1}\),作为第一步的主元素
然后交换\((a,b)\)的第一行和第l行元素,进行消元计算
完成第一步到第k-1步的次序后
回代求解的公式需要掌握
矩阵的三角分解法
杜立特尔分解法:矩阵的三角分解法
\(M_{ik}\)是特殊的初等矩阵,称为倍加矩阵
记录\(\(M_1=M_{n1}...M_{i1}...M_{21}\)\) 有n-1个才完成高斯消去的第一轮
M下表有两个\(M_{ij}\)是倍加矩阵
\(M_{1}\)是一系列小的标准的倍加矩阵相乘得到的
\(\(M_kA^{(k)}=A^{(k+1)}\)\) \(\(M_kb^{(k)}=b^{(k+1)}\)\) 经过n-1步消元之后,可以得到
\(\(M_{n-1}M_{n-2}...M_{1}b=b^{n}=y\)\) 实质是增广矩阵\([A,b]\)被左乘了一系列倍加矩阵M变成了上三角矩阵\([U,y]\)
\(L\)也是单位下三角矩阵,所以\(A=LU\),\(Ly=b\)
高斯消去法的消去过程，实质上是将A分解为两个三角矩阵的乘积 A=LU，并求解Ly=b的过程
上面使用倍加矩阵解释高斯消去法
\(\(Ax=b\)\) 转换成\(\(LUx=b\)\) \(\(Ux=y\)\)得到
\(\(Ly = b\)\) 解出Y,也就解出x
\(\(Ux =y\)\)
怎么写出这两个矩阵
\(\(a_{1j}=u_{1j}\)\) A矩阵的第一行就是U矩阵的第一行
因为\(\(a_{i1}=l_{i1}u_{11}\)\) 因为\(u_{11}\)已知,则\(\(l_{i1}=\frac{a_{i1}}{u_{11}}\)\)
补笔记:计算顺序和公式
特殊线性方程组的解法: