Падуя точки

При полиномиальной интерполяции двух переменных являются точки Падуи первым известным примером (и до сих пор единственным) несостоятельного множества точек (т. е. интерполирующий полином уникален) с минимальным ростом их константы Лебега , что доказано $O(\log ^{2}n)$. Их название связано с Падуанским университетом , где они были первоначально обнаружены.

Точки определены в области $[-1,1]\times [-1,1]\subset \mathbb {R} ^{2}$. Можно использовать точки с четырьмя ориентациями, полученными при последующих поворотах на 90 градусов: таким образом мы получаем четыре разных семейства точек Падуи.

Четыре семьи

Точки Падуи первого семейства степени 5, построенные вместе с их образующей кривой.

Точки Падуи первого семейства степени 6, построенные вместе с их производящей кривой.

Мы можем рассматривать точку Падуи как « выборку » параметрической кривой , называемой порождающей кривой , которая немного отличается для каждого из четырех семейств, так что точки для степени интерполяции $n$ и семья $s$ может быть определен как

${\text{Pad}}_{n}^{s}=\lbrace \mathbf {\xi } =(\xi _{1},\xi _{2})\rbrace =\left\lbrace \gamma _{s}\left({\frac {k\pi }{n(n+1)}}\right),k=0,\ldots ,n(n+1)\right\rbrace .$

Действительно, точки Падуи лежат точно на самопересечениях кривой и на пересечениях кривой с границами квадрата. $[-1,1]^{2}$. Мощность ​ множества $\operatorname {Pad} _{n}^{s}$ является ${\textstyle |\operatorname {Pad} _{n}^{s}|={\frac {(n+1)(n+2)}{2}}}$. При этом для каждого семейства точек Падуи две точки лежат в последовательных вершинах квадрата. $[-1,1]^{2}$, $2n-1$ точки лежат на краях квадрата, а остальные точки лежат на самопересечениях образующей кривой внутри квадрата.

Четыре образующие кривые представляют собой замкнутые параметрические кривые на интервале $[0,2\pi ]$, и являются частным случаем кривых Лиссажу .

Первая семья

Производящая кривая точек Падуи первого семейства имеет вид

$\gamma _{1}(t)=[-\cos((n+1)t),-\cos(nt)],\quad t\in [0,\pi ].$

Если мы сделаем выборку, как написано выше, мы получим:

$\operatorname {Pad} _{n}^{1}=\lbrace \mathbf {\xi } =(\mu _{j},\eta _{k}),0\leq j\leq n;1\leq k\leq \lfloor {\frac {n}{2}}\rfloor +1+\delta _{j}\rbrace ,$

где $\delta _{j}=0$ когда $n$ четное или нечетное, но $j$ даже, $\delta _{j}=1$если $n$ и $k$ оба странные

с

$\mu _{j}=\cos \left({\frac {j\pi }{n}}\right),\eta _{k}={\begin{cases}\cos \left({\frac {(2k-2)\pi }{n+1}}\right)&j{\mbox{ odd}}\\\cos \left({\frac {(2k-1)\pi }{n+1}}\right)&j{\mbox{ even.}}\end{cases}}$

Отсюда следует, что точки Падуи первого семейства будут иметь две вершины внизу, если $n$ четно или слева, если $n$ странно.

Вторая семья

Производящая кривая точек Падуи второго семейства имеет вид

$\gamma _{2}(t)=[-\cos(nt),-\cos((n+1)t)],\quad t\in [0,\pi ],$

что приводит к тому, что вершины находятся слева, если $n$ четный и нижний, если $n$ странно.

Третья семья

Производящая кривая точек Падуи третьего семейства имеет вид

$\gamma _{3}(t)=[\cos((n+1)t),\cos(nt)],\quad t\in [0,\pi ],$

что приводит к тому, что вершины находятся сверху, если $n$ четно и справа, если $n$ странно.

Четвертая семья

Производящая кривая точек Падуи четвертого семейства имеет вид

$\gamma _{4}(t)=[\cos(nt),\cos((n+1)t)],\quad t\in [0,\pi ],$

что приводит к тому, что вершины находятся справа, если $n$ четно и сверху, если $n$ странно.

Формула интерполяции

Явное представление их фундаментального полинома Лагранжа основано на воспроизводящем ядре $K_{n}(\mathbf {x} ,\mathbf {y} )$, $\mathbf {x} =(x_{1},x_{2})$ и $\mathbf {y} =(y_{1},y_{2})$, пространства $\Pi _{n}^{2}([-1,1]^{2})$ оснащен внутренним продуктом

$\langle f,g\rangle ={\frac {1}{\pi ^{2}}}\int _{[-1,1]^{2}}f(x_{1},x_{2})g(x_{1},x_{2}){\frac {dx_{1}}{\sqrt {1-x_{1}^{2}}}}{\frac {dx_{2}}{\sqrt {1-x_{2}^{2}}}}$

определяется

$K_{n}(\mathbf {x} ,\mathbf {y} )=\sum _{k=0}^{n}\sum _{j=0}^{k}{\hat {T}}_{j}(x_{1}){\hat {T}}_{k-j}(x_{2}){\hat {T}}_{j}(y_{1}){\hat {T}}_{k-j}(y_{2})$

с ${\hat {T}}_{j}$ представляющий нормированный полином Чебышева степени $j$ (то есть, ${\hat {T}}_{0}=T_{0}$ и ${\hat {T}}_{p}={\sqrt {2}}T_{p}$, где $T_{p}(\cdot )=\cos(p\arccos(\cdot ))$ – классический полином Чебышева первого рода степени $p$). Для четырех семейств точек Падуи, которые мы можем обозначить через $\operatorname {Pad} _{n}^{s}=\lbrace \mathbf {\xi } =(\xi _{1},\xi _{2})\rbrace$, $s=\lbrace 1,2,3,4\rbrace$, интерполяционная формула порядка $n$ функции $f\colon [-1,1]^{2}\to \mathbb {R} ^{2}$ в общей целевой точке $\mathbf {x} \in [-1,1]^{2}$ тогда

${\mathcal {L}}_{n}^{s}f(\mathbf {x} )=\sum _{\mathbf {\xi } \in \operatorname {Pad} _{n}^{s}}f(\mathbf {\xi } )L_{\mathbf {\xi } }^{s}(\mathbf {x} )$

где $L_{\mathbf {\xi } }^{s}(\mathbf {x} )$ — фундаментальный полином Лагранжа

$L_{\mathbf {\xi } }^{s}(\mathbf {x} )=w_{\mathbf {\xi } }(K_{n}(\mathbf {\xi } ,\mathbf {x} )-T_{n}(\xi _{i})T_{n}(x_{i})),\quad s=1,2,3,4,\quad i=2-(s\mod 2).$

Веса $w_{\mathbf {\xi } }$ определяются как

$w_{\mathbf {\xi } }={\frac {1}{n(n+1)}}\cdot {\begin{cases}{\frac {1}{2}}{\text{ if }}\mathbf {\xi } {\text{ is a vertex point}}\\1{\text{ if }}\mathbf {\xi } {\text{ is an edge point}}\\2{\text{ if }}\mathbf {\xi } {\text{ is an interior point.}}\end{cases}}$

Внешние ссылки

• Список публикаций, связанных с точками Падуи и некоторым программным обеспечением для интерполяции .