• / 69
  • 下载费用:10 下载币  

数值分析(06)矩阵分解法

关 键 词:
数值分析课件
资源描述:
数值分析数值分析( 1 ) ( 1 ) ( 1 )1 1 1 2 1( 1 ) ( 1 ) ( 1 )2 1 2 2 2( 1 ) ( 1 ) ( 1 )12n a aa a aa a a   ( 1 ) ( 1 ) ( 1 )11 12 1( 2 ) ( 2 )22 2()a 顺序高斯消元的基本思想:将矩阵 第三节 矩阵的三角分解法一、矩阵三角 分解的基本定理顺序高斯消元与 112111,:1L=完 成 第 一 步 消 元 得( 2 )11 2 30 1 20 1 1A L A    ( 2 )2 2 2 11111,L L A L L A=,完 成 第 二 步 消 元 得( 3 ) ( 2 )2 2 11 2 30 1 20 0 3A L A L L A   1 2 3A = 2 3 41 3 2求 矩 阵 的例 3 解 100=0021 0 00 1 00 1 1L=( 3 ) ( 2 )2 2 11 2 30 1 2 = 3A L A L L A   解 :1112A L L U1112L L L令 :1 1 0 02 1 0 1 01 1 0 1 1               00=001211 1 100=01 1 2 32 1 0 1 21 1 1 0 0 3A                 000数值分析数值分析( 1 ) ( 1 )11 1( 1 ) ( 1 ) ( 1 ) ( 1 )12( 1 ) ( 1 )1..., , ... ,..n       记 ( 1 ) ( 1 )1(1)1 1 1 1 1, , 0 , . . . , 0 a 对 的第一列 构造使1(1) 11 1 1 1110 , , 2 , . . . ,ii aa m i  ()():设 取第一步2111111( 1 ) ( 1 )1 1 121(1)1( 1 ) ( 1 )111..n     数值分析数值分析( 1 ) ( 1 ) ( 1 )1 1 1 2 1( 2 ) ( 2 )( 1 ) ( 2 ) ( 2 ) ( 2 ) ( 2 )2 2 21 1 2( 2 ) ( 2 )2, , .. .,n na a       ( 2 ) ( 1 ) ( 1 )11 2 , , , 2 , ,i j i j i ja a m a i n j n   ( 1 ) ( 1 )1 1 121(1)1( 1 ) ( 1 )111..n     数值分析数值分析( 2 )( 2 ) 22 2 2 ( 2 )220 3 , . . . ,ii aa m i  :设 , ,第二步 取( 2 ) ( 2 )32222( 1 ) ( 1 ) ( 1 ) ( 1 )11 12 13 1 ,( 2 ) ( 2 ) ( 2 )22 23 2 ,( 2 ) ( 1 ) ( 3 ) ( 3 ) ( 3 )2 2 1 33 3 ,( 3 ) ( 3 )3,111 ,100000n a a aa a L L A a a        第 二 列 构 造2 )22 ( 2 )22,ii am a( 3 ) ( 2 ) ( 2 )22 , , 3 , ,i j i j i ja a m a i j n   ( 1 ) ( 1 ) ( 1 )11 12 1( 2 ) ( 2 )( 2 ) 22 2322( 2 ) ( 2 )22( 1 ) ( 1 ) ( 1 ) ( 1 )11 12 13 1 ,( 2 ) ( 2 ) ( 2 )22 23 2 ,( 3 ) ( 3 )33 3 ,( 3 ) ( 3 )3,1....n n na a a a aa a        3 )A数值分析数值分析进行到第 ) ( 1 ) ( )k k A k下 一 步 消 元 , 从 , 将 的 第 列 的 对 角 元以 下 的 元 素 化 为 零 。( 1 ) ( 1 ) ( 1 ) ( 1 )11 12 13 1( 2 ) ( 2 ) ( 2 )22 23 2( 3 ) ( 3 )33 3()( ) ( )1( ) ( )1 , 1 , 1( ) ( ) ( ),1... ... ...... ... ...... ... ...... ...... .....k k kk k kn k n k n na a a aa a a a    数值分析数值分析()()()0,( 1 , ..., )kk k nG au 设 取,构 造 变 换 阵 ,,111111 l    ( 1 ) ( )kk A  消 元 计 算 递 推 公 式 :()( 1 , 2, , 1 )称为主元素.( ) ( )( 1 ) ( ) ( )1 , ,1/2 1 , ,ik k ij ik k nm a aa a m a j k n   ( )( ) ,数值分析数值分析是高斯消元的前提。)1,,2,1(,0)(  ( 1 ) ( 1 ) ( 1 )1 1 1 2 1( 2 ) ( 2 )() 2 2 2()000nn a 最 后 得得到令由111211)(11121211)1()()1(1221........12131 3231 321 2 , 11 2 . 11111111111n n n nn n n l lm m m     22211211)()2(2)2(22)1(1)1(12)1(11)(数值分析数值分析步消元计算后,第的二维数组存放一个用用动态存储方式。最初在计算机中计算时,采存储方式),,1;,,1(),,1()1()()()()(1,)()(1,1)(,1)(1)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(.........................................( 消元过程全部完成后,原来的二维数组中存放的元素实际上是一个新的矩阵,记为用动态形式表示为)(1,321)3(3)3(1,3)3(333231)2(2)2(1,2)2(23)2(2221)1(1)1(1,1)1(13)1(12)1(11数值分析数值分析=)%功能:对方阵 =中,% 输入:方阵 A。%输出:紧凑存储 A=[L\U].%注意:当 0时退出 n,n]=); % 确定 k=1:i=k+1:n (k,k) ==0 i,k) =A(i,k)/ A(k,k);A(i,k+1:n)= A(i,k+1:n)- A(i,k) *A(k,k+1:n);) ( )( 1 ) ( ) ( )1 , ,1/2 1 , ,ik k ij ik k nm a aa a m a j k n   ( )( ) ,数值分析数值分析=)%功能:对方阵 =中,% 输入:方阵 A。%输出:紧凑存储 A=[L\U]n,n]=); % 确定 k=1:(k,k) ==0 i=k+1:n A(i,k) =A(i,k)/ A(k,k);A(i,k+1:n)= A(i,k+1:n)- A(i,k) *A(k,k+1:n);) ( )( 1 ) ( ) ( )1 , ,1/2 1 , ,ik k ij ik k nm a aa a m a j k n   ( )( ) ,数值分析数值分析=)%功能:对方阵 =中,% 输入:方阵 A。%输出:紧凑存储 A=[L\U].[n,n]=); % 确定 k=1:(k,k) ==0 k+1:n,k) =A(k+1:n,k)/ A(k,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);e t ( ) 0 ( 1 , 2, , ) k   若 阶 方 阵 的 顺 序主 子 式则 可 唯 一 地 分 解 为 一 个 单 位 下 三 角 阵 和 非 奇 异 的上 三 角 阵 的 乘 积 。 即定 理 ( 矩 阵 分 解 定 理 )(),,0 , ( 1 , 2 , .:.. , )0 A L UA a k    存 在 性 非 奇 异 阵 存 在 分 解 式的 主 元 素的 顺 序 主 子 式证 明11111111,, , ,A L U L U U U唯 一 性 反 证 , 设 分 解 式 不 唯 一 ,其 中 为 单 位 下 三 角 阵 为 非 奇 异 上 三 角 阵 ,故 有数值分析数值分析唯一性得证。即故只能是单位阵,同时右边是上三角阵而左边是单位下三角阵111111。式则存在唯一的分解为正定矩阵  , , U为 严 格 对 角 占 优 则 存 在 唯 一 的 分 解式 。推论 1推论 2数值分析数值分析()d e t ( ) 00, ( 1 , 2, ..., )k n  是 严 格 对 角 占 优 阵非 奇 异顺 序 主 子 阵 严 格 对 角 占 优顺 序 主 子 式 非 零主 元 素4 1 1 11 4 1 11 1 4 11 1 1 4A例:数值分析数值分析11 1111 2211 2211...: 0 1 , 2, ...,01 1 1( , , ..., ) , ( , , ..., ), u k g u u u D gu u D D U L D R R D U    证 明 : ( 存 在 性 ) 显 然由且令则 其 中 是 单 位 上 三 角 阵12,,( , , .. ., ) , 0, ( 1 , 2, .. 4 L R DD di ag d d    设 为 阶 可 逆 矩 阵 ,则 可 唯 一 的 分 解 为 的 顺 序 主 子 式 非 零 。其 中 分 别 是 单 位 下 、 上 三 角 阵 , 是 对 角定 理 ( 矩 阵 分 解阵定 理 )数值分析数值分析1 1 11 1 11 1 1 11 1 1 1 1 1, , , , ,,A L D R L D D R L D D R D R D L L D R R   反 证 : 设 不 唯 一 ,由 非 奇 异 知 均 非 奇 异 ,( 一 性 )故 有唯111111L L I L I D D    而 左 边 是 单 位 下 三 角 阵 , 同 时 右 边 是 对 角 阵 ,故 只 能 是 单 位 阵即1111 1 1 11 1 1 1R R I R L D I L L D D       而 左 边 是 下 三 角 阵 , 同 时 右 边 是 单 位 上 三 角 阵故 只 能 是 单 位 阵即数值分析数值分析35le s 若 为 对 称 正 定 阵 , 则 可 唯 一 地 分定 理 : ( 对解 为其 中称 正 定为 下阵 的 分 解 )三 角 阵 。)())((),...,,(,...,2,1,0),,...,,(2121212121212121令则有令故是对称正定的又() D R A R D R L A   由 已 知 和则 有由 唯 一 性 知 故 有证 明 : Ax U Ax x bU x Y 二 、 利 用 三 角 分 解 求 解利 用 求 解设 已 有 代 入 原 方 程 得121111,( , , , ):( 2 , 3 , , )k k j bY y y b l y k n  第 求解下三角方程组 向前回步 代一 求出 21211,2132312111111数值分析数值分析2121222112111)1,,2,1()(,: 向后回代求出求解上三角方程组第二步数值分析数值分析排列阵。为是一些对换阵的乘积称其中矩阵解释是,使即寻找进行消元计算。强主元,然后换行,再素中寻找列自对角元以下的各元的第步,在第|m )()()(列主元 L U A x b利 用 列 主 元 分 解 求 解数值分析数值分析)()(1,)()(1,1)(,1)(1)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(.........................................数值分析数值分析0 1 1 21 0 0 12 1 0 11 3 0 1,A  设求 矩 阵 的 列 主 元 三 角 分 解 其 中 为 单 位下 三 角 阵 、 为 上 三 角 阵 、 为例 3排 列 阵 。数值分析数值分析11113 , 10 0 1 0 2 1 0 10 1 0 0 1 0 0 11 0 0 0 0 1 1 20 0 0 1 1 3 0 1 A                  解 :1 1 11 2 1 0 11 1 1102 2 20 1 1 1 21 7 1102 2 2L L P A                           数值分析数值分析222 2 1 12 2 2 1 14, 22 1 0 11 0 0 07100 0 0 1220 0 1 0 1 1 20 1 0 0 1 10222 1 0 11711 022213101771310077 L P P L P A U    数值分析数值分析112 1 2 211122017110127L P L P L0010000110000100,1221121221121221111212122111121211111122数值分析数值分析143(,)2341(,)4123(,)4321(21在计算机中用向量表示排列阵0010000110000100,0010010010000001,100000010010010021143(,)4123()4321(数值分析数值分析( 1 , 2, ..., )1 , 2, ..., 11, m ) , ( ) ( ) , ( ), , , ( 1 , ..., )3/ , ( 1 , ..., )i k i kj i j i ik ik a p k p k p i p i mT a a a a T j na m a a i k         对( ) 选 列 主 元确 定 使如 果 , 则 输 出 失 败 信 息 , 停 机 。( ) 如 果 , 则 换 行列 主 元 三 角 计 算 步算骤 :( ) 消 元 计, ( 1 , ..., , 1 , ..., )ik a i k n j k n    能:对方阵 A=中,% 列阵 P% 用向量 输入:方阵 A。%输出:紧凑存储 L\U],以及 p。%注意:当 LU,p]=)%初始化n=); p=1:n; ;%分解过程k=1:n%搜索列主元 ik[s,i]=U(k:n,k))); ik=i+法 3主元三角分解: 断矩阵的奇异性if s==0 交换if km=p(k); p(k)=p( p(m;U(k,:); LU(k,:)=LU(); LU()=lk;消元法计算 L\U]k==n k+1:n,k)=LU(k+1:n,k)/LU(k,k);LU(k+1:n,k+1:n)=LU(k+1:n,k+1:n)k+1:n,k)*…LU(k,k+1:n);0 1 ; 0 1;2 1;1 3 0 1][L,U,P]=)[L,U]=)bA x b U A x U x x Y      用 列 主 元 的 三 角 分 解 求 解12( 1 2 3 4 ) , ( 3 2 1 4 ) ,( 3 4 1 2 ) , ( 3 4 1 2 ),( ) (,,( 1 ) ( ( 1 ) ) ( 3 ) , ( 2 ) ( ( 2 ) ) ( 4 )( 3 ) ( ( 3 ) ) ( 1 ) , ( 4 ) ( ( 4 )())2)()x b U PA x x Pb ff b P b f b P bf b P bf i b Pf b P        为 排 列 阵 , 在 计 算 机 中 用 向 量 表 能:调用列主元三角分解函数 [LU,p]=)% 求解线性方程组 Ax=b。%解法: U, Ax=b←→b% b, y=Ly=f=f(i)=b(p(i))%输入:方阵 A, 右端项 b( 行或列向量均可 )%输出:解 x( 行向量 )数值分析数值分析x=,b)n=b);[LU,p]=);y(1)=b(p(1));i=2:ny(i)=b(p(i))i,1:y(1:;n)=y(n)/LU(n,n);i=(x(i)=(y(i)i,i+1:n)*x(i+1:n)')/LU(i,i);其中矩阵解释是,使、即寻找。换列,再进行消元计算元,然后换行、的右下角子阵中找强主步,在第 |m )(,)()()()(1,)()(1,1)(,1)(1)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(.........................................全主元 L U A x b利 用 全 主 元 分 解 求 能:对方阵 U,其中,% 列阵 P% 和 p,输入:方阵 A。%输出:紧凑存储 L\U],以及 p和 q。%注意:当 LU,p,q]=)%初始化n=); p=1:n; q=p; ;数值分析数值分析%分解过程k=1:n%搜索全主元 (ik,]=U(k:n,k:n))); %列最大值及所在行[s,j]=(j)+jk=j+判断矩阵的奇异性if s==0 交换和列交换if km=p(k); p(k)=p( p(m;U(k,:); LU(k,:)=LU(); LU()=lk;km=q(k); q(k)=q( q(m;U(:,k); ,k)=, ,ck;消元法计算 L\U]k==n k+1:n,k)=LU(k+1:n,k)/LU(k,k);LU(k+1:n,k+1:n)=LU(k+1:n,k+1:n)k+1:n,k)*…LU(k,k+1:n);) ( ) Q L UA x b P A Q Q x P b L U Q   用 全 主 元 的 三 角 分 解 求 能:调用全主元三角分解函数 [LU,p,q]=)% 求解线性方程组 Ax=b。%解法: U, Ax=b←→(1)(x)=z=y=Ly=f=f(i)=b(p(i))% Uz=y, z= x(q(i))=z(i).%输入:方阵 A, 右端项 b( 行或列向量均可 )%输出:解 x( 行向量 )数值分析数值分析x=,b)n=b);[LU,p,q]=);y(1)=b(p(1));i=2:ny(i)=b(p(i))i,1:y(1:;n)=y(n)/LU(n,n);x(q(n))=z(n);i=(z(i)=(y(i)i,i+1:n)*z(i+1:n)')/LU(i,i);x(q(i))=z(i); 2221211121222111212222111211111111111111111211n),2,(j 2 )( )1 列第行第取正(1)展开式由 三、矩阵的直接三角分解法 112km k) 若已求出了 为求第 用 00)0,,0,,,,(2121 112212 , 即得到数值分析数值分析再用 j=k+1 ,k+2,…… ,n )有0)0,,0,,,,(121  111, 即得到),2,1(/][ 11 数值分析数值分析),,2;,,1()(1),,3,2(1111211111111式432144434241333231222111321333323122322211131211数值分析数值分析及其改进分解。缺点:开方运算。不必选主元。平方根法稳定,受到控制所以说舍入误差的放大元的最大对角的值不会超过 这说明在分解过程中故  列:第行、第  、计算量小   优点:  L,A m 数值分析数值分析,00Ti j i L L 的 不 完 全 是 与 有 相 同的 稀 疏 性 , 即 若 , 。不完全 L L 将 分 解 为其 中 为 下 三 角 矩 阵 ,为 剩 余 矩 阵 。3 1 0 21 3 1 00 1 3 12 0 1 3A数值分析数值分析0032000003200000007321803282183038313 0 21 3 1 00 1 3 12 0 1 3A数值分析数值分析, C h ol e h ol e x x b是 对 称 正 定 的 矩 阵利 用 分 解 求 解, 有 分 解 式代 入 原 方 程 可 分 成 两 步1( ) / , ( , 1 , , 1 )i k i k x Yx y l x l i n n    (2) 求 解 上 三 角 方 程 组11( ) / , ( 1 , 2 , , )ii i ik k by b l y l i n   (1) 求 解 下 三 角 方 程 组数值分析数值分析定义 若 n 阶矩阵 A=(元素满足 :对于 1> a=-1*,4); b=4*,4);>> c=-1*,4);d=[3 2 2 3];>> x=zg(a,b,c,d)x = 1 1 1 1数值分析数值分析定理 3 - 6 设具有式 (3 - 18) 形式的 三对角阵 A 满足条件 ( 1 ) 011 ( 2 ) 0 ( 3 ) 1,...,3,2,0,  x d 的解存在唯一,且追赶法通常是数值稳定的。 数值分析数值分析周期三对角方程组的一般形式基本思想: 利用谢尔曼 方程组化为三对角方程组求解。Ax d矩阵表示1 1 1 12 2 2 2 21 1 1 1 1n n n n nn n n nb c x da b c x da b c x da b x d                                                3、周期三对角方程组数值分析数值分析。非奇异且、非奇异其中01,,1111 V A d 1111()1 U V V A  谢尔曼 方程组的解为莫里森公式,利用谢尔曼为三对角矩阵其中化为使原方程组、选择向量,)( V A d计算111 () U V V A d V W Z 则11,,W A d A W d U A Z U Z令 由 可 解 出令 由 可 解 出1 Z 数值分析数值分析,,()1(1.) d U  求出求先解两个辅助方程组利用谢尔曼 莫里森公式可求得原方程组的解出数值分析数值分析 U V如何选取 U, 21 1 111 12 2 211 1 101 0 00Tn n n b U Va b ba b b                  数值分析数值分析111 1 1 1( , 0 , , 0 , ) , ( 1 , 0
展开阅读全文
  石油文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:数值分析(06)矩阵分解法
链接地址:http://www.oilwenku.com/p-10796.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
copyright@ 2016-2020 石油文库网站版权所有
经营许可证编号:川B2-20120048,ICP备案号:蜀ICP备11026253号-10号
收起
展开