资源描述:
《线性方程组的求解.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、并行计算第三篇并行数值算法第八章基本通讯操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换第十章线性方程组的求解10.1三角形方程组的求解10.2三对角方程组的求解10.3稠密线性方程组的求解10.4稀疏线性方程组的求解10.1三角形方程组的求解10.1.1基本术语10.1.2上三角方程组的求解基本术语线性方程组的定义和符号a1,1x1+a1,2x2+…+a1,nxn=b1a2,1x1+a2,1x2+…+a2,nxn=b2an,1x1+an,1x2+…+an,nxn=bn记为AX=b2021/
2、8/12510.1三角形方程组的求解10.1.1基本术语10.1.2上三角方程组的求解上三角方程组的求解上三角方程组的回代解法并行化(1)SISD上的回代算法Begin(1)fori=ndownto1do(1.1)xi=bi/aii(1.2)forj=1toi-1dobj=bj-ajixiaji=0endforendforEnd可并行化2021/8/127上三角方程组的求解上三角方程组的回代解法并行化(2)SIMD-CREW上的并行回代算法-划分:p个处理器行循环带状划分-算法Beginfori=ndownt
3、o1doxi=bi/aiiforallPj,where1≤j≤pdofork=jtoi-1steppdobk=bk-akixiaki=0endforendforendforEnd//p(n)=n,t(n)=n2021/8/128第十章线性方程组的求解10.1三角形方程组的求解10.2三对角方程组的求解10.3稠密线性方程组的求解10.4稀疏线性方程组的求解10.2三对角方程组的求解10.2.1直接求解法10.2.2奇偶规约法三对角方程组的直接求解法Gauss消去法(难以并行化)①消元②回代注:由于三对角的方程
4、组的特殊性,一次消元或一次回代,只涉及邻近一个方程,故难以并行化。2021/8/121110.2三对角方程组的求解10.2.1直接求解法10.2.2奇偶规约法三对角方程组的直接求解法奇偶规约求解法(可并行化)三对角方程可以写成如下形式fixi-1+gixi+hixi+1=bii=1~nf1=hn=0串行算法描述①利用上下相邻方程消去偶序号方程中的奇下标变量:f2i-1x2i-2+g2i-1x2i-1+h2i-1x2i=b2i-1f2ix2i-1+g2ix2i+h2ix2i+1=b2if2i+1x2i+g2i+
5、1x2i+1+h2i+1x2i+2=b2i+12i-1方程乘上某个数消去2i方程中的f2ix2i-1项,2i+1方程乘上某个数消去2i方程中的h2ix2i+1项,使2i方程变为αix2i-2+βix2i+γix2i+2=ηii=1,2,…,n/22021/8/1213三对角方程组的直接求解法②重复①最终可得:case1:case2:g1x1+h1x2=b1.f2x1+g2x2+h2x3=b2.f3x2+g3x3+h3x4=b3.f4x3+g4x4=b4.可以分别得到g1x1+h1x2=b1或g1x1+h1x2
6、=b1f2x1+g2x2=b2f2x1+g2x2+h2x3=b2f3x2+g3x3=b3解得x1,x2或x1,x2,x3③回代求解x并行化分析:①、②消去奇下标可以并行化;③回代求解可以并行化2021/8/1214第十章线性方程组的求解10.1三角形方程组的求解10.2三对角方程组的求解10.3稠密线性方程组的求解10.4稀疏线性方程组的求解10.3稠密线性方程组的求解10.3.1有回代的高斯消去法10.3.2无回代的高斯-约旦法10.3.3迭代求解的高斯-赛德尔法有回代的高斯消去法算法基本原理求解过程分为消
7、元和回代两个阶段,消元是将系数矩阵A化为上三角阵T,然后对TX=c进行回代求解。消元过程中可以应用选主元方法,增加算法的数值稳定性。下面是消元过程图:2021/8/1217有回代的高斯消去法并行化分析消元和回代均可以并行化;选主元也可以并行化;消元过程的并行化图示:处理器按行划分2021/8/121810.3稠密线性方程组的求解10.3.1有回代的高斯消去法10.3.2无回代的高斯-约旦法10.3.3迭代求解的高斯-赛德尔法无回代的高斯-约旦法串行算法原理①消元:通过初等行变换,将(A,b)化为主对角线矩阵,
8、(方便起见,记b为A的第n+1列)②求解:xj=a’j,n+1/a’jj2021/8/1220无回代的高斯-约旦法SIMD-CREW上的并行算法(1)处理器:n2+n个处理器,这些处理器排成n×(n+1)的矩阵,处理器编号为Pik,i=1~n,k=1~n+1(2)并行化分析①消元的并行化://O(n)forj=1ton-1,eachPikPar-do//第j次消元Pij(i<>j):aij<—0Pi