数值分析知识内容 (26).pdf

《数值分析知识内容 (26).pdf》由会员分享，可在线阅读，更多相关《数值分析知识内容 (26).pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5.2 最佳一致逼近 设,)(baCxf，)(xf的范数定义为)(max)(xfxfbxa，则)(xf与)(xPn在范数意义下的距离定义为)()(max)()(xPxfxPxfnbxan.（6.1）5.2.1 最佳一致逼近问题 【定理 1】（Weierstrass 定理）设,)(baCxf，则对于任意给定的0，总存在多项式)(xp，使成立)()(xpxf.【注】Weierstrass 逼近定理(Weierstrass Approximation Theorem)说明，连续函数)(xf可以用多项式)(xp逼近到任意精确的程度.因此，我们希望寻找一个逼近)(xf最快的n次多项式的方法.首先引入偏差

2、(Deviation)概念.【定义 1】设,)(baCxf，对于n次多项式)(xPn，称)()(max)()(xPxfxPxfnbxan 为)(xf与)(xPn在区间,ba上的偏差.记),(10naaaI=)()(maxxPxfnbxa，若,0bax 使)()(max)()(00 xPxfxPxfnbxan，则称0 x点为偏差点.函数),(10naaaI的最小值称为)(xf与)(xPn的最小偏差，记为nE，即)()(maxmin),(min10 xPxfaaaIEnbxaanankk，（6.2）称达到最小偏差的多项式为最佳一致逼近多项式.满足（6.2）式的点0 x为最小偏差点.【注】最佳一致逼

3、近多项式这个问题，首先由切比雪夫提出并加以研究，他获得了重要的切比雪夫定理.这一定理指出了最佳一致逼近的特征，并解决了解的存在唯一性问题.5.2.2 最佳一致逼近的存在唯一性 【定理 2】设,)(baCxf，则总存在最佳一致逼近多项式)(xPn.证明省略.定理 2 指出，存在最小偏差点0 x，使)()(00 xPxfEnn.其中，正偏差点0 x满足：)()(00 xfxPEnn；负偏差点0 x满足：)()(00 xfxPEnn.【定理 3】最佳一致逼近问题同时存在正偏差点和负偏差点.定理 3 的证明省略，通过具体求解下面的零次、一次最佳一致逼近来理解.一、零次最佳一致逼近 设AxP)(0（A为

4、某常数）为)(xf的最佳一致 逼近多项式.因为,)(baCxf，因而有最大值M 和最小值m，即有点21xx 和，使Mxfmxf)(,)(21.显然，2mMA，见图 6-1.图 6-1 零次最佳一致逼近示意图 事实上，由于2)(,2)(21mMxfAmMxfA，而对任何,bax,2)(2mMxfAmM，即2mM 为最小偏差，21,xx为正、负偏差点.二、一次最佳一致逼近 图 6-2 一次最佳一致逼近示意图 设,)(2baCxf且)(xf 不变号.不妨设0)(xf，此时根据图 6-2，所求)(1xP即为平行于弦 MN 的直线，且满足)()(maxmin101xaaxfEbxaai.由于0 f，f

5、必单调增加，而偏差点必在)()(1xPxf的最大、最小值点达到，因此，两端点和使01Pf的点都是偏差点.即有)3.)()2),()()()1),()()()(12221011010110axfxfxaaEaaaafbaabfEaaaaf 由方程 1)解出abafbfa)()(1.由方程 2)解出22)()(2120 xaaxfafa，其中2xP0(x)=A y M m a b x 由12)(axf求出.从而xaaxP101)(为所求一次最佳一致逼近多项式，其几何意义如图 6-2 所示.直线xaaxP101)(与弦 MN 平行，且通过 MQ 的中点.【注】0n时，零次多项式逼近有两个偏差点；1n

6、时，一次逼近有三个偏差点，且偏差点正、负交替出现.切比雪夫发现了最佳一致逼近多项式存在的条件.【定理 4】（切比雪夫定理）n次多项式)(xPn是,)(baCxf的最佳一致逼近多项式的充要条件是，,ba上存在2n个点所构成的点组bxxxan221，它们交替为正、负偏差点.【注】定理中的2n个交替的正、负偏差点称为切比雪夫交错点组.【推论 1】设,)(baCxf，则在小于等于n次的多项式集合nH中，存在唯一的多项式)(xPn最佳一致逼近)(xf.证明 假定nH中存在两个不同的最小偏差多项式)(xPn，)(xQn，则对,bax有 nnnnnnExfxQEExfxPE)()(,)()(，从而 nnnn

7、ExfxQxPE)(2)()(，即2/)()()(xQxPxSnn也是nH中)(xf的最小偏差多项式.根据切比雪夫定理，存在2n个点，构成交错点组221nxxx,使得对nE，有 iininixQxPxf)1(2/)()()(，即iiniinixQxfxPxf)1()()(21)()(21.由于方括号内的数的绝对值都不超过nE，可见 iiniinixQxfxPxf)1()()()()(.因此，)(xPn和)(xQn在2n个点处相等，这与)(xPn，)(xQn都是n次多项式且不相同发生矛盾，因此证明了唯一性.【推论 2】若)()1(xfn在),(ba内存在，且)()1(xfn不变号，则a和b都是交

8、错点组中的点.证明 用反证法.设b（或a）不属于交错点组.由切比雪夫定理，,ba内至少存在2n个点构成交错点组，因而)(xPn-)(xf至少在),(ba内 有1n个 最 大、最 小 值 点，即 有2iabnn1,使1,1,0,0)()(nkfPkkn.反复对)(xPn-)(xf应用 Rolle 定理，则至少有一点),(ba使 0)()()()1()1()1(nnnnffP，这与)()1(nf保号矛盾，即结论为真.5.2.3 最佳一致逼近多项式的解法 设)(xf的最佳一致逼近多项式为)(xPn=nkkkxa0，由切比雪夫定理及推论，),1,0(nkak、偏差nE及交错点组bxxxxann2121

9、满足.2,2,1,0)()()(,)()(22nkxPxfbxaxExPxfknkkknknk （6.3）【注】（1）理论上求最佳一致逼近多项式的方法转化为求解非线性方程组（6.3），其精确求解是困难的，可以利用迭代方法求其数值解.例如采用 Remes 逐次逼近算法，构造偏差点组)(ix，逐次逼近切比雪夫交错点组，当i时，相应的多项式系数收敛),2,1,0()(nkaakik.（2）实际计算时，常用切比雪夫多项式求近似最佳一致逼近多项式，具体方法见下节.5.3 切比雪夫多项式及其应用 本节利用切比雪夫正交多项式（Chebyshev Polynomials），研究多项式的最佳一致逼近算法、近似最

10、佳一致逼近算法.首先介绍正交多项式(Orthogonal Polynomials)的基本概念.5.3.1 正交多项式 【定义 2】若非负函数)(x在,ba上满足条件（1）对一切0n，bandxxx)(存在；（2）对非负连续函数)(xf，若0)()(badxxfx，则在,ba上0)(xf.那么，称)(x为,ba上的权函数.【定义 3】给定,)(),(baCxgxf,)(x是),(ba上的权函数，称 badxxgxfxgf)()()(),(为f与g在),(ba上的内积.内积的性质：(1),(),(fggf；(2),(),(),(gfkkgfgkf，k为常数；(3),(),(),(2121gfgfg

11、ff；(4)当0)(xf时，0),(ff.【定义 4】若f与g的内积badxxgxfxgf)()()(),(=0，则称)(xf与)(xg在区间,ba上带权)(x正交.【注】（1）若函数序列),(),(),(10 xxxn满足 baijijijiajidxxxx.,0,0)()()(),(则称i是,ba上关于权)(x的正交函数序列(Orthogonal Set of Functions).（2）当正交函数序列的)(xi是i（,2,1,0i）次多项式时，则称)(xi是,ba上关于权函数)(x的正交多项式序列.（3）正交多项式序列一定是线性无关序列.5.3.2 切比雪夫多项式及其性质 切比雪夫正交多

12、项式可表示为 1),arccoscos()(xxnxTn.（6.4）【定理 5】)(xTn是最高次幂系数为12n的n次多项式.令xarccos，则有恒等式 10)(13,2,1,coscos2cos)(nkknknnnnnxT，（6.5）其中)1,1,0()(nknk为某些常数.证明 1n时（6.5）式显然成立.假设mn 时（6.5）式成立，即 10)(1coscos2cosmkkmkmmm,（6.6）则当1 mn时，由三角恒等式 2cos2cos2coscos，得到 mmmcoscos2)1cos()1cos(.（7）将（6.6）式代入，得到 10)(10)(1coscoscos2cos2)

13、1cos(coscos2)1cos(mkkmkmkkmkmmummm mkkkmmu01coscos2，其中ku由合并cos同次幂系数得到.依归纳法，对任意自然数n，（6.5）式都成立.)(xTn是最高次幂系数为12n的n次多项式，即)(xTn=10)(11,2nkknknnxxx.利用（6.7）式可得切比雪夫多项式的三项递推关系.【性质 1】xxTxT)(,1)(10,2,1),()(2)(11nxTxxTxTnnn.由性质 1 直接得到前面几个切比雪夫多项式为,34)(,12)(,)(,1)(332210 xxxTxxTxxTxT,52016)(,188)(355244xxxxTxxxT

14、显然有【性质 2】n为偶数时)(xTn是偶函数；而n为奇数时)(xTn是奇函数.从公式（6.4）直接得到)cos()arccoscos()(nxnxTn.零 点 为2 kn，即),2,1(,212nknk；极 值 点 为kn，即),1,0(,nknk.【性质 3】（1）)(xTn在-1，1上的n个零点为),2,1(,212cosnknkxk；（2）)(xTn的极值点为),1,0(cosnknkxk，其极大、极小值交替为1.利用正交多项式的概念，又得到【性质 4】在区间-1，1上，多项式序列0)(nnxT关于权函数212)1()(xx为正交多项式序列，即有.0,0,2,01)()(112nmnm

15、nmdxxxTxTnm 证明 由切比雪夫多项式及正交概念，有 11)()()(dxxTxTxnm=dxxxTxTnm1121)()(=0)sin(sincoscosdnm=0.0,0,2,0coscosnmnmnmdnm 因此结论成立.5.3.3)(xf为多项式时的逼近方法 将切比雪夫多项式改写为)()()()(21111xPxfxPxxTnnnnn，其中10)(112)(nkknknnxxP，利用极大值性质，有 111111121)(max0)(21maxnnnxnnxxPxxT，即)(1xPn与nx的偏差为121n.由切比雪夫定理可知，)(1xPn为nx的最佳一致逼近多项式 存在1n个交错

16、点组.因此有下面定理.【定理 6】在最高次项系数是 1 的一切n次多项式中，于区间-1，1上与零有最小偏差的多项式为121n)(xTn.定理 6 又指出：)(1xPn是nx的最佳一致逼近多项式，且)(21)(11xTxxPnnnn.（6.8）例 2 利用切比雪夫多项式，求12)(23xxxxf在-1，1上的二次最佳一致逼近多项式)(2xP.解)(xf是三次多项式，利用式)(21)(11xTxxPnnnn，有 xxxTxPxf43)(21)()(33132，所以 141143)()(232xxxxxfxP.5.3.4 近似最佳一致逼近算法 近似最佳一致逼近算法，即 Lagrange 插值余项极小

17、化方法.设在-1，1上)(xf的Lagrange 插值多项式为)(1xLn,则有余项)(!)()()()(1xwnfxLxfnnn，其中节点为),2,1(nkxk，)()()(1nnxxxxxw.如果以任意节点做插值，)(1xLn不可能一致逼近)(xf.但经适当的安排节点，再利用切比雪夫多项式使余项达极小，就能近似地得到最佳一致逼近多项式的插值算法.由定理 6可知，区间-1，1上使余项极小化（即与零有最小偏差）的多项式为121n)(xTn，取)(21)()()(11xTxxxxxwnnnn.插值节点为切比雪夫多项式的零点，即),2,1(212cosnknkxk，因此，111121!)()(ma

18、xnnnxnMxLxf，其中)(max)(11xfMnxn.【注】在区间-1，1上，取切比雪夫多项式的零点为插值节点，得到的)(1xLn是)(xf的近似最佳一致逼近多项式.一般地，对于,)(baCxf，令tabbax22，则 1,1t，从而把,ba上的)(xf化为)22(tabbaf在区间-1，1上的插值问题.此时，)22()()()(1tabbawxxxxxwnnn)(2)()()(2)(21twabttttttabnnnnnn.只要选取),2,1(212cosnknktk，即节点为 nknkabbaxk,2,1,212cos22，就能使 121112)(!)(max2)(!)()(maxn

19、nnntnnnnbxaabnMtwabnMxLxf.例 3 求函数4/)(xexf在0，1上的近似最佳一致逼近多项式，使其误差不超过4105.解 1）确定多项式的次数：因为nhnnxneMexf4/2840.14/,4/)(4/14/)(，nnnxnnxLxfxR42!2840.1)()(max)(121101，所以只要取3n，则满足4121105)42!/(2840.1)(nnnnxR.2）确定插值节点：由3,2,1),612cos1(21kkxk，得插值节点为 06699.0,5000.0,93301.0321xxx.3）用 Lagrange 插值公式得到4/xe的近似最佳一致逼近多项式

20、001.12484.003544.0)(22xxxL.例 4 在区间41，上求下面函数的近似最佳一致逼近多项式.2sin1xexxxf.首先编写被逼近的函数 m 文件：Uniformfun.m.function f=Uniformfun(x)f=(1+x).*exp(-x.2).*sin(x);编写近似最佳一致逼近多项式的计算程序：Uniformopt.m.%Uniformity Optimal Approximation f=(1+x).*exp(-x.2).*sin(x);clear all n=input(Input the degree of approximation polynom

21、ial:n=)a=input(Input the end point of interval a=)b=input(Input the end point of interval b=)x=a:0.001*(b-a):b;f=feval(Uniformfun,x);for i=0:n+1;xk(i+1)=(2.(a+b+(b-a).*cos(n+1).(n-i+1)*pi);end xk=fliplr(xk);y=feval(Uniformfun,xk);L=ones(length(y),length(x);for i=1:n+1;for j=1:n+1;if j=i L(i,:)=(xk(i

22、)-xk(j).(x-xk(j).*L(i,:);else L(i,:)=L(i,:);end end end PN=y*L;plot(x,f,x,PN,-.),axis equal title(Suboptimal Uniformity Approximation)legend(f(x)=sinx(1+x)exp(-x2),Optimal Uniformity Approximation Polynomial)运行程序 Uniformopt.m.根据程序提示，分别输入 n=8，n=10，输入 a=1，b=4，得到近似最佳一致逼近多项式图形，见图 6-3，左图为 n=8，右图为 n=10.11.522.533.54-0.500.51Suboptimal Uniformity Approximationf(x)=sinx(1+x)exp(-x2)Optimal Uniformity Approximation Polynomial11.522.533.54-0.500.51Suboptimal Uniformity Approximationf(x)=sinx(1+x)exp(-x2)Optimal Uniformity Approximation Polynomial 图 6-3 近似最佳一致逼近（左图 n=8，右图 n=10）