第二章牛顿插值法

数值分析第二章插值法均差与牛顿插值公式Lagrange插值多项式的缺点)(xljnjiiijixxxx0)()(nj,,2,1,0我们知道,Lagrange插值多项式的插值基函数为理论分析中很方便，但是当插值节点增减时全部插值基函数就要随之变化，整个公式也将发生变化，这在实际计算中是很不方便的；Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。两点直线公式((xk,yk)(xk+1,yk+1))11111111()()(()(kkkkkkkkkkkkkkyyLxyxxxxxxxxLxyyxxxx点斜式）两点式）考虑点斜式，两点为((x0,y0)(x1,y1)):1010010()()yyPxyxxxx在此基础上增加一个节点(x2,y2)，则过这三个点的插值多项式21()()()PxPxcxC(x)应是一个二次多项式。21()()()PxPxcx2010021111()()()()PxPxyPxPxy所以有0101()()0,()()()cxcxcxaxxxx所以C(x)应是一个二次多项式。根据插值条件根据插值条件：222()Pxy可以求出：221221221202120()()()()()()()pxpxypxaxxxxxxxx重新写p2(x)：21102120001102021010201001011021222021()()()()()()()()()()()()()()()PxPxcxyyyPxyxxxxxxxxxxxxaaxxaxxxxayyyaxxyPxaxxxx其中,ix设插值节点为nifi,,1,0,函数值为1,,2,1,0,1nixxhiiiiihhmaxnifxPii,,1,0,)(插值条件为具有如下形式设插值多项式)(xP01,,naaa其中……为待定系数基函数)())(())(()()(110102010nnxxxxxxaxxxxaxxaaxP)())(())(()()(110102010nnxxxxxxaxxxxaxxaaxPnifxPxPii,,1,0,)()(应满足插值条件000)(afxP有)()(011011xxaafxP00fa01011xxffa))(()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa再继续下去待定系数的形式将更复杂。。。。。。为此引入差商和差分的概念差商(亦称均差)/*divideddifference*/),()()(],[jijijijixxjixxxfxfxxf1阶差商/*the1stdivideddifferenceoffw.r.t.xiandxj*/)(],[],[],,[kixxxxfxxfxxxfkikjjikji2阶差商定义2.nifxxfii,,1,0,)(处的函数值为在互异的节点设11101010111010],,...,[],,...,[],,...,[],...,,[],...,[kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶差商)()()()()()(4433221100xfxxfxxfxxfxxfxxfxkk四阶差商三阶差商二阶差商一阶差商差商的计算方法(表格法):],[10xxf],[21xxf],[32xxf],[43xxf],,[210xxxf],,[321xxxf],,[432xxxf],,,[3210xxxxf],,,[4321xxxxf],,,[410xxxf规定函数值为零阶差商差商表差商具有如下性质:且的线性组合表示可由函数值阶差商的,)(,),(),(],,,,[)()1(10110kkkxfxfxfxxxxfkxf],,,,[110kkxxxxfkikiiiiiiixxxxxxxxxf0110)())(()()(Warning:myheadisexploding…Whatisthepointofthisformula?差商的值与xi的顺序无关！Newton插值公式及其余项],[)()()(000xxfxxxfxf],,[)(],[],[101100xxxfxxxxfxxf],...,,[)(],...,[],...,,[0010nnnnxxxfxxxxfxxxf12…………n+11+(xx0)2+……+(xx0)…(xxn1)n+1...))(](,,[)](,[)()(102100100xxxxxxxfxxxxfxfxf))...(](,...,[100nnxxxxxxf))()...(](,...,,[100nnnxxxxxxxxxfNn(x)Rn(x)ai=f[x0,…,xi]Newton插值公式及其余项ix0x1x2x3x[]ifx0()fx1()fx2()fx3()fx1[,]iifxx01[,]fxx12[,]fxx23[,]fxx12[,,]iiifxxx012[,,]fxxx123[,,]fxxx123[,,,]iiiifxxxx0123[,,,]fxxxx00100121001110()()()[,]()()[,,]()()()[,,,]nnnPxfxxxfxxxxxxfxxxxxxxxxfxxxNewton插值公式及其余项例：已知x=1,4,9的平方根为1,2,3，利用牛顿基本差商公式求的近似值。ix149ix1231[,]iifxx2103333341.320294.12[,,]iiifxxx0203333300166791...7解：从而得二阶牛顿基本差商公式为21033333100166714().().()()Pxxxx27269992()..P因此计算得的近似值为7复习：多项式插值问题：寻找一个n次多项式，满足下列插值条件：niyxPiin,,2,1,0)(函数()yfx在插值节点上的取值为：bxxxxan210(),0,1,,iifxyinLagrange插值方法0()()nniiiPxlxynjijjijixxxxxl0)()()(其中：余项公式：(1)1()()()(1)!nnnfRxxn)())(()(101nnxxxxxxxNewton插值方法00100120101011()()[,]()[,,]()()[,,,]()()()nnnnNxfxfxxxxfxxxxxxxfxxxxxxxxx其中：12011010[,,,][,,,][,,,]kkkkfxxxfxxxfxxxxx余项公式：00101()[,,...,]()...()()[,,...,]()nnnnnnRxfxxxxxxxxxfxxxx性质3P32练习7401701831[2,2,,2][2,2,,2]fxxxff已知，求及()fx分析：本题是一个多项式，可利用差商的性质解：由差商与导数之间的关系(7)017()7![2,2,,2]177!ff！(8)018()0[2,2,,2]088!ff！上面我们讨论了节点任意分布的插值公式，但实际应用时经常会遇到等距节点的情形，这时插值公式可以进一步简化，计算也简单多了，为了给出等距节点的插值公式，我们先来看一个新概念；称处的函数值为在等距节点设,,,1,0,)(0nkfkhxxxfkkkkkfff1处的一阶向前差分在为kxxf)(1,,1,0nk1kkkfff处的一阶向后差分在为kxxf)(nk,,2,11122(/2)(/2)kkkkkffxhfxhff()kfxx为在处的中心差分向前向后中心差分算子不在函数表上，要用到函数表上的值111122,kkkkkkffffffkkkfff12处的二阶向前差分在为kxxf)(12kkkfff处的二阶向后差分在为kxxf)(利用一阶差分可以定义二阶差分差分kmkmkmfff111阶向前差分处的在为mxxfk)(阶向后差分处的在为mxxfk)(111kmkmkmfff可以用归纳法证明mkmkmff1kkff222kkff333kkff如差分4433221100fxfxfxfxfxfxkk四阶差分三阶差分二阶差分一阶差分0f1f2f3f02f12f22f03f13f04f差分表4f3f2f1f42f32f22f43f33f44f差分与函数值之间的关系010121232,,,yyyyyyyyy201021021213212232432222yyyyyyyyyyyyyyyyyy2222()abaabb1()abab322010321032212143213222325432333333yyyyyyyyyyyyyyyyyyyyy3223333()abaababb433010432104331215432143323265432464464464yyyyyyyyyyyyyyyyyyyyyyyy4322443464()abaabababb归纳可知，k阶差商可表示为01111kiikikiikkkkkkyyyCCyCCy在等距节点的前提下,差商与差分有如下关系],[1iixxfhfi],,[21iiixxxf212hffii222hfihfi12212hfxfii2222hfiiiiixxff112211],[],[iiiiiixxxxfxxf],,,[321iiiixxxxf312223hffii33!3hfi332121],,[],,[iiiiiiiixxxxxfxxxf3322223hfxfii333!3hfi],,,[1miiixxxf依此类推mimhmf!mmimhmf!],,,[10kxxxfkkhkf!0kkkhkf!即是等距节点如果节点,,,,10nxxxnabhnkkhxxk,,,1,0,0],,,[10kxxxfkkhkf!0由差商与向前差分的关系)(xNnnkkkxxxxff1100)(],,,[Newton插值基本公式为如果假设thxx01.Newton向前(差分)插值公式10)(kjjxx)(xk1000)(kjjhxthx10)(kjhjtkkhkf![0nkf10])(10kjhjt![0kfknkf10])(10kjjt)(xNnnkkkxxxxff1100)(],,,[)(0thxNn)(xRn)()!1()(1)1(xnfnn则插值公式化为其余项)(0thxRn)!1()()1(nfnnjnjth01)(化为)(0thxRn)!1()()1(nfnnjnjth01)(![0k