计算方法引论主编

1、第二章 插值法知识点：拉格朗日插值法，牛顿插值法，余项，分段插值。实际问题中，时常不能给出f（x）的解析表达式或f（x）解析表达式过于复杂而难于计算，能采集的只是一些f（x）的离散点值xi,f(xi)(i=0,1,2,n)。因之，考虑近似方法成为自然之选。定义：设f（x）为定义在区间a，b上的函数，x0,x1,xn为a，b上的互异点，yi=f（xi）。若存在一个简单函数j（x），满足（插值条件）j（xi）=f（xi），i=0，1，n。则称 j（x）为f（x）插值函数，f（x）为被插函数,点x0,x1,xn为插值节点,点xi,f(xi),i=0,1,2,n为插值点。于是计算f（x）的问题就转换为

2、计算 j（x）。构造插值函数需要解决：插值函数是否存在唯一；插值函数如何构造(L插值)；插值函数与被插函数的误差估计和收敛性。对插值函数 j（x）类型有多种不同的选择，代数多项式常被选作插值函数。P23(2.18)和(2.19)指出，存在唯一的满足插值条件的n次插值多项式pn(x)。但是需要计算范德蒙行列式，构造插值多项式工作量过大，简单表达式不易得到，实际中不采用这类方法。pn(x)f(x)插值法是一种古老的数学方法，拉格朗日（Lagrange）、牛顿（Newton）等分别给出了不同的解决方法。拉格朗日插值拉格朗日（Lagrange）插值的基本思想：把插值多项式pn(x)的构造问题转化为n+

3、1个插值基函数li(x)(i=0,1,n)的构造。(1)线性插值构造插值函数已知函数y=f(x)的两个插值点(x0,y0)，(x1,y1)，构造多项式y=p1(x)，使p1(x0)=y0,p1(x1)=y1。由直线两点式可知，通过A，B的直线方程为()(1001010xpxxxxyyyy=-=+x-x1p1(x)=x0-x1+x-x0x1-x0y0y1变形为x-x1l0(x)=x0-x1x-x0l1(x)=x1-x0记则p1(x)=l0(x)y0+l1(x)y1插值完毕！注意性质：l0(x0)=l1(x1)=1，l0(x1)=l1(x0)=0，p1(x0)=y0，p1(x1)=y1。称l0(x

4、)，l1(x)为点x0、x1的线性插值基函数。插值函数p1(x)是这两个插值基函数的线性组合，这种形式的插值称作为拉格朗日（Lagrange）插值，相应多项式称拉格朗日线性插值多项式，记作L1（x）。误差设L1（x）为插值点(x0,y0)，(x1,y1)的插值函数,f(x0)= y0,f(x0)=y1,f(x)一阶连续可导,二导数存在.则对任意给定的xa,b,存在一点a,b,使R1(x)=(x-x0)(x-x1) f ()（2）2！,a,bf(x)-L1(x)=引进辅助函数,利用洛尔定理即证，见P17定理2.1。(2)二次插值构造插值函数给定三个点xi,f(xi), i=0,1,2,其中xi互

5、不相同，构造函数f（x）的二次插值多项式L2（x），满足：L 2(x0)=y0,L2(x1)=y1,L2(x2)=y2。通过三点的插值问题称为二次插值或抛物插值。仿线性插值，用插值基函数构造插值多项式。令L2（x）=l0(x)y0+l1(x)y1+l2(x)y2待定函数li(x)应是二次函数，满足约束条件li(xi)=1，li(xj)=0（ij），i，j=0，1，2。此设l0(x)=A(x-x1)(x-x2)，l1(x)=B(x-x0)(x-x2)，l2(x)=C(x-x0)(x-x1)。根据约束条件确定系数1A=(x0-x1)(x0-x2)1C=(x2-x0)(x2-x1)1B=(x1-x0

6、)(x1-x2)由此得L2(x)=(x-x1)(x-x2)(x0-x1)(x0-x2)f(x0)(x-x0)(x-x2)(x1-x0)(x0-x2)f(x1)(x-x0)(x-x1)(x2-x0)(x2-x1)f(x2)+误差R2(x)=(x-x0)(x-x1)(x-x2)f ()（3）3！,Minx0,x1, x2,x, Minx0,x1, x2,x证明见P22定理2.2。例 设sin11°=0.190809,sin12°=0.207912。用线性插值计算sin11°30.x-12L1(x)=11-12x-110.190809+12-110.207912解L1(

7、11.5)=0.199361R1(x)=(x-x0)(x-x1) f ()（2）2！=(x-11)(x-12) -Sin()2！|R1(11.5)|(11.5-11)(11.5-12)|=0.125 12例 设sin11°=0.190809,sin12°=0.207912，sin13°=0.224951。用二次插值计算sin11°30解L2(x)=(x-12)(x-13)(11-12)(11-13)0.190809(x-11)(x-13)(12-11)(12-13)0.207912(x-11)(x-x12)(13-11)13-12)0.224951+L2

8、(11.5)=0.199369.(3)一般情况knknknkjjjkjkknyxxxxxlyxL)()()(000ååÕ=¹=-=两个插值点可求出一次插值多项式L1(x)，而三个插值点可求出二次插值多项式L2(x)。当插值点增加到n+1个时，利用Lagrange插值方法写出n次插值多项式Ln(x)。详细说明见P22-24，（2.20），（2.21）至（2.24）。关于Langrange插值的几点说明Ln(x)仅与已知数据(xi,yi),(i =0,1,n) 有关，与f(x)的原来形式无关，但余式与f(x)密切相关。)()(,0)(xfxLxRnn=即若f

9、(x)本身是一个不超过n次多项式，则内插（x位于x0,x1,xn之间）误差较小，外插有可能误差变大，慎用!插值点的增减,基函数要重新计算,很不方便!插值节点过多其精度不一定很好；limLn(x)=f(x), "xa,b一般不成立.第二章 插值法知识点：拉格朗日插值法，牛顿插值法，余项，分段插值。Newton插值法Lagrange插值多项式的一个缺点是没有承袭性质，增加插值节点时，需要重新计算所有插值基函数。牛顿插值多项式克服了这一缺点：增加一个节点时，可在原插值多项式基础上增加一项构成高一阶的插值多项式。（1）差商即其性质上的二在节点定义设函数y=f(x)在区间a,b上n+1个互异节

10、点0 xj n处的值为：yi = f(xi)（i=0,1,2,n）-称jijijixxxfxfxxf-D)()(,为f(x)在节点xi,上的一阶差商；称 kikjjikjixxxxfxxfxxxf-D,为在节点阶差商；依次类推： 称nnnnxxxxxfxxxfxxxf-D-02111010,.,.,.,为上的n阶差商.商；xjf(x)xkxj,xi,f(x)x0,x1,xn).()()()()(,.,),.,2,1,0()(,.,1100'1010nnjjjnjnxxxxxxxxxfxxxfnjxfxxxfn-=ww其中的线性组合，即函数值是阶差商性质证 采用数学归纳法即证性质2差商与

11、节点排列顺序无关。（2）线性牛顿插值设互异y0=f(x0)，y1=f(x1),构造线性插值函数的牛顿格式N1(x)使y0= N1 (x0)，y1= N1 (x1)。利用点斜式，构造N1(x)=a0+a1(x-x0)由f(x0)=N1 (x0)= a0)()(0101,10xxfxxxfxf=-a1= f(x1)= N1 (x1)= f(x0) +a1(x1-x0)得,10xxfN1 (x)= f(x0) + (x-x0)（3）二次牛顿插值设互异y0=f(x0)，y1=f(x1), y2=f(x2),构造二次牛顿插值多项式N2(x)使y0= N2(x0)，y1= N2(x1)，y2= N2(x2

12、)。令N2(x)=a0+a1(x-x0) +a2(x-x0) (x-x1)因在构造N1 (x)过程中已得a0和a1，只要求出a2即可由a2=,210xxxf,10xxff(x2)=N2(x2)= f(x0) + (x2-x0)+a2(x2-x0)(x2-x1)得,210xxxf,10xxfN2(x2)= f(x0) + (x2-x0)+ (x2-x0)(x2-x1)(4)一般情况设互异yi=f(xi)，i=0,1,n。构造n次牛顿插值多项式Nn(x)使yi= Nn(xi)，i=0,1,n,。根据差商定义插值公式和余项。上的在节点分别为、其中Newton)()()()(,.,).()(.,)(,

13、)()()(010110210101000ninnnnnxxfxR)(nxNxRxNxxxfxxxxxxxxxfxxxxxxfxxxfxf+=-+-+-+=,.,)().()(10110nnnxxxxfxxxxxxxx-+-)(n+1xN)(nxN,.,)().()(10110n+1nnxxxfxxxxxxxx-+-=分段插值（1）高阶插值与龙格现象构造插值多项式时，根据误差表达式，是否多取插值点比少取插值点好？不一定！若被插函数是多项式，则多取插值点比少取插值点好。但对某些函数，有时插值点越多，效果越不理想。例如给定225x11=x)f(+xÎ-1,1225x11,x(+ii)对-

14、1，1作等距分割，取h=2/10=0.2，xi= -1+0.2i， ，i=0，1，10。构造10次插值多项式L10(x),在0点附近, L10(x)近似f(x)的效果好，但在x=-0.90,-0.70, 0.70, 0.90时，误差较大！插值多项式在插值区间内有激烈振荡，这种现象称龙格现象。P29图2-4。龙格现象揭示了插值多项式的缺陷，表明高次多项式的插值效果不一定优于低次多项式的插值效果。插值误差由截断误差和舍入误差组成，由插值节点和计算产生的舍入误差，在插值过程中可能被扩散或放大，造成插值不稳定，高次多项式的稳定性一般比较差。（2）分段线性插值加密插值节点不一定能使插值函数很好逼近被插函

15、数，于是就有了分段线性插值的概念。基本思想：给定区间a，b，作分割a=x0<x1<<xn=b，在每个小xi，xi+1上做f(x)的以xi,xi+1为节点的线性插值。然后，把每个小区间上的线性插值函数连接起来得到f(x)的分段线性插值函数p(x)。几何上，p(x)是平面上以点(xi,f(xi)为折点的折线。X0X1P1(x)f(x)X2X3X4X5oX第三章 数据拟合知识点：曲线拟合，最小二乘法。离散数据曲线拟合（1）曲线拟合问题实践活动中，如果只能观测或测量到函数y=f(x)的一组离散的实验数据: (xi,yi)，i=,n。则当这些数据比较准确时，可以构造插值函数j(x)逼近

16、f(x),只要满足插值原则: j(xi)= yi (i=,n)如果离散数据序列(xi,yi)带有不可避免的误差（噪音）：插值原则限定可能使误差保留和扩散。如果在非插值节点处插值函数j(x)不能很好近似f(x)，误差可能很大。如果实验数据很多，因插值节点多,得到的插值多项式的次数较高：不仅计算量过大,而收敛性和稳定性不能保证,会出现龙格现象,逼近效果不好！于是，构造的逼近函数j(x)最优靠近样点（如图）成为理想选择，即向量T=（j(x0)， j(x1)，j(xn)）与Y=（y0，y1，。，yn）的误差和距离最小。按T和Y之间误差最小原则作为最优标准构造的逼近函数称拟合函数。2442·&

17、#183;······-4-2样点y=j(x)如何为f(x)找到一个既简单又合理的逼近函数j(x)？通常采用曲线拟合方法来处理，曲线拟合就是构造近似函数j(x)，在包含全部基节点xi (i=,n)的区间上能“最好”逼近f(x)，不必满足插值原则。这类问题称曲线拟合问题，近似函数y=j(x)称经验公式或拟合曲线或函数。拟合法则根据数据集(xi,yi)，i,n找出其间合适的数学公式，构造出一条反映这些给定数据一般变化趋势的曲线j(x)，不要求曲线j(x)通过所有的点(xi,yi)，但要求这条曲线j(x)能尽可能靠近这些数据点或样点，即各点

18、误差i=j(xi)-yi按某种标准达到最小。通常用误差的2-范数平方（均方误差或误差平方和）2220nii=dd作为总体误差的度量，以误差平方和达到最小最小二乘原理作为最优标准构造拟合曲线的方法为曲线拟合的最小二乘法。（2）多项式拟合线性拟合给定一组(xi,yi)， i=,n。构造线性拟合函数p1(x)=a+bx，使均方差22d20nii=d20ni=(p1(xi)-yi)20ni=(a+bxi-yi)=F(a,b) 达到最小。即如何选择a、b，使F(a,b) 达到最小，转化为求多元函数F(a,b)极小值问题。F(a,b)取极小值应满足0ni=(a+bxi-yi)=F(a,b)a020ni=(

19、a+bxi-yi)=F(a,b)b02xi整理得到拟合曲线满足=0ni=xiyiyi0ni=ba0ni=xin20ni=xi0ni=xi上式称为拟合曲线的法方程组或正则方程组。用消元法或克莱姆法则求解方程组得=a0ni=xi0i=xiyi-20ni=xi0ni=yin）（/n20ni=xi20ni=xi（）-（）bn0i=xiyiyi0ni=0ni=xin-（）n20ni=xi20ni=xi（）-（）=/得到均方误差意义下的拟合函数p1(x)。二次拟合给定一组(xi,yi)， i=,n。用二次多项式拟合这组数据。2设p2(x)= a 0+ a 1x+ a 2x，作出拟合函数与数据序列的均方误差

20、：=20ni=(a 0+ a 1xi+a2 xi -yi)F(a0,a1,a2)2(22d20nii=d)20ni=(p2(xi)-yi)类似线性拟合，根据最小二乘和极值原理:=00ni=(a 0+ a 1xi+a2 xi -yi)Fa 0220ni=(a 0+ a 1xi+a2 xi -yi) xiFa 122=00ni=(a 0+ a 1xi+a2 xi -yi) xiFa2222=0整理得到二次多项式函数拟合的法方程:=0ni=xin20ni=xi20ni=xi0ni=xi30ni=xi30ni=xi0ni=xi40ni=xi2a 1a 0a20ni=xiyiyi0ni=0ni=xiyi

21、2解法方程，便得到均方误差意义下的拟合函数p2(x)。不过当多项式的阶数n>5时，法方程的系数矩阵病态。计算中要用双精度或一些特殊算法以保护解得准确性。一般情况 0(x )mkj 0(x )mkj给定一组(xi,yi)， i=0,1 ,2,n。在函数类 （m<n）中寻求一个函数p(x)，使误差的2-范数平方达到最小。这里j0(x )，j 1 (x )，j m (x )是一组线性无关的连续函数，p(x)是 的线性组合。类似线性拟合处理。（3）例 用二次多项式拟合如下一组数据x-3-2-10123y4230-1-2-5解 设p2(x)= a 0+ a 1x+ a 2x²，经计

22、算得xyxyx²x ² yx³x-34-12936-2781-22-448-816-13-313-1100000001-1-11-1112-2-44-88163-5-159-45278101-3928-70196相应的法方程为:7 a 0 +0 a 1 +28 a 2=1 0 a 0 +28 a 1 +0 a 2=-3928 a 0 +0 a 1 +196 a 2=-7解方程得:a 0= 0.66667，a 1=-1.39286， a 2=-0.13095。2所以p2(x)= 0.66667-1.39286x-0.13095x22d217ii=d=217i=(p2

23、(xi)-yi)=3.09524拟合曲线均方误差:如何根据测量的数据设计和确定“最贴近”的拟合曲线？关键在于找到适当的拟合曲线类型，可以根据专业知识和工作经验确定拟合曲线类型。如果对拟合曲线一无所知，可以先绘制数据略图，可能从中观测出拟合曲线类型。一般情况下，应对数据进行多种曲线类型拟合，计算均方误差，用数学实验的方法找出最小二乘法意义下的误差最小的拟合函数。第六章 线性方程组的解法-直接法知识点：简单消元法，主元消元法，矩阵的三角分解。1.概 念（A）设线性方程组简记 AX=B, 其中代替所得。列用的第是，其中法则：BiAAADniDDxGrameriiiii)det(0A)det(D,.,

24、2,1=采用克来姆法则解方程组工作量非常大，寻求数值解成为必要，线性方程组的数值解法一般归结为两类.直接法：经过有限步算术运算，求得方程组的精确解（若在计算过程中没有舍入误差）。迭代法：用某种极限过程去逐步逼近线性方程组精确解。2.Gauss消去法古老的直接求解线性方程组的方法例 1.解方程组ïïîïïíì=+-=-=+)3(122)2(54)1(632132321xxxxxxxx11-225-1406111增广阵解 第一步：-2 x （1 ）+(3)得同解方程组ïïîïï&

25、#237;ì-=-=-=+)4(114)2(54)1(63232321xxxxxxx-11-1-405-1406111第二步：1 x （2 ）+ （4 ）得同解方程ïïîïïíì-=-=-=+)5(62)2(54)1(6332321xxxxxx-6-2005-1406111回代得解向量：x=1,2,3T(1)顺序Gauss消去法顺序消去未知数的方法。例2 .解方程组=+)3()2()1(6321=+-122321xxxxxx=-+133212xxx=+(5)4()1(6321=-11432xxxxx=-52323x

26、x解 第一步：用方程（1）消去（2），（3）中x1，即（1） x （-1 ）+(2)，（1） x （-2）+(3)，并保留（1）得第二步：用方程（4）消去（5）中x2，即（4） x （2 ）+(5)，并保留（1），（4）得上三角形方程组=+(6)4()1(6321=-2137xxxx=-52323xx回代得解：x=1,2,3T。0)(kkka求解过程中假设了变换后的同解方程组或等价矩阵的主对角元非零，即一般计算过程见教材P106-109. 建议认真阅读。.,)(即数值不稳定做除数易产生解的失真用此时kkka,0)(很小注kkka算法见教材110-111. 建议认真阅读。运算量见教材111。（2

27、）主元素 Gauss消去法列主元消去法：在一列中选取按模（绝对值）最大的元素，将其调到主干方程位置进行顺序消元的方法。例 3.用列主元消去法解方程组(强调选择列中绝对值最大元)=+-)3()2()1(15321=+6321xxx3x3x12x=-+-153-321xx18x(A|b)=1561113-312-153-1-186111153-312-153-1-1831/617/187/6057/3-10-153-1-1831/617/187/6057/3-10-153-1-1831/617/187/6066/722/700-153-1-181，2行交换2，3行交换消元消元回代得解：x=1,2,

28、3T Gauss列主元消元法一般形式第1步消元从第一列中选出按模最大的元素作为主元素:|ai1|=max|aj1|,1jn，交换第1行和第i行的所有元素，然后，顺序将a21,a31,a11,ai+1，1,an1变为零。第k步消元(k)nk.a.(k)kka1+(k)kka)(Ak从 的第k列 ， ， 中选取绝对值最大项，记录所在行，即kil=记=maxnikkakik|)(|kaki|)(|kl若 交换第k行与l行的所有对应元素，再进行顺序消元。建议认真阅读全主元消去法：在方程组整个系数矩阵A中选取绝对值最大的元素作为主元素，适当交换方程组中方程或未知数位置次序进行消元的方法。例4 .用全主元

29、消去法解例 3所示方程组，取四位有效数字。解 首先，三个方程的系数中绝对值最大者为-18（做主元），交换第一个方程与第二个方程的位置，以交换后的方程组（方程组形式学生课堂回答）的第一个方程为主干方程，消去其余两个方程中的x1（具体操作学生课堂回答），得=+-5.00032=+5.167320.944x1.167x2.333x x=-+-153-321xx18x然后，在方程组中的后两个方程中，再选取系数中绝对值最大者为主元，此时主元应为2.333。交换方程组中x2和x3位置，并消去x3得=5.0003=3.14421.572x2.333x-2 x=+-15-1-3x32x18x回代得解：x=1.

30、000,2.000,3.000T（3） 高斯-约当消去法高斯消元法将系数矩阵化为上三角矩阵，再进行回代求解。而Gauss-Jordan消去法是将系数矩阵化为对角矩阵，再进行求解，无回代过程见教材P112.。Gauss列主元消去法算法见教材P117，从算法优化的角度考虑， Gauss列主元消去法比较好。3.矩阵三角分解法LU分解相关信息见教材P118-123。建议认真阅读，有利巩固线性代数知识。4.误差分析教材P127，6.5节。范数基础另课介绍。回顾、阅读、理解与运用 ：P127范数，计算量统计，消去法一般解释115-117。第六章 线性方程组的解法-范数知识点：向量范数与矩阵范数及其性质，谱

31、半径，条件数。1.概念在一维数轴上，任意两点x1，x2之间距离用| x1-x2 |表示。在二维平面上，平面上任意两点P1(x1,y1),P2(x2,y2)的距离用表示。 推广到n 维空间，就有了向量范数的概念。2.向量范数且满足:x的范数。为向量则称，都有三角不等式：对任意齐次性：时，当且仅当非负性：法则对应于一非负实数按某一确定的设任一向量xxRRkkkRyxyxyxxxxxxxnn|,;|,|;0|00|,|,1定义1 +=（1）常见的向量范数（2）向量范数性质nnnnxxxRRxxyxyxyx-ba|,|R3,.,|,2121中定义的任意两种范数对性质的一致连续函数。是分量则向量范数设性

32、质。有对任意性质，一切范数都是等价的，即Mm,使得则必存在两正数nRMmxxxx"bab|nxxx11|1 例如 参阅P127定理6.1。（3）向量的收敛性（P128定理6.2）=设中一向量序列其中RkxxxnkkkknkTxx(1,2,.),.,()()1()2()()定义2*2*1*),.,2,1(lim),.,(xi(k)）iknTnnixxRxxx满足如果存在=*)(lim,xxxx(k)kk记作依次收敛到则称向量序列=-=如果有则称向量序列依范数收敛到k(k)kxxxxlim|0|*()*kk()*(1定理向量序列依坐标收敛到的充分必要条件是依范=xxxk)(1,2,.)数

33、收敛到。x*|事实上（）-=-=xxkkkinikiikixxxxin*1()()*lim|0limmax0lim(1,2,.)k3.矩阵范数的一种范数。为则称，相容性：三角不等式：，奇次性：时，当且仅当非负性且满足应于一非负实数若按某一确定的法则对设任意定义nnnnnnnnRARBABAABRBABABARkAkkAAAAARA""+=|,;,|,|;|;0|00|:|:|,|,.3（1）算子范数上的算子范数。算子范数是矩阵范数。为称设定义,|max|max|,41|0nnxxnnnRAxxAxARARx=单位矩阵的范数等于1（练习）。（2）相容范数是相容的。与此向量范数

34、则称该矩阵范数如果的一种范数和分别为设定义|,|,|5xAxAAxRRAxnnn（3）常见的矩阵范数（P129）=ppx),2,1(2相容的矩阵范数是与向量范数定理=-niijnjaA111|1max范数：（列和范数）=-TAAAmax2)(|2范数：l（谱范数）=-njijniaA11|max|范数：（行和范数）844.4466.23|534.1,466.2301710108|17101084212412264|2|,1|2max|54|1|,2|2max|:|2211=-=-=-=+-+=+-+=TTAAAIAAAA。，故解得由因为解lllll),2,1(|4212=-=ppAA求设矩阵例

35、题4矩阵的谱半径和矩阵序列收敛性Aini|max)(1lr=612,i(i,.,n)A定义设为矩阵的特征值则称的谱半径。为矩阵A关系。的任何一种范数有某种但可能与的一种范数不是的谱半径矩阵AAAA,)(r例题33)(33,3304212|421221+=-=+=-=-úûùêëé-=AAIArlllll所以。特征值得：解：由的谱半径。求矩阵(1)谱半径和矩阵序列的收敛性。则若的任意一种算子范数为这里则设定理AAAAAAAARATnn=|)(,;|,|)(,32rrxxx则的任一特征对，即为矩阵设证明AAAAxxxx=,llll。的任意性，有由，故有由于AAAx=max)(0lrllP129（6.35），P130（6.37）。(2)矩阵序列的收敛性。收敛于依范数则称矩阵序列如果记作收敛到矩阵则称矩阵序列如果及矩阵设矩