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

数值分析(05)高斯消元法

关 键 词:
数值分析课件
资源描述:
数值分析数值分析第二节 高斯消元法第三节 矩阵的三角分解法第四节 误差分析和解的精度改进第五节 大型稀疏方程组的迭代法第三章 线性代数方程组的数值解法言第六节 极小化方法数值分析数值分析线性代数方程组的一般形式( 1 )x 用 矩 阵 形 式 表 示 为其 增 广 矩 阵 记 为1 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 2m m n n ma x a x a x ba x a x a x ba x a x a x b               1 1 1 2 1 12 1 2 2 2 212,m m n ma a a ba a a ba a a b    第一节 引 言数值分析数值分析A x b A A 线 性 方 程 组有 解 的 充 分 必结 论 1 ( 线 性 代 数 方 程 组要 条 件 是 : 秩 ( ) = 秩有 解 判 定 理(别 ))( 1 ) ( ) ( ) ,Ax r n Ax b   线 性 方 程 组 有 解 ( 即 相 容 ) 时 ,秩结 论 2秩 则 方 程 组 存 在 唯 一 解 。( 2 ) ( ) ( ) ,r A r A r n Ax b    方 程 组 有 无 穷 多 解 。通 解 原 方 程 组 一 个 特 解 对 应 齐 次 方 程 组 的 基础 解 系 的 线 性 组 合 。222, || || | ||bx x x x Ax b常 见 是 , 称 为 欠 定 方 程 组 ( 方 程 数 少 于 未 知 数 )此 时 , 从 的 无 穷 多 个 解 中 需 求 出 范 数 最 小 的 解 。即 求 使 , 满 足 。数值分析数值分析22( ) ( )()|| || m r A Ax R b A x方 程 组 无 解 ( 即 不 相 容 ) 。常 见 是 , 称 为 超 定 方 程 组 ( 又 称 矛 盾 方 程 组 )此 时 , 向 量 不 在 的 列 空 间 之 中 , 原 方 程 组无 解 , 但 可 求 出 最 小 二 乘 意 义 下 的 解 。即 求 使 x=A\ 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 2n nn n x a x a x ba x a x a x ba x a x a x b              本 章 介 绍 求 解 阶 线 性 方 程 组 的 数 值 方 法数值分析数值分析数值求解方法有以下三条途径直接法:利用 阵分解,通过有限次运算可求出精确解。迭代法:构造迭代格式,产生迭代序列,通过无限次迭代过程求解。有限次截断得近似解。极小化方法:构造二次模函数,用迭代过程求二次模函数的极小化问题,即变分法(经 论上得精确解)要求 值分析数值分析用增广矩阵表示为同解初等变换组化为同解的上三角方程将原方程组求解第二节 高斯消元法数值分析数值分析三角形方程组包括上三角形方程组和下三角形方程组 , 是最简单的线性方程组之一 。 上三角方程组的一般形式是 :),......,2,1(0...................................................................................................其中一、三角形方程组的解法数值分析数值分析1 2 42 3 43444573 1 3 1 31 3 1 3x x xx x         用 回 代 法 求 解 线 性 方例 程 组4342 4 31 4 21 2 3 41( 13 13 ) / 3 0( 7 5 ) ( 7 5 0 ) 24 4 1 2 1, , , ) ( 1 , 2, 0:, 1 )x xx x xx x x x                  所 以 , 解 为 (解数值分析数值分析1/( ) / 1 , , 1n n i ik k b ax b a x a i n    为求解上三角方程组,从最后一个方程入手,先解出 xn=bn/然后按方程由后向前的顺序,从方程中依次解出 ,x 1。 这样就完成了上三角方程组的求解过程。这个过程被称为回代过程其计算步骤如下:1 1 1 1 2 2 1 12 2 2 2 21 1 1 1 1.................................................................................................. . 1 , 2, ......, )n n n n n n x a x a x ba x a x ba x a x ba x ba i n          其 中数值分析数值分析=,b)%A is an n× n is an n× 1 X is to X=数表n=b);X=n,1);X(n)=b(n)/A(n,n);i=1:1X(i)=(b(i)-A(i,i+1:n)* X(i+1:n))/A(i,i); i+1到 ) / 1 , , 1n n i ik k b ax b a x a i n    数值分析数值分析1 2 42 3 43444573 1 3 1 31 3 1 3x x xx x         求 解 上 三 角 方 程 组例4: 1x 解2 2x 122333230    3 0x 12232  11 2 3 41, , , ) ( 1 , 2 , 0 , 1 )x x x所 以 , 解 为(数值分析数值分析i= n : – 1 : 2b ( i ) = b ( i ) / A ( i , i );b (1: i - 1 ) = b (1: i - 1 ) - b ( i ) *A (1: i - 1 , i ) ; 1 ) = b ( 1 ) / A ( 1 ,1 );求解上三角方程组 Ax= ( 1 )211 ) ( 1 )2i n ni n n n    求 解 一 个 三 角 形 方 程 组 需 次 除 法 , ( 次 乘 法 ,( 次 加 法 。 总 计 算 量 约 为 。数值分析数值分析1121 2 32223 2 4 9x x  用 回 代 法 求 解 线 性 方 程 组例1231 2 32 / 2 1( 2 1 ) / 1 1( 9 3 1 2 1 ) / 4 1, , ) ( 1 , 1 , ):1x x       所 以 , 解 为 (解数值分析数值分析121 1 1111, , , ,/( ) / ( 2, 3, , )i ik k x xx b ax b a x a i n  下 三 角 形 方 程 组 可 以 参 照 上 三 角 形 方 程 组 的 解 法 来 求 解 ,下 三 角 形 方 程 组 的 求 解 顺 序 是 从 第 一 个 方 程 开 始 , 按 从 上 到 下的 顺 序 , 依 次 解 出 : 其 计 算 公 式 为 :如 上 解 三 角 形 方 程 组 的 方 法 称 为 回 代 法 121 1 22 2 21 1 2 20, 1 , 2, ,n n nn n x ba x a x ba x a x a x ba i n    下三角方程组的一般形式为:其中数值分析数值分析高斯消元法是一个古老的直接法 ,由它改进得到的选主元法 ,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法 ,其特点就是通过消元将 一般线性方程组 的求解问题转化为 三角方程组 的求解问题。高斯消元法的求解过程 ,可大致分为两个阶段 :首先 ,把原方程组化为上三角形方程组 ,称之为 “ 消元 ”过程 ;然后 ,用逆次序逐一求出上三角方程组 (原方程组的等价方程组 )的解 ,称之为 “回代”过程 消 元 ”过程 可通过矩阵运算来实现。具体过程如下:二、顺序高斯消元法数值分析数值分析1 2 31 2 31 2 32 3 62 3 4 9313 2 6s sx x xx x xx x x        用 顺 序 消 元 法 求 解 方例 程 组11/1/21/2/01,3623194326321][11313111212111)1(:1112 1 , :11L A x L b1L = , 完 成 第 一 步 消 元 得数值分析数值分析( 2 ) ( 2 ) ( 2 )2 2 3 2 3 2 2 22 2 1 2 11 0 , / 1 /( 1 ) 111,11a m a L A x L L b       =, 完 成 第 二 步 消 元 得3332632332321 31 2 33 / 3 1( 3 2 ) ( 3 2 1 ) 16 2 3 6 2 1 3 1 11 , 1 , 1x xx x x                    回 代 求 得故 所 求 解 为011032106321)2(A330032106321)3(x=1 1 1 2 1 12 1 2 2 2 212,n n n na a a ba a a bA b Aa a a b( 1 ) ( 1 ) ( 1 )11 1 1( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )12( 1 ) ( 1 ) ( 1 )1..., , ... , ,..nn na a ba a b        记 ( 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 )1 1 1 2 1 1( 2 ) ( 2 ) ( 2 )( 1 ) ( 2 )( 2 ) ( 2 ) ( 2 ) ( 2 )2 2 2 21 1 2( 2 ) ( 2 ) ( 2 )2... ., , .. ., ,0 .. nn na a a ba a A ba a b         ( 2 ) ( 1 ) ( 1 )11( 2 ) ( 1 ) ( 1 )112 , , , 2 , ,, 2 , ,ij ij i ji i ia a m a i n j nb b m b i n     ( 1 ) ( 1 )1( 1 ) ( 1 )11A x b x L b对 方 程 组 从 左 边 乘 以( 1 ) ( 1 ) ( 1 )1 1 1 1(1) 211( 1 ) ( 1 ) ( 1 )111..n n a a     数值分析数值分析( 2 )( 2 ) 22 2 2 ( 2 )220 3 , . . . ,ii aa m i  :设 , ,第二步 取( 2 )( 2 )32222( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )11 12 13 1 , 1( 2 ) ( 2 ) ( 2 ) ( 2 )22 23 2 , 2( 2 ) ( 1 )( 3 ) ( 3 ) ( 3 )( 3 )2 2 1 33 3 , 3( 3 ) ( 3 ) ( 3 )3,111 ,100000n n a a a ba a a L L A a a b       第二列 构造2 )22 ( 2 )22,ii am a( 1 ) ( 1 )2 1 2 1L L A x L L b( 3 ) ( 2 ) ( 2 )22( 3 ) ( 2 ) ( 2 )22, , 3, ,3, 4, ...,i j i j i ji i ia a m a i j nb b m b i n    ( 1 ) ( 1 ) ( 1 ) ( 1 )11 12 1 1( 2 ) ( 2 ) ( 2 )( 2 )22 2 2322( 2 ) ( 2 ) ( 2 )22( 1 ) ( 1 ) ( 1 ) ( 1 )11 12 13 1 ,( 2 ) ( 2 ) ( 2 )22 23 2 ,( 3 ) ( 3 )33 3 ,(331....n n a a ba a a a a aa a         1 )1( 2 )2( 3 )( 3 )3) ( 3 ) ( 3 ),nn b数值分析数值分析进行到第 ) ( 1 ) ( )k k A k下 一 步 消 元 , 从 , 将 的 第 列 的 对 角 元以 下 的 元 素 化 为 零 。( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )11 12 13 1 1( 2 ) ( 2 ) ( 2 ) ( 2 )22 23 2 2( 3 ) ( 3 ) ( 3 )33 3 3()( ) ( ) ()1( ) ( ) ()1 , 1 , 1 1( ) ( ) ( ) (),1... ... ...... ... ...... ... ...... ...... .....kk kk k k k kk k k kn k n k n n na a a a ba a a ba a a b       数值分析数值分析()()()0,( 1 , .. ., )kk k k nG a 设取,构造 变换阵,,111111l    ( 1 ) ( ) A 消元计算递推公式:()( 1 , 2, , 1 )称为主元素.( ) ( )( 1 ) ( ) ( )( 1 ) ( ) ( )1 , ,1/2 1 , ,3ik k ij ik k ki i ik ki k nm a aa a m a j k nb b m b   ()( ) ,()数值分析数值分析( 1 ) ( 1 ) ( 1 ) ( 1 )1 1 1 1 2 2 1 1( 2 ) ( 2 ) ( 2 )2 2 2 2 2( ) ( )n n na x a x a x ba x a x ba x b       即用回代过程求解上三角方程组,即可得解向量( …,x n* )1,,2,1(,0)(  ( 1 ) ( 1 )1 2 1 1 2 1 L A x L L L b ( 1 ) ( 1 ) ( 1 ) ( 1 )1 1 1 2 1 1( 2 ) ( 2 ) ( 2 )() 2 2 2 2( ) ( )000nn n na a a ba a 最后得数值分析数值分析求解的全过程包括两个步骤:消元和回代1 回代求解( ) ( )( ) ( ) ( )1/( ) / , 1 , 2, , 1n n k kk k kj j b ax b a x a k n n     ( ) ( )( 1 ) ( ) ( )( 1 ) ( ) ( )1 , , 11 , ,1/2 1 , ,3ik k kk k ij ik k jk k ki i ik k nm a aa a m a j k nb b m b   ()( ) ,()数值分析数值分析步消元计算后,第的二维数组存放一个用用动态存储方式。最初在计算机中计算时,采存储方式),,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数值分析数值分析=,b)%A is an n× n is an n× 1 X is to X= n n]=); % 确定 n,1);k=1:i=k+1:n % 消元过程A(i,k) =A(i,k)/ A(k,k); % A(k,k) ≠0A(i,k+1:n)= A(i,k+1:n)- A(i,k) *A(k,k+1:n);b(i)= b(i)- A(i,k) *b(k);, b); %回代求解数值分析数值分析高斯消元法的计算量分析3321 3 3 3n n   加减法计算量 为乘除 法计算量 为31 ( 1 ) ( 2 5 ) / 6 3nN n n n   高斯消元法的计算量 约 为323 - 1 ),.()( 全不为零 的充分必要条 件是 A 的顺序主子式 不为零,即 ),..(,0 k  。 )()2(22)1(11)()2(2)2(22)1(1)1(12)1(111111..........................证明 : 由于对系数矩阵 A 的消元计算不改变 A 的行列式的值, 因此 A 的顺序主子式为 当 ),..,2,1(0)(  时,显然 ),..(,0 k  , 必要性得证。 用归纳法证充分性。 数值分析数值分析定理 3线性代数方程组 Ax=b,其中 系数矩阵 可用顺序高斯消元法求解线性代数方程组 Ax=b。消元法是解线性方程组的基本方法,具有计算简单的优点,但有时由于主元过小,使得计算结果严重失真 ,实际中常采用选主元高斯消元法。数值分析数值分析例 3x1+0-3 101 101 101 101 解 :本题用机器数系表示为, 消元 得回代解得 , 严重失真 !(本题的准确解为 10000/9999, 998/9999 ))= 101 - 104  101= 105 - 105 (对阶计算 )= - 0-3 101 105 105主元 斯消元法的 基本思想用高斯消元法求解线性方程组时 ,为避免小的主元 应该在第 i=k,…,n )中找出第一个出现的绝对值最大者 ,例如 再把第 使 成为主元 由于只在第 通常也称为 按列选主元 .)() ( )m k i ()主元 高斯消元法)(在第 i=k,…,n;j=k,…,n )中 ,找出绝对值最大者 ,例如 ,再交换第 k,) ( ),m a j i jk i j 数值分析数值分析方程和第 k,使 成为主元 . 称这个过程为 完全选主元 而后再按上面介绍的计算步骤进行消元的计算 ,一般都称为选主元的高斯消元法 常用按列选主元的高斯消元法 .()) ( )()( ) ( )()( ) | | m |,, 1 , ,,( 1 )),(,,2k k i k i i kj i j i jk i k k i k i n a b i kT i ka a j k k nT a a a a Tb b T b b b b T         对 每 一 步 第 步 消 元 , 分 两 步确 定 使对 增 广 矩 阵 使列 主 元 高 斯 消 元 法 具 体 做 法 是 :选 列 主 元 换 行在 计 算 机 上 , 用 一 个 工 作 单 元 来 完 成 , 对 ,包 括消 元 计 算数值分析数值分析列主元高斯消元法解线性方程组 Ax=息输出失败则认为如果使确定、选列主元步。循环执行到第对、置,,0d e t ,0 ,m a x 2 51,,2,1 1d e t 1 d e td e t , ),,1,( , 4 , 3则交换行步转出执行第、如果具体执行行交换要通过工作单元 T。; ;; ;数值分析数值分析。、输出解向量、否则停机。输出失败信息则认为如果、回代求解、e t , ,),,,( 8d e td e ,2,,2,1( /)( / ,,0,6d e td e t 5211( 3) ),,1( ( 2) /( 1) ,,2,14、消元计算数值分析数值分析算法 3主元高斯消元法解线性方程组 X,,b)%输入 —A 是一个 n× n 非奇异矩阵, b 是一个列向量。%输出 —X=的行列式。[n n]=); % 确定 ; k=1:索列主元 ,i]=(k:n,k))); ik=i+判断矩阵的奇异性<=, 交换数值分析数值分析%行交换if (k,k:n);A(k,k:n)=A(k:n);A(k:n)=lk;m=b(k); b(k)=b( b(m;消元过程i=k+1:n A(i,k) =A(i,k)/ A(k,k); % A(k,k) ≠0A(i,k+1:n)= A(i,k+1:n)- A(i,k) *A(k,k+1:n);b(i)= b(i)- A(i,k) *b(k);A(k,k)*回代过程if (n,n))<=, n)=b(n)/A(n,n);i=1:1b(i)=(b(i)-A(i,i+1:n)* b(i+1:n))/A(i,i);A(n,n)*=b;x1+将两个方程对调,得x1+在四位浮点十进制数的计算机上 ,上式为x1+ 即 x1+ ( 101 ( x1+消元,得解得: , 例 3用列主元高斯消元法解数值分析数值分析编写 求解下三角方程组 Ax=种方法)习题
展开阅读全文
  石油文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

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

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