吴及《数据与算法课程讲义》清华大学：4基本数值算法2-2-线性方程组直接解法

《吴及《数据与算法课程讲义》清华大学：4基本数值算法2-2-线性方程组直接解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2015-2016秋季学期数据与算法课程讲义基础数值算法吴及wuji_ee@tsinghua.edu.cn清华大学电子工程系2015年11月内容提要线性方程组的特性线性方程组的直接解法高斯消去法LU分解线性方程组的迭代求解数据与算法吴及2(20230253)电子工程系高斯消去法24−2?12×−2×149−3?2=8−2−37?31024−2?12011?2=4×−1消元过程015?31224−2?12011?2=4004?38数据与算法吴及3(20230253)电子工程系高斯消去法对变形得到的线性方程组，采用回代求解24−2?12?1=2−−2

2、×?3−4×?22=−1011?2=4?2=4−?3=2004?38?3=2数据与算法吴及4(20230253)电子工程系高斯消去法?为了将??+1,?;⋯,??,?消为零，将第?行乘以−??,???,?然后加到第?行，其中?+1≤?≤??1,1⋯?1,??1,?+1⋯?1,?⋯⋯⋯⋯⋯⋯0⋯??,???,?+1⋯??,?×−??,???,?0⋯??+1,???+1,?+1⋯??+1,?⋯⋯⋯⋯⋯⋯0⋯??,???,?+1⋯??,?数据与算法吴及5(20230253)电子工程系高斯消去法消去过程基本代码实现for(i=1;i

3、1;k<=n;k++){s=-a[k][i]/a[i][i];for(j=i+1;j<=n;j++)a[k][j]+=s*a[i][j];//消去i列k行中的元素a[k][i]=0;b[k]+=s*b[i];//同时更新b}}数据与算法吴及6(20230253)电子工程系高斯消去法完成消去过程，系数矩阵成为上三角阵，线性方程组变形为：?1,1⋯?1,??1,?+1⋯?1,??1?1⋯⋯⋯⋯⋯⋯⋮⋮0⋯??,???,?+1⋯??,?????0⋯0??+1,?+1⋯??+1,???+1=??+1⋯⋯⋯⋯⋯⋯⋮⋮0⋯00⋯??,?????数据与算法吴及7(202302

4、53)电子工程系高斯消去法回代求解过程基本代码实现for(i=n;i>0;i--){s=b[i];for(k=i+1;k<=n;k++)s-=a[i][k]*x[k];x[i]=s/a[i][i];}数据与算法吴及8(20230253)电子工程系时间复杂度分析消去过程for(i=1;i

5、1=3?=1}}数据与算法吴及9(20230253)电子工程系时间复杂度分析回代求解过程for(i=n;i>0;i--){s=b[i];for(k=i+1;k<=n;k++)总的乘法次数为：?−1s-=a[i][k]*x[k];?2−??−?=x[i]=s/a[i][i];2?=1}数据与算法吴及10(20230253)电子工程系时间复杂度分析采用乘法次数来估计高斯消去法的时间复杂度，加法次数与乘法次数相仿主要的计算量消耗在消元过程，时间复杂度为??3数据与算法吴及11(20230253)电子工程系列选主元在高斯消去的过程中，对角线上的元素??,?会作为

6、除数因此应满足??,?≠0，否则消元过程会失败如果??,?很小??,???,?可能出现上溢−??,???,?×??,?≫??,?，导致明显的舍入误差，严重影响求解精度数据与算法吴及12(20230253)电子工程系列选主元在第?步消元时，先从??,?,⋯,??,?中选取新的主元?1,1⋯?1,??1,?+1⋯?1,?⋯⋯⋯⋯⋯⋯0⋯??,???,?+1⋯??,?0⋯???+1,?+1⋯??+1,??+1,?⋯⋯⋯⋯⋯⋯0⋯??,???,?+1⋯??,?求?=argmax??,??≤?≤?如果?≠?，则交换第?行和第?行然后再进行消元，此时??,???

7、,?≤1数据与算法吴及13(20230253)电子工程系选主元列选主元虽然增加了计算复杂度，但是能大大提高算法的稳定性还可以进一步引入全选主元?1,1⋯?1,??1,?+1⋯?1,?⋯⋯⋯⋯⋯⋯0⋯??,???,?+1⋯??,?0⋯??+1,???+1,?+1⋯??+1,?⋯⋯⋯⋯⋯⋯0⋯??,???,?+1⋯??,?列选主元一般能够满足求解的要求，而全选主元复杂度过高，因此在实际应用中一般不采用数据与算法吴及14(20230253)电子工程系LU分解为求解线性方程组??=??11?12?1??1?1⋯?21?22?2??2?2=⋮⋮⋱⋮