四章 多项式插值与数值逼近

第四章 多项式插值与函数逼近/*Polynomial Interpolation and Approximation of Functions */

本章主要内容： 1、Lagrange插值方法 2、Newton插值方法 3、Hermite插值方法 4、三次样条插值方法

5、函数逼近:最佳平方逼近和最佳一致逼近

问题背景

实际问题中经常要涉及到函数值的计算问题： (1)如果函数表达式本身比较复杂，且需要多次重复计算时， 计算量会很大； (2)有的函数甚至没有表达式，只是一种表格函数，而我们需 要的函数值可能不在该表格中。 对于这两种情况，我们都需要寻找一个计算方便且表达简单 的函数来近似代替，这就是数值逼近问题。

§1

插值问题

/* Interpolation Problem */

Def 4.1(插值的定义) .1n

已知定义于区间 [a , b]上的实值函数 f ( x )在 n 1 个互异节点

xi i 0 [a , b] 处的函数值 f ( xi ) i 0 ,若函数集合 中的函n

数 ( x ) 满足

则称 ( x )为 f ( x )在函数集合 中关于节点 xi i 0 的一个插 n 值函数，并称 f ( x )为被插值函数,[a,b]为插值区间， xi i 0 为插值节点，(*)式为插值条件。n

( xi ) f ( xi ) i 0,1, 2, , n

( )

设

M max xi i 0 , m min xi i 0n n

内插法： ( x )计算被插值函数 f ( x ) 在点x ( m , M )处的近似值 用 外插法： ( x )计算被插值函数 f ( x ) 在点 x [a, b], x (m , M ) 用 处的近似值

代数插值：集合 为多项式函数集

插值类型

有理插值：集合 为有理分式函数集 三角插值：集合 为三角函数集

几何意义：g(x) f(x)

y f ( x) y g( x )x0 x1 x2 x x3 x4

代数插值的存在唯一性 设 H n span 1, x , x , , x22

( x ) ( x ) a0 a1 x a2 x an x , ai R, 0 i n n

n

即

代入插值条件： ( xi ) f ( xi ) i 0,1, 2, , n2 n ( x0 ) a0 a1 x0 a2 x0 an x0 f ( x0 ) 2 n ( x1 ) a0 a1 x1 a2 x1 an x1 f ( x1 ) 2 n ( xn ) an a1 xn a2 xn an xn f ( xn )

方程组的系数矩阵是Vandermonde矩阵

1 x0 x 1 x1 x

2 0 2 1

x x

n 0 n 1

2 n

0 j i n n n

( xi x j ) 0

1 xn x

x

Th4.1.1

方程组存在唯一解，因此满足插值条件(*) 的不超过n次的插值多项式是唯一存在的.

Th4.1.2 代数插值的插值余项设f(n)

/* Remainder */

f ( x )在区间 [a,b]上连续，

( n 1)

( x )在区间 [a,b]上存在,

( x )是满足插值条件(*)的不超过n次的插值多项式，则对 x [a, b]存在 ( x ) [a, b],满足 f ( n 1) ( ) Rn ( x ) f ( x ) ( x ) n 1 ( x )( n

1)!f ( n 1) ( x ) 在区间 [a,b]有上 其中 n 1 ( x ) ( x xi )。 且当界 M n 1 时，有i 0 n

M n 1 Rn ( x ) n 1 ( x ) ( n 1)!截断误差

插值余项

§2 代数插值多项式的构造方法一、 拉格朗日多项式 /* Lagrange Polynomial */n 求 n 次多项式 Pn ( x ) a0 a1 x an x 使得

Pn ( x i ) y i ,

i 0 , ... , n

条件：无重合节点，即 i j n=1P1 ( x 0 ) y0 , P1 ( x1 ) y1

xi x j

已知 x0称为拉氏基函数 /*Lagrange a1 x 使得 , x1 ; y0 , y1 ,求 P1 ( x ) a0 Basis*/, 满足条件 li(xj)= ij 可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。 y1 y 0 P1 ( x ) y0 ( x x0 ) x1 x 0

1 i j = li ( x j ) ij 0 i j

x x1 y + x 0 x1 0

x x0 y x1 x 0 1

l ( x) yi 0 i

1

i

l0(x)

l1(x)

n 1

希望找到li(x),i = 0, …, n 使得 li(xj)= ij;然后令Pn ( x )

l (x) yi 0 i

n

i

,则显然有Pn(xi) = yi 。n

li(x) 每个 li(x) 有 n 个根 x0 … xi-1 、 xi+1 … xnli ( xi ) 1n

li ( x ) Ci ( x x0 ) ( x xi 1 )( x xi 1 ) ( x xn ) C i ( x x j )

Ci

1 j i ( xi x j )Ln ( x ) l i ( x ) yii 0 n

j 0 j i

(x xj ) li ( x ) ( xi x j ) j ij 0

( x x0 )( x x1 ) ( x xi 1 )( x xi 1 ) ( x xn ) li ( x ) ( xi x0 )( xi x1 ) ( xi xi 1 )( xi xi 1 ) ( xi xn )与 节点 有关，而与 f 无关

Lagrange Polynomial

注： (1)若不将多项式次数限制为 n ,则插值多项式不唯一。 例如 P ( x ) Ln ( x ) q( x ) ( x xi ) 也是一个插值i 0 n

多项式，其中 q( x )可以是任意多项式。(2)Lagrange插值多项式结构对称，形式简单.

(3)误差估计

f ( n 1) ( ) Rn ( x ) f ( x ) Ln ( x ) n 1 ( x ) ( n 1)!(4)当插值节点增加时，拉氏基函数需要重新计算， n较大时，计算量非常大,故常用于理论分析。

二、 牛顿插值 /* Newton’s Interpolation */Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 li(x) 都需重新算过。

? 1( 将 Ln(x) 改写成 a0 a? x x0 ) a?( x x0 )( x x1 ) ... 2 a?( x x0 )...( x xn 1 ) 的形式，希望每加一个节点， n只附加一项上去即可。

差商(亦称均差) /* pidedf ( xi ) f ( x j ) f [ xi , x j ] xi x j

difference */(i j , xi x j )

1阶差商 /* the 1stpided difference of f w.r.t. xi and xj */

f [ xi , x j ] f [ x j , xk ] f [ xi , x j , xk ] (i k ) xi xk

2阶差商

(K+1)阶差商： f [ x0 , x1 , ... , xk ] f [ x1 , ... , xk , xk 1 ] f [ x0 , ... , xk 1 ] x 0 x k 1 f [ x0 , ... , xk 1 , xk ] f [ x0 , ... , xk 1 , xk 1 ]

x k x k 1

f ( xi ) 事实上 f [ x0 , ... , xk ] i 0 k 1 ( x i )其中 ( x ) ( x x ) , k 1 ( xi ) ( xi x j ) k 1 ii 0j 0 j i

k

k

k

差商的值与 xi 的顺序无关！

N n ( x ) a0 a1 ( x x0 ) a2 ( x x0 )( x x1 ) ... an ( x x0 )...( x xn 1 )

f ( x ) f ( x0 ) ( x x0 ) f [ x , x0 ]f [ x , x0 ] f [ x0 , x1 ] ( x x1 ) f [ x , x0 , x1 ] f [ x, x0 , x1 ] f [ x0 , x1 , x2 ] ( x x2 ) f [ x , x0 , x1 , x2 ]

1 2 3

…………f [ x, x0 , ... , xn 1 ] f [ x0 , ... , xn ] ( x xn ) f [ x, x0 , ... , xn ]1 + (x x0) 2 + … … + (x x0)…(x xn 1) n+1 n+1

f ( x ) f ( x0 ) f [ x0 , x1 ]( x x0 ) f [ x0 , x1 , x2 ]( x x0 )( x x1 ) ... f [ x0 , ... , xn ]( x x0 )...( x xn 1 )

f [ x , x0 , ... , xn ]( x x0 )...( x xn 1 )( x xn )

Nn(x)

ai = f [ x0, …, xi ]

Rn(x)

注： 由唯一性可知 Nn(x) Ln(x), …… 此处隐藏：3110字，全部文档内容请下载后查看。喜欢就下载吧 ……