华东师范大学数学科学学院 目录页 School of Mathematical Sciences,ECNU Contents LU分解 2 LU分解并行计算 3 三角线性方程组的并行求解 http://math.ecnu.edu.cn/~jypan
目录页 Contents http://math.ecnu.edu.cn/~jypan 1 2 LU 分解 LU 分解并行计算 3 三角线性方程组的并行求解 华东师范大学 数学科学学院 School of Mathematical Sciences, ECNU
华东师范大学数学科学学院 目录页 School of Mathematical Sciences,ECNU Contents LU分解 ■ LU分解算法 U分解 ■ 部分选主元LU分解算法 2 LU分解并行算法 3 三角方程并行求解 http://math.ecnu.edu.cn/~jypan
目录页 Contents http://math.ecnu.edu.cn/~jypan LU 分解算法 1 部分选主元 LU 分解算法 2 LU 分解 LU分解并行算法 1 LU 分解 3 三角方程并行求解 华东师范大学 数学科学学院 School of Mathematical Sciences, ECNU
LU分解 定理(LU分解的存在性和唯一性)设A∈R”xn.则存在唯一的单位下 三角矩阵L和非奇异上三角矩阵U,使得A=LU的充要条件是A的 所有顺序主子矩阵Ak=A(1:k,1:k)都非奇异，k=1,2,.,n. http://math.ecnu.edu.cn/~jypan 4
http://math.ecnu.edu.cn/~jypan 4 LU 分解
LU分解 LU分解的实现一矩阵初等变换 给定一个矩阵 a11a12··a1m a21a22···a2m A= ∈Rnxn an1am2···ann」 ·第一步：假定a11卡0，构造矩阵 100·0 l2110.…0 L1= l3101.0 其中l1= a1,i=2,3,n. a11 . Lln100·1 http://math.ecnu.edu.cn/~jypan 5
http://math.ecnu.edu.cn/~jypan 5 LU 分解
LU分解 易知L1的逆为 100.·07 -l2110…0 L1= -l3101.0 -ln100…1 用L1左乘A,并将所得到的矩阵记为A1),则 a11a12·a1m 0 (1) (1) A(1)=LIA 022 ···02n : 0 (1) (1) an2 即左乘L11后，A的第一列中除第一个元素外其它都变为0. http://math.ecnu.edu.cn/~jypan 6
http://math.ecnu.edu.cn/~jypan 6 LU 分解
·第二步：将上面的操作作用在A1)的子矩阵A)(2:n,2:n)上，将 其第一列除第一个元素外都变为0：假定a2≠0，构造矩阵 [100.07 010..0 (1) L2= 01321…0 其中 l2= 08i=3,4,m 022 L0lm20…1 用L21左乘A1四)，并将所得到的矩阵记为A(②)，则 011012 013 .··01n 0 ,(1) (1) (1) 022 023 .··a2m A②)=L21A=L21L11A= 2) 0 0 (2) 033 ..·a3n 0 0 ) an3 ) ann nttp://matn.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 7 LU 分解
依此类推，假定经”≠0（低=3,4n-1),则我们可以构造一系 ● 列的矩阵L3,L4,.,Ln-1,使得 a11 a12 a13··· ain 0 (1) (1) 022 (1) 023 02 2) (2) Ln1…L21L11A= 0 0 33 03m 会U→上三角 0 0 0 -1) ann 于是可得A=LU 其中 1 0 0··0 l21 1 L=L1L2…Ln-1= l31l32 1·0 Lln1ln2ln3·1 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 8 LU 分解
算法1.2LU分解 1:for k 1 ton-1 do 2: for i=k+1 to n do 3: lk=a/akk%计算L的第k列 4: end for 5 for j=k to n do 6: =aj%计算U的第k行 7: end for 8: for i=k+1 to n do 9 forj=k+1ton do 10: aij=aij-likukj %更新A(k+1:n,k+1:n) 11: end for 12: end for 13:end for http://math.ecnu.edu.cn/~jypan 9
http://math.ecnu.edu.cn/~jypan 9 LU 分解
LU分解 算法1.3LU分解 1:for k 1 ton-1 do 2: for i=k+1 ton do 3: aik =aik/akk 4: forj=k+1 ton do 分 aij=aii一aikakj 6: end for 7 end for 8:end for http://math.ecnu.edu.cn/~jypan 10
http://math.ecnu.edu.cn/~jypan 10 LU 分解
LU分解 如果数据是按行存储的，如C/C++,我们一般采用下面的IK)型LU分解 算法1.4LU分解(IK型) 1:for i=2 to n do 2: for k:=1 to i-1 do 3: aik =aik/akk 4 forj=k+1to n do 5 ai)=ai订-aikakj 6: end for 7: end for 8:end for http://math.ecnu.edu.cn/~jypan 11
http://math.ecnu.edu.cn/~jypan 11 LU 分解