Падуя очков

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

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

Четыре семьи

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

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

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

${\displaystyle {\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 .}$

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

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

Первая семья

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

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

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

${\displaystyle \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 ,}$

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

с

${\displaystyle \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}}}$

Из этого следует, что точки Падуи первого семейства будут иметь две вершины внизу, если четно, или слева, если нечетно. ${\displaystyle n}$ ${\displaystyle n}$

Вторая семья

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

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

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

Третья семья

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

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

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

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

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

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

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

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

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

${\displaystyle \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}}}}}$

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

${\displaystyle 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})}$

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

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

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

${\displaystyle 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).}$

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

${\displaystyle 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}}}$

Ссылки

1. Caliari, Marco; Bos, Len; de Marchi, Stefano; Vianello, Marco; Xu, Yuan (2006), «Двумерная интерполяция Лагранжа в точках Падуи: подход с использованием порождающей кривой», J. Approx. Theory , 143 (1): 15–25, arXiv : math/0604604 , doi :10.1016/j.jat.2006.03.008
2. де Марки, Стефано; Калиари, Марко; Вианелло, Марко (2005), «Двумерная полиномиальная интерполяция в новых узловых наборах», Appl. Математика. Вычислить. , 165 (2): 261–274, номер документа : 10.1016/j.amc.2004.07.001.
3. Caliari, Marco; de Marchi, Stefano; Vianello, Marco (2008), "Алгоритм 886: Padua2D — интерполяция Лагранжа в точках Падуи на двумерных доменах", ACM Transactions on Mathematical Software , 35 (3): 1–11, doi :10.1145/1391989.1391994
4. Бос, Лен; де Марки, Стефано; Вианелло, Марко; Сюй, Юань (2007), «Двумерная интерполяция Лагранжа в точках Падуи: подход идеальной теории», Numerische Mathematik , 108 (1): 43–57, arXiv : math/0604604 , doi :10.1007/s00211-007-0112- я

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

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