当前位置：文档之家 › (数值分析)第五章 解线性方程组的直接法

(数值分析)第五章 解线性方程组的直接法

  • 格式：ppt
  • 大小：1.99 MB
  • 文档页数：83

下载文档原格式

  / 83

合集下载

数值分析--解线性方程组的直接方法

数值分析--解线性方程组的直接方法

值 为A的特征值，x为A对应的特征向量，A的全体特征值
分 析
称为A的谱，计作 ( A),即 ( A) {i ,i 1,2,, n}, 则称
》
( A)
max
1in
|
i
|
为矩阵A的谱 半 径.
三、特殊矩阵
第5章 解线性方程组的直接方法
1) 对角矩阵
2) 三对角矩阵
3) 上三角矩阵
4) 上海森伯(Hessenberg)阵
分 析
1.00x 1.00y 2.00
》 解法1： 1.00105 x 1.00 y 1.00
(1.00 1.00105) y (2.00 1.00105)
1.00105 x 1.00 y 1.00
1.00
105
y
1.00
105
x 0.00,
y 1.00
第5章 解线性方程组的直接方法
1
Ly b y 3,Ux y x 1.
2
1
第5章 解线性方程组的直接方法
§3 高斯主元素消去法
若ak(kk) 0,或ak(kk)很接近于0，会导致其他元素数量级严重 增长和舍入误差的扩散，使得计算结果不可靠.
《例3’采用3位十进制，用消元法求解
数 值
1.00105 x 1.00y 1.00
L21L1 U2U11
L21L1
U
U 1
21
I
(因为上式右边为上三角矩阵，左边为单位下三角矩阵
从而上式两边都必须等于单位矩阵)
《 数
L1 L2 , U1 U2
1 1 1
值分例2
析
.例1中，A
0
4
-1，将A作LU分解。

数值分析知识点总结

数值分析知识点总结

数值分析知识点总结数值分析知识点总结：本文提供了数值分析中的一些重要知识点和例题，但更多的例题可以参考老师布置的作业题和课件相关例题。

第1章数值分析与科学计算引论：绝对误差和相对误差是衡量近似值精度的指标，有效数字则是描述近似值精度的一种方式。

其中，相对误差限是绝对误差的上界。

有效数字的计算方法为：如果近似值x的误差限是某一位的半个单位，该位到x的第一位非零数字共有n位，就说x*共有n位有效数字。

一个比较好用的公式是f(x)的误差限：f(x)f'(x)(x)。

第2章插值法：插值多项式的余项表达式可以用来估计截断误差。

三次样条插值与三次分段埃尔米特插值有所不同，但哪一个更优越需要根据实际情况而定。

确定n+1个节点的三次样条插值函数需要多少个参数？为确定这些参数，需加上什么条件？三弯矩法可以用来求解三次样条表达式。

第3章函数逼近与快速傅里叶变换：带权(x)的正交多项式是在特定区间上满足一定条件的多项式，其中[-1,1]上的勒让德多项式具有重要性质。

切比雪夫多项式也有其独特的性质。

用切比雪夫多项式零点做插值点得到的插值多项式与拉格朗日插值有所不同。

最小二乘拟合的法方程可以用来拟合曲线，但当次数n较大时，不直接求解法方程。

第4章数值积分与数值微分：XXX让德求积公式和XXX-XXX求积公式是数值积分中的两种方法，其中高斯求积公式可以用来计算定积分。

勒让德多项式的零点就是高斯点，这种形式的高斯公式被称为XXX让德求积公式。

中点方法是一种数值积分方法，其公式如下：插值型的求导公式有两点公式和三点公式。

第5章介绍了解线性方程组的直接方法，其中包括LU矩阵的推导过程。

相关例题可以在教材第4章作业题和课件中找到。

第6章介绍了解线性方程组的迭代法，判断迭代法是否收敛的条件如下：第7章介绍了非线性方程与方程组的数值解法，其中牛顿法是一种常见的方法。

对于单根且光滑的f(x)=0，牛顿法是局部二阶收敛的。

简化牛顿法和牛顿下山法都是非线性方程组的求解方法。

数值分析Ch5.1

数值分析Ch5.1

单位向量
k
定义2 u lk 0 0 mk1 mn ，v ek 0 1 0 0 ，
1，称E
(
l
k
,
e
k
,1)
k
I
lk
e
T k
Lk (lk )
指标为k初等下三角阵。
0
1
k
Lk (lk )
I
lk ekT
I
0
mk
1
0
k 1
0
0
1 mk1
1
k行，
mn
mn
1
1
0
1
I ij
。
1
0 Leabharlann 1 2.3 初等反射阵（称为境面反射阵或Householder变换）
1、定义
定义4 设向量 w Rn，且wT w 1（模或范数等于1)， 2，
称矩阵 E(w, w,2) I 2wwT H (w) 为初等反射阵。 2、性质 定理2 设H (w) I 2wwT ,其中wT w 1 ，为初等反射阵，则
（1）H是对称阵，即 H T H;
（2）H是正交阵，即 H 1 H T ;
（3）设A为对称矩阵，那么A1 H 1 AH HAH 亦是对称阵。 证明：（1）H T (I 2ww T )T I 2(wT )T wT I 2wwT H；
（2）H T H HHT H 2 (I 2wwT )( I 2wwT )
1)
||2 ，
于是由定理3
存在H变换：
记
u
x
e1
w (u1 ,
|| u2
x e1 ，使 x e1 ||2
,, un )T，于 是
HxHyI12||2u||u||ue22u1|， T|22

数值分析线性方程组直接法实验

数值分析线性方程组直接法实验

实验报告
一、实验目的
1.了解LU 分解法的优点
二、实验题目
1.给定矩阵A 和向量b:
.1000,123121⎪⎪⎪⎪⎪
⎪⎭
⎫ ⎝⎛=⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--= b n n n n n n A (1)求A 的LU 分解，n 的值自己确定；
(2)利用A 的LU 分解求解下列方程组
(a)b Ax =, (b)b x A =2, (c)b x A =3.
对方程组(c)，若先求3A LU =,再解b x LU =)(有何缺点？
三、实验原理
求解线性方程组的LU 分解法直接解线性方程组.
四、实验内容及结果
2. b Ax =,b x A =2,b x A =3的求解。

3. 若先求3
A LU =,再解b x LU =)(.
五、实验结果分析
LU 分解法的优点：根据题目，如果直接用b x A =3来计算的话，需要先计算3A 的值，然后再计算方程组的值，步骤会多出很多，使得计算更复杂。

如果使用LU 分解法来解方程组的话，只需要对系数矩阵做一次LU 分解，以后只要解三角方程即可，计算的步骤明显减少。

数值分析课件 (第5、6章)

数值分析课件 (第5、6章)

(1 ( La1n) b11) (2) (2) a L 2n b2 = A(3) : b(3) LM M (3) (3) Lamn bn
[
]
( ( ( aij3) = aij2) −mij a22) j (3) ( bi = bi(2) −mi2b22)
(i = 3,L m j = 3,L n) , ; , (i = 3,L m) ,
[
]
( ( ( aij2) = aij1) − mij a11) j (2) bi = bi(1) − mi1b(1) 1
研究生公共课程数学系列
(i = 2,L m j = 2,L n) , ; , (i = 2,L m) ,
机动 上页 下页 首页 结束
(2)
[A
(2)
: b(2)
]
(1 (1 a11) a12) (2 0 a22) = M M (2) 0 am2
(n)
续 述 程 到 成 s 消 计 。 继 上 过 , 直 完 第步 元 算
后 到 原 程 等的 单 程 A 最 得 与 方 组 价 简 方 组 (s+1) x = b,(s+1) 中（ ） 上 形 其 A s+1 为 梯 。
(1 (1 (1 a11) a12) L a1n) (2 ( a22) L a22) n = O M (n ann)
( a2k ) k m = (k ) ik akk
(k (akk ) ≠0)
−−−−−→
(i=k+1,Lm) ,
(1 (1 ( a11) a12) L a11) k (2 ( a22) L a22) k O M (k akk ) M 0

数值分析题库1

数值分析题库1
2010-2011数值分析
第一章 绪论 2 第二章 函数插值 3 第三章 函数逼近 6 第四章 数值积分与数值微分 10 第五章 解线性方程组的直接解法 13 第六章 解线性方程组的迭代解法 14 第七章 非线性方程求根 16 第九章 常微分方程初值问题的数值解法 19
第一章 绪论
1.1 要使的相对误差不超过0.1%，应取几位有效
解 对y=f(x)的反函数进行三次插值，插值多项式为
+ + + =, 于是有
。
第三章 函数逼近
3.1证明定义于内积空间H上的函数是一种范数。
证明： 正定性当且仅当时； 齐次性 设为数域K上任一数 三角不等式 ；
于是有 故是H上的一种范数。
3.2求，在空间上的最佳平方逼近多项式，并给出 误差。
解： 第一步：构造内积空间上的一组正交基，其中内积： 第二步：计算的二次最佳平方逼近多项式 从第一步已经知道，利用公式得： 误差为：
数字？
解：
的首位数字。 设有 n位有效数字，由定理知相对误差限 令， 解得，即需取四位有效数字.
1.2 序列满足关系式，若，计算到，误差有多
大？这个算法稳定吗？
解：，于是 ，一般地，因此计算到其误差限为，可见这个计算过程是不稳定的。
1.3 计算球的体积，要使相对误差限为1%，问测 量半径R时允许的相对误差限是多少？
4.1、计算积分，若用复化梯公式，问区间应分多 少等份才能使截断误差不超过？若改用复化辛普 森公式，要达到同样的精度，区间应分多少等 份？
解：由于，，,故对复化梯公式，要求 ，
即，.取，即将区间分为等份时，用复化梯公式计算，截断误差不超过. 用复化辛普森公式，要求 ，
即，.取，即将区间等分为8等份时，复化辛普森公式可达精度.

数值分析作业答案

数值分析作业答案

第2章 插值法1、当x=1，-1，2时，f(x)=0，-3，4，求f(x)的二次插值多项式。

（1）用单项式基底。

（2）用Lagrange 插值基底。

（3）用Newton 基底。

证明三种方法得到的多项式是相同的。

解：（1）用单项式基底设多项式为:2210)(x a x a a x P ++=，所以：6421111111111222211200-=-==x x x x x x A 37614421111111424113110111)()()(222211200222221112000-=-=---==x x x x x x x x x f x x x f x x x f a 2369421111111441131101111)(1)(1)(12222112002222112001=--=--==x x x x x x x x f x x f x x f a 6565421111111421311011111)(1)(1)(12222112002211002=--=---==x x x x x x x f x x f x x f x a 所以f(x)的二次插值多项式为：2652337)(x x x P ++-= （2）用Lagrange 插值基底)21)(11()2)(1())(())(()(2010210-+-+=----=x x x x x x x x x x x l)21)(11()2)(1())(())(()(2101201------=----=x x x x x x x x x x x l)12)(12()1)(1())(())(()(1202102+-+-=----=x x x x x x x x x x x lLagrange 插值多项式为：372365)1)(1(314)2)(1(61)3(0)()()()()()()(22211002-+=+-⨯+--⨯-+=++=x x x x x x x l x f x l x f x l x f x L所以f(x)的二次插值多项式为：22652337)(x x x L ++-= (3) 用Newton 基底: 均差表如下：Newton 372365)1)(1(65)1(230))(](,,[)](,[)()(21021001002-+=+-+-+=--+-+=x x x x x x x x x x x x f x x x x f x f x N所以f(x)的二次插值多项式为：22652337)(x x x N ++-= 由以上计算可知，三种方法得到的多项式是相同的。

数值分析-线性方程组的直接解法

数值分析-线性方程组的直接解法

算法 Gauss(A,a,b,n,x)
1. 消元 For k=1,2, … , n-1 1.1 if akk=0 , stop; 1.2 For i=k+1,k+2, …, n 1.2.1 l ik=aik /akk => aik 1.2.2 For j=k+1，k+2, … ,n ai j -aik ak j =>aij 1.2.3 bi -aik bk=> bi 2. 回代 2.1 bn / an=>xn; 2.2 For i=n-1,n-2, …, 2,1 2.2.1 bk => S 2.2.2 For j=k+1，k+2, … ,n S –akj xj =>S 2.2.3 S/ akk => xk a1 1 a1 2 a13 a2 1 a2 2 a23
线性方程组的直接解法
刘 斌
线性方程组的直接解法
§1 Gauss消去法 1.1 顺序Gauss消去法
1.2
§2 2.1 2.2 2.3
列主元Gauss消去法
Gauss消去法的矩阵运算 Doolittle分解法 平方根法
直接三角分解方法
2.4
追赶法
引入
在科学计算中，经常需要求解含有n个未知量 的n个方程构成的线性方程组 a11 x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2 n xn b2 (1) an1 x1 an 2 x2 ann xn bn
(1) a12 ( 2) a22 0
(1) (1) a13 a1 n ( 2) ( 2) a23 a2 n ( 3) ( 3) a33 a3 n
0

数值分析小论文线性方程组的直接解法

数值分析小论文线性方程组的直接解法

数值分析小论文线性方程组的直接解法线性方程组的直接解法是指通过一系列的代数运算直接求解线性方程组的解。

线性方程组是数值分析中非常重要的问题，广泛应用于工程、科学、计算机图形学等领域。

在线性方程组的直接解法中，最常用的方法是高斯消元法，它是一种基于矩阵变换的方法。

高斯消元法将线性方程组表示为增广矩阵，并通过一系列的行变换将增广矩阵转化为行阶梯形矩阵，从而得到方程组的解。

高斯消元法的主要步骤包括消元、回代和得到方程组的解。

消元是高斯消元法的第一步，通过一系列的行变换将增广矩阵的元素转化为上三角形式。

在消元过程中，我们首先找到主元素，即矩阵的对角线元素，然后将其它行的元素通过消元操作转化为0，从而使得矩阵逐步变成上三角形矩阵。

回代是高斯消元法的第二步，通过一系列的回代操作求解线性方程组。

回代操作是从上三角形矩阵的最后一行开始，通过依次求解每个未知数的值，最终得到方程组的解。

高斯消元法的优点是算法简单易于实现，可以在有限的步骤内求解线性方程组，适用于一般的线性方程组问题。

但是高斯消元法也存在一些问题，例如当矩阵的主元素为0时，无法进行消元操作，此时需要通过行交换操作来避免这种情况。

另外，高斯消元法对病态矩阵的求解效果较差，容易引起舍入误差累积，导致解的精度下降。

在实际应用中，为了提高求解线性方程组的效率和精度，人们常常使用一些改进的直接解法，例如列主元高斯消元法和LU分解法。

列主元高斯消元法通过选择最大主元来避免主元为0的情况，进一步提高了求解线性方程组的精度。

LU分解法将矩阵表示为两个矩阵的乘积，从而将线性方程组的求解问题转化为两个三角形矩阵的求解问题，提高了求解效率。

综上所述，线性方程组的直接解法是一种基于矩阵变换的方法，通过一系列的代数运算求解线性方程组的解。

高斯消元法是最常用的直接解法之一，它简单易于实现，适用于一般的线性方程组问题。

在实际应用中，可以通过改进的直接解法来进一步提高求解效率和精度。

数值分析线性方程组的直接解法

数值分析线性方程组的直接解法

数值分析课程实验报告实验名称线性方程组的直接解法_____________________实验目的①掌握高斯消去法的基本思路和迭代步骤；②了解高斯消去法可能遇到的困难。

用文字或图表记录实验过程和结果列主元高斯消去法算法描述将方程组用增广矩阵B=[A：b]=（a j \心申）表示。

步骤1:消兀过程，对k=12|j|, n—1（1）选主元，找i k亡｛k,k+1,川,n｝使得k卜maxi a ikai k，（2）如果a i k,k = 0 ,则矩阵A奇异，程序结束；否则执行（3）。

（3）如果ik^k,则交换第k行与第i k行对应兀素位置，aq㈠a i k j,j=k,IH, n + 1。

（4）消兀，对i = k +1」H,n，计算m k=a k / a kk,对j = k +1,川,n +1，计算a j = a ij — m ik a^.步骤2:回代过程：（1）右a nn -0,则矩阵奇异，程序结束；否则执行（2）。

厲（2）nX n =a ng/a nn；对i = n—1川,2,1，计算X j = a,n 出一》a j X j /a H< j4 丿三、练习与思考题分析解答1、解方程组0.10伙2.304X2 3.555X3 =1.183-1.347为3.712X2 4.623X3 = 2.137-2.835X, 1.072X25.643X^3.035（1）编程用顺序高斯消去法求解上述方程组，记下解向量，验证所得到的解向量是否是原方程组的解，若不是原方程组的解，试分析原因，并证实你的分析的正确性!解：采用顺序消元法求得如下结果：请输入一个3行矩阵0.101 2.304 3.555 1.183-1.347 3.712 4.623 2.137-2.835 1.072 5.643 3.0350.101 2.304 3.555 1.1830 34.4396 52.0347 17.91420 0 6.09738 2.0435最后计算得到x =(-0.3982,0.0138,0.3351) T，代入原方程验证可知解向量是原方程组的解。

(完整版)数值分析课后习题答案

(完整版)数值分析课后习题答案

第一章绪论习题一1.设x>0,x*的相对误差为δ，求f(x)=ln x的误差限。

解：求lnx的误差极限就是求f(x)=lnx的误差限，由公式(1.2.4)有已知x*的相对误差满足，而，故即2.下列各数都是经过四舍五入得到的近似值，试指出它们有几位有效数字，并给出其误差限与相对误差限。

解：直接根据定义和式(1.2.2)(1.2.3)则得有5位有效数字，其误差限，相对误差限有2位有效数字，有5位有效数字，3.下列公式如何才比较准确？（1）（2）解：要使计算较准确，主要是避免两相近数相减，故应变换所给公式。

（1）（2）4.近似数x*=0.0310,是 3 位有数数字。

5.计算取，利用：式计算误差最小。

四个选项：第二、三章插值与函数逼近习题二、三1. 给定的数值表用线性插值与二次插值计算ln0.54的近似值并估计误差限. 解：仍可使用n=1及n=2的Lagrange插值或Newton插值,并应用误差估计（5.8）。

线性插值时，用0.5及0.6两点，用Newton插值误差限，因，故二次插值时，用0.5，0.6，0.7三点，作二次Newton插值误差限，故2. 在-4≤x≤4上给出的等距节点函数表，若用二次插值法求的近似值，要使误差不超过，函数表的步长h 应取多少?解：用误差估计式（5.8），令因得3. 若，求和.解：由均差与导数关系于是4. 若互异，求的值，这里p≤n+1.解：，由均差对称性可知当有而当P＝n＋1时于是得5. 求证.解：解：只要按差分定义直接展开得6. 已知的函数表求出三次Newton均差插值多项式，计算f(0.23)的近似值并用均差的余项表达式估计误差.解：根据给定函数表构造均差表由式(5.14)当n=3时得Newton均差插值多项式N3(x)=1.0067x+0.08367x(x-0.2)+0.17400x(x-0.2)(x-0.3) 由此可得f(0.23) N3(0.23)=0.23203由余项表达式(5.15)可得由于7. 给定f(x)=cosx的函数表用Newton等距插值公式计算cos 0.048及cos 0.566的近似值并估计误差解：先构造差分表计算，用n=4得Newton前插公式误差估计由公式（5.17）得其中计算时用Newton后插公式（5.18)误差估计由公式（5.19）得这里仍为0.5658．求一个次数不高于四次的多项式p(x),使它满足解：这种题目可以有很多方法去做，但应以简单为宜。

数值分析52(高斯消去法)

数值分析52(高斯消去法)

二、矩阵的三角分解
由矩阵理论可知，对系数矩阵 A 实施行的初
等变换相当于用初等矩阵左乘 A ，即
A 行初等变换
A'
等价于
A'LA
E 其中
行初等变换
初等 矩阵
L
例
1 1 1
A 0 4 1 2 2 1
①*(-2)+③
则 A'LA
E 其中
①*(-2)+③
1 0 0
L
0
1 0
2 0 1
1 1 1 A' 0 4 1
高斯消去法的特点：消元和回代不同步！
3. 使用高斯消去法的条件
使用高斯消去法要求在每步消元时 ak(kk) 0 ， 那么矩阵A满足什么，才能保证这一条件呢？
引理：约化的主元素 ak(kk) 0 (i=1,2,…,n) 的充 要条件是矩阵A的顺序主子式 D i 0(i1,2,..n.),
推论：如果A的顺序主子式不等于0，则
aa1k((1k1k))
D1 Dk
Dk1
(k=2,3,…,n)
定理：如果 n 阶矩阵A的所有顺序主子式均 不为零，则可通过高斯消去法（不进行交 换两行的初等变换），将方程组约化为三 角形方程组。
定理：如果A为 n 阶非奇异矩阵，则可通过 高斯消去法（及交换两行的初等变换）将方 程组 Ax=b 化为三角形方程组。
第五章 解线性方程组的直接法 §2 高斯消去法
一、高斯消去法 二、矩阵的三角分解 三、高斯消去法的计算量 四、高斯—约当消去法
一、高斯消去法
1. 高斯消去法的基本思想
举例 用消去法解方程组
基原本来思方想程4x：1x组2用AxX逐2x=3次b化x消53为去与6未其知等数价的的方三法角把 形方程组2，x1而 求2x解2 三x角3形方1 程组就容易

数值计算方法-第5章_解线性方程组的直接法

数值计算方法-第5章_解线性方程组的直接法
①直接法：准确，可靠，理论上得到的解是精确的 ②迭代法：速度快，但有误差
本章讲解直接法
5.1 消元法
我们知道，下面有3种方程的解我们可以直接求出：
①
n次运算
A
diag(a11, a22 ,
, ann )
xi
bi aii
,i
1,
,n
②
（n＋1）n/2次运算
l11
A
l21 ln1
l22 ln2
(aik
k 1
liklkr ) r 1 lkk
,i k 1, , n
因此不常用
又 l11
1
l11
l21 l22
ln1
ln2
lnn
l '21 l 'n1
1 l'n2
1
l22
lnn
则有
A L~D~D~T L~T LDLT
L~
D~
1
L
l21 ln1
lnn
xi
bi
i 1
lij x j
j 1
lii
,i
1,
,n
③
（n＋1）n/2次运算
u11
A
u12 u22
u1n
u2n unn
xi
bi
n
uij x j
j i 1
uii
,i
n,
,1
对方程组，作如下的变换，解不变 ①交换两个方程的次序 ②一个方程的两边同时乘以一个非0的数 ③一个方程的两边同时乘以一个非0数，加到另一个方程
1 ln2
1
d1
D
d2
dn
a11 a12
a21 a22

数值分析第五章解线性方程组的直接法

数值分析第五章解线性方程组的直接法

数值分析第五章解线性方程组的直接法解线性方程组是数值分析中的一个重要问题，对于大规模的线性方程组来说，直接法是一种常用的求解方法。

本文将介绍解线性方程组的直接法，包括高斯消元法和LU分解法，并对其稳定性和计算复杂度进行讨论。

高斯消元法是一种常用的直接法，用于求解非奇异线性方程组。

其基本思想是通过初等行变换将线性方程组转化为上三角方程组，然后通过回代求解得到方程的解。

高斯消元法的步骤如下：1.将线性方程组表示为增广矩阵[A，b]，其中A是系数矩阵，b是常数向量。

2.从第一行开始，选择一个非零元素作为主元，通过行变换将主元下方的元素全部消为零。

3.重复第2步，直到矩阵变为上三角矩阵。

4.通过回代求解上三角矩阵，得到方程组的解。

高斯消元法的主要优点是简单直接，容易实现，但存在一些问题。

首先，如果系数矩阵A是奇异矩阵，即行列式为零，那么高斯消元法无法得到方程组的解。

其次，如果系数矩阵A的其中一行或几行接近于线性相关，那么在消元过程中会引入大量的舍入误差，导致计算结果不准确。

这也说明了高斯消元法的稳定性较差。

为了提高稳定性，可以使用LU分解法来解线性方程组。

LU分解法将系数矩阵A分解为两个矩阵L和U的乘积，其中L是下三角矩阵，U是上三角矩阵。

这样，原始的线性方程组可以表示为LUx=b，进而可以通过两个步骤来求解方程组：1.进行LU分解，将系数矩阵A分解为L和U。

2.分别用前代和回代的方法求解方程组Ly=b和Ux=y。

LU分解法相对于高斯消元法的优点是，可以在求解多个右端向量时，避免重复计算LU分解，从而提高计算效率。

同时，LU分解法的稳定性也较高，对于多个右端向量求解时，舍入误差的累积相对较小。

然而，LU分解法也存在一些问题。

首先，LU分解法的计算复杂度较高，需要进行两次矩阵乘法和一次矩阵向量乘法，而且LU分解过程中需要对系数矩阵A进行大量的行变换，增加了计算量。

其次，当系数矩阵A的一些元素非常小或非常大时，LU分解法容易出现数值不稳定的情况，即舍入误差的累积较大，导致计算结果不准确。

第5章 解线性方程组的直接方法

第5章 解线性方程组的直接方法

第5章
解线性方程组的直接方法
定理3 若A∈Rnⅹn 为对称矩阵.如果det(Ak) ＞0(k=1,2,…,n),
或A得特征值λi＞0（i=1,2, …,n ）.则A为对称正定矩阵。
《 数 值 分 析 》
有重特征值的矩阵不一定相似于对角矩阵，那么一般n阶 矩阵A在相似变换下能简化到什么形状？
定理4(若尔当（Jordan）标准型） 设A为n阶矩阵，则 存在一个非奇异矩阵P使得
a1(1) x1 b1(1) n ( 2) ( 2) a2 n x2 b2 ( k ) . (2.8) (k ) akn xk bk (k ) (k ) ann xn bn
（2.12 ）
(2.7)
简记为
A（2）X=b（2） ，
( ( ( aij2) aij1) mi1 a11) , j
其中A（2），b（2）的元素计算公式为
(i, j 2,3,, n),
bi( 2) bi(1) mi1 b1(1) , (i 2,3,, n).
第k步：若
(k akk ) 0,
a11 ... ... Ak ak1 ... ... , akk
《 数 值 分 析 》
a
1k
k 1,2, n.
（3）A的特征值λi＞0（i=1,2, …,n ）. （4）A的顺序主子式都大于零，即det(Ak) ＞0(k=1,2,…,n)
(1)）=(a
), b(1)=b. ij
第5章 解线性方程组的直接方法 （1）消元过程 1 (1 第1步：设 a (1) 0,首先计算乘数 mi1 ai(1 ) / a11) , i 2,3n, 11 用－mi1乘（2.1）的第1个方程组，加到第i个中，消去方程组（2.1）的从 第2个方程到第n个方程中的未知数X1，得到与方程组（2.1）等价的线性方 程组 《 数 值 分 析 》

数值分析实验报告

数值分析实验报告

实验五 解线性方程组的直接方法实验5.1 （主元的选取与算法的稳定性） 问题提出：Gauss 消去法是我们在线性代数中已经熟悉的。

但由于计算机的数值运算是在一个有限的浮点数集合上进行的，如何才能确保Gauss 消去法作为数值算法的稳定性呢？Gauss 消去法从理论算法到数值算法，其关键是主元的选择。

主元的选择从数学理论上看起来平凡，它却是数值分析中十分典型的问题。

实验内容：考虑线性方程组n n n R b R A b Ax ∈∈=⨯,,编制一个能自动选取主元，又能手动选取主元的求解线性方程组的Gauss 消去过程。

实验要求：（1）取矩阵⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=1415157,6816816816 b A ，则方程有解T x )1,,1,1(* =。

取n=10计算矩阵的条件数。

让程序自动选取主元，结果如何？（2）现选择程序中手动选取主元的功能。

每步消去过程总选取按模最小或按模尽可能小的元素作为主元，观察并记录计算结果。

若每步消去过程总选取按模最大的元素作为主元，结果又如何？分析实验的结果。

（3）取矩阵阶数n=20或者更大，重复上述实验过程，观察记录并分析不同的问题及消去过程中选择不同的主元时计算结果的差异，说明主元素的选取在消去过程中的作用。

（4）选取其他你感兴趣的问题或者随机生成矩阵，计算其条件数。

重复上述实验，观察记录并分析实验结果。

思考题一：（Vadermonde 矩阵）设⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=∑∑∑∑====n i i n n i i ni i n i i n n n n n n nx x x x b x x x x x x x x x x x x A 002010022222121102001111 ，， 其中，n k k x k ,,1,0,1.01 =+=，（1）对n=2,5,8，计算A 的条件数；随n 增大，矩阵性态如何变化？（2）对n=5，解方程组Ax=b ；设A 的最后一个元素有扰动10-4，再求解Ax=b（3）计算（2）扰动相对误差与解的相对偏差，分析它们与条件数的关系。

数值分析5-2(高斯消去法)

数值分析5-2(高斯消去法)

M M ... (3) xn bn (3) ann
…
( 1 0 ... 0 x1 b1n) 0 1 ... 0 x b(n) • 2 = 2 O M M 0 0 ... 1 x (n) n bn
高斯-约当消去法的应用 高斯 约当消去法的应用
1.同时求解系数矩阵相同的多个方程组 同时求解系数矩阵相同的多个方程组 用高斯-约当消去法求解两个方程 例 用高斯 约当消去法求解两个方程 组 AX=b1 和AX=b2 ，其中
3 4 6 2 4 5 A= 1 2 3
3 b1 = 4 1
(1 a11) ≠ 0
第一次 消元
(2 a22) ≠ 0
(2 (2 ( 1 a12) ... a1n) x1 b12) b(2) (2) (2) 0 a22 ... a2n x2 2 • = ... M M (2) (2) (2) 0 an2 ... ann xn bn
1 1 1 A = 0 4 − 1 2 − 2 1 1 0 0 1 1 1 ∆ = 0 1 0 • 0 4 − 1 = LU ห้องสมุดไป่ตู้ 2 − 1 1 0 0 − 2
则求解原方程组可转化为如下两个三角形方 程组： 程组：
第五章 解线性方程组的直接法 §2 高斯消去法
一、高斯消去法 二、矩阵的三角分解 三、高斯消去法的计算量 四、高斯—约当消去法 高斯 约当消去法
一、高斯消去法
1. 高斯消去法的基本思想 举例 用消去法解方程组
基本思想：用逐次消去未知数的方法把 x1 + x2 + x3 = 6
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
3 2
2
11 .
10 5 10
0
1 9
7 9
2 3
华长生制作
8
第二步消元，令 l32 10 / 63, 得增广矩阵
1 0
2
3 7
1
3 2
2
11
.
10 5 10
0
0
53 53 63 63
利用回代公式依次得到
x3 1, x2 1, x1 1.
在这个例子中我们写出的是分数运算的结果。如果在计算机上
a(1) 13
x3
0.49105820
事实上,方程组的准确解为
x* (0.491058227,0.050886075,0.367257384)T
华长生制作
15
例2所用的方法是在Gauss消去法的基础上,利用换行 避免小主元作除数,该方法称为Gauss列主元消去法
列主元素消去法也称按列部分主元的消去法。一般地，在完成 了第k-1步消元运算后，在 ( A(k) , b(k) ) 的第k 列元素 akk(k)之下的所有 元素中选一个绝对值最大的元素作为主元素，即若
的列元素为a13 2, 因此1,3行交换
华长生制作
13
r1 r3
2 1
108
1.072 3.712
2
5.643 3 4.623 2
3 1
( A(1) , b(1) )
绝对值最大 不需换行
m21 0.5
m31 0.5108
2 0
0
m32 0.629 72292
1.072 0.3176 10
2 3.712 1.072
3 4.623 5.643
x1 x2 x3
1 2 3
解: 这个方程组和例1一样,若用Gauss消去法计算会有 小数作除数的现象,若采用换行的技巧,则可避免
108
A ( A,b) 1
2
2 3.712 1.072
3 1
4.623 2
5.643
3
108 很小, 绝对值最大
则将 ( A(k) , b(k) ) 的第 ik 行与第k行交换，然后进行消元运算。
华长生制作
16
完成了n-1步主元，换行与消元运算后，得到 A(n) x b(n)，这是
与原方程组等价的方程组, A(n)是一个上三角阵,再代回求解.这就是列
主元素消去法的计算过程.
除了列主元素消去法外,还有一种完全主元素消去法.在其过程的第k
进行计算，系数矩阵和中间结果都用经过舍入的机器数表示，中间
结果和方程组的解都会有误差。
华长生制作
9
Gauss列主元消去法的引入
例1. 用Gauss消去法解线性方程组(用3位十进制浮 点数计算）
0.0001x1 x1
x2 x2
1 2
解: 本方程组的精度较高的解为
x* (0.99989999,1.00010001)T
xn
a (n) n,n1
/ ann(n) ,
n
a (n) n,n1
x
j
)
/aii ( i )
,
i
n
1,
n
2,L
,1.
jk 1
求解上式的过程称为回代过程。
以上由消去过程和回代过程合起来求解方程组的过程就称为
Gauss消去法，或称为顺序Gauss消去法。
华长生制作
6
由前面可知,消元过程的第k步需出发运算n-k次，乘法和减法运算各 需（n-k）（n+1-k）次，所以消元过程共需乘除法运算的次数为
中,含 x1 的项已经消去.
第k步消元:设消去法已进行k-1步,得到方程组 A(k) x b(k) ,此时对
应的增广矩阵是
华长生制作
4
a11(1)
( A(k) , b(k) )
假设
a(k) kk
0令,
a (1) 12
a (2) 22
a (k) kk
a (n) nk
a (1) 1n
a (2) 2n
)
a11(1)
a (1) 12
a (2) 22
a (1) 1n
a (2) 2n
a (1) 1,n1
a (2) 2,n1
.
a (n) nn
a( n,n1
n
)
这就完成了消元过程。 因为A非奇异，所以可求解上三角方程组，通过逐次代入计算
可得方程组的解，其计算公式为
xi
(a (i) i , n 1
14
经过回代后可得
x3
b3( 3 ) a(3)
0.685 138 54
0.186 555 41 10
0.367 257 39
33
x2
b2(2) a2(23) x3 a(2)
22
0.5 0.18015 10 x3 0.3176 10
0.05088607
x1
b1(1)
a(1) 12
x2
a(1) 11
a (1) 1,n1
a (2) 2,n1
a (k) (k) nn
a( n,n1
k
)
lik
a (k) ik
a (k) kk
, aij (k 1)
a (k) ij
lik akj (k )
i k 1, k 2, n; j k 1, k 2, , n 1,
将 ( Ak , bk )变换为 ( Ak1 , bk1 ) ，( Ak1 , bk1 ) 中第1至第k行的元素
a (k) ik ,k
max
kin
aik
(
k
)
,
行变换相 当于左乘 初等矩阵
则以
a (k) kk
为主元素，这里
ik
k
,且
A(k )由于非奇异，
有
a (k) kk
0
.这样，lik
a (k) ik
/ a (k) ik ,k
1 有达到控制舍入误差的作
用。
选出主元素后，若则进行顺序Gauss消去法的第k步若 ik k ，
华长生制作
11
如果在求解时将1,2行交换,即
A ( A,b) 0.0010100
1 1
21
m210.0001
1 0
1 1.00
1.200
0.9999
回代后得到
x1 1.00 , x2 1.00
这是一个相当不错的结果
华长生制作
12
例2. 解线性方程组(用8位十进制尾数的浮点数计算)
108 1 2
去法完成后,再按记录恢复自变量为自然次序.完全主元法比列主元法
运算量大得多,由于列主元法的舍如误差一般已较小,所以在实际计 算中多用列主元法.
华长生制作
17
例3 用列主元素消去法解方程组Ax=b,计算过程中五位有效 数字进行运算,其中
0.002 2 2 0.4
(
A,
b)
1
0.78125 0 1.3816.
x (1.92730 ,0.698496 ,0.900423 )T ,
而用不选住主元的顺序Gauss消去法，则解得 x (1.9300 ,0.68695 ,0.88888 )T ,
这个结果误差较大，这是因为消去法的第1步中，a11(1) 按绝对值比 其他元素小很多所引起的。从此例看到列主元素消去法是有效 的方法。
将 ( A(1) , b(1) ) 变换为
a (1) 11
( A(2)
, b(2)
)
a (1) 12
a (2) 22
M
L L L
a (2) n2
L
a (1) 1n
a (2) 2n M
a (2) nn
a (1) 1,n1
a (2) 2,n1
M
a (2) n,n1
它对应的方程组 A(2) x b(2) 与原方程组等价,而在第2至第n个方程
a11 x1 a12 x2 a1n xn b1a1,n1
a21
x1
a22 x2
a2n xn
b2 a 2,n1
an1 x1 an2 x2 ann xn bn an,n1
设方程组的系数矩阵A非起奇异,记
a (1) ij
aij
(i 1,2, , n; j 1,2, , n)
( A(1) , b(1) ) ( A, b)
第二步选列主元为 算得
a (2) 32
2.0028
,交换第2行与第3行，再消元计
华长生制作
18
3.996
(
A( 3 )
, b(3)
)
0
0
5.5625 2.0028
0
4 2.0020 0.39047
7.4178 0.40371 . 0.35159
消去过程至此结束。回代计算依次得到解
x3 0.90043 , x2 0.69850 , x1 1.9273 这个例题的精确解是
用Gauss消去法求解(用3位十进制浮点数计算)
华长生制作
10
主元
A ( A,b) 0.0010100
1 1
1 2
9999
m2110 000
0.000100 0
1
1
1.00 104 1.00 104
回代后得到
x1 0.00 , x2 1.00
与精确解相比,该结果相当糟糕
究其原因,在求行乘数时用了很小的数0.0001作除数
n1
n1
n3 n2 5n
(n k) (n k)(n 1 k)
k 1
k 1
326
需加减法运算的次数