科学计算学习.pptx

《科学计算学习.pptx》由会员分享，可在线阅读，更多相关《科学计算学习.pptx（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、定义定义3.2.1 设设 ，为一复数，如下形式的矩阵为一复数，如下形式的矩阵称为称为初等矩阵初等矩阵(elementary matrix).).3.2 初等矩阵初等矩阵1.初等矩阵的定义和性质初等矩阵的定义和性质第1页/共82页 定理定理3.2.1 初等矩阵初等矩阵E(u,v,)具有如下性质：具有如下性质：第2页/共82页矩阵的初等变换矩阵的初等变换 下列三种变换称为矩阵的初等变换：（1）交换矩阵的两行（列）；（2）矩阵的某一行（列）乘以非零常数 k；（3）矩阵某一行（列）的 倍加到另一行（列）。线性代数中的初等矩阵线性代数中的初等矩阵 对单位矩阵施行一次初等变换所得的矩阵称为初等矩阵。第3页

2、/共82页（1 1）交换单位矩阵的第）交换单位矩阵的第i,j行（列）行（列）称为初等交换矩阵。称为初等交换矩阵。第4页/共82页（2 2）用）用k k乘单位矩阵的第乘单位矩阵的第i i行（列）行（列）第5页/共82页（3 3）将单位矩阵的第将单位矩阵的第j j行（第行（第i i列）的列）的k k倍加到第倍加到第i i行（第行（第j j列）列）第6页/共82页初等矩阵的性质初等矩阵的性质：初等矩阵都是可逆的，并且初等矩阵都是可逆的，并且第7页/共82页初等矩阵的作用初等矩阵的作用：交换矩阵交换矩阵A A的第的第i,ji,j行；行；交换矩阵交换矩阵A A的第的第i,ji,j列；列；用用k k乘矩阵

3、乘矩阵A A的第的第i i行；行；用用k k乘矩阵乘矩阵A A的第的第i i列；列；将矩阵将矩阵A A的第的第j j行的行的k k倍加到第倍加到第i i行；行；将矩阵将矩阵A A的第的第i i列的列的k k倍加到第倍加到第j j列。列。第8页/共82页特殊的初等矩阵特殊的初等矩阵 例例3.2.13.2.1 初等矩阵 P(i,j)=E(ei-ej,ei-ej,1)。例例3.2.2 3.2.2 初等矩阵 P(i(k)=E(ei,ei,1-k)。例例3.2.3 3.2.3 初等矩阵 P(i,j(k)=E(ei,ej,-k)。第9页/共82页2.2.初等下三角矩阵初等下三角矩阵称为初等下三角矩阵初等下

4、三角矩阵(elementary triangular matrix),即第10页/共82页(3)当i j 时，有初等下三角矩阵具有如下性质：初等下三角矩阵具有如下性质：第11页/共82页 用初等下三角矩阵用初等下三角矩阵 Li 左乘一个矩阵左乘一个矩阵 A，等于，等于从从A的第的第 k 行减去第行减去第 i 行乘以行乘以 。对于对于 ，如果，如果 ，取，取第12页/共82页3.HouseholderHouseholder矩阵矩阵称为Householder矩阵矩阵或初等初等Hermite矩阵矩阵(elementary Hermitian matrix)。取u=v=w,=2，并且w是单位向量，即|

5、w|=1，初等矩阵第13页/共82页并且若上述条件成立，则使H(w)a=b 成立的单位向量w可取为其中为任一实数。定理定理3.2.2 Householder矩阵H(w)具有如下性质：第14页/共82页第15页/共82页4.Givens 矩阵矩阵称为称为Givens矩阵矩阵,其中其中 第16页/共82页第17页/共82页定义定义3.3.1 设设V是数域是数域P上的线性空间，上的线性空间，|是以是以V中中的向量的向量为自变量的非负实值函数，如果它满足以为自变量的非负实值函数，如果它满足以下三个条件下三个条件：则称则称|为向量为向量的的范数范数(norm)，并称定义了范数的，并称定义了范数的线性空间

6、为线性空间为赋范线性空间赋范线性空间(normed linear space)。3.3 向量与矩阵范数向量与矩阵范数 1.向量范数向量范数第18页/共82页 对赋范线性空间对赋范线性空间V中任意向量中任意向量有有 在赋范线性空间在赋范线性空间V中，由范数可定义两点间的距离。中，由范数可定义两点间的距离。第19页/共82页例例.第20页/共82页可以证明：可以证明：第21页/共82页例例.在线性空间在线性空间Ca,b中，对任意中，对任意则则 都是都是 f(x)的范数。的范数。第22页/共82页定义定义3.3.2向量范数的等价具有自反性、对称性和传递性向量范数的等价具有自反性、对称性和传递性。第2

7、3页/共82页可以证明：可以证明：定理定理3.3.1 有限维线性空间有限维线性空间V V 上任意两个向量范数都是等价的上任意两个向量范数都是等价的。例如，对任意的向量例如，对任意的向量 ，容易证明：，容易证明：第24页/共82页定义定义3.3.3不收敛的向量序列称为发散的。不收敛的向量序列称为发散的。第25页/共82页向量序列的收敛性具有如下性质向量序列的收敛性具有如下性质。定理定理3.3.2第26页/共82页定义定义3.3.4 设设|A|是以是以Cmn中的矩阵中的矩阵A为自变量的为自变量的非负实值函数，如果它满足以下三个条件非负实值函数，如果它满足以下三个条件：2.2.矩阵范数矩阵范数（Ma

8、trix Norms)Matrix Norms)第27页/共82页例例.第28页/共82页定理定理3.3.3由定理由定理3.3.1即得矩阵范数等价性定理即得矩阵范数等价性定理。第29页/共82页定义定义3.3.53 3.相容矩阵范数相容矩阵范数Compatible Matrix Norms)Compatible Matrix Norms)第30页/共82页定理定理3.3.4定理定理3.3.5第31页/共82页为矩阵为矩阵A A的谱半径的谱半径.定义定义3.3.6 3.3.6 设设 ，其特征值，其特征值 ，称，称由定理由定理3.3.5知知第32页/共82页4 4.算子范数算子范数（Induced

9、 Matrix Norms)Induced Matrix Norms)第33页/共82页定理定理3.3.6第34页/共82页定义定义3.3.7第35页/共82页定理定理3.3.7第36页/共82页定理定理3.3.8第37页/共82页第38页/共82页例例.通常将通常将|A|1叫做叫做A的的列和范数列和范数，|A|2叫做的叫做的谱范数谱范数，|A|叫做的叫做的行和范数行和范数。定理定理3.3.9第39页/共82页定理定理3.3.10第40页/共82页定义定义3.3.85.5.矩阵序列矩阵序列(Sequences of Matrices)(Sequences of Matrices)第41页/共8

10、2页定理定理3.3.11第42页/共82页关于矩阵序列的极限运算有如下性质关于矩阵序列的极限运算有如下性质:第43页/共82页定理定理3.3.12推论推论3.3.1第44页/共82页定理定理 3.3.13第45页/共82页3.4 3.4 三角矩阵与三角形方程组 1.1.三角矩阵及其性质 如下形状的矩阵称为下三角矩阵，对角元全为1的下三角矩阵称为单位下三角矩阵。下三角矩阵具有如下性质：（1）两个下三角矩阵的和、乘积仍是下三角矩阵；（2）下三角矩阵可逆的充分必要条件是其对角元均非零。当下三角矩阵可逆时，其逆矩阵仍是下三角矩阵；（3）两个单位下三角矩阵的乘积仍是单位下三角矩阵，并且单位下三角矩阵的逆

11、矩阵仍是单位下三角矩阵。类似地，讨论上三角矩阵及其性质。第46页/共82页2.2.下下三角形方程组的解法 下三角形线性方程组 容易得到其求解递推式 第47页/共82页算法3.4.1 求解下三角方程组的前推法 for j=1:n-1 b(j)=b(j)/L(j,j);b(j+1:n)=b(j+1:n)-b(j)L(j+1:n,j);end b(n)=b(n)/L(n,n)算法3.4.1所需要的乘除运算次数 第48页/共82页3.3.上上三角形方程组的解法 上三角形线性方程组 容易得到其求解回代式 第49页/共82页算法3.4.2 求解上三角方程组的回代法 for j=n:-1:2 y(j)=y(

12、j)/U(j,j);y(1:j-1)=y(1:j-1)-y(j)U(1:j-1,j);end y(1)=y(1)/U(1,1)算法3.4.2所需要的乘除运算次数 第50页/共82页3.5 Gauss消去法与矩阵的LU分解思路首先将首先将A化为上三角阵，再回代求解化为上三角阵，再回代求解 。=1.1.Gauss 消元法第51页/共82页步骤如下：第一步：乘除运算量：(n-1)(n+1)(n-1)(n+1)第52页/共82页乘除运算量：(n-2)n第二步：第53页/共82页乘除运算量：(nk)(nk2)第k步：第54页/共82页n n1 1步以后，可得变换后的矩阵消元的乘除运算量：如果加上解上述上

13、三角形方程组的乘除运算量(n+1)n/2(n+1)n/2，总的乘除运算量为第55页/共82页如果 ，Gauss消去法的第1步取初等下三角矩阵2.矩阵的LU分解 其中 ，即第56页/共82页如果 ，Gauss消去法的第2步取初等下三角矩阵其中 ，即第57页/共82页如果 ，Gauss消去法的第k步取初等下三角矩阵其中 ，即第58页/共82页经过n n1 1步计算，可得记 ，则第59页/共82页 的计算则 和 的前k行元素相同，并且 4阶矩阵经过2步计算后，其存贮形式为 第60页/共82页算法3.5.1 矩阵的LU分解算法 for k=1:n-1 A(k+1:n,k)=A(k+1:n,k)/A(k

14、,k);A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-A(k+1:n,k)*A(k,k+1:n);end Gauss消去法或算法3.5.1能进行到底当且仅当问题：矩阵A满足什么条件才能保证所有的主元都不为零？第61页/共82页定理3.5.1 算法3.5.1中主元 的充分必要条件是矩阵A的前n-1阶顺序主子式均非零，并且 定理3.5.2 设A是n阶矩阵，如果A的前n-1阶顺序主子式均非零，则存在唯一的单位下三角矩阵 L 和上三角矩阵U,使得 A=LU。注意：如果A是n阶非奇异矩阵，定理3.5.2的条件也是必要的。分解式A=LU称为矩阵A的LU分解。第62页/共82页定理3.5.3

15、设A是n阶矩阵，如果A的前n-1阶顺序主子式均非零，则存在唯一的下三角矩阵 L 和单位上三角矩阵U,使得 A=LU。第63页/共82页因为非奇异上三角矩阵 定理3.5.4 设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵 L，对角矩阵 和单位上三角矩阵U,使得 A=LDU的充分必要条件是A的所有顺序主子式均非零，并且 其中 表示矩阵A的k阶顺序主子式。分解式A=LDU称为矩阵A的LDU分解。第64页/共82页3.6 主元Gauss消去法Gauss 消元法存在的问题：（1 1）如果矩阵A非奇异，则Ax=b有唯一解。但A非奇异并不能 保证A的所有顺序主子式非零，所以Gauss消去法可能出 现中断（

16、break-down)；（2）如果主元 很小，会引入大的舍入误差，Gauss消去 法是数值不稳定的（unstable）.第65页/共82页例.解方程组/*精确解为 和 */8个8个用Gauss 消去法计算：8个第66页/共82页在第k步消元时，通常采用如下方式选取主元：（1 1）列主元：在 中选择模最大者作为主元；（2）全主元：在 中选择模最大者作为主元。在消元过程中必须避免绝对值相对小的数做主元。第67页/共82页例.用列主元Gauss 消去法解方程组解.第68页/共82页3.7 三对角线性方程组的追赶法 如下形式的矩阵称为三对角矩阵。如果所有次对角元都不等于零，则称A为不可约三对角矩阵。第

17、69页/共82页定理3.7.1 设A是如下不可约三对角矩阵如果A满足以下条件则A非奇异，并且 A的所有顺序主子式非零。第70页/共82页 如果A是不可约三对角矩阵，且满足定理3.7.1的条件，则由定理3.5.3知，其中第71页/共82页求解三对角线性方程组的追赶法如下：(1)计算 的递推公式(2)解Ly=b(3)解Ux=y追赶法的乘除运算次数为5n，存储量为6n.第72页/共82页3.8 对称正定线性方程组的Cholesky分解法 1.Hermite正定矩阵及其性质 定义定义3.8.1第73页/共82页正定（非负定）矩阵具有如下基本性质正定（非负定）矩阵具有如下基本性质：第74页/共82页定理

18、定理3.8.1 设设A是是n 阶阶Hermite矩阵，则下列命题等价矩阵，则下列命题等价：(1)A是正定矩阵是正定矩阵；(2)对任意对任意n 阶可逆矩阵阶可逆矩阵P,PHAP 都是都是Hermite正定正定 矩阵矩阵；(3)A的的n 个特征值均为正数个特征值均为正数；(4)存在存在n 阶可逆矩阵阶可逆矩阵P使得使得PHAP =I；(5)存在存在n 阶可逆矩阵阶可逆矩阵Q使得使得A=QHQ；(6)存在存在n 阶可逆阶可逆Hermite矩阵矩阵S 使得使得A=S2；(8)A的顺序主子式均为正数；的顺序主子式均为正数；(9)A的所有主子式全大于零的所有主子式全大于零;(10)存在存在n 阶非奇异下三

19、角矩阵阶非奇异下三角矩阵 L 使得使得 .(7)存在存在n 阶阶Hermite正定矩阵正定矩阵S 使得使得A=S2；第75页/共82页推论推论3.8.1第76页/共82页定理定理3.8.2 设设A是是n 阶阶Hermite矩阵矩阵,则下列命题等价则下列命题等价：(1)A是非负定矩阵是非负定矩阵；(2)对任意对任意n 阶可逆矩阵阶可逆矩阵P,PHAP是是Hermite非负定非负定 矩阵矩阵；(3)A的的n 个特征值均为非负数个特征值均为非负数；(7)A的所有主子式均非负的所有主子式均非负。第77页/共82页推论推论3.8.2 第78页/共82页2.Cholesky分解法 由定理3.8.1，实对称

20、正定矩阵A可分解为比较两边对角元比较两边非对角元第79页/共82页算法3.8.1 对称正定矩阵的Cholesky分解算法 for k=1:n-1 A(k,k)=sqrt(A(k,k);A(k+1:n,k)=A(k+1:n,k)/A(k,k);for j=k+1:n A(j:n,j)=A(j:n,j)-A(j:n,k)*A(j,k);end end A(n,n)=sqrt(A(n,n)算法3.8.1所需四则运算的次数为第80页/共82页解对称正定线性方程组的解对称正定线性方程组的Cholesky分解法如下：分解法如下：(1)用算法用算法3.8.1计算计算A的的Cholesky分解分解(2)用算法用算法3.4.1解下三角形方程组解下三角形方程组 Ly=b；(3)用用算法用用算法3.4.2解上三角形方程组解上三角形方程组第81页/共82页感谢您的观看！第82页/共82页