数值分析5-2(高斯消去法)
- 格式：ppt
- 大小：2.08 MB
- 文档页数：10
下载文档原格式
合集下载
数值分析Gauss消去法课件
高斯消元法的代码实现
初始化矩阵
将系数矩阵A进行初始化，并存储在二维数 组中。
消元过程
通过一系列行变换，将系数矩阵变为上三角 矩阵。
主元选择
选择主元，即系数矩阵中所在行和列的最大 元素。
回带求解
利用上三角矩阵的元素，求解线性方程组的 解。
选主元的优化策略
1 2
自然主元
选择系数矩阵中绝对值最大的元素作为主元。
病态问题
对于一些病态问题，高斯 消元法可能无法得到准确 解，需要采用其他方法进 行求解。
01
Gauss消去法的应 用实例
应用领域与案例介绍
线性方程组求解
01
Gauss消去法是求解线性方程组的一种常用方法，适用于大ห้องสมุดไป่ตู้模
、稀疏矩阵的求解。
矩阵求逆
02
通过Gauss消去法可以计算矩阵的逆，这在许多科学计算和工程
最小二乘主元
选择使所在行和列的绝对值之和最小的元素作为 主元。
3
随机主元
随机选择一个元素作为主元，可以避免某些数值 问题。
数值稳定性与误差控制
01
02
03
数值稳定性
高斯消元法在某些情况下 可能产生数值不稳定性， 如主元接近零或数值误差 累积。
误差控制
在消元过程中，可以通过 一些技巧来控制误差，如 预处理、选主元策略和舍 入误差控制。
领域中都有应用。
特征值和特征向量计算
03
Gauss消去法可以用于计算矩阵的特征值和特征向量，这在物理
、工程和经济学等领域有广泛的应用。
实际应用中的问题与挑战
数值稳定性
Gauss消去法在处理病态问题或 接近奇异矩阵时可能会出现数值 不稳定性，导致计算结果误差较 大。
数值线性代数课程设计高斯消去法
数值线性代数课程设计⾼斯消去法数值线性代数课程设计线性⽅程组的直接解法数理学院 09405011班 0940501120 沈骁摘要：如何利⽤电⼦计算机来快速、有效的求解线性⽅程组的问题是数值线性代数的核⼼问题。
本⽂将主要介绍解线性⽅程组的基本的直接法——⾼斯消去法，平⽅根法，并⽤实例来验证此⽅法的有效性。
关键字：⾼斯消去法，顺序消去法，选主元消去法，平⽅根法，消元过程，回代过程,主元数和乘数引⾔：因为各种各样的科学与⼯程问题往往最终都要归结为⼀个线性⽅程组的求解问题。
本⽂在⽐较着⼏个⽅法的基础上，通过⼀道实例来得到最⽅便最有效的⽅法。
基本原理：⼯程计算和科学研究中的许多问题，最终归结为线性代数⽅程组的求解。
求解的⽅法也有很多，如⾼斯消去法（顺序消去法，选主元消去法），平⽅根法。
⾼斯消去法是⽬前求解中⼩规模线性⽅程组最常⽤的⽅法；平⽅根法是求解对称正定线性⽅程组最常⽤的⽅法之⼀。
为了更快速、更⽅便的求解线性⽅程组，下⾯我们⽐较⼀下这⼏种⽅法哪种更好。
⼀、⾼斯（Causs ）消去法就是逐步消去变元的系数，将原⽅程组Ax b =化为系数矩阵为三⾓形的等价⽅程组Ux d =，然后求解系数矩阵为三⾓形的⽅程组⽽得出原⽅程组解的⽅法。
把逐步消元去变元的系数，将⽅程组化为以系数矩阵为三⾓形的等价⽅程组的过程称为⼩院过程；把求系数矩阵为三⾓形的⽅程组解的过程称为回代过程。
最初求解⽅程组的⾼斯消去法也称为顺序消去法，它由消元过程和回代过程组成。
顺序消去法 1．消元过程考虑⼀般⽅程组，为了推导过程⽅便，记系数矩阵A 的元素ij a 为(0)ij a ，右端向量b 的元素i b 记为(0),1i n a +，于是⽅程组11112211211222221122n n n n n n nn n na x a x a xb a x a x a x b a x a x a x b +++=??+++=+++=（1.1）成为()()()()()()()()()()()()00011112211100021122222100011221n n n n n n n n nn n nn a x a x a x a a x a x a x a a x a x a x a +++?+++=?+++=+++=假设(0)110a ≠，将第1个⽅程乘以(0)1(0)11()i a a -加到第i 个⽅程(2)i n ≤≤,得到第1个导出⽅程组(0)(0)(0)(0)111122111(1)(1)(1)222221(1)(1)(1)221n n n n n n n nn n nn a x a x a x a a x a x a a x a x a +++?++=?+=??+=其中：(0)(1)(0)(0)11(0)11i ij ij j a a a a a =-，2i n ≤≤，21j n ≤≤+。
高斯消去法
2011-1-1
数值分析
例1 用消去法求解方程组 1 1 1 4 -1 2 -2 1 6 5 1
x1 + x2 + x3 = 6 4 x2 − x3 = 5 2 x − 2 x + x = 1 2 3 1
1 1 1 6 4 -1 5 0 -4 -1 -11 1 1 4 0 0 1 6 -1 5 -2 -6
xk = (bk( k ) −
∑+1 j =k
n
( ( akkj) x j ) / akkk) ,(k = n − 1, n − 2,L,1)
(2)如果系数矩阵 为非奇异矩阵则可通过高斯消去法与初等行 如果系数矩阵A为非奇异矩阵则可通过高斯消去法与初等行 如果系数矩阵 变换方法，将方程组约化为三角形方程组。 变换方法，将方程组约化为三角形方程组。
还原为方程组
x1 + x2 + x3 = 6 4 x2 − x3 = 5 − 2 x3 = −6
（消元过程） 消元过程）
x3=3， x2=2， x1=1 ， ，
2011-1-1 数值分析
（回代过程） 回代过程）
一般线性方程组的高斯消去法
设有方程组
a11 x1 + a12 x2 + L + a1n xn = b1 , a21 x1 + a22 x2 + L + a2 n xn = b2 , LLLLLLLLLLLL a x + a x + L + a x = b , m2 2 mn n m m1 1
( (k (k akk ) ≠ 0 计算乘数 mik = aikk ) ,L , m)
乘上面的线性方程组的第k个方程加到第 个方程， 个方程加到第i个方程 用-mik乘上面的线性方程组的第 个方程加到第 个方程，可 以消去x 以消去 k元,得到同解方程组 A ( k +1) x = b ( k +1) 得到同解方程组 ( 其中 ai(k+1) = ai(k) −m kakkj) (i = k +1,L, m, j = k +1,Ln). j j i
高斯消去法的计算步骤
机械与建筑结构的设计计算问题等等，都归结为
求解线性方程组或非线性方程组的数学问题。因 此线性方程组的求解对于实际问题是极其重要的。
引例: 设有电源及一些电阻组成的简单电路，求各环 路电流。 E2 R
解: 设I1 ,I2 , I3为图示的 E1 环路电流, 对每一个环 F 路,利用克 希霍夫定律 H 在任何一个
akk
(1) a11
a a
(1) 12 ( 2) 22
a a
(k ) kk
(k ) nk
(1) x a 1 b1 ( 2) a x 2 b2 (k ) (k ) a kn x k bk k (k ) a nn xn bn (1) 1n ( 2) 2n
3.2.2 高斯消去法算法构造 我们知道,线性方程组(3.1)用矩阵形式表示为
a11 a 21 a n1 a12 a 22 an2 a1n a2n a nn x1 b1 x b 2 2 x n bn
2 ~ A A b 4 1 1 2 2 3 5 0
1 2 r ( 2 ) r 4 0 1 r ( ) r 2 7 0
2 1 3 1
i 行）
1 2 13 2
1 3 4 1 5 3 2 2
⑴ 消元过程,高斯消去法的消元过程由n-1步组成：
(1) 第1步 设 a11 0 ,把(3.3)中的第一列中元素 (1) a (1) (1) (1) i1 消为零 , 令 m , (i 2,3,, n) a21 , a31 ,, an i 1 1 (1)
数值分析高斯顺序消去法、列主元消去法LU分解法
数值分析实验报告（1）学院：信息学院班级：计算机0903班姓名：***学号：********课题一A.问题提出给定下列几个不同类型的线性方程组，请用适当的方法求解线性方程组1、设线性方程组⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡--------------------------1368243810041202913726422123417911101610352431205362177586832337616244911315120130123122400105635680000121324⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡10987654321x x x x x x x x x x =⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡-2119381346323125 x *= ( 1, -1, 0, 1, 2, 0, 3, 1, -1, 2 )T2、设对称正定阵系数阵线方程组⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡----------------------19243360021411035204111443343104221812334161206538114140231212200420424⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡87654321x x x x x x x x = ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡---4515229232060 x * = ( 1, -1, 0, 2, 1, -1, 0, 2 )T3、三对角形线性方程组⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡------------------4100000000141000000001410000000014100000000141000000001410000000014100000000141000000001410000000014⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡10987654321x x x x x x x x x x = ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡----5541412621357 x *= ( 2, 1, -3, 0, 1, -2, 3, 0, 1, -1 )TB.（1）对上述三个方程组分别用Gauss 顺序消去法与Gauss 列主元消去法；平方根 与改进平方根法；追赶法求解（选择其一） （2）编写算法通用程序（3）在应用Gauss 消去时，尽可能利用相应程序输出系数矩阵的三角分解式C.(1)通过该课题的程序编制，掌握模块化结构程序设计方法 (2)掌握求解各类线性方程组的直接方法，了解各种方法的特点 (3)体会高斯消去法选主元的必要性 实验步骤：（高斯消去法，列主元，LU ）1顺序高斯消去法2.LU 分解法3.列主元高斯消去法（如下图）（1）高斯消去法运行结果如下（2）对方程的系数矩阵进行LU分解并求出方程组的解（3）列主元高斯消去法实验体会总结：利用gauss消去法解线性方程组的时候，如果没有经过选主元，可能会出现数值不稳定的现象，使得方程组的解偏离精确解。
实验五 高斯消去法
实验五 高斯消去法1 实验目的(1)熟悉求解线性方程组的有关理论和方法； (2)能编程实现雅可比及高斯-塞德尔迭代法、列主元高斯消去法、约当消去，追赶法 (3)通过测试，进一步了解各种方法的优缺点 (4) 根据不同类型的方程组，选择合适的数值方法2 实验内容用高斯消去法求解方程组⎪⎩⎪⎨⎧=+--=-+-=--2.453.82102.7210321321321x x x x x x x x x输入：系数矩阵A ，最大迭代次数N ，初始向量，误差限e输出：解向量3 算法基本原理无论是三次样条还是拟合问题最终都归结为线性方程组，求解线性方程组在数值分析中非常重要，在工程计算中也不容忽视。
线性方程组大致分迭代法和直接法。
只有收敛条件满足时，才可以进行迭代。
雅可比及高斯-塞德尔是最基本的两类迭代方法，最大区别是迭代过程中是否引用新值进行剩下的计算。
消元是最简单的直接法，并且也十分有效的，列主元高斯消去法对求解一般的线性方程组都适用，同时可以用来求矩阵对应的行列式。
约当消去实质是经过初等行变换将系数矩阵化为单位阵，主要用来求矩阵的逆。
在使用直接法，要注意从空间、时间两方面对算法进行优化。
列主元高斯消去法：列主元;0||max ||≠=≤≤ik ni k lk a a 消元)...,,1,()()()1()()()1(n k j i bm b b a m a a k k ik k i k i k kj ik k ij k ij +=⎩⎨⎧-=-=++ 回代)1...,,()(1)()(n i a x a b x i ii n i j j i ij i ii =-=∑+=4计算用例的参考输出。
数值分析实验报告(包括高斯消去、二分法、牛顿迭代法)
N=input('please enter the largest number of iterations:N=');
for k=1:N
x=(a+b)/2;
fx=feval(f,x);fa=feval(f,a);
if abs((b-a)/2)<e || abs(fx)<e
disp('the number of iterations is');k
f=input('please enter a function:f(x)=');
x0=input('please enter the initial value:x0=');
e=input('please enter error:e=');
N=input('please enter the largest number of iterations:N=');
disp('the approximate solution is');x
disp('f(x) is');fx
disp('the number of iterations is');k
return
else
x0=x;
end
end
end
disp('The maximum number of iterations is reached, stop calculation');
开课学院、实验室：实验时间：2014年1月1日
课程
名称
数值分析基础性实验
实验项目
名称
数值计算算法及实现
for k=1:N
x=(a+b)/2;
fx=feval(f,x);fa=feval(f,a);
if abs((b-a)/2)<e || abs(fx)<e
disp('the number of iterations is');k
f=input('please enter a function:f(x)=');
x0=input('please enter the initial value:x0=');
e=input('please enter error:e=');
N=input('please enter the largest number of iterations:N=');
disp('the approximate solution is');x
disp('f(x) is');fx
disp('the number of iterations is');k
return
else
x0=x;
end
end
end
disp('The maximum number of iterations is reached, stop calculation');
开课学院、实验室：实验时间：2014年1月1日
课程
名称
数值分析基础性实验
实验项目
名称
数值计算算法及实现
数值分析第五版第5章习题答案
第5章
）矩阵行列式的值很小。
）矩阵的范数小。
）矩阵的范数大。
（7）奇异矩阵的范数一定是零。
答：错误，
∞
•可以不为0。
（8）如果矩阵对称，则|| A||1 = || A||∞。
答：根据范数的定义，正确。
（9）如果线性方程组是良态的，则高斯消去法可以不选主元。
答：错误，不选主元时，可能除数为0。
（10）在求解非奇异性线性方程组时，即使系数矩阵病态，用列主元消去法产生的误差也很小。
答：错误。
对于病态方程组，选主元对误差的降低没有影响。
（11）|| A ||1 = || A T||∞。
答：根据范数的定义，正确。
（12）若A是n n的非奇异矩阵，则
)
(
cond
)
(
cond1-
=A
A。
答：正确。
A是n n的非奇异矩阵，则A存在逆矩阵。
根据条件数的定义有：
1
111111 cond()
cond()()
A A A
A A A A A A A
-
------
=•
=•=•=•
习题
如有侵权请联系告知删除，感谢你们的配合！。
数值分析第五版第5章习题答案
第5章
）矩阵行列式的值很小。
）矩阵的范数小。
）矩阵的范数大。
（7）奇异矩阵的范数一定是零。
答：错误，
∞
•可以不为0。
（8）如果矩阵对称，则|| A||1 = || A||∞。
答：根据范数的定义，正确。
（9）如果线性方程组是良态的，则高斯消去法可以不选主元。
答：错误，不选主元时，可能除数为0。
（10）在求解非奇异性线性方程组时，即使系数矩阵病态，用列主元消去法产生的误差也很小。
答：错误。
对于病态方程组，选主元对误差的降低没有影响。
（11）|| A ||1 = || A T||∞。
答：根据范数的定义，正确。
（12）若A是n n的非奇异矩阵，则
)
(
cond
)
(
cond1-
=A
A。
答：正确。
A是n n的非奇异矩阵，则A存在逆矩阵。
根据条件数的定义有：
1
111111 cond()
cond()()
A A A
A A A A A A A
-
------
=•
=•=•=•
习题
如有侵权请联系告知删除，感谢你们的配合！。
数值分析5(高斯消元法)
a31 a11
b1 b1
an 1 a11
a12 ann
an 1 a11
an 1 a11
消元阶段: 所用除法次数(n-1)+ (n-2)+· · · +1= n(n-1)/2, 所用乘法次数(n-1)*n+ (n-2)* (n-1) +· · · +1*2= (n3-n)/3。
回代阶段:
25/44
13:30
含n个变量的n个方程的一般形式是
a11 a21 a n1 a12 a1n a22 a2 n an 2 ann b1 b2 bn
消去阶段: 使用行初等变换使对角线以下的每个 元素都为零。 例如,消去第一列对角线以下的元素a21 , a31, · · · , an1。
13:30
求解
a11 x1 a12 x2 a1n xn b1 a x a x a x b 21 1 22 2 2n n 2 an1 x1 an 2 x2 ann xn bn
12/44
13:30
线性方程组的矩阵形式
27/44
计算：xn = bn /ann
a11 x1 a12 x 2 a1n x n b1 a 22 x 2 a 2 n x n b2 a nn x n bn
13:30
高斯消元法由不相等的两部分组成:工作量相对多 的消元阶段和工作量相对少的回代阶段。对于大的n, 幂次较低的n相比而言可以忽略不计,最高次幂决定了 当n趋近于无穷时的极限形态。换而言之, 对大的n, 低 阶项对算法的执行时间的估计没有太大的影响, 当仅需 近似估计执行时间时可以忽略不计。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
两个三 角矩阵
相乘
1
其中
m
21
1
L L11 Ln11 m31 m32 1
mn1 mn2 mn,n1 1
定理: (矩阵的LU分解)
设 A 为 n 阶矩阵，如果 A 的顺序主子式 Di 0 ( i = 1,2,…,n-1)， 则 A 可分解为一个单位下
三角矩阵 L 和一个上三角矩阵 U 的乘积，且
这种分解是唯一的。
求解两个三角形 方程组!
注：若A 实现了LU分解，则
Ax = b
(LU)x=b
Ly = b Ux = y
举例：用系数矩阵的LU分解求下列方程组
4x1x2x2x3x53 6 2 x1 2 x2 x3 1
（求解过程详见书，请同学们自学）
2. 高斯消去法的一般过程
记 Ax = b 为 A(1)x =
b((11))， 消元过
程
aa12((1111))
a1(12)
a
ቤተ መጻሕፍቲ ባይዱ
(1) 22
... ...
a1(1n) a2(1n)
x1 x2
bb12((11))
...
则求解原方程组可转化为如下两个三角形方
程组：
1 0 0 y1 b1
0
1
0
y2
b2
2 1 1 y3 b3
1 1 1 x1 y1
0
4
1
x2
y2
0 0 2 x3 y3
a
(k kk
)
j k 1
(k n 1, n 2,...,2,1)
高斯消去法的特点：消元和回代不同步！
3. 使用高斯消去法的条件
使用高斯消去法要求在每步消元时 ak(kk) 0 ， 那么矩阵A满足什么，才能保证这一条件呢？
引理：约化的主元素 ak(kk) 0 (i=1,2,…,n) 的充 要条件是矩阵A的顺序主子式 Di 0(i 1,2,..., n)
1
1
m21
1
L11 m31
1
mn1
1
重复这一过程，共进行 ｎ－1
消元，得 A(n)
b
(
n)
Ln1 L1 A(1) Ln1 L1b(1)
,
次 Gauss消 去法将A 分解为
将上三角矩阵 A(n) 记为 U，则有
A A(1) L11L21 Ln11U LU
第五章 解线性方程组的直接法 §2 高斯消去法
一、高斯消去法 二、矩阵的三角分解 三、高斯消去法的计算量 四、高斯—约当消去法
一、高斯消去法
1. 高斯消去法的基本思想
举例 用消去法解方程组
基原本来思方想程4x组：1x2用 AXx=逐2xb3化次x为消53 与去 其未6 等知价数的的三方角法形把 方程组，2而x1求 解2 x三2 角 x形3方 程1 组就容易了！
L
0
1 0
2 0 1
1 1 1 A' 0 4 1
0 4 1
L
考察高斯消去法过程 ：
A(1) x b(1)
第一次消元
A(2) x b(2)
等价于 其中
A(2) L1 A(1) , b(2) L1b(1)
1
0
1
an(11)
a
(1) n2
...
an(1n)
xn
bn(1)
a1(11) 0
第一次 消元
a01(11)
a1(12) a 2( 22)
... ...
a1(1n) a 2( 2n)
x1 x2
bb12((12))
L1 0
1
mn1
1
1
1
0
1
m21
m31
1
0
0
1 0
消元时的 系数
1
1
1
而且
1
m21
1
L1 m31
1
mn1
...
0
a n( 22)
...
a n( 2n)
xn
bn( 2 )
……
(记 为 A(2)x =
b(2)) a1(11) a1(12) ... a1(1n) x1 b1(1)
第n-1
a 2( 22)
...
解： 系数矩阵为
1 1 1
A 0 4 1 2 2 1
由高斯消去法， m21=0，m31=2 m32=－1，故
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
二、矩阵的三角分解
由矩阵理论可知，对系数矩阵 A 实施行的初
等变换相当于用初等矩阵左乘 A ，即
行初等变换
A
A'
等价于
E 其中
A' LA
行初等变换
初等 矩阵
L
例
1 1 1
A 0 4 1 2 2 1
①*(-2)+③
则 A' LA
E 其中
①*(-2)+③
1 0 0
a 2( 2n)
x2
b2( 2 )
次消元
...
a n( nn)
xn
bn( n )
(记 为 A(n)x =
(n)
(2) 回代过
程 xn bn(n) an(nn)
x
k
(bk(k )
n
ak(kj ) x j )
推论：如果A的顺序主子式不等于0，则
a1(11) D1 ak(kk) Dk Dk1
(k=2,3,…, n)
定理：如果 n 阶矩阵A的所有顺序主子式 均 不为零，则可通过高斯消去法（不进行交 换两行的初等变换），将方程组约化为三 角形方程组。 定理：如果A为 n 阶非奇异矩阵，则可通过 高斯消去法（及交换两行的初等变换）将方 程组 Ax=b 化为三角形方程组。