数值分析思考题1
1、讨论绝对误差(限)、相对误差(限)与有效数字之间的关系。 2、相对误差在什么情况下可以用下式代替?
e *x *-x
e =*=
x x *
*r
3、查阅何谓问题的“病态性”,并区分与“数值稳定性”的不同点。
≈1. 41,计算
4、 取
1),下列方法中哪种最好?为什么?
6
(1)3-((2),(7-3
2
,(31
3
(3+,(411
)
6
,(5)99-数值实验
数值实验综述:线性代数方程组的解法是一切科学计算的基础与核心问题。求解方法大致可分为直接法和迭代法两大类。直接法——指在没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法,因此也称为精确法。当系数矩阵是方的、稠密的、无任何特殊结构的中小规模线性方程组时,Gauss 消去法是目前最基本和常用的方法。如若系数矩阵具有某种特殊形式,则为了尽可能地减少计算量与存储量,需采用其他专门的方法来求解。
Gauss 消去等同于矩阵的三角分解,但它存在潜在的不稳定性,故需要选主元素。对正定对称矩阵,采用平方根方法无需选主元。方程组的性态与方程组的条件数有关,对于病态的方程组必须采用特殊的方法进行求解。
数值计算方法上机题目1
1、实验1. 病态问题
实验目的:
算法有“优”与“劣”之分,问题也有“好”和“坏”之别。所谓坏问题就是问题本身的解对数据变化的比较敏感,反之属于好问题。希望读者通过本实验对此有一个初步的体会。
数值分析的大部分研究课题中,如线性代数方程组、矩阵特征值问题、非线性方程及方程组等都存在病态的问题。病态问题要通过研究和构造特殊的算法来解决,当然一般要付出一些代价(如耗用更多的机器时间、占用更多的存储空间等)。
问题提出:
考虑一个高次的代数多项式
p (x ) =(x -1)(x -2)...(x -20) =
∏(x -k ) (E1-1)
k =1
20
显然该多项式的全部根为l ,2,„,20,共计20个,且每个根都是单重的(也称为简
单的)。现考虑该多项式方程的一个扰动
p (x ) +εx 19=0 (E1-2) 其中ε是一个非常小的数。这相当于是对(E1-1)中x 的系数作一个小的扰动。我们希望比较(E1-1)和(E1-2)根的差别,从而分析方程(E1-1)的解对扰动的敏感性。
实验内容:
为了实现方便,我们先介绍两个 Matlab 函数:“roots ”和“poly ”,输入函数
u =roots (a )
其中若变量a 存储n +1维的向量,则该函数的输出u 为一个n 维的向量。设a 的元素依次为a 1, a 2,..., a n +1,则输出u 的各分量是多项式方程
19
a 1x n +a 2x n -1+... a n x +a n +1=0
的全部根,而函数
b=poly(v)
的输出b 是一个n +1维变量,它是以n 维变量v 的各分量为根的多项式的系数。可见“roots ”和“Poly ”是两个互逆的运算函数.
ve=zeros(1,21); ve(2)=ess;
roots(poly(1:20))+ve) 上述简单的Matlab 程序便得到(E1-2)的全部根,程序中的“ess ”即是(E1-2)中的ε。 实验要求:
(1)选择充分小的ess ,反复进行上述实验,记录结果的变化并分析它们。如果扰动项的系数ε很小,我们自然感觉(E1-1)和(E1-2)的解应当相差很小。计算中你有什么出乎意料的发现?表明有些解关于如此的扰动敏感性如何?
(2)将方程(E1-2)中的扰动项改成εx 或其他形式,实验中又有怎样的现象出现? (3)请从理论上分析产生这一问题的根源。注意我们可以将方程(E1-2)写成展开的形式,
18
p (x , α) =x 20-αx 19+... =0
同时将方程的解x 看成是系数α的函数,考察方程的某个解关于α的扰动是否敏感,与研究它关于α的导数的大小有何关系?为什么?你发现了什么现象,哪些根关于α的变化更敏感?
2、实验2。多项式插值的振荡现象,即插值的龙格(Runge )现象
问题提出:
考虑在一个固定的区间上用插值逼近一个函数。显然,拉格朗日插值中使用的节点越多,插值多项式的次数就越高、自然关心插值多项式的次数增加时,L n (x ) 是否也更加靠近被逼
近的函数。龙格给出的一个例子是极著名并富有启发性的。设区间[-1, 1]上函数
f (x ) =
实验内容:
考虑区间[-1, 1]的一个等距划分,分点为
1
2
1+25x
x i =-1+
则拉格朗日插值多项式为
2i
, i =0, 1, 2,..., n n
n
L n (x ) =∑
1
l (x ) 2i
1+25x i =0i
其中的l i (x ) ,i =0, 1, 2,..., n 是n 次拉格朗日插值基函数。 实验要求:
(l )选择不断增大的分点数目n =2, 3,... ,画出原函数f (x ) 及插值多项式函数L n (x ) 在
[-1, 1]上的图像,比较并分析实验结果。
(2)选择其他的函数,例如定义在区间[-5,5]上的函数 h (x ) =重复上述的实验看其结果如何。 (3)区间[a , b ]上切比雪夫点的定义为
x
, g (x ) =arctan x 4
1+x
x k =
⎛(2k -1) π⎫b +a b -a
⎪+cos ⎪, k =1, 2,..., n +1 22(2(n +1) ⎝⎭
以x 1, x 2,..., x n +1为插值节点构造上述各函数的拉格朗日插值多项式,比较其结果。
3、实验3。 样条插值的收敛性
问题提出:
一般的多项式插值不能保证收敛性,即插值的节点多,效果不一定就好。对样条函数插值又如何呢?理论上证明样条插值的收敛性是比较困难的,也超出了本课程的内容。通过本实验可以验证这一理论结果。
实验内容:
请按一定的规则分别选择等距或者非等距的插值节点,并不断增加插值节点的个数。考虑实验2. 中的函数或选择其它你有兴趣的函数,可以用 Matab 的函数 “spline ”作此函数的三次样条插值。在较新版本的Matlab 中,还提供有spline 工具箱,你可以找到极丰富的样条工具,包括B-样条。
实验要求:
(1)随节点个数增加,比较被逼近函数和样条插值函数误差变化情况。分析所得结果
并与拉格朗目多项式插值比较。
(2)样条插值的思想最早产生于工业部门。作为工业应用的例子,考虑如下问题:某
(3)计算此实验的B-样条插值(选做)。
数值计算方法(二)
1、利用Newton 方法和Muller (抛物线) 方法计算下列方程
f (x ) =2-x +e x +2cos(x ) -6=0
在区间[1, 3]上的实根,要求精度为ε=10,并比较迭代次数。
-5
2、用Gauss 列主元消去法求解下列方程组
⎡6-2
⎢12-8⎢
-13 ⎢3⎢
⎣-64
2
4⎤⎡x 1⎤⎡0⎤⎢x ⎥⎢⎥410⎥⎢2⎥⎢-10⎥⎥=
33⎥⎢x 3⎥⎢-39⎥
⎥⎢⎥⎢⎥218⎦⎣x 4⎦⎣-16⎦
T
3、用改进的平方根(A =LDL 分解)法求解下列方程组
⎡4⎢0⎢⎢6⎢⎢0⎢⎣2
2⎤⎡x 1⎤⎡12⎤
⎢x ⎥⎢⎥⎥1302⎥⎢2⎥⎢6⎥
31926⎥⎢x 3⎥=⎢36⎥
⎥⎢⎥⎢⎥
025-5⎥⎢x 4⎥⎢2⎥
⎢⎥⎢⎥x 26-516⎥21⎦⎣5⎦⎣⎦0
6
实验一
一、实验名称:矩阵的LU 分解.
二、实验目的:用不选主元的LU 分解和列主元LU 分解求解线性方程组 Ax=b, 并比较这两
种方法.
三、实验内容与要求 (1)用所熟悉的计算机语言将不选主元和列主元LU 分解编成通用的子程序,然后用编写的程序求解下面的84阶方程组
将计算结果与方程组的精确解进行比较,并就此谈谈你对Gauss 消去法的看法。 (2)写出追赶法求解三对角方程组的过程,并编写程序求该实验中的方程组
实验二
一、实验名称:实对称正定矩阵的A 的Cholesky 分解.
二、实验目的:用平方根法和改进的平方根方法求解线性方程组 Ax=b. 三、实验内容与要求
用所熟悉的计算机语言将Cholesky 分解和改进的Cholesky 分解编成通用的子程序,然后用编写的程序求解对称正定方程组Ax=b,其中 (1) b 随机的选取,系数矩阵为100阶矩阵
(2) 系数矩阵为40阶Hilbert 矩阵,即系数矩阵A 的第i 行第j
列元素为
,向量b 的第i
个分量为
(3) 用实验一的程序求解这两个方程组,并比较所有的计算结果,然后评价各个方法的
优劣。
实验三
实验名称:直接法的时间复杂性试验。
实验目的:分别用三种不同方法求解线性方程组 Ax=b,不同工作量得出不同时间。 实验内容与要求:
生成方程组Ax =b 中矩阵A 和右端项b ,分别用x =A \b ,x =inv (A )*b 和三角分解法计算,并分别记录所花费的CPU 时间,进行分析比较。
实验要求:
(1)取n =300,随机生成A 的一条主对角线元素和二条次对角线元素,使A 为严格对角占优的三对角阵和b ;其中三条对角线元素分别用三个一维数组存储;
(2)用Matlab 语言自编M 文件分别用x =A \b ,x =inv (A )*b 和追赶法计算这三对角方程组;并分别记录所花费的CPU 时间;
(3) 分析结果,得出你的结论。
数值分析思考题4
1、Gauss 消去法和LU 三角分解法解线性方程组的工作量相同吗?工作量为多少?平方根方法的工作量为多少?
2、求解一个线性方程的LU 分解法什么条件下可以保障成功?选主元的目的是什么?分别用列主元和全主元Gauss 消去法求解下列方程组:
⎧12x 1-3x 2+3x 3=15
⎪
⎨-18x 1+3x 2-x 3=-15 ⎪x 1+x 2+x 3=6⎩
3、用平方根方法(Cholesky 分解法)求解下列方程组,并用紧凑格式存储。
8⎤⎡x 1⎤⎡-4⎤⎡164
⎢4⎥⎢x ⎥=⎢3⎥
5-4⎢⎥⎢2⎥⎢⎥⎢⎣8-422⎥⎦⎢⎣x 3⎥⎦⎢⎣10⎥⎦
4、已知线性方程组
⎡2.00021.9998⎤⎡x 1⎤⎡4⎤⎢1.99982.0002⎥⎢x ⎥=⎢4⎥ ⎣⎦⎣2⎦⎣⎦
-1
(1)求系数矩阵的逆A 和条件数cond (A ) ; (2)若方程组右端有微小扰动
δb =(2⨯10-4, -2⨯10-4)
T
,不用求解方程
组,试利用解与系数扰动之间的关系式来估计解的相对变化率。
数值分析思考题5
1、插值与拟合的相同点和不同点分别是什么?
2、写出n 次多项式拟合的一般形式,奇函数和偶函数的多项式拟合的一般形式。
3、详述你所知道的矩阵分解,它们的意义如何?
4、超定(矛盾)线性方程组的最小二乘解有哪些情况?说明它与广义逆的关系。
5、给出各种正交化方法的优劣比较。
6、用Householder 变换求解下列线性方程组的极小最小二乘解
⎡1⎢1⎢⎢1⎢⎢1⎢⎣1
124⎤⎡4⎤
x ⎡1⎤⎢⎥
235⎥⎥⎢x 2⎥⎢5⎥346⎥⎢⎥=⎢6⎥
⎥⎢x 3⎥⎢⎥
457⎥⎢⎥⎢7⎥
⎣x 4⎦⎢9⎥568⎥⎦⎣⎦
实验一
1.根据Matlab 语言特点,描述Jacobi 迭代法、Gauss-Seidel 迭代法和SOR 迭代法。 2.编写Jacobi 迭代法、Gauss-Seidel 迭代法和SOR 迭代法的M 文件。 3.给定A ∈R
20⨯20
为五对角矩阵
⎡⎢⎢⎢-⎢⎢-⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣
31214
-
123
12 1-4-
141-2-3 1-21-4
141-2 -3121-4-
14 1-2-3-12
⎤⎥⎥⎥⎥⎥⎥⎥ 1⎥-⎥4⎥1⎥-⎥2⎥3⎥⎦
(1)选取不同的初始向量x
(0)
及右端面项向量b ,给定迭代误差要求,分别用编写的Jacobi 迭
代法和Gauss-Seidel 迭代法程序求解,观察得到的序列是否收敛?若收敛,通过迭代次数分析计算结果并得出你的结论。
(2)用编写的SOR 迭代法程序,对于(1)所选取的初始向量x
(0)
及右端面项向量b 进行求解,
(k ) (k +1)
≤10-5时停止迭代,通过迭代次数分析计松驰系数ω取1
算结果并得出你的结论。
实验二
题目: 多项式最小二乘法
摘要:对于具体实验时,通常不是先给出函数的解析式,再进行实验,而是通过实验的观察和测量给出离散的一些点,再来求出具体的函数解析式。又因为测量误差的存在,实际真实的解析式曲线并不一定通过测量给出的所有点。最小二乘法是求解这一问题的很好的方法,本实验运用这一方法实现对给定数据的拟合。 数学原理:
对于给定的测量数据(x i ,f i )(i=1,2,„,n ) ,设函数分布为
y (x ) =∑a j ϕj (x )
j =0
m
特别的,取ϕj (x ) 为多项式
ϕj (x ) =x j (j=0, 1,„,m )
则根据最小二乘法原理,可以构造泛函
n
m
H (a 0, a 1, , a m ) =∑(f i -∑a j ϕj (x i ) )
i =1
j =0
令
∂H
=0 (k=0, 1,„,m ) ∂a k
则可以得到法方程
⎡(ϕ0, ϕ0) (ϕ1, ϕ0) (ϕm , ϕ0) ⎤⎡a 0⎤⎡(f , ϕ0) ⎤⎢(ϕ, ϕ) (ϕ, ϕ) (ϕ, ϕ) ⎥⎢a ⎥⎢(f , ϕ) ⎥
11m 1⎥⎢1⎥1⎥⎢01=⎢
⎢ ⎥⎢⎥⎢⎥ ⎢⎥⎢⎥⎢⎥(ϕ, ϕ) (ϕ, ϕ) (ϕ, ϕ) a (f , ϕ) 0m 1m m m m m ⎣⎦⎣⎦⎣⎦
求该解方程组,则可以得到解a 0, a 1, , a m ,因此可得到数据的最小二乘解
f (x ) ≈∑a j ϕj (x )
j =0
m
程序设计:编写求解多项式拟合的Matlab 函数子程序
并作出f (x ) 的近似分布图。
分别采用一次,二次、五次和偶数次多项式来拟合数据得到相应的拟合多项式,并分别作出它们的曲线图。
实验三
实验名称:非线性方程组数值求解的Newton 类方法试验。 实验目的:用Newton 类方法求解线性方程组 F(x)=0,理解其解的复杂性、初始点选择策略、减少算法工作量的方法等。 实验内容与要求:
分别用Newton 法用Broyden 秩1校正法求解下面非线性方程组
⎧3x 1-cos(x 2x 3) -0.5=0⎪⎪22
⎨x 1-81(x 2+0.1) +sin x 3+1.06=0 ⎪1
⎪e -x 1x 2+20x 3+(10π-3) =0
3⎩
(1) 写出MATLAB 源代码;
(2) 给出迭代五次以上的结果;
(3) 尝试不同的初值,如可取(0.1,0.1,-0.1) ); (4) 计算两种方法的用时。
数值分析思考题6
1、数值计算中迭代法与直接法的区别是什么? 2、详述你所知道的线性方程组的迭代法的收敛性定理。
3、详述你所知道的非线性方程(组)的迭代法以及收敛性结果。 4、举例说明解线性方程组的SOR 方法的最佳松弛因子与何种因素有关?
5、指出解非线性方程组的Newton 法的主要工作量所在。分别用Newton 法和Broyden 秩1校正方法求解如下方程组在(1, 1, 1)点附近的根:
2⎧12x 1-x 2-4x 3-7=0, ⎪2
⎨x 1+10x 2-x 3-11=0, ⎪x 3+10x -8=0.
23⎩
T