ch2：代數(shù)插值1.ppt

第2章插值 Interpolation 當(dāng)精確函數(shù)y f x 非常復(fù)雜或未知時 在一系列節(jié)點x0 xn處測得函數(shù)值y0 f x0 yn f xn 由此構(gòu)造一個簡單易算的近似函數(shù)g x f x 滿足條件g xi f xi i 0 n 這里的g x 稱為f x 的插值函數(shù) 最常用的插值函數(shù)是 多項式 g x f x 1拉格朗日多項式 LagrangePolynomial n 1 可見P1 x 是過 x0 y0 和 x1 y1 兩點的直線 稱為拉氏基函數(shù) LagrangeBasis 滿足條件li xj ij KroneckerDelta 1LagrangePolynomial n 1 LagrangePolynomial 1LagrangePolynomial 定理 唯一性 滿足的n階插值多項式是存在且唯一的 證明 存在性證明 p 161利用Vandermonde行列式論證 唯一性用反證法 若不唯一 則除了Ln x 外還有另一n階多項式Pn x 滿足Pn xi yi 注 若不將多項式次數(shù)限制為n 則插值多項式不唯一 例如也是一個插值多項式 其中可以是任意多項式 1LagrangePolynomial 插值余項 Remainder Rolle sTheorem 若充分光滑 則存在使得 推廣 若 使得 Rn x 至少有個根 n 1 x 有n 2個不同的根x0 xnx 注意這里是對t求導(dǎo) 1LagrangePolynomial 注 通常不能確定 x 而是估計 x a b 將作為誤差估計上限 當(dāng)f x 為任一個次數(shù) n的多項式時 可知 即插值多項式對于次數(shù) n的多項式是精確的 Q 給定xi i 1 i 0 1 2 3 4 5 下面哪個是l2 x 的圖像 1LagrangePolynomial 解 n 1 分別利用x0 x1以及x1 x2計算 利用 這里 而 sin50 0 7660444 外推 extrapolation 的實際誤差 0 0101 利用 內(nèi)插 interpolation 的實際誤差 0 0059 內(nèi)插通常優(yōu)于外推 選擇要計算的x所在的區(qū)間的端點 插值效果較好 1LagrangePolynomial n 2 sin50 0 7660444 2次插值的實際誤差 0 0006 高次插值通常優(yōu)于低次插值 但絕對不是次數(shù)越高就越好 嘿嘿 2牛頓插值 Newton sInterpolation 差商 亦稱均差 divideddifference 1階差商 the1stdivideddifferenceoffw r t xiandxj 2階差商 2Newton sInterpolation k 1 階差商 Warning myheadisexploding Whatisthepointofthisformula 差商的值與xi的順序無關(guān) 2Newton sInterpolation 牛頓插值 Newton sInterpolation Nn x Rn x ai f x0 xi 2Newton sInterpolation 注 由唯一性可知Nn x Ln x 只是算法不同 故其余項也相同 即 實際計算過程為 f x0 f x1 f x2 f xn 1 f xn f x0 x1 f x1 x2 f xn 1 xn f x0 x1 x2 f xn 2 xn 1 xn f x0 xn f xn 1 f xn xn 1 f xn 1 xn xn 1 f x1 xn 1 f x0 xn 1 2Newton sInterpolation 等距節(jié)點公式 FormulaewithEqualSpacing 向前差分 forwarddifference 向后差分 backwarddifference 中心差分 centereddifference 其中 當(dāng)節(jié)點等距分布時 Moregivenonp 174 2Newton sInterpolation 差分的重要性質(zhì) 線性性質(zhì) 例如 若f x 是m次多項式 則是次多項式 而 差分值可由函數(shù)值算出 函數(shù)值可由差分值算出 2Newton sInterpolation 牛頓公式 牛頓前差公式 Newton sforward differenceformula 牛頓后差公式 Newton sbackward differenceformula 將節(jié)點順序倒置 注 一般當(dāng)x靠近x0時用向前插值 靠近xn時用向后插值 故兩種公式亦稱為表初公式和表末公式 3埃爾米特插值 HermiteInterpolation 不僅要求函數(shù)值重合 而且要求若干階導(dǎo)數(shù)也重合 即 要求插值函數(shù) x 滿足 xi f xi xi f xi mi xi f mi xi 注 N個條件可以確定階多項式 N 1 一般只考慮f與f 的值 3HermiteInterpolation 例 設(shè)x0 x1 x2 已知f x0 f x1 f x2 和f x1 求多項式P x 滿足P xi f xi i 0 1 2 且P x1 f x1 并估計誤差 模仿Lagrange多項式的思想 設(shè) 解 首先 P的階數(shù) 3 h0 x 有根 x1 x2 且h0 x1 0 x1是重根 又 h0 x0 1 C0 h2 x h1 x 有根x0 x2 由余下條件h1 x1 1和h1 x1 0可解 與h0 x 完全類似 有根x0 x1 x2 與Lagrange分析完全類似 3HermiteInterpolation 一般地 已知x0 xn處有y0 yn和y0 yn 求H2n 1 x 滿足H2n 1 xi yi H 2n 1 xi yi 解 設(shè) hi x 由余下條件hi xi 1和hi xi 0可解Ai和Bi 有根x0 xn 除了xi外都是2重根 這樣的Hermite插值唯一 3HermiteInterpolation 斜率 1 求Hermite多項式的基本步驟 根據(jù)多項式的總階數(shù)和根的個數(shù)寫出表達(dá)式 根據(jù)尚未利用的條件解出表達(dá)式中的待定系數(shù) 最后完整寫出H x 4分段低次插值 piecewisepolynomialapproximation RememberwhatIhavesaid IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult sincehigh degreepolynomialsareoscillating 例 在 5 5 上考察的Ln x 取 n越大 端點附近抖動越大 稱為Runge現(xiàn)象 4PiecewisePolynomialApproximation 分段線性插值 piecewiselinearinterpolation 在每個區(qū)間上 用1階多項式 直線 逼近f x 分段Hermite插值 Hermitepiecewisepolynomials Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf Headache 5三次樣條 CubicSpline 注 三次樣條與分段Hermite插值的根本區(qū)別在于S x 自身光滑 不需要知道f的導(dǎo)數(shù)值 除了在2個端點可能需要 而Hermite插值依賴于f在所有插值點的導(dǎo)數(shù)值 f x H x S x 5CubicSpline 構(gòu)造三次樣條插值函數(shù)的三彎矩法 methodofbendingmoment 對每個j 此為3次多項式 則S j x 為次多項式 需個點的值確定之 1 2 設(shè)S j xj 1 Mj 1 S j xj Mj 對應(yīng)力學(xué)中的梁彎矩 故名 對于x xj 1 xj 可得到 S j x 積分2次 可得S j x 和S j x 5CubicSpline 下面解決Mj 利用S 在xj的連續(xù)性 xj 1 xj S j x xj xj 1 S j 1 x j 1 n 1 即 有個未知數(shù) 個方程 n 1 n 1 還需2個邊界條件 boundaryconditions 5CubicSpline 第1類邊條件 clampedboundary S a y0 S b yn 類似地利用 xn 1 b 上的S n x 第2類邊條件 S a y0 M0 S b yn Mn 這時 特別地 M0 Mn 0稱為自由邊界 freeboundary 對應(yīng)的樣條函數(shù)稱為自然樣條 NaturalSpline 第3類邊條件 periodicboundary 當(dāng)f為周期函數(shù)時 yn y0 S a S b M0 Mn 5CubicSpline 注 另有三轉(zhuǎn)角法得到樣條函數(shù) 即設(shè)S j xj mj 則易知 xj 1 xj 上的S j x 就是Hermite函數(shù) 再利用S 的連續(xù)性 可導(dǎo)出關(guān)于mj的方程組 加上邊界條件即可解 CubicSpline由bound