华东师大ACM算法课件第三讲-矩阵计算教程教案.ppt

ECNU Yinping Liu 矩阵计算 柳银萍 ECNU Yinping Liu That’s the secret to life . . . Replace one worry with another. ----Charles M. Schulz (1922-2000), American cartoonist . 这一章介绍一种建立在变换基础上的设计方法，我们称它为变换求解方法。其思路如下： 更简单的问题 or 一个问题 原问题的另一种表示 or 解 另一个问题 我们以矩阵计算为例来说明这种方法 高斯消元法 ECNU Yinping Liu 考虑如下的包含两个方程、两个未知数的方程组： (*1) 我们知道，除非两个方程的系数成比例，否则方程有唯一的解。一般来说，我们求解该系统的方法为: 先将一个方程中的一个未知数用另一个未知数表示。然后将其代入另一个方程，得到一个一元一次方程。求解该一元一次方程，获得第二个未知数的值。继而通过上面的表达式求出第一个未知数的值。 在许多应用中，我们需求解一个有 n 方程 n 个未知数的方程组: ECNU Yinping Liu (*2 ) 其中 n 是一个大整数 . 理论上, 我们可通过推广上述求解系统(*1)的迭代法来求解系统(*2) ; 然而, 该方法太繁琐. 因此，下面我们介绍一种更完美的求解该系统的方法, 即高斯消去法: 其基本思想即为将原系统转化为另一个等价的系统( 该系统与原系统有相同的解)，但变换后的系统系数矩阵为上三角形矩阵： ECNU Yinping Liu 用矩阵表示如下： 其中 ECNU Yinping Liu ECNU Yinping Liu 则我们可通过回代得到原方程的解 x3=(-2)/2=-1, x2=(3-(-3)x3)/3=0, and x1=(1-x3-(-1)x2)/2=1. 下面给出了高斯消元法的伪代码 Algorithm GaussElimination (A[1…n, 1…n], b[1…n]) for i ? 1 to n do A[i, n+1] ? b[i] for i ? 1 to n-1 do for j ? i+1 to n do for k ? i to n+1 do A[j, k] ? A[j, k]-A[i, k]*A[j, i]/A[i, i] ECNU Yinping Liu 注： 这里有几点需要说明: 1. 该算法隐含着错误，即若 A[i, i]=0, 则出错. 2. 若A[i, i]太小，使得 A[j, i]/A[i, i] 太大. 当出现两行相减时，导致较大的误差. 同时该算法的内层循环效率低. 3. 该算法中新旧值混用。 为此，我们给出如下修正算法： ECNU Yinping Liu Algorithm BetterGaussElimination (A[1..n, 1..n], b[1..n]) for i ? 1 to n do A[i, n+1] ? b[i] for i ? 1 to n-1 do pivotrow ? i for j ? i+1 to n do if |A[j, i]| |A[pivotrow, i]| pivotrow ? j for k ? i to n+1 do swap(A[i, k], A[pivotrow, k]) for j ? i+1 to n do temp ? A[j, i]/A[i, i] for k ? i to n+1 do A[j, k] ? A[j, k]-A[i, k]*temp ECNU Yinping Liu 下面我们讨论该算法的时间复杂度 考虑最内层的循环，仅一行: A[j, k] ? A[j, k]-A[i, k