数值分析-线性方程组的解法GUESS消去法

1、第二章 线性方程组的解法,n元线性方程组,(2.1),矩阵形式,ax=b,(2.2),其中,设系数矩阵a非奇异，即deta0，则方程组（2.1）,有唯一解向量 x。,求解线性方程组的方法可分为两大类：,直接法和迭代法,直接法（精确法）：指在没有舍入误差的情况下经过 有限次运算就能得到精确解。,迭代法（逐次逼近法）：从一个初始向量出发，按照一 定的计算格式，构造一个向量的无穷序列，其极限才是 所求问题的精确解，只经过有限次运算得不到精确解。,cramer（克莱姆）法则是直接方法中的一种，根据 此法则，方程组（2.1）的解为,i=1,2,n,直接法（精确法）：指在没有舍入误差的情况下经过 有限次运

2、算就能得到精确解。,迭代法（逐次逼近法）：从一个初始向量出发，按照一 定的计算格式，构造一个向量的无穷序列，其极限才是 所求问题的精确解，只经过有限次运算得不到精确解。,i=1,2,n,cramer法则:,2010年11月17日，国防科技大学研制的天河一号以每秒4700万亿次的峰值速度和每秒2566万亿次的持续速度，在世界超级计算机500强中位居第一，中国人首次站到了超级计算机世界冠军的领奖台上。,天河一号 曾经的王者,2011年6月21日日本理化学研究所20日宣布，与富士 通共同研发中的超级计算机“京”以每秒8612万亿次的 运算速度在最新全球超级计算机500强排名中位列第一。,由170个机

3、 柜组成的 天河二号 整齐排列， 气势恢宏。,北京时间6月17日下午，正在德国莱比锡召开的2013国际超级计算大会上，世界超级计算机top500组织正式发布了第41届世界超级计算机500强排名榜，国防科技大学研制的天河二号超级计算机，以峰值计算速度每秒5.49亿亿次、持续计算速度每秒3.39亿亿次双精度浮点运算的优异性能位居榜首,小时,“天河2号”每秒的计算速度高达3京3860兆次， 美国克雷公司研发的“泰坦”位列第二，每秒计算速度为1京7590兆次， 美国ibm开发的“红杉”超级计算机居第三位，每秒计算速度为1京7170兆次， 日本富士通公司研发的超级计算机“京”以每秒1京510兆次居第4位

4、。,2013年6月17日,2014年6月,第二章 线性方程组的解法,2.1 gauss消去法,2.2 直接三角分解法,2.3 矩阵的条件数与病态方程组,2.4 迭代法,第二章 线性方程组的解法,2.1 gauss消去法,、三角形方程组的解法,二、gauss消去法,2.1 gauss消去法,、三角形方程组的解法,下三角形方程组,2.上三角形方程组,2.1 gauss消去法,、三角形方程组的解法,下三角形方程组,前代法,2.上三角形方程组,回代法,二、gauss消去法,2.1 gauss消去法,、三角形方程组的解法,1、gauss消去法的基本思想,2、顺序gauss消去法,3、列主元素gauss消

5、去法,二、gauss消去法,例,(1),(2),(3),(1) 2-(2),(1)+(3),消元1,回代,消元2,二、gauss消去法,例,(1),(2),(3),(1) 2-(2),(1)+(3),消元,回代,1、gauss消去法的基本思想：,消元与回代。,gauss消去法分为: 顺序gauss消去法,列主元素gauss消去法,2、顺序gauss消去法,例1在四位十进制的限制下，试用顺序gauss消去法求 解下列线性方程组,二、gauss消去法,解,(1)消元,(2)回代,精确解：,n元线性方程组,(2.1),矩阵形式,ax=b,(2.2),推导求方程组ax=b的顺序gauss消去法在计算机

6、上可执 行计算公式：,设,令,（i,j=1,2,，n）,n元线性方程组,(2.1),矩阵形式,ax=b,(2.2),推导求方程组ax=b的顺序gauss消去法在计算机上可执 行计算公式：,设,令,（i,j=1,2,，n）,推导求方程组ax=b的顺序gauss消去法在计算机上可执 行计算公式：,设,令,（i,j=1,2,，n）,第一步：,第一步：,第一步：,第一步：,第一步：,第一步：,第一步：,第一步:,第二步:,第k步:,第一步:,第二步:,第k步:,第一步:,第二步:,第k步:,第一步:,第二步:,第k步:,第一步:,第二步:,第k步:,顺序gauss消去法的计算公式：,消元过程,对于 k

7、=1,2,n-1 执行,（1）如果,则算法失效，,（2）对于i=k+1,k+2,n,计算,停止计算；否则转（2）;,顺序gauss消去法的计算公式：,回代过程,k=n-1,n-2,1,顺序gauss消去法的计算公式：,消元过程,对于 k=1,2,n-1 执行,（1）如果,则算法失效，,（2）对于i=k+1,k+2,n,计算,停止计算；否则转（2）;,回代过程,k=n-1,n-2,1,顺序gauss消去法的计算量：,消元过程,对于 k=1,2,n-1 执行,（1）如果,则算法失效，,（2）对于i=k+1,k+2,n,计算,停止计算；否则转（2）;,顺序gauss消去法 的计算量,消元过程的计算量

8、,第k步(k=1,2,n-1),需n-k次除法;,需 次乘法;,需 n-k 次乘法,顺序gauss消去法的计算量,消元过程的计算量,第k步(k=1,2,n-1) 计算:,需n-k次除法;,需 次乘法;,需 n-k 次乘法,消元过程中乘除法总次数:,顺序gauss消去法的计算量,消元过程的计算量,第k步(k=1,2,n-1),需n-k次除法;,需 次乘法;,需 n-k 次乘法,消元过程中乘除法总次数:,回代过程的计算量,回代过程的计算量,计算ax=b,顺序gauss消去法的乘除次数,当n=10时,需430次乘除法;,当n=20时,需3060次乘除法;,消元过程中乘除法总次数,顺序gauss消去法

9、能进行到底的条件,(1)主元,证明关键：,(2),顺序gauss消去法的缺点,没有很好的数值稳定性。,当a可逆时，ax=b有唯一解，但顺序gauss消去 法不一定能进行到底。,例：在四位十进制的限制下用 顺序gauss消去法求解方程组,(2)列主元gauss消去 法求解,消元:,回代:,精确解:,(1)利用顺序gauss消去法求解,交换两个方程:,消元,回代,解,(1)消元,(2)回代,精确解：,例1,用顺序gauss消去法求解,用列主元素gauss消去法解例1,消元过程,回代得,精确解：,3、列主元gauss消去法,列主元gauss消去法算法：,记,消元过程,回代过程,列主元素gauss消去法能进行到底的条件,当a可逆时，列主元gauss消去法一定能进行到底。,列主元gauss消去法的优点,具有很好的数值稳定性；,当a可逆时，列主元gauss消去法一定能进行到底。,列主元素gauss消去法能进行到底的条件,当a可逆时，列主元gauss消去法一定能进行到底。,小 结,基本思想：,消元与回代,顺序gauss消去法能进行到底的条件,(1)主元,顺序gauss消去法的缺点,没有很好的数值稳定性。,当a可逆时，ax=b有唯一解，但顺序gauss