3、插值与多项式逼近
? ?种类：拉格朗日插值多项式、牛顿插值多项式、Hermite插值、样条插值等等。
3.1拉格朗日插值多项式
? ?最简单的插值是用直线连接两个数据点。如右图，这种方法称为线性插值(linear interpolation)。由直线斜率相等得:
f ( x ) ? f ( x 1 ) x ? x 1 = f ( x 2 ) ? f ( x 1 ) x 2 ? x 1 \frac{{f(x) - f({x_1})}}{{x - {x_1}}} = \frac{{f({x_2}) - f({x_1})}}{{{x_2} - {x_1}}} x?x1?f(x)?f(x1?)?=x2??x1?f(x2?)?f(x1?)?? ?整理得到：
f ( x ) = f ( x 1 ) + f ( x 2 ) ? f ( x 1 ) x 2 ? x 1 ( x ? x 1 ) f(x) = f({x_1}) + \frac{{f({x_2}) - f({x_1})}}{{{x_2} - {x_1}}}(x - {x_1}) f(x)=f(x1?)+x2??x1?f(x2?)?f(x1?)?(x?x1?)
? ?将线性插值的公式进行重新整理可以得到：
f
(
x
)
=
x
?
x
2
x
1
?
x
2
f
(
x
1
)
+
x
?
x
1
x
2
?
x
1
f
(
x
2
)
f(x) = \frac{{x - {x_2}}}{{{x_1} - {x_2}}}f({x_1}) + \frac{{x - {x_1}}}{{{x_2} - {x_1}}}f({x_2})
f(x)=x1??x2?x?x2??f(x1?)+x2??x1?x?x1??f(x2?)? ?即将线性插值多项式看成由直线相连的两个点的加权平均,就是拉格朗日插值多项式:
f ( x ) = L 1 f ( x 1 ) + L 2 f ( x 2 ) f(x) = {L_1}f({x_1}) + {L_2}f({x_2}) f(x)=L1?f(x1?)+L2?f(x2?)
? ?其中L是加权系数。由此推断，第一个加权系数可以是在x处等于1，在x,处等于0的直线:
L
1
=
x
?
x
2
x
1
?
x
2
{L_1} = \frac{{x - {x_2}}}{{{x_1} - {x_2}}}
L1?=x1??x2?x?x2??。同理,第二个系数是在x处等于1、在x处等于0的直线:
L
2
=
x
?
x
1
x
2
?
x
1
{L_2} = \frac{{x - {x_1}}}{{{x_2} - {x_1}}}
L2?=x2??x1?x?x1??。（这里有点像有限元当中的形函数）。公式:
f
(
x
)
=
x
?
x
2
x
1
?
x
2
f
(
x
1
)
+
x
?
x
1
x
2
?
x
1
f
(
x
2
)
f(x) = \frac{{x - {x_2}}}{{{x_1} - {x_2}}}f({x_1}) + \frac{{x - {x_1}}}{{{x_2} - {x_1}}}f({x_2})
f(x)=x1??x2?x?x2??f(x1?)+x2??x1?x?x1??f(x2?)称为线性拉格朗日插值多项式。
? ?一次、二次以及更高次的拉格朗日多项式都可以简写为:
f
n
?
1
(
x
)
=
∑
i
=
1
n
L
i
(
x
)
f
(
x
i
)
{f_{n - 1}}(x) = \sum\limits_{i = 1}^n {{L_i}(x)f({x_i})}
fn?1?(x)=i=1∑n?Li?(x)f(xi?) 其中：
L
i
(
x
)
=
∏
j
=
1
n
x
?
x
j
x
i
?
x
j
(
i
≠
j
)
{L_i}(x) = \prod\limits_{j = 1}^n {\frac{{x - {x_j}}}{{{x_i} - {x_j}}}} {\rm{ }}(i \ne j)
Li?(x)=j=1∏n?xi??xj?x?xj??(i?=j) n=数据点的个数。
3.2牛顿插值多项式
? ?线性插值：
f
1
(
x
)
=
f
(
x
1
)
+
f
(
x
2
)
?
f
(
x
1
)
x
2
?
x
1
(
x
?
x
1
)
{f_1}(x) = f({x_1}) + \frac{{f({x_2}) - f({x_1})}}{{{x_2} - {x_1}}}(x - {x_1})
f1?(x)=f(x1?)+x2??x1?f(x2?)?f(x1?)?(x?x1?)
b
1
=
f
(
x
1
)
{b_1} = f({x_1})
b1?=f(x1?)，
b
2
=
f
(
x
2
)
?
f
(
x
1
)
x
2
?
x
1
{b_2} = \frac{{f({x_2}) - f({x_1})}}{{{x_2} - {x_1}}}
b2?=x2??x1?f(x2?)?f(x1?)? 则：
f
(
x
)
=
b
1
+
b
2
(
x
?
x
1
)
f(x) = {b_1} + {b_2}(x - {x_1})
f(x)=b1?+b2?(x?x1?)
? ?二次插值：
f
2
(
x
)
=
b
1
+
b
2
(
x
?
x
1
)
+
b
3
(
x
?
x
1
)
(
x
?
x
2
)
{f_2}(x) = {b_1} + {b_2}(x - {x_1}) + {b_3}(x - {x_1})(x - {x_2})
f2?(x)=b1?+b2?(x?x1?)+b3?(x?x1?)(x?x2?)? ?确定系数值，首先令
x
=
x
1
x = {x_1}
x=x1?得到：
b
1
=
f
(
x
1
)
{b_1} = f({x_1})
b1?=f(x1?)，再令
x
=
x
2
x = {x_2}
x=x2?得到：
b
2
=
f
(
x
2
)
?
f
(
x
1
)
x
2
?
x
1
{b_2} = \frac{{f({x_2}) - f({x_1})}}{{{x_2} - {x_1}}}
b2?=x2??x1?f(x2?)?f(x1?)?，最后令
x
=
x
3
x = {x_3}
x=x3?得到：
b
3
=
f
(
x
3
)
?
f
(
x
2
)
x
3
?
x
2
?
f
(
x
2
)
?
f
(
x
1
)
x
2
?
x
1
x
3
?
x
1
{b_3} = \frac{{\frac{{f({x_3}) - f({x_2})}}{{{x_3} - {x_2}}} - \frac{{f({x_2}) - f({x_1})}}{{{x_2} - {x_1}}}}}{{{x_3} - {x_1}}}
b3?=x3??x1?x3??x2?f(x3?)?f(x2?)??x2??x1?f(x2?)?f(x1?)??。
? ?牛顿插值多项式的一般形式：
? ?考虑用(n-1)次多项式拟合n个数据点，前面的分析可以进行推广。(n-1)次插值多项式为:
f
n
?
1
(
x
)
=
b
1
+
b
2
(
x
?
x
1
)
+
?
+
b
n
(
x
?
x
1
)
(
x
?
x
2
)
?
(
x
?
x
n
?
1
)
{f_{n - 1}}(x) = {b_1} + {b_2}(x - {x_1}) + \cdots + {b_n}(x - {x_1})(x - {x_2}) \cdots (x - {x_{n - 1}})
fn?1?(x)=b1?+b2?(x?x1?)+?+bn?(x?x1?)(x?x2?)?(x?xn?1?)
? ?与线性插值与二次插值一样，系数
b
1
,
b
2
,
b
3
,
?
?
,
b
n
{b_1},{b_2},{b_3}, \cdots ,{b_n}
b1?,b2?,b3?,?,bn?由数据点确定。 (n-1)次多项式需要n个数据点: 。可以用这些数据点和下面的公式计算系数:
b
1
=
f
(
x
1
)
,
b
2
=
f
[
x
2
,
x
1
]
,
b
3
=
f
[
x
3
,
x
2
,
x
1
]
?
?
,
b
n
=
f
[
x
n
,
x
n
?
1
,
?
?
,
x
2
,
x
1
]
{b_1} = f({x_1}),{\rm{ }}{b_2} = f[{x_2},{x_1}],{\rm{ }}{b_3} = f[{x_3},{x_2},{x_1}] \cdots ,{\rm{ }}{b_n} = f[{x_n},{x_{n - 1}}, \cdots ,{x_2},{x_1}]
b1?=f(x1?),b2?=f[x2?,x1?],b3?=f[x3?,x2?,x1?]?,bn?=f[xn?,xn?1?,?,x2?,x1?]
? ?带方括号的函数值表示为有限均差。例如一阶有限均差表示为：
f
[
x
i
,
x
j
]
=
f
(
x
i
)
?
f
(
x
j
)
x
i
?
x
j
f[{x_i},{x_j}] = \frac{{f({x_i}) - f({x_j})}}{{{x_i} - {x_j}}}
f[xi?,xj?]=xi??xj?f(xi?)?f(xj?)?
? ?两个一阶均差的差分是二阶有限均差，它的一般表示形式为:
f
[
x
i
,
x
j
,
x
k
]
=
f
[
x
i
,
x
j
]
?
f
[
x
j
,
x
k
]
x
i
?
x
k
f[{x_i},{x_j},{x_k}] = \frac{{f[{x_i},{x_j}] - f[{x_j},{x_k}]}}{{{x_i} - {x_k}}}
f[xi?,xj?,xk?]=xi??xk?f[xi?,xj?]?f[xj?,xk?]?
? ?n阶有限均差为：
f
[
x
n
,
x
n
?
1
,
?
?
,
x
2
,
x
1
]
=
f
[
x
n
,
x
n
?
1
,
…
,
x
2
]
?
f
[
x
n
?
1
,
x
n
?
2
,
…
,
x
1
]
x
n
?
x
1
f[{x_n},{x_{n - 1}}, \cdots ,{x_2},{x_1}] = \frac{{f[{x_n},{x_{n - 1}}, \ldots ,{x_2}] - f[{x_{n - 1}},{x_{n - 2}}, \ldots ,{x_1}]}}{{{x_n} - {x_1}}}
f[xn?,xn?1?,?,x2?,x1?]=xn??x1?f[xn?,xn?1?,…,x2?]?f[xn?1?,xn?2?,…,x1?]?
| x i {x_i} xi? | f ( x i ) f({x_i}) f(xi?) | 一阶 | 二阶 | 三阶 |
|---|---|---|---|---|
| x 1 {x_1} x1? | f ( x 1 ) f({x_1}) f(x1?) | f [ x 2 , x 1 ] = f ( x 2 ) ? f ( x 1 ) x 2 ? x 1 f[{x_2},{x_1}] = \frac{{f({x_2}) - f({x_1})}}{{{x_2} - {x_1}}} f[x2?,x1?]=x2??x1?f(x2?)?f(x1?)? | f [ x 3 , x 2 , x 1 ] = f [ x 3 , x 2 ] ? f [ x 2 , x 1 ] x 3 ? x 1 f[{x_3},{x_2},{x_1}] = \frac{{f[{x_3},{x_2}] - f[{x_2},{x_1}]}}{{{x_3} - {x_1}}} f[x3?,x2?,x1?]=x3??x1?f[x3?,x2?]?f[x2?,x1?]? | f [ x 4 , x 3 , x 2 , x 1 ] = f [ x 4 , x 3 , x 2 ] ? f [ x 3 , x 2 , x 1 ] x 4 ? x 1 f[{x_4},{x_3},{x_2},{x_1}] = \frac{{f[{x_4},{x_3},{x_2}] - f[{x_3},{x_2},{x_1}]}}{{{x_4} - {x_1}}} f[x4?,x3?,x2?,x1?]=x4??x1?f[x4?,x3?,x2?]?f[x3?,x2?,x1?]? |
| x 2 {x_2} x2? | f ( x 2 ) f({x_2}) f(x2?) | f [ x 3 , x 2 ] = f ( x 3 ) ? f ( x 2 ) x 3 ? x 2 f[{x_3},{x_2}] = \frac{{f({x_3}) - f({x_2})}}{{{x_3} - {x_2}}} f[x3?,x2?]=x3??x2?f(x3?)?f(x2?)? | f [ x 4 , x 3 , x 2 ] = f [ x 4 , x 3 ] ? f [ x 3 , x 2 ] x 4 ? x 2 f[{x_4},{x_3},{x_2}] = \frac{{f[{x_4},{x_3}] - f[{x_3},{x_2}]}}{{{x_4} - {x_2}}} f[x4?,x3?,x2?]=x4??x2?f[x4?,x3?]?f[x3?,x2?]? | |
| x 3 {x_3} x3? | f ( x 3 ) f({x_3}) f(x3?) | f [ x 4 , x 3 ] = f ( x 4 ) ? f ( x 3 ) x 4 ? x 3 f[{x_4},{x_3}] = \frac{{f({x_4}) - f({x_3})}}{{{x_4} - {x_3}}} f[x4?,x3?]=x4??x3?f(x4?)?f(x3?)? | ||
| x 4 {x_4} x4? | f ( x 4 ) f({x_4}) f(x4?) |