Интерполяция Биркгофа

В математике является интерполяция Биркгофа расширением полиномиальной интерполяции . Речь идет о задаче нахождения многочлена $P(x)$ степени $d$ так, что только определенные производные имеют указанные значения в указанных точках:

$P^{(n_{i})}(x_{i})=y_{i}\qquad {\mbox{for }}i=1,\ldots ,d,$

где точки данных $(x_{i},y_{i})$ и неотрицательные целые числа $n_{i}$ даны. Он отличается от интерполяции Эрмита тем, что можно указать производные от $P(x)$ в некоторых точках без указания младших производных или самого полинома. Название отсылает к Джорджу Дэвиду Биркгофу , который впервые изучил эту проблему в 1906 году.

Существование и единственность решений

В отличие от интерполяции Лагранжа и интерполяции Эрмита , задача интерполяции Биркгофа не всегда имеет единственное решение. Например, не существует квадратичного многочлена $P(x)$ такой, что $P(-1)=P(1)=0$ и $P^{(1)}(0)=1$. С другой стороны, задача интерполяции Биркгофа, в которой значения $P^{(1)}(-1),P(0)$ и $P^{(1)}(1)$ заданы, всегда имеет единственное решение.

Важной проблемой теории интерполяции Биркгофа является классификация задач, имеющих единственное решение. Шенберг формулирует проблему следующим образом. Позволять $d$ обозначим количество условий (как указано выше) и пусть $k$ быть числом точек интерполяции. Учитывая $d\times k$ матрица $E$, все записи которого либо $0$ или $1$, такой, что именно $d$ записи $1$, то соответствующая задача состоит в определении $P(x)$ такой, что

$P^{(j)}(x_{i})=y_{i,j}\qquad \forall (i,j)/e_{ij}=1$

Матрица $E$ называется матрицей инцидентности . Например, матрицы инцидентности для задач интерполяции, упомянутых в предыдущем абзаце, таковы:

${\begin{pmatrix}1&0&0\\0&1&0\\1&0&0\end{pmatrix}}\qquad \mathrm {and} \qquad {\begin{pmatrix}0&1&0\\1&0&0\\0&1&0\end{pmatrix}}.$

Теперь возникает вопрос: является ли интерполяционная задача Биркгофа с заданной матрицей инцидентности $E$ иметь единственное решение для любого выбора точек интерполяции?

Случай с $k=2$ точки интерполяции были рассмотрены Джорджем Полиа в 1931 году. Позволять $S_{m}$ обозначают сумму записей в первом $m$ столбцы матрицы заболеваемости:

$S_{m}=\sum _{i=1}^{k}\sum _{j=1}^{m}e_{ij}.$

Тогда интерполяционная задача Биркгофа с $k=2$ имеет единственное решение тогда и только тогда, когда $S_{m}\geqslant m\quad \forall m$. Шёнберг показал, что это необходимое условие для всех значений $k$.

Несколько примеров

Рассмотрим дифференцируемую функцию $f(x)$ на $[a,b]$, такой, что $f(a)=f(b)$. Посмотрим, что не существует интерполяционного квадратичного многочлена Биркгофа такого, что $P^{(1)}(c)=f^{(1)}(c)$ где $c={\frac {a+b}{2}}$: С $f(a)=f(b)$, можно записать многочлен как $P(x)=A(x-c)^{2}+B$ ( заполнив квадрат ) где $A,B$ являются просто коэффициентами интерполяции. Производная интерполяционного полинома определяется выражением $P^{(1)}(x)=2A(x-c)^{2}$. Это подразумевает $P^{(1)}(c)=0$, однако это абсурдно, поскольку $f^{(1)}(c)$ не обязательно $0$. Матрица заболеваемости определяется следующим образом:

${\begin{pmatrix}1&0&0\\0&1&0\\1&0&0\end{pmatrix}}_{3\times 3}$

Рассмотрим дифференцируемую функцию $f(x)$ на $[a,b]$, и обозначим $x_{0}=a,x_{2}=b$ с $x_{1}\in [a,b]$. Посмотрим, что действительно существует интерполяционный квадратичный полином Биркгофа такой, что $P(x_{1})=f(x_{1})$ и $P^{(1)}(x_{0})=f^{(1)}(x_{0}),P^{(1)}(x_{2})=f^{(1)}(x_{2})$. Постройте интерполяционный полином $f^{(1)}(x)$ в узлах $x_{0},x_{2}$, такой, что $\displaystyle P_{1}(x)={\frac {f^{(1)}(x_{2})-f^{(1)}(x_{0})}{x_{2}-x_{0}}}(x-x_{0})+f^{(1)}(x_{0})$. Таким образом, полином: $\displaystyle P_{2}(x)=f(x_{1})+\int _{x_{1}}^{x}\!P_{1}(t)\;\mathrm {d} t$ – интерполяционный полином Биркгофа. Матрица заболеваемости определяется следующим образом:

${\begin{pmatrix}0&1&0\\1&0&0\\0&1&0\end{pmatrix}}_{3\times 3}$

Учитывая натуральное число $N$и дифференцируемая функция $f(x)$ на $[a,b]$, существует ли такой полином, что: $P(x_{0})=f(x_{0})$ и $P^{(1)}(x_{i})=f^{(1)}(x_{i})$ для $i=1,\cdots ,N$ с $x_{0},x_{1},\cdots ,x_{N}\in [a,b]$? Постройте полином Лагранжа/ Ньютона (тот же интерполяционный полином, но другая форма для его расчета и выражения) $P_{N-1}(x)$ это удовлетворяет $P_{N-1}(x_{i})=f^{(1)}(x_{i})$ для $i=1,\cdots ,N$, то полином $\displaystyle P_{N}(x)=f(x_{0})+\int _{x_{0}}^{x}\!P_{N-1}(t)\;\mathrm {d} t$ – интерполяционный полином Биркгофа, удовлетворяющий указанным выше условиям. Матрица заболеваемости определяется следующим образом:

${\begin{pmatrix}1&0&0&\cdots &0\\0&1&0&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&1&0&\cdots &0\\\end{pmatrix}}_{N\times N}$

Учитывая натуральное число $N$и $2N$ дифференцируемая функция $f(x)$ на $[a,b]$, существует ли такой полином, что: $P^{(k)}(a)=f^{(k)}(a)$ и $P^{(k)}(b)=f^{(k)}(b)$ для $k=0,2,\cdots ,2N$? Построить $P_{1}(x)$ как интерполяционный полином $f(x)$ в $x=a$ и $x=b$, такой, что $P_{1}(x)={\frac {f^{(2N)}(b)-f^{(2N)}(a)}{b-a}}(x-a)+f^{(2N)}(a)$. Затем определите итерации $\displaystyle P_{k+2}(x)={\frac {f^{(2N-2k)}(b)-f^{(2N-2k)}(a)}{b-a}}(x-a)+f^{(2N-2k)}(a)+\int _{a}^{x}\!\int _{a}^{t}\!P_{k}(s)\;\mathrm {d} s\;\mathrm {d} t$ . Затем $P_{2N+1}(x)$ – интерполяционный полином Биркгофа. Матрица заболеваемости определяется следующим образом:

${\begin{pmatrix}1&0&1&0\cdots \\1&0&1&0\cdots \\\end{pmatrix}}_{2\times N}$