p=2称为平方收敛
其中:
ek=(x*-xk)为迭代误差。
定理3:
对于迭代过程xk+1=ϕ(xk),如果ϕ(p)(x)在所求根x*的邻近连续,并且ϕ’(x*)=ϕ’’(x*)=...=ϕ(p-1)(x*)=0,ϕ(p)(x*)≠0,则该迭代过程在点x*邻近是P阶收敛的。
注:
牛顿迭代公式在根x*的邻近至少是平方收敛的。
三、数值计算实验(以下实验都需利用Matlab软件来完成)
实验2.1(求非线性方程根实验
(一))
实验目的:
会求非线性方程的根
实验内容:
1、用Matlab软件做出下列方程的图形,观察根所在的区间:
2、用二分法求上述方程的根,并分析其误差。
实验2.1(求非线性方程根实验
(二))
实验目的:
会求非线性方程的根
实验内容:
试有方程:
1、分别用Newton迭代法和快速弦截法求上述方程的根;
2、比较两种迭代法的收敛速度。
四、具体操作见下例。
(以下实验都需利用Matlab软件来完成)
例1:
用二分法求方程x2-x-1=0的正根,要求误差小于0.05
解:
1)首先根据程序框图编制二分法的函数文件:
erfen.m
2)再编写函数文件fc.m
funtiony=fc(x)
y=x^2-x-1;
3)最后在Matlab命令窗口输入调用命令:
erfen(‘fc’,0,10,0.05)
4)输出结果为n=56
ans=1.6180
例2:
求解非线性方程5x2sinx-e-x=0,观察知有多解,如何求出所有解?
解:
1)编写M—文件:
newton.m
2)编写函数文件:
fc1.m和df.m
%fc1.m
functiony=fc1(x)
y=5*x^2*sin(x)-exp(-x);
%df.m
functiony=df(x)
y=10*x*sin(x)+5*x^2*cosx+exp(-x);
3)用命令fplot(‘[5*x^2*sin(x)-exp(-x),0]’,[0,10]))作图,%在指定的范围内画出函数的图形。
(注意:
[5*x^2*sin(x)-exp(-x),0]中的‘[…,0]’是作y=0直线,即x轴)(见图3)
从图中可看出方程在[0,10]区间有4个解,分别在0、3、6、9附近,所以
4)用命令
>>>>newton(x0)
即可求出求方程fc1=0在x0附近的近似解
得出结果
ans=
0.50183.14076.28329.4248
图3
注:
用Newton迭代法可求出多个根。
具体做法:
先用fplot命令作出函数的图形,再根据图形给出不同的初始值x0,最后通过调用Newton迭代法程序求出非线性方程的所有根。
五、思考题
思考题1、在二分法中取区间中点,每次计算一次函数值。
如果每次把区间三等份,计算两个函数值,是否可以找出方程的根?
给出它的算法。
和二分法比较它的效率如何?
思考题2、目的:
找出一维搜索的最佳途径。
内容:
假设f(x)=0在[a,b]区间内只有一个根(可以是重根),求解该方程等价于在[a,b]区间找|f(x)|的极小值点。
设计一种寻找极小值点的方法,使得计算f(x)的次数尽可能的少,并完成数值实验。
你能从理论上证明你的搜索方法最好吗?
思考题3、目的:
了解牛顿收敛法的结构和“局部”收敛性。
内容:
牛顿法可以直接用来求解复数方程z3-1=0,在复平面上它的三个根是z1*=1,
。
选择中心位于坐标原点边长为2的正方形内的点为初始值,把收敛到三个不同根的初始值分别标上不同的颜色。
只要计算足够多的点,你将得到关于牛顿收敛域的彩色图片。
第三章线性方程组的解法
一、主要要求
编写方程组求解的通用程序:
Jacobi迭代、Seidel迭代以及SOR迭代程序
二、主要结果回顾
1、迭代法:
•它的基本思想是将线性方程组AX=b化为:
X=BX+f
•再由此构造向量序列{X(k)}:
X(k+1)=BX(k)+f
•若{X(k)}收敛至某个向量x*,则可得向量X*就是所求方程组AX=b的准确解.
•线性方程组的迭代法主要有Jocobi迭代法、Seidel迭代法和超松弛(Sor)迭代法.
2、收敛性判定定理:
定理1:
对任意初始向量X(0)及任意向量f,由此产生的迭代向量序列{X(k)}收敛的充要条件是
。
定理2:
若||B||<1,则迭代公式X(k)=BX(k-1)+f收敛.
3、Jacobi迭代公式:
其中:
BJ=-D-1(U+L),fJ=D-1b。
4、Seidel迭代公式:
其中:
Bs=-(D+L)-1U,fs=(D+L)-1b。
5、Jacobi迭代、Seidel迭代的算法:
Jacobi迭代算法:
1)给出矩阵A,b,x0
2)计算B=D-1(-U-L),f=D-1b
3)y=BX0+f
4)若||y-x0||<=1.0e-6,则转到5),否则,转到3)
5)输出y和n。
Seidel迭代算法:
1)给出矩阵A,b,x0
2)计算B=(D-L)-1U,f=(D-L)-1b,则有:
3)y=BX0+f
4)若||y-x0||<=1.0e-6,则转到5),否则,转到3)
5)输出y和n。
6、程序框图:
(见图4)
开始
Y
N
N
输入a,b,x0
由矩阵a,生成D,U,L,B,f
y=B*x0+f
n=1
||y-x0||>=1.0e-6
x0=yy=B*x0+f
n=n+1
输出x
结束
图4
仿Jacobi迭代法算法和Seidel迭代算法可给出超松驰迭代的算法(略)
三、数值计算实验(以下实验都需用Matlab软件来完成)
实验3.1(求解线性方程组实验)
实验目的:
掌握各种迭代法,比较各种迭代法的渐进收敛速度.
实验内容:
令
1、计算A的条件数cond(A);(可选用任何一种范数)
2、上述方程组是否为病态方程组?
若是,如何改变方程组的病态性?
3、分别用Jacobi迭代、Seidel迭代与超松驰迭代求方程组AX=b的近似解;
4、比较Jacobi迭代、Seidel迭代与超松驰迭代的渐进收敛速度。
注:
上述实验分两次完成。
四、具体操作见下例(以下实验都需用Matlab软件来完成)
例:
用Jacobi方法求解下列方程组,设X(0)=0,精度为10-6
解:
1)先根据Jacobi算法编写M—文件:
Jacobi(a,b,X0)
2)在Matlab命令窗口输入命令:
>>a=[10-10;-110-2;0-110];
>>b=[9;7;6];
>>Jacobi(a,b,[0;0;0])
3)输出结果:
y=
0.9938
0.9381
0.6938
n=9
注:
n=9为迭代次数。
五、思考题
思考题:
目的:
以Hilbert矩阵为例,研究处理病态问题可能遇到的困难。
内容:
设Hilbert矩阵为
它是一个对称正定矩阵,而且cond(Hn)随着n的增加迅速增加。
其逆矩阵Hn-1=(aij),这里
1)画出ln(cond(Hn))~n之间的曲线(可以用任何一种范数)。
你能猜出ln(cond(Hn))~n之间有何种关系吗?
提出你的猜测并想法验证。
2)设D是Hn的对角元素开方构成的矩阵。
,不难看出它仍然是对称矩阵,而且对角线元素都是1。
把Hn变成
的技术称为预处理(preconditioning)。
画出ln(cond(
)/cond(Hn))~n之间的曲线(可以用任何一种范数)。
对于预处理你能得出什么印象?
3)对于4≤n≤12,给出不同的右端项b。
分别用X1=Hn-1b,
,X2=D-1
以及X3=Hn\b(这是Matlab的一条命令)求解HnX=b,比较计算结果。
4)取不同的n并以Hn的第一列为右端向量b,同高斯—塞德尔迭代求解HnX=b,观察其收敛性。
最后你能对于有关Hilbert矩阵的计算得出哪些结论。
第四章插值与拟合
一、主要要求
编写拉格朗日插值法、分段线性插值法、*三次样条插值通用程序(Matlab自带)。
拉格朗日插值多项式:
二、主要结果回顾
插值法是函数逼近的重要方法之一,有着广泛的应用。
在生产和实验中,函数f(x)或者其表达式复杂不便于计算或者无表达式而只有函数在给定点的函数值(或其导数值),此时我们希望建立一个简单的而便于计算的函数ϕ(x),使其近似的代替f(x),这就是所谓的插值法.有很多种插值法,其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点,常用的插值还有Hermit插值,分段插值和样条插值.
1、插值:
求近似函数的方法:
由实验或测量的方法得到所求函数y=f(x)在互异点x0,x1,...,xn处的值y0,y1,…,yn,
构造一个简单函数ϕ(x)作为函数y=f(x)的近似表达式:
y=f(x)≈ϕ(x)
使ϕ(x0)=y0,ϕ(x1)=y1,⋯,ϕ(xn)=yn,(*)
这类问题称为插值问题。
f(x)称为被插值函数,ϕ(x)称为插值函数,x0,x1,...,xn称为插值节点。
(*)式称为插值条件。
2、Lagrange插值公式
其中x0,x1,...,xn为插值节点,yj为插值节点xj处的函数值(j=1,2,…n)。
3、Lagrange插值的截断误差(插值余项)
定理:
设Ln(x)是过点x0,x1,x2,…xn的n次插值多项式,f(n)(x)在[a,b]上连续,f(n+1)(x)在[a,b]上存在,其中[a,b]是包含点x0,x1,x2,…,xn的任一区间,则对任意给定的x∈[a,b],总存在一点∈ξ(a,b)(依赖于x)使
其中:
。
4、拉格朗日插值法程序框图:
(见图5)
(图5)
三、数值计算实验(以下实验都需利用Matlab软件来完成)
实验4.1(观察龙格(Runge)现象实验)
实验目的:
观察拉格朗日插值的龙格(Runge)现象.
实验内容:
对于函数
进行拉格朗日插值,取不同的节点数,在区间[-5,5]上取等距间隔的节点为插值点,把f(x)和插值多项式的曲线画在同一张图上进行比较。
(a可以取任意值)具体步骤:
1、a=1时,1)n=4,作出f(x)和插值多项式的曲线图;
2)n=10,作出f(x)和插值多项式的曲线图;
2、a=0.5时,1)n=4,作出f(x)和插值多项式的曲线图;
2)n=10,作出f(x)和插值多项式的曲线图;
3、分析上述曲线图,你可以得出什么结论?
四、具体操作
例1、给出f(x)=lnx的数值表,用Lagrange插值计算ln(0.54)的近似值。
x
0.4
0.5
0.6
0.7
0.8
Lnx
-0.916291
-0.693147
-0.510826
-0.357765
-0.223144
解:
1)首先根据程序框图拉格朗日插值法的函数文件:
lagrange(x0,y0,x)
2)在Matlab命令窗口输入调用命令:
>>x0=[0.4:
0.1:
0.8];
>>y0=[-0.916291-0.693147-0.510826-0.356675-0.223144];
>>lagrange(x0,y0,0.54)
3)输出结果为:
-0.616143(精确解:
-0.616186)
实验4.2分段插值实验
实验目的:
分段插值计算,会使用一维插值函数,寻找最佳的插值方法。
实验内容:
在1—12的11小时内,每隔1小时测量一次温度,测得的温度依次为:
5,8,9,15,25,29,31,30,22,25,27,24。
1)试估计每隔1/2小时的温度值。
2)分别用分段线性插值,立方插值,三次样条插值和最邻近插值估计其值。
实验4.3(插值与拟合实验)
实验目的:
求下列数据的多项式拟合函数
x=[0,1,2,3,4,5,6,7,8,9,10];
y=[1,2.3,2.1,2,4.6,4.7,4.3,8.1,9.2,9.8,10.3];
实验内容:
1、做出原始数据的散点图;
2、做出原始数据的折线图(即分段线性插值函数图);
3、做出原始数据的分段二次拟合曲线图(见图6);
4、做出原始数据的分段三次拟合曲线图。
(图6)
五、思考题
思考题1、目的:
观察最小二乘多项式的数值不稳定性现象。
内容:
1、在[-1,1]区间上取n=20个等距节点,计算出以相应节点上ex的值做为数据样本,
2、以1,x,x2,...,xt为基函数做l=3,5,7,9次的最小二乘多项式。
3、画出ln(cond(A))~n之间的曲线,其中A是确定最小二乘多项式系数的矩阵。
4、计算出不同阶最小二乘多项式给出的最小偏差
思考题2、目的:
观察对于非光滑函数进行多项式插值的可能性。
内容:
在[0,1]上取f(x)=|sinkπx|,选择不同的k和n,用等距节点做拉格朗日多插值项式,观察误差大小和收敛情况。
第五章数值积分
一、主要要求
编写定步长复合梯形公式、定步长复合Simpson公式、变步长梯形法及龙贝格算法*通用子程序;
二、主要结果回顾
1、梯形公式:
对于连续函数f(x),有积分中值定理
其中f(ξ)是被积函数f(x)在积分区间上的平均值。
因此,如果我们能给出求平均值f(ξ)的一种近似方法,相应地就可以得到计算定积分的一种数值方法。
如果取
,即得下列梯形公式:
二、辛普生(Simpson)公式:
先用某个简单函数近似逼近f(x),然后用
在[a,b]区间的积分值近似表示f(x)在[a,b]区间上的定积分,即取
我们可以取
为前面介绍的f(x)的插值多项式Ln(x)或拟合多项式P(x)进行近似计算。
如取
为插值多项式Ln(x),则相应得到的数值积分公式称为插值型求积公式。
如:
若考虑过点A,B,C三点的抛物线段L代替曲线段y=f(x)(见图7)