2016年4月 扩充话题大版内专家分月排行榜第二2015年10月 扩充话题大版内专家分月排行榜第二2015年9月 扩充话题大版内专家分月排行榜第二
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。第3章数值分析_学霸学习网
第3章数值分析
第3章函数逼近与快速傅里叶变换3.1 函数逼近的基本概念 3.2 正交多项式 3.3 最佳平方逼近 3.4 曲线拟合的最小二乘法 3.5 有理逼近 3.6 三角多项式与快速傅里叶变换13.13.1.1问题函数逼近的基本概念函数逼近与函数空间1、数值计算中经常要计算函数值，如计算机中计算 基本初等函数及其他特殊函数； 2、当函数只在有限点集上给定函数值，要在包含该 点集的区间上用公式给出函数的简单表达式. 这些都涉及到在区间 [a, b] 上用简单函数逼近已知复杂 函数的问题，这就是函数逼近问题.2插值法就是函数逼近问题的一种. 本章讨论的函数逼近，是指“对函数类 A 中给定的函数f (x), 记作 f ( x) ? A ， 要在另一类简单的便于计算的函数类B 中求函数 p( x) ? B ，使 p (x)与 f (x) 的误差在某种度量意义下最小”. 函数类 A通常是区间 [a, b] 上的连续函数，记作 C[a, b] ， 称为连续函数空间.3函数类 B通常为 n 次多项式，有理函数或分段低次多项式等.数学上常把在各种集合中引入某些不同的确定关系称为 赋予集合以某种空间结构，并将这样的集合称为空间. 例如将所有实 n维向量组成的集合，按向量加法及向量 与数的乘法构成实数域上的线性空间， 记作 R n， 称为 n 维向量空间.4对次数不超过 n( n为正整数)的实系数多项式全体， 按通常多项式与多项式加法及数与多项式乘法也构成数域 用 R上一个线性空间， H n表示，称为多项式空间.所有定义在 [a, b] 上的连续函数集合，按函数加法和数与函数乘法构成数域 R 上的线性空间，记作 C[a, b]. 类似地, 记 C p [a, b]为具有 p 阶连续导数的函数空间.5定义1设集合 S 是数域 P上的线性空间，元素x1 ,?, xn ? S , 如果存在不全为零的数 ?1 ,?, ? n ? P ，使得?1 x1 ? ? ? ? n xn ? 0,则称 x1 , ?, xn 线性相关.（1.1）否则，若等式(1.1)只对 ?1 ? ? 2 ? ? ? ? n ? 0成立， 则称 x1 , ?, xn线性无关.6若线性空间 S 是由 n 个线性无关元素 x , ?, x 生成的， 1 n 即对? x ? S 都有 ? x ? ?1 x1 ? ? ? ? n xn 则 x1 , ?, xn 称为空间 S 的一组基，记为S ? span{x1 ,?, xn }并称空间 S 为 n 维空间，系数 ?1 ,?, ? n 称为 x 在基x1 , ?, xn下的坐标， 记作 (?1 ,?, ? n ).如果 S 中有无限个线性无关元素 x1 ,?, xn ,?, 则称 S 为无限维线性空间.7考察次数不超过 n次的多项式集合 H n， 其元素p( x) ? H n 表示为p( x) ? a0 ? a1 x ? ? ? an x n ,它由 n ? 1 个系数 (a0 , a1 ,?, an ) 唯一确定.（1.2）1, x,?, x n是线性无关的， 它是 H n 的一组基，故H n ? span{1, x, ?, x n },且 (a0 , a1 ,?, an ) 是 p (x) 的坐标向量，H n 是 n ? 1维的.8对连续函数 f ( x) ? C[a, b]，它不能用有限个线性无关的 函数表示，故 C[a, b] 是无限维的，但它的任一元素 f (x) 均可用有限维的 p( x) ? H n 逼近，使误差max f ( x) ? p( x) ? ?a ? x ?b( ?为任给的小正数)，这就是著名的魏尔斯特拉斯定理.9定理1设 f ( x) ? C[a, b] ， 则对任何 ? ? 0 ，总存在一个代数多项式 p (x) ， 使f ( x) ? p ( x )???在 [a, b] 上一致成立. 伯恩斯坦1912年给出的证明是一种构造性证明. 他根据函数整体逼近的特性构造出伯恩斯坦多项式k Bn ( f , x) ? ? f ( ) Pk ( x) n k ?0n（1.3）10其中?nf k Bn ( f , x) ? ? ? ( k ) Pk ( x) ? k Pk ( x) ?k? 0 ? x n(1 ? x) n , ? ? ? ?k ?n（1.3）? n ? n(n ? 1) ? (n ? k ? 1) ? ?? ?k ? k! ? ?n ??为二项式展开系数，并证明了lim Bn ( f , x) ? f ( x) 在 [0,1] 上一致成立；若 f (x) 在 [0,1] m阶导数连续，则 上( lim Bnm) ( f , x) ? f n ?? ( m)( x).这个结果不但证明了定理1，而且由(1.3)给出了 f (x) 的一个逼近多项式，但它收敛太慢，实际中很少使用.11更一般地，可用一组在 C[a, b] 上线性无关的函数集合??i ( x) ?in?0 来逼近 f ( x) ? C[a, b]，此时元素? ( x) ? ? ? span{?0 ( x), ?1 ( x), ?, ?n ( x)} ? C[a, b]可表示为? ( x) ? a0?0 ( x) ? a1?1 ( x) ? ? ? an?n ( x).（1.4）函数逼近问题就是对任何 f ( x) ? C[a, b]， 在子空间Φ 中?* * 找一个元素 ? ( x) ? ?， 使 f ( x) ? ? ( x)在某种意义下最小.123.1.2范数与赋范线性空间为了对线性空间中元素大小进行衡量，需要引进范数 定义，它是 R n空间中向量长度概念的直接推广. ?13定义2设 S为线性空间， ? S ，若存在唯一实数‖? ‖， x满足条件：x （1） ? ? 0, 当且仅当 x ? 0 时， x ? 0; （正定性）（2） （3）?x ? ? x ,? ? R;(齐次性)x? y ? x ? y ,x, y ? S . (三角不等式)?则称‖?‖为线性空间 S上的范数，S 与‖?‖一起称为赋范 线性空间，记为 X .14例如，在 R n上的向量 x ? ( x1 , ?, xn )T ? R n , 三种常 用范数为xxx?? max xi ,1?i ? nn称为 ? 范数或最大范数， 称为 1-范数，1??i ?1nxi ,1 22? (? xi2 ) ,i ?1称为 2-范数.15实际上任何向量的实值函数，只要满足上述三个条件， 就可以定义成一种向量范数. 在 R 中，满足‖? 2 =1 ，即 x1 ? x2 ‖22 2? 1的向量为单位圆， 满足‖? ∞ =1 ，即 max{ x1 , x2 } ? 1的向量为单位正 ‖ 方形， 而满足‖? 1 =1 的向量 x1 ? x2 ? 1 则为对角线长 ‖ 度为1的菱形.16所以说，范数是对向量长度的度量，度量方式不同， 结果也不一样，但不同范数之间是存在等价关系的.17类似地，对连续函数空间 C[a, b] ，若 f ( x) ? C[a, b] ,可定义三种常用范数如下：?ff?? max f ( x) ,a ? x ?bb称为 ? 范数， 称为 1-范数，1 21??af ( x) dx,bf2? ( ? f 2 ( x) dx) ,a称为 2-范数.可以验证这样定义的范数均满足定义2中的三个条件.183.1.3内积与内积空间在线性代数中， R n中两个向量 x ? ( x1 , ?, xn )T 及y ? ( y1 , ?, yn )T 的内积定义为( x, y) ? x1 y1 ? ? ? xn yn .（1.5）若将它推广到一般的线性空间 X，则有下面的定义.19定义3 X 是数域K(R或C)上的线性空间，对?u, v ? X, 有K中一个数与之对应，记为 (u , v) ，它满足以下条件：(1)(2) (3)(4)(u, v) ? (v, u ),?u, v ? X;(?u, v) ? ? (u, v),? ? K, u, v ? X;?u, v, w ? X;(u ? v, w) ? (u, w) ? (v, w),(u, u) ? 0,当且仅当u ? 0 时， , u) ? 0. (u则称 (u, v)为X上 u 与 v 的内积.20定义了内积的线性空间称为内积空间. 定义中（1）的右端 (u , v) 称为 (u, v) 的共轭， 当K为实数域R时 (u, v) ? (v, u ).? 如果 (u, v) ? 0 ，则称 u与 v 正交，这是向量相互垂直概念的推广.21定理2 设X为一个内积空间， 对 ?u, v ? X , 有(u , v) ? (u , u )(v, v).2（1.6）称为柯西-施瓦茨(Cauchy-Schwarz)不等式.证明当 v ? 0 时（1.6）式显然成立.现设 v ? 0 ，则 (v, v) ? 0， 且对任何数 ? 有0 ? (u ? ?v, u ? ?v) ? (u, u ) ? 2? (u, v) ? ?2 (v, v).代入上式右端，得 取 ? ? ?(u, v) /( v, v) ，22(u, u ) ? 2(u, v)2(v, v)?(u, v)2(v, v)?0即得 v ? 0时(u , v) ? (u , u )(v, v).223定理3矩阵u 设X为一个内积空间， 1 , u2 ,?, un ? X,? (u1 , u1 ) ?(u , u ) G?? 1 2 ? ? ? ?(u1 , u n )(u 2 , u1 ) (u 2 , u 2 ) ? (u 2 , u n )? ? ?(u n , u1 ) ? (un , u 2 ) ? ? ? ? ? (u n , u n )?（1.7）称为格拉姆(Gram)矩阵，?? 则 G 非奇异的充分必要条件是 u1 , u2 ,?, un 线性无关.24证明 方程组G非奇异等价于 det G ? 0，其充要条件是齐次(? ? j u j , uk ) ? ? (u j , uk )? j ? 0, k ? 1,2, ?, n（1.8）j ?1 j ?1nn只有零解； 而??j ?1nju j ? ?1u1 ? ? 2u2 ? ? ? ? nun ? 0 ? (? ? j u j , ? ? j u j ) ? 0j ?1 n j ?0 n n（1.9）? (? ? j u j , uk ) ? 0,j ?0k ? 1,2, ?, n25从以上等价关系知，det G ? 0 等价于从（1.8）推出?1 ? ? 2 ? ? ? ? n ? 0,n n 而后者等价于从（1.9）推出 ?1 ? ? 2 ? ? ? ? n ? 0, (? ? j u j , uk ) ? ? (u j , uk )? j ? 0, k ? 1,2, ?, n（1.8） j ?1 j ?1 即 u1 , u2 ,?, un 线性无关.在内积空间X上，可以由内积导出一种范数，即对于? ?? u ? ? u ? ? u ? ? ? ? u ? 0u ? X, 记u ? (u, u )j ?1 j j 1 1 2 2 n nn（1.10）26利用(u ? v) ? u2 2?2 u v ? v2? (u, u ) ? 2(u, v) ? (v, v)? (u ? v, u ? v) ? u ? v2两端开方即得三角不等式u?v ? u ? v（1.11）27例1 设R n 与 C n的内积.T x, y ? R n , x ? ( x1 , ?, xn )T , y ? ( y1 , ?, yn ) ,( x, y ) ? ? xi yii ?1n（1.12）向量2-范数为x ? ( x, x) ? (? xi2 )i ?1 1 2 n 1 2228若给定实数 ?i ? 0(i ? 1,2,?, n), 称{?i } 为权系数，R n 上的加权内积为( x, y ) ? ? ?i xi yii ?1 n（1.13）相应的范数为x2? (? ?i xi2 ) .i ?1n1 2当 ?i ? 1(i ? 1,2,?, n) 时， （1.13）就是前面定义的内积.29如果 x, y ? C n，带权内积定义为( x, y ) ? ? ?i xi yii ?1 n（1.14）这里 {?i } 仍为正实数序列，yi 为 yi 的共轭. 在 C[a, b]上也可以类似定义带权内积.30定义4设 [a, b] 是有限或无限区间，在 [a, b] 上的非负函数 ? (x)满足条件： （1） ?a x k ? ( x)dx 存在且为有限值 (k ? 0,1, ?), ?b（2） 对 [a, b] 上的非负连续函数 g (x) ，如果?则?( x) ? 0. gbag ( x) ? ( x)dx ? 0,则称 ? (x) 为[a, b]上的一个权函数.31例2 C[a, b] 上的内积.设 f ( x), g ( x) ? C[a, b], ? (x) 是 [a, b] 上给定的权函数,则可定义内积( f ( x), g ( x)) ? ? ? ( x) f ( x) g ( x)dx.a b（1.15）由此内积导出的范数为f ( x)? b ? ( x) f 2 ( x) dx ? ? ( f ( x), f ( x)) ? ? ? a ? （1.16） ? ?1 21 22称（1.15）和（1.16）为带权 ? (x) 的内积和范数.32常用的是 ? ( x) ? 1 的情形，即( f ( x), g ( x)) ? ? f ( x) g ( x)dx.a bf ( x)2? b f 2 ( x) dx ? ? ? ? a ? ? ?1 233若 ?0 , ?1 ,?, ? n是 C[a, b]中的线性无关函数族，记? ? span{?0 , ?1 ,?, ?n }, 它的格拉姆矩阵为G ? G(?0 , ?1 , ?, ? n )?(? 0 , ? 0 ) ? (? , ? ) ?? 1 0 ? ? ? ?(? n , ? 0 ) (? 0 , ?1 ) (?1 , ?1 ) ? (? n , ?1 ) ? ? ? (? 0 , ? n ) ? (?1 , ? n ) ? ? ? ? ? (? n , ? n ) ?（1.17）根据定理3可知 ?0 , ?1 ,?, ? n 线性无关的充要条件是det G(?0 , ?1 ,?, ? n ) ? 0.343.1.4最佳逼近函数逼近主要讨论给定 f ? C[a, b]，求它的最佳逼近 多项式的问题. 若 P* ( x) ? H n使误差f ( x) ? P* ( x) ? min f ( x) ? P( x)P?H n则称 P* ( x) 是 f (x)在 [a, b]上的最佳逼近多项式.若 P( x) ? ? ? span{?0 , ?1 ,?, ?n }则称相应的 P* ( x)为最佳逼近函数. 通常将范数 ? 取为 ??或 ? 2.35若取 ? ，即 ?f ( x) ? P * ( x)?? min f ( x) ? P( x)P?H n P?H n a ? x ?b?（1.18）? min max f ( x) ? P( x) ,则称 P* ( x) 是 f (x)在 [a, b]上的最优一致逼近多项式. 求 P* ( x)就是求 [a, b]上使最大误差 max f ( x) ? P( x)a ? x ?b最小的多项式.36若取 ? ，即 2f ( x) ? P * ( x)2 2? min f ( x) ? P( x)P?H n2 2（1.19）? minP?H n?ba[ f ( x) ? P( x)]2 dx,则称 P* ( x) 是 f (x)在 [a, b]上的最佳平方逼近多项式. 若 f (x) [a, b] 是 上的一个列表函数，在a ? x0 ? x1 ? ? ? xm ? b上给出 f ( xi )(i ? 0,1,?, m) ，要求 P* ? ? 使f ? P * 2 ? min f ? PP?? 2? minP??[ f ( xi ) ? P( xi )]2 （1.20） ?i ?0m则称 P* ( x) 为 f (x)的最小二乘拟合.373.23.2.1定义5正交多项式正交函数族与正交多项式若 f ( x), g ( x) ? C[a, b], ? ( x )为 [ a, b]上的权函数且满足( f ( x), g ( x)) ??ba? ( x) f ( x) g ( x)dx ? 0.（2.1）则称 f( x ) g ( x ) [ a, b] 与 在 上带权 ? ( x ) 正交.38若函数族 ?0 ( x), ?1 ( x), ?, ?n ( x), ? 满足关系(? j , ? k ) ??baj ? k. ? 0, ? ( x)? j ( x)?k ( x)dx? ? j ? k. ? Ak ? 0,（2.2） 则称{? k ( x)} [a, b] 上带权 ? (x)的正交函数族. 是 若 Ak ? 1，则称之为标准正交函数族.39三角函数族b?0, j ? k. j ? k. ? Ak ? 0,? 1, cos k ) ? x cos ) x ( x ?k ? (? j , ?x, sin ? , ? ( x2?,jsin)2 x,( x)dx? ? a就是在区间 [?? , ? ] 上的正交函数族. （2.2） 定义6设 ? n ( x)是 [a, b] 上首项系数 an ? 0 的 n次多项式，? (x) 为 [a, b] 上权函数，如果多项式序列 {? n ( x)}? 0 满足关系式(2.2)，则称多项式序列 {? n ( x)}? 为在 [a, b] 上 0 带权 ? (x) 正交，称 ? n ( x) 为 [a, b] 上带权 ? (x) 的 n次正 交多项式.40只要给定区间 [a, b] 及权函数 ? (x) ，均可由一族线性无关的幂函数 {1, x,?, x n ,?}, 利用逐个正交化手续构造 出正交多项式序列 {? n ( x)}? ： 0?0 ( x) ? 1,? n ( x) ? x n ? ?j ?0 n ?1( x n , ? j ( x))(? j ( x), ? j ( x))? j ( x)(n ? 1,2, ?).（2.3）41正交多项式 ? n ( x) 的最高次项系数为1. 而若 {? n ( x)}? 0是正交多项式，则 ?0 ( x), ?1 ( x), ?, ? n ( x)在 [a, b]上是 线性无关的. 事实上，若c0?0 ( x) ? c1?1 ( x) ? ? ? cn? n ( x) ? 0,用 ? ( x)? j ( x)( j ? 0,1, ?, n)乘上式并积分得c0 ? ? ( x )? 0 ( x )? j ( x )dx ? c1 ? ? ( x )?1 ( x )? j ( x )dx ? ?a a b b? c j ? ? ( x )? j ( x )? j ( x )dx ? ?ab? cn ? ? ( x )? n ( x )? j ( x )dx ? 0,ab42利用正交性有c j ? ? ( x)? j ( x)? j ( x)dx ? 0.a b由于 ?a ? ( x)? j ( x)? j ( x)dx ? 0，故 c j ? 0( j ? 0,1, ?, n)即?0 ( x), ?1 ( x), ?, ? n ( x) 线性无关.b关于正交多项式，有? （1） 任何 P( x) ? H n 均可表示为 ?0 ( x), ?1 ( x), ?, ?n ( x)的线性组合. 即P( x) ? ? c j? j ( x).j ?0 n43（2） ? n ( x)与任一次数小于 n 的多项式 P( x) ? H n ?1 正交. 即(? n ( x), P) ??ba? ( x)? n ( x) P( x)dx ? 0.除此之外，还有44定理4设 {? n ( x)}? 是 [a, b]上带权 ? ( x )的正交多项式， 0对n成立关系 ?0?n?1 ( x) ? ( x ? ? n )?n ( x) ? ? n?n ?1 ( x)(n ? 0,1, ?).（2.4）其中?0 ( x) ? 1,??1 ( x) ? 0,(n ? 1,2, ?).? n ? ( x? n ( x), ?n ( x)) /(?n ( x), ?n ( x)),? n ? (? n ( x), ? n ( x)) /(?n ?1 ( x), ? n ?1 ( x)),2 这里 ( x? n ( x), ?n ( x)) ? ?a x? n ( x) ? ( x)dx. b45定理5 则设 {? n ( x)}? 是 [a, b]上带权 ? ( x )的正交多项式， 0(内有 个不同的零点. a, b) n在区间 ? n ( x)( n ? 1) 证明假定 ? n (x) 在(a, b) 内的零点都是偶数重的，则? n (x)在 [a, b]符号保持不变，这与(? n ( x), ?0 ( x)) ??ba? ( x)? n ( x)?0 ( x)dx ? 0.矛盾.故 ? n (x) 在 (a, b)内的零点不可能全是偶数重的，现设为 xi (i ? 1,2,?, l ) ? n (x)在 (a, b)内的奇数重零点，不妨设a ? x1 ? x2 ? ? ? xl ? b,则 ? n (x) 在 xi (i ? 1,2,?, l ) 处变号.46令q( x) ? ( x ? x1 )( x ? x2 ) ?( x ? xl ),于是? n ( x)q( x)在 [a, b]上不变号，则得(? n , q) ??bba? ( x)? n ( x)q( x)dx ? 0.若l ? n ，由 {? n ( x)}? 的正交性可知 0(? n , q) ??a? ( x)? n ( x)q( x)dx ? 0,这与 (? n , q) ? 0 矛盾，故 l ? n.而 ? n (x) 只有 n个零点， 故 l ? n ，即 n个零点都是单重的.473.2.2勒让德多项式当区间为[?1, 1] ，权函数 ? ( x) ? 1时，由 {1, x,?, x n ,?}正交化得到的多项式就称为勒让德(Legendre)多项式， 并用 P ( x), P ( x), ?, P ( x), ? 表示. 0 1 n罗德利克(Rodrigul）给出了简单的表达式P ( x) ? 1, 01 dn P ( x) ? n {( x 2 ? 1) n } n 2 n! dx n(n ? 1,2, ?),（2.5）48由于 ( x 2 ? 1) n是 2n 次多项式， 所以对其求 n 阶导数后得1 P ( x) ? n (2n)( 2n ? 1) ? (n ? 1) x n ? an ?1 x n ?1 ? ? ? a0 , n 2 n!于是得首项 x 的系数 an ?n( 2n)! . n 2 2 ( n!)最高项系数为1的勒让德多项式为~ P ( x) ? n n! d n [( x 2 ? 1) n ]. (2n)! dx n（2.6）49勒让德多项式重要性质：性质11正交性? 0, ? Pn ( x) Pm ( x) dx ? ? 2 ??1 , ? 2n ? 1 ?m ?m ? n.（2.7）证明令 ? ( x) ? ( x 2 ? 1) n，则? ( k ) (?1) ? 0(k ? 0,1, ?, n ? 1).设 Q(x)是在区间 [?1, 1] 上 n 阶连续可微的函数，由分部 积分知50?1?1Pn ( x)Q( x)dx ?1 1 Q( x)? ( n ) ( x)dx 2 n n! ??11 1 ? ? n ? Q?( x)? ( n ?1) ( x) dx 2 n! ?1?? ( ?1) n ? n 2 n!?1?1Q ( n ) ( x )? ( x ) dx下面分两种情况讨论: 则 （1） 若 Q(x) 是次数小于 n的多项式， Q ( n ) ( x) ? 0,故得?1?1Pn ( x) Pm ( x)dx ? 0, 当n ? m.51（2） 若 则 于是1Q( x) ? Pn ( x) ?(2n)! n 1 x ? ?, ? ( n ) ( x) ? n 2 n 2 (n!) 2 n!Q ( n ) ( x) ? Pn( n ) ( x) ?( 2n)! , n 2 n!(?1) n (2n)! 1 P 2 ( x)dx ? ( x 2 ? 1) n dx n 2 2 ??1 ??1 2 (n!)(2n)! ? 2n 2 (n!) 2?1?1(1 ? x 2 ) n dx.由于?故10(1 ? x ) dx ? ? cos 2 n ?1 tdt2 n2?0?1?1Pn2 ( x)dx ?2 . 2n ? 152性质2奇偶性 （2.8）P (? x) ? (?1) n P ( x). n n由于 ? ( x) ? ( x 2 ? 1) n 是偶次多项式，经过偶次求导仍为 偶次多项式，经过奇次求导则为奇次多项式，故 n 为偶数时 为偶函数， 为奇数时 Pn (x)为奇函数，于是（2.8）成 P ( x) n n 立.53性质3递推关系考虑 n ? 1 次多项式 xP ( x), 它可表示为 nxP ( x) ? a0 P ( x) ? a1 P ( x) ? ? ? an ?1 P ?1 ( x). n 0 1 n两边乘 Pk ( x), 并从-1到1积分， 得?1?1xP ( x) P ( x)dx ? ak ? P 2 ( x)dx. n k k?11当 k ? n ? 2 时， xP ( x)次数小于等于 n ? 1 上式左端积分 ， k 为0， 故得 ak ? 0.54当 k ? n 时，xP2 ( x)为奇函数， 左端积分仍为0， 故 nan ? 0.于是 其中xP ( x) ? an ?1 P ?1 ( x) ? an ?1 P ?1 ( x) n n nan ?1 2n ? 1 1 ? n ??1 xP ( x) Pn ?1 ( x)dx 2 2n ? 1 2n n ? ? ? , 2 2 4n ? 1 2n ? 1 2n ? 3 1 ? n ??1 xP ( x) Pn ?1 ( x)dx 2? 2n ? 3 2(n ? 1) n ?1 ? ? , 2 ( 2n ? 1)( 2n ? 3) 2n ? 155an ?1从而得到以下的递推公式(n ? 1) P ?1 ( x) ? (2n ? 1) xP ( x) ? nP ?1 ( x) n n n（2.9）(n ? 1,2, ?),由 P ( x) ? 1, P ( x) ? x, 利用上述递推公式就可推出 0 1P ( x) ? (3x 2 ? 1) / 2, 2P ( x) ? (5 x 3 ? 3 x) / 2, 3P ( x) ? (35 x 4 ? 30 x 2 ? 3) / 8, 4P ( x) ? (63 x 5 ? 70 x 3 ? 15 x) / 8, 5P ( x) ? (231x 6 ? 315 x 4 ? 105 x 2 ? 5) / 16, 6 ?56图3-1给出了P ( x), P ( x), P ( x), P ( x) 的图形. 0 1 2 3图3-157?性质4P ( x )在区间 [?1, 1] 内有 n 个不同的实零点.? n583.2.3 切比雪夫多项式当权函数 ? ( x ) ?1 1? x2，区间为 [?1, 1]时，由序列 {1, x,?, x n ,?} 正交化得到的正交多项式就是切比雪夫 (Chebyshev)多项式.它可表示为Tn ( x) ? cos( n arccos x),x ? 1.（2.10）若令 x ? cos? ， 则 Tn ( x) ? cos n? , 0 ? ? ? ? .59切比雪夫多项式有很多重要性质：性质1递推关系(n ? 1,2, ?),Tn ?1 ( x) ? 2 xTn ( x) ? Tn ?1 ( x) T0 ( x) ? 1,T1 ( x) ? x.（2.11）这只要在三角恒等式cos( n ? 1)? ? 2 cos ? cos n? ? cos( n ? 1)? (n ? 1)中，令 x ? cos? 即得.60由（2.11）可推出T2 ( x) ? 2 x 2 ? 1,3 T3 ( x) ? 2 xTn 3 x Tn ?1 ( x)? 4 x ?( x),? Tn ?1 ( x)T4 ( x) ? 8 x 4 ? 8 x 2 ? 1,T5 ( x) ? 16 x 5 ? 20 x 3 ? 5 x,T6 ( x) ? 32 x 6 ? 48 x 4 ? 18 x 2 ? 1, ?T0 ( x), T1 ( x), T2 ( x), T3 ( x) 的函数图形见图3-2.61图3-2由递推关系（2.11）还可得到 Tn (x) 的最高次项系数是2 n ?1.Tn ?1 ( x) ? 2 xTn ( x) ? Tn ?1 ( x)62性质2切比雪夫多项式 {Tk ( x)} 在区间 [?1, 1]上带权? ( x) ? 1 / 1 ? x 2 正交，且? 0, 1 T ( x )T ( x ) dx ?? n m ?? , ??1 2 1? x ?2 ?? ,n ?n ? m ? 0;（2.12）n ? m ? 0.令 x ? cos? ，则 dx ? ? sin ?d? ，于是? 0, n ? 1 T ( x )T ( x ) dx ? ?? n m ? ? , n ? m ? 0; ? ? cos n? cos m?d? ??1 2 0 1? x ?2 ? ? , n ? m ? 0.63性质3T2 k ( x) 只含 x 的偶次幂， 2 k ?1 ( x)只含 x 的奇次幂. T这个性质由递推关系直接得到.性质4Tn (x) 在区间 [?1, 1]上有 n 个零点2k ? 1 xk ? cos ?, 2nk ? 1,2, ?, n.性质5Tn (x) 的首项 x n 的系数为 2 n ?1.2~ ~ ~ 若令 T0 ( x) ? 1, Tn ( x) ? 1?1 Tn ( x), n ? 1,2, ?，则 Tn ( x) n是首项系数为1的切比雪夫多项式.64~ 若记 H n 为所有次数小于等于 n 的首项系数为1的多项 ~ 式集合，对 Tn ( x)有以下性质：定理6~ 设 Tn ( x)是首项系数为1的切比雪夫多项式，则?1? x ?1~ max Tn ( x) ? max P( x) ,?1? x ?1~ ?P( x) ? H n .且?1? x ?1~ max Tn ( x) ?1 . n ?1 265~ 定理6表明在所有首项系数为1的 n 次多项式集合 H n 中， ~ ~ ~ Tn ( x) ? min P( x) ? ,所以 Tn ( x)是 H n中最大值最小的多项 ~ ? P?Hn式，即?1? x ?1~ max Tn ( x) ? min max P( x) ? ~P?H n ?1? x ?11 . n ?1 2（2.13）利用这一结论，可求 P( x) ? H n 在 H n ?1中的最佳（一致）逼近多项式.66例3 求 f ( x) ? 2 x3 ? x 2 ? 2 x ? 1 在 [?1, 1]上的最佳2次逼 近多项式. 解 由题意，所求最佳逼近多项式 P2* ( x) 应满足?1? x ?1max f ( x) ? P* ( x) ? min . 2由定理6可知， 当1 3 3 f ( x) ? P ( x) ? T3 ( x) ? 2 x ? x 2 2* 2* 时，多项式 f ( x) ? P2 ( x) 与零偏差最小，? 故671 7 2 P ( x) ? f ( x) ? T3 ( x) ? x ? x ? 1 2 2* 2就是 f (x) 在 [?1, 1]上的最佳2次逼近多项式. 由于切比雪夫多项式是在区间 [?1, 1]上定义的，对于 一般区间 [a, b]，要通过变量替换变换到 [?1, 1] ，可令1 x ? [(b ? a) t ? a ? b], 2 则可将 x ? [a, b] 变换到 t ? [?1, 1].（2.14）683.2.4切比雪夫多项式零点插值切比雪夫多项式 Tn (x)在区间 [?1, 1]上有 n 个零点xk ? cos 2k ? 1 ?, 2nk ? 1,2, ?, n.和 n ?1 个极值点（包括端点）k? xk ? cos , nk ? 0,1, ?, n.这两组点称为切比雪夫点，它们在插值中有重要作用.69从图3-3可以看到切比雪夫点恰好是单位圆周上等距分布点的横坐标，这些点的横坐标在接近区间 [?1, 1]的端点处是密集的. 利用切比雪夫点做插值，可 使插值区间最大误差最小化. 设插值点 x0 , x1 ,?, xn ? [?1,1]f ? C n ?1[?1,1], Ln ( x)为相应的 n次拉格朗日插值多项式，则余项图3-3f ( n ?1 (? ) Rn ( x) ? f ( x) ? Ln ( x) ? ?n?1 ( x), (n ? 1)!70于是?1? x ?1max f ( x) ? Ln ( x)M n ?1 ? max ( x ? x0 )( x ? x1 ) ? ( x ? xn ) , ?1? x ?1 (n ? 1)!其中M n ?1 ? f ( n ?1) ( x)?? max f ( n ?1) ( x)?1? x ?1是由被插函数决定的. 如果插值节点为 Tn?1 ( x)的零点xk ? cos 2k ? 1 ?, 2(n ? 1)k ? 0,1,?, n,71则由（2.13）可得1 ~ max ?n ?1 ( x) ? max Tn ?1 ( x) ? n . ?1? x ?1 ?1? x ?1 2由此可导出插值误差最小化的理论. 定理7 设插值节点 x0 , x1 ,?, xn 为切比雪夫多项式 Tn?1 ( x)的零点，被插函数 f ? C n ?1[?1,1], Ln ( x) 为相应的插值多项 式，则1 max f ( x) ? Ln ( x) ? n f ( n ?1) ( x) . ? ?1? x ?1 2 (n ? 1)!（2.15）72对于一般区间 [a, b]上的插值只要利用变换（2.14）则可得到相应结果，此时插值节点为b?a 2k ? 1 a?b xk ? cos ?? , 2 2(n ? 1) 2k ? 0,1,?, n,73例4求 f ( x) ? e x在 [0, 1]上的四次拉格朗日插值多项式x ，插值节点用 T5 ( x)的零点并估计误差 max e ? L4 ( x) . L4 ( x) 0? x ?1解利用 T5 ( x)的零点和区间变换可知节点xk ? 1 2k ? 1 (1 ? cos ? ), 2 10 k ? 0,1,2,3,4,即x0 ? 0.97553, x3 ? 0.20611, x1 ? 0.79390, x4 ? 0.02447, x2 ? 0.5,对应的拉格朗日插值多项式为74L4 ( x) ? 1.000 022 74 ? 0.998 862 33x ? 0.509 022 51x 2 ? 0.141 841 05 x 3 ? 0.068 494 35 x 4利用（2.15）可得误差估计M n ?1 (b ? a) n ?1 max e ? L4 ( x) ? , 2 n ?1 0? x ?1 (n ? 1)! 2xn ? 4,而M n?1 ? f (5) ( x)?? ex?? e1 ? 2.72,于是有max e x ? L4 ( x) ?0? x ?1e 1 2.72 1 . 9 ? ? 4.4 ?10 ?5. 5! 2 6 1024075在第2章中曾经指出，高次插值会出现龙格现象，一般Ln (x)不收敛于 f (x)，因此并不适用. 但若用切比雪夫多项式零点插值却可避免龙格现象，可保证整个区间上收敛.761 ，在 [?5,5]上利用T11 ( x)的零点 2 1? x ~ 作插值点，构造10次拉格朗日插值多项式 L10 ( x). 与第2章例5设 f ( x) ?得到的等距节点造出的 L10 ( x)近似 f (x) 作比较. 解 在[?1, 1] 上的10次切比雪夫多项式 T11 ( x) 的零点为t k ? cos 21 ? 2k ?, 22 k ? 0,1, ?,10.作变换 xk ? 5tk ,k ? 0,1,?,10.它们是 (?5,5)内的插值点， ~ 由此得到 y ? f (x) 在 [?5,5]上的拉格朗日插值多项式 L10 ( x).77~ ~ 的图形见图3-4，从图上可见 L10 ( x) f ( x), L10 ( x), L10 ( x)没有出现龙格现象.图3-4783.2.5 其他常用的正交多项式区间 [a, b] 及权函数 ? (x)不同，则得到的正交多项式也不同. 除上述两种最重要的正交多项式外，下面是三种较常 用的正交多项式. 1. 第二类切比雪夫多项式 在区间[?1, 1] 上带权 ? ( x) ? 称为第二类切比雪夫多项式.791 ? x 2 的正交多项式表达式为U n ( x) ? sin[( n ? 1) arccos x] 1? x2 .（2.16）令 x ? cos? ，可得?1?1U n ( x)U m ( x) 1 ? x dx ? ? sin( n ? 1)? sin( m ? 1)?d?2 0?? 0, m ? ? ? ?? ? 2 , m ? n, ?即 {U n ( x)}是 [?1, 1]上带权 ? ( x) ?1 ? x 2 的正交多项式族.80递推关系U 0 ( x) ? 1, U1 ( x) ? 2 x,U n ?1 ( x) ? 2 xUn ( x) ? U n ?1 ( x),(n ? 1,2, ?).812. 拉盖尔多项式 在区间 [0,??)上带权 ? ( x) ? e ? x 的正交多项式称为拉 盖尔(Laguerre)多项式.其表达式为dn Ln ( x) ? e x ( x n e ? x ). dx n（2.17）正交性质??0? 0, m ? e Ln ( x) Lm ( x)dx ? ? 2 ?(n!) , m ? n,?x82递推关系L0 ( x) ? 1, L1 ( x) ? 1 ? x,Ln ?1 ( x) ? (1 ? 2n ? x) Ln ( x) ? n 2 Ln ?1 ( x),(n ? 1,2, ?).833. 埃尔米特多项式 在区间 (??,??)上带权 ? ( x) ? e 为埃尔米特多项式. 表达式H n ( x) ? (?1) en x2? x2的正交多项式称dn ? x2 (e ), n dx（2.18）正交关系?????e? x20, m ? ? H n ( x) H m ( x)dx ? ? n ?2 n! ? , m ? n,84递推关系H 0 ( x) ? 1, H1 ( x) ? 2 x,H n ?1 ( x) ? 2 xHn ( x) ? 2nH n ?1 ( x),(n ? 1,2, ?).853.3最佳平方逼近863.3.1最佳平方逼近及其计算对 f ( x) ? C[a, b] 及 C[a, b] 中的一个子集? ? span{?0 ( x), ?1 ( x), ?, ?n ( x)}若存在 S * ( x) ? ? ，使f ( x) ? S ( x)* 2 2? min f ( x) ? S ( x)S ( x )??2 2（3.1）? minS ( x )???ba? ( x)[ f ( x) ? S ( x)]2 dx.则称 S * ( x) 是 f (x) 在子集 ? ? C[a, b]中的最佳平方逼近 函数.87由（3.1）可知该问题等价于求多元函数I (a0 , a1 ,?, an ) ? ? ? ( x)[ ? a j? j ( x) ? f ( x)]2 dx （3.2） ab j ?0 n的最小值.I (a0 , a1 ,?, an ) 是关于 a0 , a1 ,?, an 的二次函数，2 利用多元函数求极值的必要条件 * f ( x) ? S ( x) ? min f ( x) ? S ( x) 2 2 2 S ( x )??（3.1）?I ?0 ? min ?akS ( x )???ba(k ? 0,1, ?, n), 2 ? ( x)[ f ( x) ? S ( x)] dx.即n b ?I ? 2? ? ( x)[ ? a j? j ( x) ? f ( x)]? k ( x)dx a ?ak j ?0(k ? 0,1, ?, n),88于是有? (?j ?0nk( x), ? j ( x)) a j ? ( f ( x), ? k ( x)) (k ? 0,1, ?, n). （3.3）这个关于 a0 , a1 ,?, an 的线性方程组，称为法方程.由于 ?0 ( x), ?1 ( x), ?, ?n ( x) 线性无关，故det G(?0 , ?1 ,?, ?n ) ? 0* 于是方程组（4.3）有唯一解 ak ? ak(k ? 0,1, ?, n),从而得到??* * S * ( x) ? a0?0 ( x) ? ? ? an? n ( x).89下面证明 S * ( x)满足（3.1）， 即对任何 S ( x) ? ? , 有?ba? ( x)[ f ( x) ? S ( x)] dx ? ? ? ( x)[ f ( x) ? S ( x)]2 dx* 2 ab（3.4） 为此只要考虑b f ( x) ? S ( x) ? min 2 ( x) ? b ( x) 2 f S （3.1） 2 2) ? S ( x )x? ?)] dx ? D ? ? ? ( x)[ f ( x S ( ? ( x)[ f ( x) ? S * ( x)] dx ?* 2 2a??ba? min ? 2? ( x)[ f ( x) ? S ( x)]2 dx. * ( ?x a ? ( x)[ f ( x) ? SSx )(? )] dxbba? 2? ? ( x)[ S * ( x) ? S ( x)][ f ( x) ? S * ( x)]dx.a90* 由于S * ( x)的系数 a k 是方程（3.3）的解，故?n j ?0ba? ( x)[ f ( x) ? S * ( x)]?k ( x)dx ? 0 (k ? 0,1,?, n),从而上式第二个积分为0，(于是 ( x)) (k ? 0,1, ?, n). ? (?k ( x), ? j ( x))a j ? ( f x), ?k （3.3）D ? ? ? ( x)[ S ( x) ? S * ( x)]2 dx ? 0,a b故（3.4）成立. 这就证明了S * ( x)是 f (x) 在 ? 中的最佳平方逼近函数.?ba? ( x)[ f ( x) ? S ( x)] dx ? ? ? ( x)[ f ( x) ? S ( x)]2 dx* 2 ab（3.4）91若令 ? ( x) ? f ( x) ? S * ( x), 则平方误差为? ( x)2 2? ( f ( x) ? S * ( x), f ( x) ? S * ( x))? ( f ( x), f ( x)) ? ( S * ( x), f ( x))? f ( x)2 2 * ? ? ak (? k ( x), f ( x)). k ?0 n（3.5）若取 ? k ( x) ? x k , ? ( x) ? 1, f ( x) ? C[0, 1], 则要在 H n 中求 n次最佳平方逼近多项式* * * S * ( x) ? a0 ? a1 x ? ? ? an x n ,92此时(? j ( x), ? k ( x)) ??1 010x k ? j dx ?1 , k ? j ?1( f ( x), ? k ( x)) ??f ( x) x k dx ? d k .n 即 若用 H表示 Gn ? G (1, x, ?, x ) 对应的矩阵，??1 ? ? 1/ 2 H?? ? ? ? ?1 /( n ? 1)1/ 2 1/ 3 ? 1 /( n ? 2)1 /( n ? 1) ? ? 1 /( n ? 2) ? ? ? ? ? ? ? 1 /( 2n ? 1) ? ?（3.6）称为希尔伯特(Hilbert)矩阵.93T T 记 a ? (a0 , a1 ,?, an ) , d ? (d 0 , d1 ,?, d n ) , 则Ha ? d* ak ? ak (k ? 0,1, ?, n) 即为所求. 的解（3.7）94例6设 f ( x) ? 1 ? x 2 , 求 [0, 1]上的一次最佳平方逼近多项式. 解 利用（3.7），得1 0d0 ? ?11 1 ? x dx ? ln( 1 ? 222 2) ? ? 1.147, 212 Ha1? d 2 3 /（3.7） 2 ? 1 ? 0.609, 2 2 ? d1 ? ? x 1 ? x dx ? (1 ? x ) 0 3 3 0得方程组1 / 2? ?a0 ? ?1.147 ? ? 1 ?1 / 2 1 / 3? ? a ? ? ?0.609?, ? ?? 1 ? ? ?95解之a0 ? 0.934, a1 ? 0.426,故* S1 ( x) ? 0.934 ? 0.426 x.平方误差? ( x)2 2* ? ( f ( x), f ( x)) ? ( S1 ( x), f ( x))? ? (1 ? x 2 )dx ? 0.426d1 ? 0.934d 0 ? 0.0026. 01最大误差? ( x)?? max0? x ?1* 1 ? x 2 ? S1 ( x) ? 0.066.963.3.2用正交函数族作最佳平方逼近设 f ( x) ? C[a, b], ? ? span{?0 ( x), ?1 ( x), ?, ?n ( x)},若 ?0 ( x), ?1 ( x), ?, ?n ( x) 是满足条件(2.2)的正交函数族， 则(? k ( x),(?ji ( x)) ?jj ( x( f ?x), ? k (? )) (k ? 0,1, ?, n). （3.3） ? ( x), a ? )) ( 0, i x j ?n而j ?0j ? k. ? 0, (? j , ? k ) ? ? ? ( x)? j ( x)? k ( x)dx? ? a j ? k. 故法方程（3.3）的系数矩阵 ? Ak ? 0,b(? j ( x), ? j ( x)) ? 0（2.2） Gn ? G(?0 ( x), ?1 ( x), ?, ?n ( x))97为非奇异对角阵，且方程（3.3）的解为* ak ? ( f ( x), ? k ( x)) /(? k (k ), ? k ( x))（3.8）(k ? 0,1, ?, n).j ?0 于是( x), ? a ? (?f ( x) ? C([x))b] a,k jnj在 ? 中的最佳平方逼近函数为? ( f ( x), ? k ( x)) (k ? 0,1, ?, n). （3.3）S ( x) ? ?* k ?0n( f ( x), ? k ( x))? k ( x)2 2? k ( x).（3.9）98由（3.5）可得均方误差为? n ( x)2* ? f ( x) ? S n ( x)21 22 ? n ? ( f ( x), ? k ( x)) ? ? 2 ? ? ? f ( x) 2 ? ? ? ? ? . ? ? k ( x) 2 ? ? ? k ?0 ? ? ? ? ? 2 ? ( x) 2 ? ( f ( x) ? S * ( x), f ( x) ? S * ( x))（3.10）由此可得贝塞尔(Bessel)不等式 ? ( f ( x), f ( x)) ? ( S * ( x), f ( x)) n 2 * (ak ? k ( x) 2 ) 2 2 f n( x) 2 . ? ? * k ?1 ? f ( x) 2 ? ? ak (? k ( x), f ( x)).k ?0（3.5） （3.11）99若 f ( x) ? C[a, b]，按正交函数族 {? k ( x)} 展开，系数* ak (k ? 0,1, ?) 按（3.8）计算，得级数* ak ? k ( x ) ? k ?0 ?（3.12）* 称这个级数为 f (x) 的广义傅里叶(Foureir)级数， 系数 a k * ak ? ( f ( x), ? k ( x)) /(? k (k ), ? k ( x)) （3.8） 称为广义傅里叶系数. 它是傅里叶级数的直接推广. (k ? 0,1, ?, n). 讨论特殊情况，设 {?0 ( x), ?1 ( x), ?, ?n ( x)} 是正交多项式， ? span{?0 ( x), ?1 ( x), ?, ?n ( x)},?k ( x)( k ? 0,1,?, n) ? 可由 1, x,?, x n 正交化得到，则有下面的收敛定理.100定理8设 f ( x) ? C[a, b], S * ( x) 是由（3.9）给出的f (x)的最佳平方逼近多项式，其中 {?k ( x), k ? 0,1,?, n}是正交多项式族， 则有* lim f ( x) ? S n ( x) n ?? 2? 0.( f ( x), ? k ( x)) S考虑函数 f ( x) ?C[?1, 1], k按勒让德多项式（3.9） ( x) ? ? ? ( x). 2 ? ( x)n * k ?0 k{P ( x), P ( x), ?, P ( x)} 展开， 由(3.8)，(3.9)可得 0 1 n* * * * S n ( x) ? a0 P0 ( x) ? a1 P ( x) ? ? ? an Pn ( x), 12（3.13）101其中( f ( x), Pk ( x)) 2k ? 1 1 a ( x) ? ? ??1 f ( x) Pk ( x)dx. ( Pk ( x), Pk ( x)) 2* k（3.14）* ? n ( x) 2 ? f ( x) ? S n ( x) 2 根据均方误差公式(3.10)，平方误差为2 n ? 1 2 n ? 2 2 ( x)) ? ? * ? k ( x)?2 ?? f?( xf 2(?)dx ? (? x), ? k ak ? ? . （3.15） x ? f( （3.10） ? k ?0?2k x)1 . ? ?1 ) 2 ? ? ? k ?0 ? ? ? k( 2 ? ? ? ? 1 22由定理8可得* lim f ( x) ? S n ( x) n ?? 2? 0.102* 如果 f (x) 满足光滑性条件,还有 S n 一致收敛于 f (x)的结论. 定理9* 设 f ( x) ?C 2 [?1, 1], S n ( x)由(3.13)给出，则对任意 x ? [?1, 1]和 ?? ? 0, 当 n充分大时有* f ( x) ? S n ( x) ??n.* * * * ~ （3.13） S n公式(2.6)给出了首项系数为1的勒让德多项式 Pn ， ( x) ? a0 P0 ( x) ? a1 P ( x) ? ? ? an Pn ( x), 1它具有以下性质.~ P ( x) ? nn! d n [( x 2 ? 1) n ]. (2n)! dx n（2.6）103定理10 在所有最高次项系数为1的 n次多项式中，~ 勒让德多项式 Pn ( x) 在 [?1, 1] 上与零的平方误差最小.证明 设 Qn (x)是任意一个最高次项系数为1的 n次 多项式，它可表示为n ?1 ~ ~ Qn ( x) ? Pn ( x) ? ? ak Pk ( x), k ?0104于是Qn ( x)2 22 ? (Qn ( x), Qn ( x)) ? ? Qn ( x)dx ?1 1n ?1 ~ ~ ~ 2 ~ ? ( Pn ( x), Pn ( x)) ? ? ak ( Pk ( x), Pk ( x)) k ?0~ ~ ? ( P ( x), P ( x)) n n~ ? Pn ( x)2 2当且仅当 a0 ? a1 ? ? ? an?1 ? 0 时等号才成立， 即当 ~ Qn ( x) ? P ( x) 时平方误差最小.?? n105例7项式.求 f ( x) ? e x 在 [?1, 1]上的三次最佳平方逼近多~ ( f ( x), Pk ( x)) 先计算1 x解(k ? 0,1,2,3).1 ( f ( x), P ( x)) ? ? e dx ? e ? ? 2. e( f ( x), P ( x)) ? ? xe x dx ? 2e ?1 ? 0.3 1 ( f ( x), P2 ( x)) ? ? ( x 2 ? )e x dx ?1 2 211? e?7 ? 0.1431; e5 3 3 ( f ( x), P ( x)) ? ? ( x ? x)e x dx 3 ?1 2 211 ? 37 ? 5e ? 0.02013. e106由(3.14) 得* a0 ? ( f ( x), P0 ( x)) / 2 ? 1.1752,* a1 ? 3( f ( x), P ( x)) / 2 ? 1.1036, 1 ( f ( x), Pk ( x)) 2k ? 1 1 * * ak ( x) ? ? 5( f ( x), P ( x)) / 2 ? 0.3578,) Pk ( x)dx. a2 ( P ( x), P ( x2 ? 2 ??1 f ( x )) k k （3.14） * a3 ? 7( f ( x), P ( x)) / 2 ? 0.07046. 3代入(3.13) 得三次最佳平方逼近多项式* S3 ( x) ? 0.9963 ? 0.9979 x ? 0.5367 x 2 ? 0.1761x 3 . * * * * S n ( x) ? a0 P0 ( x) ? a1 P ( x) ? ? ? an Pn ( x), 1（3.13）107均方误差? n ( x) 2 ? e ? S ( x)x * 322 *2 ? ? e dx ? ? ak ?1 k ?0 2k ?11 2x3? 0.0084.最大误差? n ( x)* ? e x ? S 3 ( x) ??? 0.0112.如果 f ( x) ? C[a, b], 求 [a, b] 上的最佳平方逼近多项式， 做变换b?a b?a x? t? 2 2(?1 ? t ? 1),108于是b?a b?a F (t ) ? f ( t? ), 2 2在 [?1, 1]上可用勒让德多项式做最佳平方逼近多项式 S n (t ), 从而得到区间 [a, b]上的最佳平方逼近多项式* Sn (*1 (2 x ? a ? b)). b?a109由于勒让德多项式 {Pk ( x)}是在区间 [?1, 1]上由{1, x,?, x k ,?} 正交化得到的，因此利用函数的勒让德展开部分和得到最佳平方逼近多项式与由S * ( x) ? a0 ? a1 x ? ? ? an x n直接通过解法方程得到 H n 中的最佳平方逼近多项式是一致 的. 只是当 n 较大时法方程出现病态，计算误差较大，不能 使用，而用勒让德展开不用解线性方程组，不存在病态问题， 因此通常都用这种方法求最佳平方逼近多项式.?1103.3.3切比雪夫级数如果 f ( x) ?C[?1,1] ，按 {Tk ( x)}?展成广义傅里叶级数， 0 由（3.12）可得级数* ? C0 * ? ? Ck Tk ( x), 2 k ?1（3.16）其中系数根据（3.8）式，由（2.12）得到C* k?2??1f ( x)Tk ( x) dx 1? x2?1,k ? 0,1, ? , （3.17）这里Tk ( x) ? cos(k arccos x),x ? 1.级数（3.16）称为 f (x) 在 [?1,1] 上的切比雪夫级数.111若令 x ? cos ? , 0 ? ? ? ? ，则（3.16）就是 f (cos ? ) 的傅里 叶级数，其中C ?* k2??1?1f (cos ? ) cos k? d? ,k ? 0,1, ?.（3.18）根据傅里叶级数理论，只要 f ??(x) 在 [?1,1] 上分段连续，则 在 上的切比雪夫级数（3.16）一致收敛于 f (x) . f (x) [?1,1]从而* ? C0 * f ( x) ? ? ? Ck Tk ( x). 2 k ?1（3.19）112取部分和* n C0 * C ( x) ? ? ? Ck Tk ( x), 2 k ?1 * n（3.20）其误差为* * f ( x) ? Cn ( x) ? Cn ?1Tn ?1 ( x).在 [?1,1] 上 Tn?1 ( x) 是均匀分布的，它的最大值 max Tn?1 ( x)?1? x ?1* 最小，因此 Cn ( x) 可作为 f (x) 在 [?1,1] 上的近似最佳一致逼近多项式.113例8 解* 求 f ( x) ? e x在 [?1, 1]上的切比雪夫部分和 C3 ( x) .由（3.18）得C ?* k2???0e cos? cos k? d? ,k ? 0,1,2,3.利用第4章的数值积分法得* C0 ? 2., C1* ? 1., * * C2 ? 0., C3 ? 0..由（3.20）及 Tk (x) 的表达式有* C3 ( x) ? 0.994531 ? 0.997308 x ? 0. ? 0.177347 x 3 ,* 及 e x ? C3 ( x)?? 0.00607.1143.43.4.1曲线拟合的最小二乘法最小二乘法及其计算在函数的最佳平方逼近中 f ( x) ? C[a, b], 如果 f (x)只在一组离散点集 {xi , i ? 0,1, ?, m} 上给定，这就是科学实验中经常见到的实验数据 {( xi , yi ), i ? 0,1,?, m}的曲线拟合.115问题为利用 yi ? f ( xi ), i ? 0,1,?, m, 求出一个函数y ? S * ( x) 与所给数据{( xi , yi ), i ? 0,1,?, m} 拟合.记误差? i ? S * ( xi ) ? yi ,? ? (? 0 , ?1 ,?, ? m )Ti ? 0,1, ?, m,116设 ?0 ( x), ?1 ( x), ?, ?n ( x)是 C[a, b] 上线性无关函数族， 在 ? ? span{?0 ( x), ?1 ( x), ?, ?n ( x)}中找一函数 S * ( x)，使误差平方和?2 2? ? ? ? ? [ S * ( xi ) ? yi ]2i ?0 2 i i ?0mm? minS ( x )??[ S ( xi ) ? yi ]2 ?i ?0m（4.1）这里S ( x) ? a0?0 ( x) ? a1?1 ( x) ? ? ? an?n ( x)( n ? m) （4.2）117这个问题称为最小二乘逼近，几何上称为曲线拟合的最小二乘法. 用最小二乘求拟合曲线时,首先要确定 S (x ) 的形式. 确定 S (x ) 的形式问题不仅是数学问题, 还与问题的 实际背景有关. 通常要用问题的运动规律及给定的数据进行数据描图, 确定 S (x )的形式, 然后通过实际计算选出较好的结果.118S (x ) 的一般表达式为（4.2）表示的线性形式.若 ? k (x)是 k 次多项式， (x ) 就是 n次多项式. S 为了使问题的提法更有一般性，通常在最小二乘法中 S ( x) ? a0?0 ( x) ? a1?1 ( x) ? ? ? an?n ( x) (n ? m) 考虑加权平方和 （4.2）?2 2? ? ? ( xi )[ S ( xi ) ? yi ]2 .i ?0m（4.3）这里 ? ( x) ? 0是 [a, b] 上的权函数，它表示不同点 ( xi , f ( xi ))处的数据比重不同.119用最小二乘法求拟合曲线的问题，就是在形如(4.2)的S (x )中求一函数 y ? S * ( x)， 使（4.3）取得最小.这样，最小二乘问题就转化为求多元函数S ( x) ? a0?0 ( x) ?ma1?1 ( x) ?n ? an?n ( x) (n ? m) ? ? ? ? ( xi )[ ? a j? j ( xi ) ? f ( xi )]2 （4.2） （4.4）i ?0mI (a0 , a1 ,?, an )j ?0* 2 a* a * )[ S ( x ) 的极小点 (a0 , ?1 , ?,( xn ) 问题. ? y ]2 . ? 2 ?? i i i（4.3）由求多元函数极值的必要条件，有m n ?I ? 2? ? ( xi )[ ? a j? j ( xi ) ? f ( xi )]? k ( xi ) ? 0 ?ak i ?0 j ?0 (k ? 0,1, ?, n).i ?0120若记(? j , ? k ) ? ? ? ( xi )? j ( xi )? k ( xi ), ( f , ? k ) ? ? ? ( xi ) f ( xi )? k ( xi ) ? d ki ?0 i ?0 m m（4.5）(k ? 0,1, ?, n).上式可改写为? (?j ?0nk, ? j )a j ? d k(k ? 0,1, ?, n). （4.6）可写成矩阵形式 这方程称为法方程，121Ga ? d .a ? (a0 , a1 , ?, an )T , d ? (d 0 , d1 , ?, d n )T , 其中?(? 0 , ? 0 ) ? (? , ? ) G?? 1 0 ? ? ? ?(? n , ? 0 ) (? 0 , ?1 ) (?1 , ?1 ) ? (? n , ?1 ) ? ? ? (? 0 , ? n ) ? (?1 , ? n ) ? ?. ? ? ? (? n , ? n )?（4.7）要使法方程(4.6)有唯一解，就要求矩阵 G非奇异， 而 ?0 ( x), ?1 ( x), ?, ?n ( x)在 [a, b]上线性无关不能推出 矩阵 G非奇异，必须加上另外的条件. ,?, n). （4.6） ? (?k , ? j )a j ? d k (k ? 0,1j ?0 n122定义7设 ?0 ( x), ?1 ( x), ?, ?n ( x) ?[a, b]的任意线性组合在点集 {xi , i ? 0,1,?, m}(m ? n) 上至多只有 n 个则称 ?0 ( x), ?1 ( x), ?, ?n ( x)在点集 不同的零点，{xi , i ? 0,1,?, m}上满足哈尔(Haar)条件.显然 1, x,?, x n在任意 m(m ? n)个点上满足哈尔条件.m 如果 ?0 ( x), ?1 ( x), ?, ?n ( x) ?[a, b] 在 {xi }0 上满足哈尔条件，则法方程(4.6) 的系数矩阵(4.7) 非奇异， 于是* 方程(5.6)存在唯一的解 ak ? ak , k ? 0,1, ?, n. 从而得到n 函数 f (x) 的最小二乘解为 ? (?k , ? j )a j ? d k j ?0(k ? 0,1, ?, n). （4.6）123* * * S * ( x) ? a0?0 ( x) ? a1?1 ( x) ? ? ? an? n ( x).这样得到的 S * ( x) 对任何形如(4.2)的 S (x ) ，都有 ，? ( xi )[ S * ( xi ) ? f ( xi )]2 ? ? ? ( xi )[ S ( xi ) ? f ( xi )]2 , ?i ?0 i ?0mm故 S * ( x)确是所求最小二乘解.S ( x) ? a0?0 ( x) ? a1?1 ( x) ? ? ? an?n ( x)( n ? m) （4.2）124给定 f (x) 的离散数据 {( xi , yi ), i ? 0,1, ?, m}， 一般可取 ? ? span{1, x,?, x n } ，但这样做当 n ? 3时， 求解法方程（4.6）将出现系数矩阵 G为病态的问题， 通常对 n ? 1的简单情形都可通过求法方程（4.6）得到S * ( xn). (? , ? )a ? d ? k j j k (k ? 0,1,?, n). （4.6） j ?0 有时根据给定数据图形，其拟合函数 y ? f (x) 表面上不是（4.2）的形式，但通过变换仍可化为线性模型. 例如， S ( x) ? aebx ，若两边取对数得 S ( x) ? a0?0 ( x) ? a1?1 ( x) ? ? ? an?n ( x)( n ? m) （4.2）125ln S ( x) ? ln a ? bx,此时，若令 S ( x) ? ln S ( x), 则A ? ln a,B ? b,S ( x) ? A ? Bx ,这样就变成了形如（4.2）的线性模型 .126例9已知一组实验数据如下，求它的拟合曲线.xi fi 1 4 2 2 4.5 1 3 6 3 4 8 1 5 8.5 1?i解将所给数据在坐标纸上标出，见图3-5.图3-5127从图中看到各点在一条直线附近，故可选择线性函数作拟合曲线， 令 S1 ( x) ? a0 ? a1 x, 这里 m ? 4, n ? 1, ?0 ( x) ? 1, ?1 ( x) ? x, 故(? 0 , ? 0 ) ? ? ?i ? 8,i ?0 4(? 0 , ?1 ) ? (?1 , ? 0 ) ? ? ?i xi ? 22,i ?04(?1 , ?1 ) ? ? ?i xi2 ? 74,i ?0 44(? 0 , f ) ? ? ?i f i ? 47,i ?0 4(?1 , f ) ? ? ?i xi f i ? 145.5.i ?0128由（4.6）得方程组?8a0 ? 22a1 ? 47 ? ?22a0 ? 74a1 ? 145.5.(k ? 0,1, ?, n). （4.6） j ?0 解得 a0 ? 2.77, a1 ? 1.13. 于是所求拟合曲线为k? (?n, ? j )a j ? d k* S1 ( x) ? 2.77 ? 1.13x.129关于多项式拟合，Matlab中有现成的程序a ? polyfit ( x, y, m)其中输入参数 x, y为要拟合的数据， m为拟合多项式的次数，输出参数 a 为拟合多项式的系数.利用下面的程序，可在Matlab中完成上例的多项式拟合.130x=[1 1 2 3 3 3 4 5]; f=[4 4 4.5 6 6 6 8 8.5]; aa=poly(x,f,1); y=polyval(aa,x); plot(x,f,’r+’,x,y,’k’) xlabel(‘x’); ylabel(‘y’); gtext(‘y=s1(x)’）131结果如下：132例10 设数据 ( xi , yi )(i ? 0,1,2,3,4) 由表3-2给出， 表中第4行为 ln yi ? yi ,通过描点可以看出数学模型为 及 y ? aebx , 用最小二乘法确定 a b .?表3 ? 2 i xi yi 0 1.00 5.10 1 1.25 5.79 2 1.50 6.53 3 1.75 7.45 4 2.00 8.46133解用给定数据描图可确定拟合曲线方程为 y ? aebx ,ln y ? ln a ? bx,它不是线性形式. 两边取对数得 若令 y ? ln y, A ? ln a, 则得 y ? A ? bx, ? ? {1, x}. 为确定 A, b ，先将 ( xi , yi )转化为 ( xi , yi ), 数据表见表3-2. 根据最小二乘法，取? ( x) ? 1, ?1 ( x) ? x, ? ( x) ? 1, ?0得表3 ?? ) ? 5, (?0 , 20 4 i 0 1 2 (? 0 , ?1 ) ? ? xi ? 7.5, xi 1.00 i ?0 .25 1 1.50 5.10 4 5.79 6.53 (?1 , ?1 ) ? ? xi2 ? 11.875, yi 1.629 i ?1.756 1.876 0 yi3 1.75 7.45 2.0084 2.00 8.46 2.135134(? 0 , y ) ? ? yi ? 9.404,i ?0 44(?1 , y ) ? ? xi yi ? 14.422.i ?0故有法方程5 A ? 7.50b ? 9.404 ? ? ?7.50 A ? 11.875b ? 14.422.解得A ?1.122, b ? 0.505, a ? e A ? 3.071.于是得最小二乘拟合曲线为y ? 3.071e0.505x .135利用下面的程序，可在Matlab中完成曲线拟合.x=[1.00 1.25 1.50 1.75 2.00]; y=[5.10 5.79 6.53 7.45 8.46]; y1=log(y); aa=poly(x,y1,1); a=aa(1); b=exp(aa(2)); y2=b*exp(a*x); plot(x,y,’r+’,x,y2,’k’) xlabel(‘x’); ylabel(‘y’); gtext(‘y=a*exp(bx))’;136结果如下：1373.4.2用正交多项式做最小二乘拟合用最小二乘法得到的法方程组（4.6），其系数矩阵G是病态的.如果 ?0 ( x), ?1 ( x), ?, ?n ( x) 是关于点集 ? (? , ? )a ? d k ( ( ? ( 1? 0, n). （4.6） {xi }?0i ? k0,1,j?,j m) 带权 ?k xi )0,i ,?,1,?, m) 正交的? ( jn函数族，即? 0, (? j , ? k ) ? ? ? ( xi )? j ( xi )? k ( xi ) ? ? i ?0 ? Ak ? 0,mj ? k,j ? k,（4.8）138则方程（4.6）的解为( f ,?k ) ? i ?0 m (k ? 0,1, ?, n). ((?kk,,? k )a j ? d k ? ( x(k ?(0,i1, ?, n). （4.6） ? ?j ) ? i )? k2 x )i i k i ?0* ak n?? ? ( x ) f ( x )?m( xi )?j ?0（4.9）且平方误差为?2 2? f2 2* ? ? Ak (ak ) 2 . k ?0n139接下来根据给定节点 x0 , x1 , ?, xm 及权函数 ? ( x) ? 0, 构造带权 ? ( x ) 正交的多项式 {Pn ( x)} . 注意 n ? m，用递推公式表示 Pk (x) ，即? P ( x) ? 1, （4.10） 0 ? ? P ( x) ? ( x ? ?1 ) P0 ( x), 1 ? P ( x) ? ( x ? ? ) P ( x) ? ? P ( x) k ?1 k k k ?1 ? k ?1(k ? 1,2, ?, n ? 1).这里 Pk (x) 是首项系数为1的 k 次多项式， 根据 Pk (x) 的 正交性，得140? ( xP ( x ), Pk ( x)) k ? ? k ?1 ? i ? 0 ? m ( Pk ( x ), Pk ( x)) ? ? ? ( xi ) Pk2 ( xi ) ? i ?0 ? ? ( xP , Pk ) k ? ? ( Pk , Pk ) ? ? m ? ? ? ( xi ) Pk2 ( xi ) ? ( Pk , Pk ) i ?0 ? ? ?k ? m ( Pk ?1 , Pk ?1 ) ? ? ( xi ) Pk2 1 ( xi ) ? ?i ?0? ( xi ) xi Pk2 ( xi ) ?m（4.11）(k ? 1,2, ?, n ? 1).下面用归纳法证明这样给出的 {Pk ( x)}是正交的.141由（4.10）第二式及（4.11）中 ?1 的表达式，有( P , P ) ? ( P , xP ) ? ?1 ( P , P ) 0 1 0 0 0 0? P ( x) ? 1, （4.10） 0 ? 假定 ( P , P ) ? 0(l ? s) 对 s ? 0,1,?, l ? 1 及 l ? 0,1, ?, s ? P ( x) ? (l x ? ?1 ) P0 ( x), 1 ? P ( x) ? ( x ? ? ) P ( x) ? ? P ( x) k k s ? ? 均成立，要证k ?1P k , P ) ? 0 对?1 ? 0,1, ?, k 均成立. ( k ? kn1k ?1 s? ( P , xP ) ? 0 0( xP , P ) 0 0 ( P , P ) ? 0. 0 0 (P , P ) 0 0由（4.10）有(k ? 1,2, ?, n ? 1).( P ?1 , P ) ? (( x ? ? k ?1 ) P , P ) ? ? k ( P ?1 , P ) k s k s k s（4.12） ? P ( x) ? 1, 0 （4.10） ? ( ( ? ?1 ) P0 ( ? k k ? P ( x) ? ?x xP , Ps ) ?x), ?1 ( Pk , Ps ) ? ? k ( Pk ?1 , Ps ). 1 ? P ( x) ? ( x ? ? ) P ( x) ? ? P ( x) k ?1 k k k ?1 ? k ?1 142 (k ? 1,2, ?, n ? 1).由归纳法假定，当 0 ? s ? k ? 2 时( P , P ) ? 0, l s ( P ?1 , P ) ? 0. k s另外，xP (x) 是首项系数为1的 s ? 1 次多项式，它可由 sP , P , ?, P ?1 的线性组合表示. 0 1 s而 s ? 1 ? k ? 1， 由归纳法假定又有( xP , Ps ) ? ( Pk , xP ) ? 0, k s于是由（4.12），当 s ? k ? 2 时，( Pk ?1 , Ps ) ? 0.( P ?1 , P ) ? (( x ? ? k ?1 ) P , P ) ? ? k ( P ?1 , P ) k s k s k s（4.12）? ( xP , P ) ? ? k ?1 ( P , P ) ? ? k ( P ?1 , P ). k s k s k s143再考虑( P ?1 , P ?1 ) ? ( xP , P ?1 ) ? ? k ?1 ( P , P ?1 ) ? ? k ( P ?1 , P ?1 ), k k k k k k k k（4.13） 由假定有( P , P ?1 ) ? 0, k k ( xP , P ?1 ) ? ( P , xP ?1 ) ? ( P , P ? ? c j Pj ) ? ( P , P ). k k k k k k k kj ?0 k ?1利用（4.11）中 ? k 表达式及以上结果，得( P ?1 , P ?1 ) ? ( xP , P ?1 ) ? ? k ( P ?1 , P ?1 ) k k k k k k ( Pk , P ) ? k? ( P , P ) k? 0. ? ? (P , P ) k k k ( Pk ?1k P ?1 ) , k144最后，由 ? k 和 ? k 的表达式（4.11）有( P ?1 , P ) ? ( xP , P ) ? ? k ?1 ( P , P ) ? ? k ( P , P ?1 ) k k k k k k k k( xP , P ) , Pk ) k ( xP ? ( xP , P ) ? k ?1 ? k k ( Pk , P ) ? 0. ? k k k ( P , PPk , Pk ) (k ) k至此已证明了由（4.10）及（4.11）确定的多项式 {Pk ( x)} ? ( Pk , P ) k( Pk ?1 , P ) {xi }的正交系.? k ?1 组成一个关于点集?k ?用正交多项式 {Pk ( x)} 的线性组合作最小二乘曲线拟合， 只要根据公式（4.10）及（4.11）逐步求 Pk (x) 的同时，* 相应计算出系数 a k145( f , Pk ) ? a ? ( Pk , Pk )* k??(x ) f (x )P (x )i ?0 i i k im? ? ( x )Pi ?0 im(k ? 0,1, ?, n),2 k( xi )* 并逐步把 ak Pk ( x)累加到 S ( x ) 中去，最后就可得到所求的拟合曲线* * * y ? S ( x) ? a0 P0 ( x) ? a1 P ( x) ? ? ? an Pn ( x). 1这里 n可事先给定或在计算过程中根据误差确定. 用这种方法编程序不用解方程组，只用递推公式，并 且当逼近次数增加一次时，只要把程序中循环数加1，其余 不用改变.1463.53.5.1有 理 逼 近有理逼近与连分式有理函数逼近是指用形如Rnm ( x) ? P ( x) n ? Qm ( x)?a ?bk ?0 k ?0 mnkxk xk（5.1）k的函数逼近 f (x ).与前面讨论一样，如果 f ( x) ? Rnm ( x) 最佳有理一致逼近.?最小就可得到147如果 f ( x) ? Rnm ( x) 2 最小则可得到最佳有理平方逼近 函数.本节主要讨论利用函数的泰勒展开获得有理逼近函数的方法.对函数 ln( 1 ? x)用泰勒展开得ln( 1 ? x) ? ? (?1)k ?1 ? k ?1xk kx ? [?1,1].（5.2）取部分和S n ( x) ? ? ( ?1) k ?1k ?1 nxk ? ln( 1 ? x). k148另一方面若对（5.2）式用辗转相除可得到 ln( 1 ? x) 的 一种连分式展开x 1? x 1? k ? 1? x k ?1 x 2? ln( 1 ? x) ? ? (?1) x2 2[? x,1]. ? ?1 3k ? k ?1 22 ? x 4? 5 ?? ln( 1 ? x ) ?（5.2）x 1? x 1? x 2 2 ? x 2 2 ? x ? . 1 ? 2 ? 3 ? 4 ? 5 ??（5.3）149（5.3）右端为 ln( 1 ? x) 的无穷连分式的前5项，最后式子 是它的紧凑形式. 若取（5.3）的前2，4，6，8项，则可分别得到 ln( 1 ? x) 的以下有理逼近2x 6 x ? 3x 2 R22 ( x) ? , ? R11 ( x ) ? 2 ? x , 2 6 ? 6x ? x ? ? 2 3 ? R33 ( x) ? 60 x ? 60 x ? 11x ? , 2 ? 3x 3 ? 60 ? 90 x ? 36 x ? ? 420 x ? 630 x 2 ? 260 x 3 ? 25 x 4 ? R44 ( x ) ? . （5.4） ? 2 ? 120 x 3 ? 6 x 4 420 ? 840 x ? 540 x ?150若用同样多项的泰勒展开部分和 S 2 n ( x) 逼近 ln( 1 ? x) 并计算 x ? 1 处的值 S 2n (1)及 Rnn (1)，计算结果见表3-3.表3 ? 3 n 1 2 3 4 S 2 n (1) 0.50 0.58 0.617 0.634? s ? ln( 2) ? S 2 n (1)0.19 0.11 0.076 0.058Rnn (1) 0.667 0.122 0.? R ? ln( 2) ? Rnn (1)0.026 0.025 0.ln 2 的准确值为 0.?, 从表3-1可以看出，R44 (1) ? 0.,S8 (1) ? 0.634,151由此看出 R44 (1) 的精度比 S8 (1) 高出近10万倍， 但它们的计算量是相当的，这说明用有理逼近比多项 式逼近好得多.152例11给出有理函数2 x 4 ? 45 x 3 ? 381x 2 ? 1353x ? 1511 R43 ( x) ? x 3 ? 21x 2 ? 157 x ? 409用辗转相除法将它化为连分式并写成紧凑形式. 解 用辗转相除可逐步得到1534 x 2 ? 64 x ? 284 R43 ( x) ? 2 x ? 3 ? x 3 ? 21x 2 ? 157 x ? 409? 2x ? 3 ? 4 6( x ? 9) x?5? x 2 ? 16 x ? 714 x?5? 6 x?7? 8 x?9? 2x ? 3 ?? 2x ? 3 ?4 6 8 . x?5? x?7 ? x?9本例中用连分式计算 R43 ( x)的值只需3次除法，1次乘法和7次加法.154若直接用多项式计算的秦九韶算法则需6次乘法和1次 除法及7次加法. 可见将 Rnm (x) 化成连分式可节省计算乘除法次数. 对一般的有理函数,（5.1）可转化为一个连分式cl c2 Rnm ( x) ? P ( x) ? . 1 x ? d1 ? ? ? x ? d l它的乘除法运算只需 max( m, n) 次.而直接用有理函数（5.1）计算乘除法次数为 n ? m 次.1553.5.2帕德逼近? 利用函数 f (x) 的泰勒展开可以得到它的有理逼近.设 f (x)在 x ? 0的泰勒展开为1 f ( x) ? ? f k ? 0 k!N (k )f ( N ?1) (? ) N ?1 (0) x ? x . ( N ? 1)!k（5.5）它的部分和记作1 P( x) ? ? f k ? 0 k!N (k )(0) x k ??ck ?0Nkxk .（5.6）156定义8设 f ( x) ? C N ?1 (?a, a), N ? n ? m,如果有理函数a0 ? a1 x ? ? ? an x n Pn ( x) Rnm ( x) ? ? , m 1 ? b1 x ? ? ? bm x Qm ( x)（5.7）其中 Pn ( x), Qm ( x) 无公因式，且满足条件(k Rnm) (0) ? f (k )(0)(k ? 0,1, ?, N ),（5.8）则称 Rnm (x) 为函数 f (x) 在 x ? 0 处的 (n, m) 阶帕德逼近， 记作 R(n, m) ,简称 R(n, m) 的帕德逼近.157根据定义，若令h( x) ? P( x)Qm ( x) ? P ( x), n则满足条件（5.8）等价于h ( k ) (0) ? 0 k ? 0,1,?, N .即(k （5.8） Rnm) (0) ? f ( k ) (0) (k ? 0,1, ?, N ), (k ) (k ) h (0) ? ( P( x)Qm ( x) ? Pn ( x)) ? 0, k ? 0,1,?, N .x ?0由于 Pn( k ) (0) ? k!ak , 应用莱布尼兹求导公式得( P( x)Qm ( x) ? Pn ( x)) ( k )x ?0? k!? c j bk ? j ? k!ak ? 0j ?0kk ? 0,1, ?, N ,1581 这里 c j ? f j!( j)(0) 是由（5.6）得到的，上式两端除 k! ，并由 b0 ? 1, b j ? 0(当j ? m时), 可得ak ? ? c j bk ? j ? ckj ?0 k ?1(k ? 0,1, ?, n)（5.9） （5.6）及1 P( x) ? ? f k ? 0 k!? ? c j bk ? j ? ckj ?0 k ?1N(k )(0) x k ??ck ?0Nkxk .(k ? n ? 1, ?, n ? m)（5.10）注意当 j ? m 时 b j ? 0, 故（5.10）可写成159? ? cn ? m ?1bm ? ? ? cn ?1b2 ? cn b1 ? cn ?1 , ? ?c ? n ? m ? 2 bm ? ? ? cn b2 ? cn ?1b ? cn ? 2 , 1 ? ? ??? ??? ??? ?? ? ?? cn bm ? ? ? cn ? m ? 2b2 ? cn ? m ?1b1 ? cn ? m , ?, 其中 j ? 0时 c j ? 0， 若记（5.11）? ? cn ? m ?1 ?? c H ? ? n?m? 2 ? ? ? ? ? cn? ? ? ?? cn ?1 ? cn ? ? cn ? m ? 2? ? cn ?1 ? ?, （5.12） ? ? ? ? cn ? m ?1 ?? cnb ? (bm , bm?1 ,?, b1 )T ,c ? (cn?1 , cn? 2 ,?, cn? m )T .160则方程组（5.11）的矩阵形式为Hb ? c .定理11设 f ( x) ? C N ?1 (?a, a),N ? n ? m, 则形如（5.7）的有理函数 Rnm (x) 是 f (x) 的 (n, m)阶帕德逼近的 充分必要条件是多项式 Pn ( x), Qm ( x) 的系数 a0 , a1 ,?, an 及 b0 , b1 ,?, bm 满足方程组（5.9）及（5.11）.161根据定理11, 求 f (x) 的帕德逼近时， 首先要由（5.11）解出 Qm (x)的系数 b0 , b1 ,?, bm ，再由（5.9）直接算出 Pn (x) 的系数 a0 , a1 ,?, an .? ? cn ? m ?1bm ? ? ? cn ?1b2 ? cn b1 ? cn ?1 , ? ?c 3-4）. ? n ? m ? 2 bm ? ? ? cn b2 ? cn ?1b ? cn ? 2 , 1 ? 3- 4 表 ? ? m ??? ??? ??? ?? 0 2 ?? cn bm ? ? ? cn ? m12b2 ? cn ? m ?1b1 ?3 n ? m , c ? n ?0 1 2 4 ?k ?1 j ?0f (x )的各阶帕德逼近可列成一张表，称为帕德表（见表（5.11）4 (0, 4) (1 4) , ( 2, 4) ( 4, 4) ? ? ? ? ? ? ?162(0,0) (1 0) , ( 2,0) ( 4,0) ?(0, ) 1 (1 1) , ( 2, ) 1 ( 4, ) 1 ?(0, 2) (1 2) , ( 2, 2) ( 4, 2) ?(0,3) (1,3) ( 2,3) ( 4,3) ?ak 3 ? c 3,k ?) ? ck3,1) (k 3,2,1, ?,3,) ) ? (jb 0 j ( ( ? 0) ( n3(（5.9） 3, 4) ?例12 求 f ( x) ? ln( 1 ? x)的帕德逼近 R (2,2) 及 R(3,3). 解 由 ln( 1 ? x) 的泰勒展开1 2 1 3 1 4 ln( 1 ? x) ? x ? x ? x ? x ? ? 2 3 4 1 1 1 得 c0 ? 0, c1 ? 1, c2 ? ? , c3 ? , c4 ? ? , ?. 2 3 4当 n ? m ? 2时，由（5.11）得1 1 ? ? b2 ? b1 ? , ? 2 3 ?1 1 1 ? b2 ? b1 ? ? . 3 4 ?2求得 b1 ? 1, b2 ? 1 , 再由（5.9）得 6163a0 ? 0,a1 ? 1,a2 ?1 , 2于是得1 2 x 6 x ? 3x 2 2 ? . R22 ( x) ? 2 1 6 ? 6x ? x 1? x ? x2 6 x?当 n ? m ? 3时，由（5.11）得1 1 1 ? ? b3 ? b2 ? b1 ? ? , ? 2 3 4 ? 1 1 1 1 ? b3 ? b2 ? b1 ? , ? 3 4 5 ? 2 ?? 1 b ? 1 b ? 1 b ? ? 1 , ? 3 3 4 2 5 1 6 ?164解得b1 ? 3 , 2 b2 ? 3 , 5 b3 ? 1 . 20代入（5.9）得a0 ? 0, a1 ? 1, a2 ? 1, 11 a3 ? . 60于是得11 3 x?x ? x 60 x ? 60 x 2 ? 11x 3 60 R33 ( x ) ? ? . 2 ? 3x 3 3 3 2 1 3 60 ? 90 x ? 36 x 1? x ? x ? x 2 5 202165可以看到这里得到的 R22 ( x) 及 R33 ( x) 与 ln( 1 ? x) 的前面连分式展开得到的有理逼近（5.4）结果一样.为了求帕德逼近 Rnm (x) 的误差估计，由(5.9)及(5.11) 求得的 Pn ( x), Qm ( x)系数 a0 , a1 ,?, an 及 b0 , b1 ,?, bm ，直 接代入则得f ( x)Qm ( x) ? Pn ( x) ? xn ? m ?1 ? m(?? bk cn ? m ?1?l ? k )x l ,l ?0 k ?0将 Qm (x)除上式两端，即得166x f ( x) ? Rnm ( x) ?mn ? m ?1rl x l ?l ?0?Qm ( x),（5.13）其中 rl ? ? bk cn ? m ?l ?1? k .k ?0当 x ?1 时可得误差近似表达式f ( x) ? Rnm ( x) ? r0 xn ? m ?1,r0 ? ? bk cn ? m ?1? k .k ?0m1673.6三角多项式逼近与快速傅里叶变换当模型数据具有周期性时，用三角函数特别是正弦和余 弦函数作为基函数是合适的，这时前面讨论的用多项式、分 段多项式或有理函数作基函数都是不适合的. 用正弦函数和余弦函数级数表示函数称为傅里叶变换 （简称傅氏变换）.1683.6.1项式??最佳平方三角逼近与三角插值设 f (x) 是以 2?为周期的平方可积函数，用三角多 π1 S n ( x) ? a0 ? a1 cos x ? b1 sin x ? ? ? an cos nx ? bn sin nx 2 （6.1） 做最佳平方逼近函数. 由于三角函数族1,cos x,sin x,? ,cos kx,sin kx, ?在 [0,2 π ] 上是正交函数族，于是 f (x) 在 [0,2 π ] 上的最小 平方三角逼近多项式 S n (x) 的系数是?1691 ak ? π1 bk ? π??2?02?f ( x) cos kxdx(k ? 0,1, ?, n),（6.2）0f ( x) sin kxdx(k ? 0,1, ?, n),ak , bk 称为傅里叶系数.函数 f (x) 按傅里叶系数展开得到的级数? 1 a0 ? ? ( ak cos kx ? bk sin kx) 2 k ?1（6.3）就称为傅里叶级数.170只要 f ?(x )在 [0,2 π ] 上分段连续，则级数（6.3）一致 收敛到 f (x). 对于最佳平方逼近多项式（6.1）有? 1 a0 ? ? ( ak cos kx ? bk sin kx) 2 f ( x)k? S ( x) 2 ? f ( x) 2 ? S ?1n22n( x) 2 .2（6.3）1 由此可以得到相应于（3.11）的贝塞尔不等式 ? b sin nx S n ( x) ? a0 ? a1 cos x ? b1 sin x ? ? ? an cos nx n 2 n （6.1） 1 2 1 2? 2 2 2?2 * ( ak ? k ( x ) 2 ) 2 ? f ( x ) 2 . ? 因为右边不依赖于 n ，左边单调有界，所以级数 k ?1n2a0 ? ? (ak ? bk ) ?k ?1?0[ f ( x)] dx.（3.11）171? 1 2 2 2 a0 ? ? ( ak ? bk ) 2 k ?1收敛，并有lim ak ? lim bk ? 0.k ?? k ??当 f (x)只在给定的离散点集2π ? ? xj ? j , j ? 0,1,?, N ?1? ? N ? ?上已知时，则可类似得到离散点集正交性与相应的离散傅 里叶系数. 下面只给出奇数个点的情形.172令xj ? 2 πj 2m ? 1( j ? 0,1,?,2m),可以证明对任何 0 ? k , l ? m 成立? 2m ?0, ?? sin l x j sin kx j ? ? 2m ? 1 ? , ? j ?0 ? 2 ? ? ?0, ? ? 2m ? 1 ? 2m ?? cos l x j cos kx j ? ? ? j ?0 ? 2 ?2m ? 1, ? ? 2m 0 ? k, ?? cos l x j sin kx j ? 0, ? j ?0 ? l ? k , l ? k ? 0; l ? k ? 0; l ? l ? k ? 0; l ? k ? 0; j ? m.173这表明函数族 {1, cos x,sin x,? , cos mx,sin mx} 在点集{x j ? 2 πj } 2m ? 1上正交.若令 f j ? f ( x j )乘三角逼近为( j ? 0,1,?,2m), 则 f (x) 的最小二n 1 S n ( x) ? a0 ? ? ( ak cos kx ? bk sin kx), 2 k ?1n ? m,其中2m 2 2πjk ak ? f j cos ? 2m ? 1 j ? 0 2m ? 1(k ? 0,1, ?, m),1742m 2 2 πjk bk ? f j sin ? 2m ? 1 j ? 0 2m ? 1(k ? 1, ?, n).（6.4）当 n ? m时Sm ( x j ) ? f j ( j ? 0,1, ?,2m) ,于是m 1 S m ( x) ? a0 ? ? (ak cos kx ? bk sin kx) 2 k ?1就是三角插值多项式，系数仍由（6.4）表示.175一般情形，假定 f (x) 是以 2π为周期的复函数，给定 在 N个等分点 x j ? 由于eijx ? cos( jx) ? i sin( jx) ( j ? 0,1,?, N ? 1, i ? ? 1),2π ? 2π j ( j ? 0,1, ?, N ? 1) 上的值 f j ? f ? N ?N? j ?, ?所以函数族 {1, eix ,?, ei ( N ?1) x }在区间 [0,2 π ] 上是正交的. 函数 e ijx 在等距点集 xk ? 2π k (k ? 0,1, ?, N ? 1) 上的值Ne ijxk 组成的向量记作? j ? (1, eij2π N, ?, eij2π ( N ?1) N)T .176当 j ? 0,1,?, N ? 1时，N 个复向量 ?0 , ?1 , ?, ? N ?1 具有 如下正交性：(?l , ?s ) ? ? ek ?0 N ?1 il 2π k Ne?is2π k N? ?ek ?0N ?1i(l ? s )2π k N? 0, l ? ?? ? N , l ? s.（6.5）177事实上，令 r ? ei (l ?s )2π N, 若 0 ? l , s ? N ? 1, 则有0 ? l ? N ? 1,? ( N ? 1) ? ?s ? 0,于是? ( N ? 1) ? l ? s ? N ? 1,即N ?1 l ? s N ?1 ?1 ? ? ? ? ? 1; N N N若 l ? s ? 0, 则 r ? 1, 从而r N ? ei ( l ?s ) 2 π ? 1;178于是(?l , ?s ) ??rk ?0N ?1k1? r N ? 1? r? 0.若 l ? s, 则 r ? 1, 于是(?s , ?s ) ? r k ? N. ?k ?0 N ?1这就证明了（6.5）成立. 即 ?0 , ?1 , ?, ? N ?1 是正交的. 因此， f (x)在 N个点 {x j ? j ( j ? 0,1, ?, N ? 1)} 上的 N ? 0, l ? 最小二乘傅里叶逼近为 (?l ,?s ) ? ? （6.5） N , l ? s. ?1792πS ( x) ?ck e ikx , ?k ?0n ?1n ? N,（6.6）其中1 ck ? N?fj ?0N ?1je-ikj2π N,( k ? 0,1, ?, n ? 1). （6.7）在（6.6）中，若 n ? N ，则 S ( x )为 f (x) 在点x j ( j ? 0,1, ?, N ? 1) 上的插值函数， 即 S ( x j ) ? f ( x j ),于是由（6.6）得f j ? ? ck ek ?0 N ?1 ik 2π j N,( j ? 0,1, ?, N ? 1).（6.8）180（6.7）是由 { f j } 求 {ck } 的过程， 称为 f (x) 的离散 傅里叶变换. 简称DFT， 而（6.8）是由 {ck } { f j } 的过程，称为反变换. 求1 ck ? N?fj ?0N ?1je-ikj2π N,( k ? 0,1, ?, n ? 1). （6.7）f j ? ? ck ek ?0N ?1ik2π j N,( j ? 0,1, ?, N ? 1).（6.8）1813.6.2N点DFT与FFT算法不论是按（6.7）式由 { f j } 求 {ck } ，或是按（6.8） 由 {ck }求 { f j } 还是由（6.4）计算傅里叶逼近系数 ak , bk , ， 都可归结为计算2 kj 2 m 2 πjk c j ? k ? xk ? N? f ( cos 0,1, ?, N ? 1), , j j? a 2m ?1 （6.4） k ? 0 2m ?1 j ?0N ?1?（6.9）2m N 其中 {xk }0 ?1为已知的输入数据，{c j }0 ?1为输出数据，而 2 2 πjk Nbk ?? i 2N?N e2?j?0 2? ? cos ? isin , i ? ? 1. N N182?f 2m ?1jsin2m ?1（6.9）式称为 N点DFT，表面上看计算 c j 需要 N次复 数乘法和 N次复数加法，称为 N个操作，计算全部 c j 共要 N 2 个操作. N ?1 （6.9） c ? 当 N 较大且处理数据很多时，就是用高速的电子计算 x wkj , ( j ? 0,1, ?, N ? 1),j?k ?0k机，很多实际问题仍然无法计算，直到20世纪60年代中期产生了FFT算法，大大提高了运算速度，才使DFT得到更广泛的应用.FFT是快速算法的一个典范，其基本思想就是尽量减 少乘法次数.183对于任意正整数 k, j ，成立j k j jN k ? N ? ? N ? ? N? k , ? N ? k ? ? N (周期性）， jk jk jk k ? N ? N / 2 ? ?? N (对称性）， ? jN ? ? N .jk 由周期性可知所有 ? N ( j, k ? 0,1,?, N ? 1) 中，做多有 N个不 0 N 同的值 ? N , ?1 ,?, ? N ?1. N特别地，有0 N N ? N ? ? N ? 1, ? N / 2 ? ?1. jk 当 N ? 2 p 时， ? N 只有 N / 2 个不同的值.利用这些性质可将（6.9）式对半折成两个和式，再将对应项相加，有cj ?N / 2 ?1 k ?0 N / 2 ?1 k ?0 N / 2 ?1 k ?0?x ?kjk N??xN / 2? k ?j ( N / 2? k ) N??[ xkjk ? (?1) j x N / 2? k ]? N .184依下标奇、偶分别考察，则c2 j ?N / 2 ?1 k ?0? (xN / 2 ?1 k ?0kjk ? x N / 2 ? k )? N / 2 ,c2 j ?1 ?jk ( xk ? x N / 2? k )? N / 2 . ?若令yk ? ( xk ? xN / 2? k ),k y N / 2? k ? ( xk ? xN / 2? k )? N ,则可将 N 点DFT归结为两个 N / 2点的DFT：N / 2 ?1 ? jk c2 j ? ? y k ? N / 2 , ? ? k ?0 ? N / 2 ?1 jk ?c ? ? y N / 2? k ? N / 2 . ? 2 j ?1 k ?0 ?j ? 0,1, ?, N / 2 ? 1,如此反复施行二分手续即可得到FFT算法.185以N ? 23 为例说明FFT的计算方法，此时 k , j ? 0,1,?, N ? 1 ? 7在（6.9）中将 ? N ? ?8 记为 ? ，于是（6.9）式的和为cj ??x ?k ?0 k7jk,( j ? 0,1, ?,7).（6.10）将 k, j 用二进制表示为k ? k 2 2 2 ? k1 21 ? k0 20 ? (k 2 k1k0 ),j ? j2 2 2 ? j1 21 ? j0 20 ? ( j2 j1 j0 );其中 kr , jr (r ? 0,1,2) 只能取0或1. 例如 6 ? 22 ? 22 ? 0 ? 20 ? (110). 根据 k, j 表示法，有c j ? c( j2 j1 j0 ), xk ? x(k 2 k1k0 ).186c j ? ? xk ? kj , （6.10） 2 1 0 c( j2 j1 j0 ) ? ? ? ? x(k 2k ? 0 0 )? ( k 2 k1k0 )( j2 2 ? j1 2 ? j0 2 ) k1k1 1 1 k 0 ? 0 k1 ? 0 k 2 ? 01公式（6.10）可表示为7（6.11）? 1 ? 1 ? j1 ( k1k0 0 ) ? ? ? j0 ( k 2 k1k 0 ) j ( k 00) ? ? ? ? ? ? x(k 2 k1k0 )? ? ? ?? 2 0 ? ? k 0 ? 0 ?k1 ? 0 ? k 2 ? 0 ? ? ?若引入记号? A0 (k2 k1k0 ) ? x(k2 k1k0 ), ? 1 ? A1 (k1k0 j0 ) ? ? A0 ( k 2 k1k0 ) w j0 ( k 2 k1k0 ) , ? k 2 ?0 ? 1 ? A2 (k0 j1 j0 ) ? ? A1 (k1k0 j0 ) w j1 ( k1k0 0 ) , ? k1 ? 0 ? 1 ?A ( j j j ) ? A2 ( k 0 j1 j0 ) w j2 ( k0 00) . ?0 ? 3 2 1 0 k0 ? ?（6.12）187则（6.11）变成c( j2 j1 j0 ) ? A3 ( j2 j1 j0 ).若注意 ? j 2 ? ? j N / 2 ? (?1) j , 公式（6.12）还可进一步p?1 0 0 0简化为A1 (k1k0 j0 ) ?k 2 ?0? A (k012k1k0 )? j0 ( k 2 k1k0 )j0 ( 0 k1k 0 )? A0 (0k1k0 )?? A0 (1k1k0 )?j0 2 2?j0( 0 k1k 0 )? [ A0 (0k1k0 ) ? (?1) j0 A0 (1k1k0 )]? j0 ( 0 k1k0 ) ,A (k1k0 0) ? A0 (0k1k0 ) ? A0 (1k1k0 ), 1A1 (k1k01) ? [ A0 (0k1k0 ) ? A0 (1k1k0 )]? ( 0 k1k0 ) .188将这表达式中二进制表示还原为十进制表示：k ? (0k1k0 ) ? k1 21 ? k0 20 ,即 k ? 0,1,2,3, 得2 ? A1 (2k ) ? A0 (k ) ? A0 (k ? 2 ), ? ? 2 k ? A1 ( 2k ? 1) ? [ A0 ( k ) ? A0 ( k ? 2 )]w ? ? ( k ? 0,1,2,3). ?（6.13）同样（6.12）中的 A2 也可简化为A2 (k0 j1 j0 ) ? [ A1 (0k0 j0 ) ? (?1) j1 A1 (1k0 j0 )]? j1 ( 0 k0 0 ) ,即A2 (k0 0 j0 ) ? A (0k0 j0 ) ? A (1k0 j0 ), 1 1A2 (k01 j0 ) ? [ A1 (0k0 j0 ) ? A0 (1k0 j0 )]? ( 0 k0 0 ) .189把二进制表示还原为十进制表示，得? A2 (k 22 ? j ) ? A (2k ? j ) ? A (2k ? j ? 22 ), 1 1 ? ? 2 2 2k ? A2 ( k 2 ? j ? 2) ? [ A1 ( 2k ? j ) ? A1 ( 2k ? j ? 2 )]w ? ? （6.14） ( k ? 0,1; j ? 0,1). ?同理（6.12）中 A3 可简化为A3 ( j2 j1 j0 ) ? A2 (0 j1 j0 ) ? (?1) j2 A2 (1 j1 j0 ),即A3 (0 j1 j0 ) ? A2 (0 j1 j0 ) ? A2 (1 j1 j0 ), A3 (1 j1 j0 ) ? A2 (0 j1 j0 ) ? A2 (1 j1 j0 ).190表示为十进制，有A3 ( j ) ? A2 ( j ) ? A2 ( j ? 2 2 ), ? ? ? 2 2 ? A3 ( j ? 2 ) ? A2 ( j ) ? A2 ( j ? 2 ) ? ? ( j ? 0,1,2,3). ?（6.15）根据公式(6.13)，(6.14)，(6.15)，由A0 (k ) ? x(k ) ? xk(k ? 0,1, ?,7)逐次计算到 A3 ( j ) ? c j ( j ? 0,1, ?,7), 见表3-5(略）.从表3-5中看到计算全部8个 c j只用8次乘法运算和24次 加法运算.191上面推导的 N ? 23 的计算公式可类似地推广到 N ? 2 p的情形.根据公式(6.13)，(6.14)，(6.15)，一般情况的FFT计算公式如下：q q ?1 ? j ) ? A q ?1 ? j ? 2 p ?1 ), q ?1 (k 2 ? Aq (k 2 ? j ) ? Aq ?1 (k 2 ? ? Aq (k 2q ? j ? 2q ?1 ) （6.16） ? ? ? ? [ Aq ?1 ( k 2 q ?1 ? j ) ? Aq ?1 ( k 2 q ?1 ? j ? 2 p ?1 )]wk 2 q?1 , ?其中 q ? 1,?, k ? 0,1,?,2 p ?q ? 1; j ? 0,1,?,2q ?1 ? 1.Aq 括号内的数代表它的位置，在计算机中代表存放数的地址.192一组 Aq占用 N个复数单元，计算时需给出两组单元，从 A0 (m)( m ? 0,1,?, N ? 1) 出发， q 由 1到 p算到Ap ( j ) ? c j ( j ? 0,1, ?, N ? 1), 即为所求.计算过程中只要按地址号存放 Aq , 则最后得到的 Ap ( j ) 就是所求离散频谱的次序. 这个计算公式除了具有不倒地址的优点外，计算只有两 重循环.p ?q ? 1, 外循环 q由 1计算到 p，内循环 k由 0计算到 2j 由 0计算到 2 q ?1 ? 1, 更重要的是整个计算过程省计算量.193由公式看到算一个 Aq 共做 2 p ? q 2 q /1 ? N / 2 次复数乘法， 而最后一步计算 Ap 时，由于?k 2 p?1? (? N / 2 ) k ? (?1) k ? (?1) 0 ? 1（注意 q ? p 时 2 p ?q ? 1 ? 0, 故 k ? 0 ），因此，总共要算( p ? 1) N / 2 次复数乘法，它比直接用（6.9）需 N 2次乘法快得多，计算量比值是 N : ( p ? 1) / 2.当 N ? 210时比值是 1024 : 4.5 ? 230 : 1, 它比一般FFT的 计算量（ pN 次乘法）也快一倍. 我们称（6.16）的计算公式为改进的FFT算法 .194例13设 f ( x) ? x 4 ? 3x 3 ? 2 x 2 ? tan x( x ? 2) .给定j 确定三角插值多项式. 4yj数据 {x j , f ( x j )}7j ?0 , x j ?解先将 [0,2] 变换为 [?? , ? ] ，可令 y j ? ? ( x j ? 1) ，f j ? f (1 ?故输入数据为 { y j , f j )}7 , 0给定8个点可确定8个参数的4次三角插值多项式3 1 S 4 ( y ) ? a0 ? ? ( ak cos ky ? bk sin ky) ? a4 cos 4 y （6.17） 2 k ?1?).这里2 7 ? ? ak ? ? f j cos 28 kj, k ? 0,1, ?,4, ? 8 j ?0 ? ? 2 7 ?b ? ? f j sin 28? kj, k ? 1,2,3, k ? 8 j ?0 ?（6.18）195与（6.10）式比较可先计算ck ? ? f j? jk ,j ?0 7这里 { f j }7代替（6.10）式的 {x j }7， 0 0? ?e2 i 8??ei? 4? cos?4? isin?4.对每个 k ? 0,1,?,4有1 1 1 7 1 7 i ? kj ? i?k ik ( ? ? ? ? j ) k ?i?k 4 4 ck ( ?1) ? ck e ? ? f je e ? ? f je 4 4 4 j ?0 4 j ?0 1 7 ?j ?j ? ? f j (cosk ( ?? ? ) ? isin k ( ?? ? )) 4 j ?0 4 4 1 7 ? ? f j (cosky j ? isin ky j ), 4 j ?0196所以(?1) k 1 ak ? ibk ? ck ? ck e ?i?k , 4 4即1 ak ? Re( ck e ?i?k ), 4 1 bk ? Im( ck e ?i?k ). 4显然 b0 ? b4 ? 0 ，用FFT算法求出 ck (k ? 0,1,2,3,4)，也就 得到（6.18）式的系数，从而得到（6.17）式的4次三角插值多项式S 4 ( y ) ? 0.761979 ? 0.771841 cos y ? 0.386374 sin y ? 0.0173037 cos 2 y ? 0.0468750 sin 2 y ? 0. cos 3 y ? 0.0113738 sin 3 y ? 0. cos 4 y.197将 y ? ? ( x ? 1) 代入 S4 ( y) 可以得到 [0,2]上的三角多项式S 4 ( x).图3-6给出了 y ? f (x) 及 y ? S4 ( x) 的图形. 表3-6给出了在点 x j ? 0.125 ? j 0.25( j ? 0,1,?,7) 处 f ( x j ) 与 S 4 ( x j ) 的值.图3-6198
更多相关文档