計算方法-插值方法(參考版)
2025-05-17 04:10本頁面
【正文】 010 )1(2 jj pW ???。 例： N = 23 = 8, 計算 ， j = 0, 1, 2, 3, 4, 5, 6, 7 ??? 70kkjkj WxC技巧： 將 k , j 先記為 二進制數(shù) /* binary numbers */ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ) ( 2 2 2 ) ( 2 2 2 0 1 2 0 0 1 1 2 2 0 1 2 0 0 1 1 2 2 j j j j j j j k k k k k k k k j W ) 2 2 2 ( ) 2 2 2 ( 0 0 1 1 2 2 0 0 1 1 2 2 ? ? ? ? ? ? ? ? ? ? ? ? k k k j j j W ) ( ) 2 2 2 ( ) 2 2 2 ( 0 1 2 0 1 0 2 1 3 2 1 2 0 3 1 4 2 2 k k k j k k k j k k k j W ? ? ? ? ? ? ? ? ? ? ? ? ? ) ( ) 0 ( ) 0 0 ( 0 1 2 0 0 1 1 0 2 k k k j k k j k j W ? ? ? ? ? ?? ? ? ?????????????????10)00(10)0(10)()()(002101120120012021kkjkkkjkkkkjkkkjjj WWWxC)( 0120 kkkA)( 0011 jkkA)( 0102 jjkA)( 0123 jjjA2?3次乘法 全部計算需要 2?3 ?8次乘法 一般地：取 N = 2p ， 每個 Cj 用 2p 次乘法，共用 2N log2N 次乘法。若 N 為偶數(shù)，則 W k j只有 個不同值。 )1,...,1,0(2 ??? NkkNx k ?)( kk xff ? ???? 10)()( Njjxij eCxS kk fxS ?)(N 個未知數(shù) N 個方程 )1,...,1,0(1102 ??? ? ????????? NjefNCNkkNjikj?Discrete Fourier Transform )1,...,1,0(102??? ????????? NkeCf NjkNjijk?Inverse of DFT 總之要進行形如 的計算，其中 已知， ???? 10Nkjkkj WxC? ?kx ???????? NieW ?2? Fast Fourier Transform ???? 10Nkjkkj WxC???????? NieW ?2快速計算 ( j = 0, 1, …, N?1)， 其中 直接計算需 復(fù)數(shù)乘法 次 N 2 ? 降到 N xn=b上的函數(shù)值為 在每個小區(qū)間 [xk,xk+1]上作線性插值，得 稱 L(x)為 f(x)的分段線性插值函數(shù) ? ? ? ? ? ? ? ?njxx xxxfxx xxxfxLjjjjjjjj ,2,11111 ???????????? 快速傅立葉變換 /* Fast Fourier Transform */ ? 問題的背景 /* background */ 傅立葉變換 —— 函數(shù)展開為 三角級數(shù) 設(shè) f(x) 周期為 2?，在 [0, 2? ] 上展開為三角級數(shù) ， 其中 Cj 為復(fù)系數(shù)， ，則實際計算時要取級數(shù)的前 N 項，并要求在區(qū)間的 N 個等分點上與 f(x)重合。 經(jīng)典例子： 取等距節(jié)點 ，所構(gòu)造的拉 格朗日插值多項式為 ? ? ? ?5,51 1 2 ???? xxxf? ?nin ix i ,1,0105 ?????? ?nnin 2j0 i0j j iijxx1Lx1 x x x? ???????? ?n 越大，端點附近抖動越大，稱為 Runge 現(xiàn)象 所謂分段線性插值就是通過插值點用折線段連接 起來逼近 f(x)。i(xj)=0 h39。 定理二 :f(x)在區(qū)間 [a,b]存在 2n+2階導(dǎo)數(shù) ,則其 Hermite插值余項為 : ),()!22( )]()[()()()(2)22(12 banxfxHxfxR nn ??????? ?????(x)=(xx0)(xx1)…...(x xn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1