МЧА: Лекция 1. Интерполирование в равноотстоящих узлах

Постановка задачи интерполирования.
Примеры интерполяционных функций.
Конечные разности и их свойства.
Примеры решения задач.

1 Постановка задачи интерполирования

Рассмотрим на отрезке $[a,b]$ некоторую m – кратно дифференцируемую функцию $f(x)$ . Пусть в $k_0$ точках $x_{01}$ , $x_{02}$ , ... , $x_{0k_0}$ известны ее значения $f(x_{01})$ , $f(x_{02})$ , ..., $f(x_{0k_0})$ в $k_1$ точках $x_{11}$ , $x_{12}$ , ..., $x_{1k_1}$ известны значения первой производной $f^{(1)}(x_{11})$ , $f^{(1)}(x_{12})$ , ..., $f^{(1)}(x_{1k_1})$ и в $k_m$ точках известны значения m –ой производной $f^{(m)}(x_{m1})$ , $f^{(m)}(x_{m2})$ , ..., $f^{(m)}(x_{mk_m})$ .
Значения функции и ее производных называются данными интерполирования, а точки $x_{ij}$ – узлами интерполирования.
Задача интерполирования заключается в отыскании функции $\phi(x)$ из некоторого класса $\Phi$ такой, что выполняется условие
$\phi^{(i)}(x_{ij})$ = $f^{(i)}(x_{ij})$ , $i = 1, 2, ..., m, j = 1, 2, ..., k_j$ (1.1)
Пусть $n = k_1 + k_2 + ... + k_m$ . Рассмотрим на отрезке $[a,b]$ последовательность линейно независимых m – кратно дифференцируемых функций: $\omega_1(x)$ , $\omega_2(x)$ , ..., $\omega_n(x)$ . В качестве семейства $\Phi$ возьмем всевозможные линейные комбинации первых n функций с произвольными коэффициентами
$\phi(x) = a_1\omega_1(x) + a_2\omega_2(x) + ... + a_n\omega_n(x)$ .

Из условия (1.1) получим систему линейных алгебраических уравнений для определения коэффициентов $a_i, i = 1, 2, ..., n$

$a_1\omega_1(x) + a_2\omega_2(x) + ... + a_n\omega_n(x)$ = $f^{(i)}(x_{ij})$ (1.2)

Система (1.2) будет иметь единственное решение в том случае, если ее определитель отличен от нуля.

2 Примеры интерполяционных функций

Приведем примеры интерполяционных функций.

1. Рассмотрим следующую систему линейно независимых функций: $1, x^1, x^2, ... , x^n, ...$ .

Тогда семейством $\Phi$ является совокупность алгебраических многочленов вида

$P_n(x) = a_0x^n + a_1x^{n-1} + ...+ a_{n-1}x + a_n$ (1.3)

Геометрически это означает, что нужно найти алгебраическую кривую $y = P_n(x)$ , проходящую через систему точек $M_i(x_i, y_i)$ $(i = 1, 2, ..., n)$ , (Рис. 1.1).

Рис.1.1 Интерполяционный многочлен

Система уравнений, из которой определяютсякоэффициенты $a_i$ из (1.3),будет

$P_n(x_i) = a_0x_i^n + a_1x_i^{n-1} + ...+ a_{n-1}x_i + a_n = f(x_i)$ (1.4)

или

$a_0x_0^n + a_1x_0^{n-1} + ...+ a_{n-1}x_0 + a_n = f(x_0)$

$a_0x_1^n + a_1x_1^{n-1} + ...+ a_{n-1}x_1 + a_n = f(x_1)$

.......................................................................

$a_0x_n^n + a_1x_n^{n-1} + ...+ a_{n-1}x_n + a_n = f(x_n)$ .

Ее определитель является определителем Вандермонда,

$\begin{vmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n \ 1 & x_1 & x_1^2 & \cdots & x_1^n \ & & \cdots & \ 1 & x_n & x_n^2 & \cdots & x_n^n \end{vmatrix}$

и он отличен от нуля для различных между собой значениях $x_i$ .

Интерполирование полиномами вида (1.3) называется алгебраическим. Многочлен $P_n(x)$ называется интерполяционным многочленом. Точки $x_i (i = 1,2,...,n)$ называются узлами интерполяции.

2. Для интерполирования периодических функций с периодом $2\pi$ применяется система тригонометрических функций: $1, cos x, sin x, cos 2x, sin 2x, cos 3x, sin 3x, \cdots$ . Линейная комбинация первых $2n+1$ функций является тригонометрическим многочленом степени $n$

$\phi_n(x) = a_0 + \sum^{n}_{k=1} {(a_kcos kx + b_ksin kx)}$ . (1.5)

Интерполирование с помощью полиномов (1.5) называется тригонометрическим.

Пусть для функции $f(x)$ построена интерполирующая функция $\phi(x)$ . Тогда, если определяется значение $f(x)$ в точке $\overline{x}$ , лежащей внутри отрезка интерполирования $[a,b]$ , то такое восстановление функции называется интерполяцией. Если же точка $\overline{x}$ лежит вне отрезка $[a,b]$ , то такое восстановление функции называется экстраполяцией.

3 Конечные разности и их свойства

Конечные разности в вычислительной математике имеют значение, аналогичное дифференциалам в анализе бесконечно малых величин.

Пусть даны равноотстоящие друг от друга узлы $x_k = x_0 + kh (k = 0,1,2,...)$ и известны соответствующие значения функции $y_k = f(x_k) = f(x_0+kh)$ . Здесь $h = \Delta x = x_k - x_{k-1}$ – некоторое фиксированное значение аргумента. (или рассмотрим таблицу значений функции с постоянным шагом $h$ , для которой значения аргумента определяются формулой $x_k = x_0 + kh (k = 0,1,2,...)$ , значения функции $y_k = f(x_k) \Rightarrow$ узлы $x_k$ – равноотстоящие).

Конечными разностями нулевого порядка называются величины $y_k$ равные значениям функции $f(x_k)$ в узлах $x_k$ , т.е. $y_k = f(x_k)$ . Конечной разностью первого порядка называется разность между значениями функции в соседних узлах интерполяции

$\Delta y_0 = y_1 - y_0 \equiv f(x_0+h) - f(x_0), \Delta y_1 = y_2 - y_1, \Delta y_2 = y_3 - y_2, ..., \Delta y_k = y_{k+1} - y_k.$ (1.6)

Конечные разности второго порядка определяются равенствами по отношению к разностям первого порядка (дельта два игрек нулевое)

$\Delta^2 y_0 = \Delta y_1 - \Delta y_0, \Delta^2 y_1 = \Delta y_2 - \Delta y_1, ..., \Delta^2 y_k = \Delta y_{k+1} - \Delta y_k = y_{k+2} - y_{k+1} - (y_{k+1} - y_k) \equiv y_{k+2} - 2y_{k+1} + y_k.$

Разности n -го порядка определяются по формуле

$\Delta^n y_k = \Delta^{n-1} y_{k+1} - \Delta^{n-1} y_k, k = 0,1,2,...$ (1.7)

Конечные разности любого порядка легко выражаются через значения функции

$\Delta^n y_0 = y_n - \frac{n}{1!}y_{n-1} + \frac{n(n-1)}{2!}y_{n-2} + ... + (-1)^n y_0 = \sum^{n}_{i=0} {(-1)^i C^i_n y_{n-i}}$ , (1.8)

где $C^k_n = \frac {n!}{k!(n-k)!}$ (число сочетаний из $n$ по $k$ ).

Доказательство проведем по индукции. Пусть эта формула верна для $n=k$ . Покажем, что она будет верна и при $n=k+1$ .

$\Delta^{k+1} y_0 = \Delta^k y_1 - \Delta^k y_0 = \sum^{k}_{i=0}{(-1)^i C^i_k y_{k-i+1}} - \sum^{k}_{i=0}{(-1)^i C^i_k y_{k-i}} =$

$\sum^{k}_{i=0}{(-1)^i C^i_k y_{k-i+1}} - \sum^{k+1}_{i=1}{(-1)^i C^{i-1}_k y_{k-i+1}} = \sum^{k+1}_{i=0}{(-1)^i (C^i_k + C^{i-1}_k) y_{k-i+1}} =$

$\sum^{k+1}_{i=0}{(-1)^i (\frac {k!}{i!(k-i)!} + \frac {k!}{(i-1)!(k-i+1)!}) y_{k-i+1}} = \sum^{k+1}_{i=0}{(-1)^i (\frac {k!}{i!(k+1-i)!}(k-i+1+i)) y_{k+1-i}} =$

$\sum^{k+1}_{i=0}{(-1)^i (\frac {(k+1)!}{i!(k+1-i)!} y_{k+1-i}} = \sum^{k+1}_{i=0}{(-1)^i C^i_{k+1} y_{k+1-i}}.$

Аналогично доказывается формула

$y_n = y_0 + \frac {n} {1!} \Delta y_0 + \frac {n(n-1)}{2!} \Delta^2 y_0 + ... + \Delta^n y_0 = \sum^{n}_{i=0}{C^i_n \Delta^i y_0} = (1+\Delta)^n y_0.$ (1.9)

Из определения конечных разностей вытекают следующие свойства

если $f(x) = u(x) + v(x)$ , то $\Delta f(x) = \Delta u(x) + \Delta v(x)$ ; если функция представлена в виде суммы двух функций, то конечная разность исходной функции представляется как сумма конечных разностей слагаемых.
если $f(x) = cu(x)$ , $c=const$ , то $\Delta f(x) = c \Delta u(x)$ ; при умножении функции на $const$ , конечные разности умножаются на тот же множитель.
конечные разности $n$ –го порядка от многочлена степени $n$ постоянны $\Delta^n P_n(x) = n! a_0 h^n = const$ , а $\Delta^{n+1} P_n(x) = 0$ ;
$\Delta^m(\Delta^n f(x)) = \Delta^{m+n} f(x)$ .

Таблицу конечных разностей обычно располагают следующим образом:

Таблица 1.1 Конечные разности

$x$	$f$	$\Delta f$	$\Delta^2 f$	$\Delta^3 f$	$\Delta^4 f$	$\Delta^5 f$	$\Delta^6 f$
$x_0$	$f_0$
		$\Delta f_0$
$x_1$	$f_1$		$\Delta^2 f_0$
		$\Delta f_1$		$\Delta^3 f_0$
$x_2$	$f_2$		$\Delta^2 f_1$		$\Delta^4 f_0$
		$\Delta f_2$		$\Delta^3 f_1$		$\Delta^5 f_0$
$x_3$	$f_3$		$\Delta^2 f_2$		$\Delta^4 f_1$		$\Delta^6 f_0$
		$\Delta f_3$		$\Delta^3 f_2$		$\Delta^5 f_1$
$x_4$	$f_4$		$\Delta^2 f_3$		$\Delta^4 f_2$
		$\Delta f_4$		$\Delta^3 f_3$
$x_5$	$f_5$		$\Delta^2 f_4$
		$\Delta f_5$
$x_6$	$f_6$

4 Примеры решения задач.

1. Заданы значения

$x_0 = 0$ , $x_1 = 2$ , $x_2 = 3$ .

$f(x_0) = 2$ , $f(x_1) = 3$ , $f(x_2) = 5$ .

Построим многочлен вида (1.3) второй степени $P_2(x) = a_0 x^2 +a_1 x + a_2$ , для которого $P_2(0) = 2$ , $P_2(2) = 3$ , $P_2(3) = 5$ .

Решение.

Составим систему (1.4)

$\begin{cases} a_0 \cdot 0 + a_1 \cdot 0 +a_2 = 2, \ a_0 \cdot 4 + a_1 \cdot 2 + a_2 = 3, \ a_0 \cdot 9 + a_1 \cdot 3 + a_2 = 5 \end{cases}$ или $\begin{cases} a_2 = 2, \ a_0 \cdot 4 + a_1 \cdot 2 = 1, \ a_0 \cdot 9 + a_1 \cdot 3 = 3 \end{cases}$

Отсюда $a_0 = 0.5$ , $a_1 = -0.5$ , $a_2 = 2$ .

Итак, $P_2(x) = 0.5x^2 - 0.5x +2$ .

Не трудно проверить, что $P_2$ удовлетворяет поставленным условиям.

2. Составим таблицу значений функции $y = x^3$ с шагом $h = 0.1$ на отрезке $[0.0;0.5]$ и найдем конечные разности различных порядков.

Решение.

Значения функции и конечные разности запишем в таблицу вида 1.1

$x$	$f$	$\Delta f$	$\Delta^2 f$	$\Delta^3 f$	$\Delta^4 f$	$\Delta^5 f$
0.0	0.000
		0.001
0.1	0.001		0.006
		0.007		0.006
0.2	0.008		0.012		0
		0.019		0.006		0
0.3	0.027		0.018		0
		0.037		0.006
0.4	0.064		0.24
		0.061
0.5	0.125