maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2018-3-291-311mais-688Research ArticleОригинальные статьиArticlesOб оптимальной интерполяции линейными функциями на n-мерном кубеOn Optimal Interpolation by Linear Functions on an n-Dimensional Cubehttps://orcid.org/0000-0002-6392-7618НевскийМихаил ВикторовичNevskiiMikhail V.

д-р физ.-мат. наук, доцент, НОМЦ Центр интегрируемых систем

Doctor of Science, Centre of Integrable Systems

mnevsk55@yandex.ruУхаловАлексей ЮрьевичUkhalovAlexey Yu.

кандидат физ.-мат. наук, НОМЦ Центр интегрируемых систем

PhD, Centre of Integrable Systems

alex-uhalov@yandex.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201830062018253291311Copyright © Невский М.В., Ухалов А.Ю., 20182018Невский М.В., Ухалов А.Ю.Nevskii M.V., Ukhalov A.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/688

Пусть \(n\in{\mathbb N}\), \(Q_n=[0,1]^n\). Через \(C(Q_n)\) обозначим пространство непрерывных функций \(f:Q_n\to{\mathbb R}\) с нормой \(\|f\|_{C(Q_n)}:=\max\limits_{x\in Q_n}|f(x)|,\) через \(\Pi_1\left({\mathbb R}^n\right)\) - совокупность многочленов от \(n\) переменных степени \(\leq 1\) (или линейных функций). Пусть \(x^{(j)},\) \(1\leq j\leq n+1,\) --- вершины \(n\)-мерного невырожденного симплекса \(S\subset Q_n\). Интерполяционный проектор \(P:C(Q_n)\to \Pi_1({\mathbb R}^n)\), соответствующий симплексу \(S\), определяется равенствами \(Pf\left(x^{(j)}\right)=f\left(x^{(j)}\right).\)Норма \(P\) как оператора из \(C(Q_n)\) в \(C(Q_n)\) может быть вычислена по формуле \(\|P\|=\max\limits_{x\in ver(Q_n)} \sum\limits_{j=1}^{n+1} |\lambda_j(x)|.\) Здесь \(\lambda_j\) - базисные многочлены Лагранжа, соответствующие \(S,\) \(ver(Q_n)\) - совокупность вершин \(Q_n\). Через \(\theta_n\) обозначим минимальную величину \(\|P\|.\) Ранее первым автором были доказаны различные соотношения и оценки для величин \(\|P\|\) и \(\theta_n\), в том числе имеющие геометрический характер.Справедлива эквивалентность \(\theta_n\asymp \sqrt{n}.\) Подходящими по размерности \(n\) неравенствами являются, например, \(\frac{1}{4}\sqrt{n}<\theta_n<3\sqrt{n}.\) Для проектора \(P^*\), узлы которого совпадают с вершинами произвольного симплекса максимального объёма в~кубе, выполняется \(\|P^*\|\asymp\theta_n.\) Если существует матрица Адамара порядка \(n+1\), то \(\theta_n\leq\sqrt{n+1}.\) В настоящей статье приводятся уточнённые верхние границы чисел \(\theta_n\) для \(21\leq n \leq 26\), полученные с применением симплексов максимального объёма в~кубе. Для построения этих симплексов применяются максимальные определители, элементы которых равны \(\pm 1.\) Мы также систематизируем и комментируем лучшие на настоящий момент верхние и нижние оценки чисел \(\theta_n\) для конкретных \(n.\)

Let \(n\in{\mathbb N}\), and let \(Q_n\) be the unit cube \([0,1]^n\). By \(C(Q_n)\) we denote the space of continuous functions \(f:Q_n\to{\mathbb R}\) with the norm \(\|f\|_{C(Q_n)}:=\max\limits_{x\in Q_n}|f(x)|,\) by \(\Pi_1\left({\mathbb R}^n\right)\) --- the set of polynomials of \(n\) variables of degree \(\leq 1\) (or linear functions). Let \(x^{(j)},\) \(1\leq j\leq n+1,\) be the vertices of \(n\)-dimnsional nondegenerate simplex \(S\subset Q_n\). An interpolation projector \(P:C(Q_n)\to \Pi_1({\mathbb R}^n)\) corresponding to the simplex \(S\) is defined by equalities \(Pf\left(x^{(j)}\right)= f\left(x^{(j)}\right).\) The norm of \(P\) as an operator from \(C(Q_n)\) to \(C(Q_n)\) may be calculated by the formula \(\|P\|=\max\limits_{x\in ver(Q_n)} \sum\limits_{j=1}^{n+1} |\lambda_j(x)|.\) Here \(\lambda_j\) are the basic Lagrange polynomials with respect to \(S,\) \(ver(Q_n)\) is the set of vertices of \(Q_n\). Let us denote by \(\theta_n\) the minimal possible value of \(\|P\|.\) Earlier, the first author proved various relations and estimates for values \(\|P\|\) and \(\theta_n\), in particular, having geometric character. The equivalence \(\theta_n\asymp \sqrt{n}\) takes place. For example, the appropriate, according to dimension \(n\), inequalities may be written in the form \linebreak \(\frac{1}{4}\sqrt{n}\) \(<\theta_n\) \(<3\sqrt{n}.\) If the nodes of the projector \(P^*\) coincide with vertices of an arbitrary simplex with maximum possible volume, we have \(\|P^*\|\asymp\theta_n.\)When an Hadamard matrix of order \(n+1\) exists, holds \(\theta_n\leq\sqrt{n+1}.\) In the paper, we give more precise upper bounds of numbers \(\theta_n\) for \(21\leq n \leq 26\). These estimates were obtained with the application of maximum volume simplices in the cube. For constructing such simplices, we utilize maximum determinants containing the elements \(\pm 1.\) Also, we systematize and comment the best nowaday upper and low estimates of numbers \(\theta_n\) for a concrete \(n.\)

n-мерный симплексn-мерный кубинтерполяцияпроекторнормачисленные методn-dimensional simplexn-dimensional cubeinterpolationprojectornormnumerical methodsРабота выполнена в рамках государственного задания Министерства образования и науки РФ, проект № 1.12873.2018/12This work was carried out within the framework of the state programme of the Ministry of Education and Science of the Russian Federation, project № 1.12873.2018/12ReferencesЕсипова Е. М., “Геометрические характеристики симплексов, обладающих свойством равноотсечения”, Современные проблемы математики и информатики, 17, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2017, 49– 61Esipova E. M., “Geometricheskie haracteristiki simpleksov, obladayuschih svoistvom ravnootsecheniya”, Sovremennye problemy matematiki i informatiki, 17, P. G. Demidov Yaroslavl State University, Yaroslavl, 2017, 49–61, (in Russian).Кудрявцев И. С., Озерова Е. А., Ухалов А.Ю., “Новые оценки для норм минимальных проекторов”, Современные проблемы математики и информатики, 17, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2017, 74–81Kudryavtsev I. S., Ozerova E. A., Ukhalov A. Yu., “Novye ocenki dlya norm minimalnyh proektorov”, Sovremennye problemy matematiki i informatiki, 17, P. G. Demidov Yaroslavl State University, Yaroslavl, 2017, 74–81, (in Russian).Невский М. В., “Ортогональное проектирование и минимальная линейная интерполяция на n-мерном кубе”, Модел. и анализ информ. систем, 14:3 (2007), 8– 28Nevskij M. V., “Orthogonal projection and minimal linear interpolation on an ndimensional cube”, Modeling and Analysis of Information Systems, 14:3 (2007), 8–28, (in Russian).Невский М. В., Хлесткова И. В., “К вопросу о минимальной линейной интерполяции”, Современные проблемы математики и информатики, 9, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2008, 31–37Nevskij M. V., Hlestkova I. V., “On minimal linear interpolation”, Sovremennye problemy matematiki i informatiki, 9, P. G. Demidov Yaroslavl State University, Yaroslavl, 2008, 31–37, (in Russian).Невский М. В., “Об одном соотношении для минимальной нормы интерполяционного проектора”, Модел. и анализ информ. систем, 16:1 (2009), 24–43Nevskij M. V., “On a certain relation for the minimal norm of an interpolational projection”, Modeling and Analysis of Information Systems, 16:1 (2009), 24–43, (in Russian).Невский М. В., “Об одном свойстве n-мерного симплекса”, Матем. заметки, 87:4 (2010), 580–593Nevskii M. V., “On a property of n-dimensional simplices”, Math. Notes, 87:4 (2010), 543–555Невский М. В., Геометрические оценки в полиномиальной интерполяции, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2012Nevskii M. V., Geometricheskie ocenki v polinomialnoy interpolyacii, P. G. Demidov Yaroslavl State University, Yaroslavl, 2012, (in Russian).Невский М. В., Ухалов А.Ю., “О числовых характеристиках симплекса и их оценках”, Модел. и анализ информ. систем, 23:5 (2016), 602–618Nevskii M. V., Ukhalov A. Yu., “On numerical charasteristics of a simplex and their estimates”, Modeling and Analysis of Information Systems, 23:5 (2016), 602–618, (in Russian).Невский М. В., Ухалов А.Ю., “Новые оценки числовых величин, связанных с симплексом”, Модел. и анализ информ. систем, 24:1 (2017), 34–50Nevskii M. V., Ukhalov A. Yu., “New estimates of numerical values related to a simplex”, Modeling and Analysis of Information Systems, 24:1 (2017), 34–50, (in Russian).Невский М. В., Ухалов А.Ю., “Об n-мерных симплексах, удовлетворяющих включениям S ⊂ [0, 1]n ⊂ nS”, Модел. и анализ информ. систем, 24:5 (2017), 578– 595Nevskii M. V., Ukhalov A. Yu., “On n-Dimensional Simplices Satisfying Inclusions S ⊂ [0, 1]n ⊂ nS”, Modeling and Analysis of Information Systems, 24:5 (2017), 578–595, (in Russian).Невский М. В., Ухалов А.Ю., “О минимальном коэффициенте поглощения для n-мерного симплекса”, Модел. и анализ информ. систем, 25:1 (2018), 140–150Nevskii M. V., Ukhalov A. Yu., “On Minimal Absorption Index for an n-Dimensional Simplex”, Modeling and Analysis of Information Systems, 25:1 (2018), 140–150, (in Russian).Сегё Г., Ортогональные многочлены, Гос. изд-во физ.-мат. литературы, М., 1962Szego G., Orthogonal Polynomials, American Mathematical Society, New York, 1959, (in English).Суетин П. К., Классические ортогональные многочлены, Наука, М., 1979Suetin P. K., Klassicheskie ortogonalnye mnogochleny, Nauka, Moscow, 1979, (in Russian).Холл M., Комбинаторика, Мир, М., 1970Hall M., Jr, Combinatorial theory, Blaisdall publishing company, Waltham (Massachusets)–Toronto–London, 1967, (in English).Butzer P. L., Schmidt M., Stark E. L., “Observations on the history of central B-splines”, Archive for History of Exact Sciences, 1988, № 2, 137–156.Butzer P. L., Schmidt M., Stark E. L., “Observations on the history of central B-splines”, Archive for History of Exact Sciences, 1988, № 2, 137–156.Comtet L., “Permutations by number of rises; Eulerian numbers”, Advanced Combinatorics: The Art of Finite and Infinite Expansions”, Reidel, Dordrecht, Netherlands, 1974.Comtet L., “Permutations by number of rises; Eulerian numbers”, Advanced Combinatorics: The Art of Finite and Infinite Expansions”, Reidel, Dordrecht, Netherlands, 1974.Ehrenborg R., Readdy M., Steingrimsson E., “Mixed volumes and slices of the cube”, Journal of Combinatorial Theory. Series A., 81 (1998), 121–126.Ehrenborg R., Readdy M., Steingrimsson E., “Mixed volumes and slices of the cube”, Journal of Combinatorial Theory. Series A., 81 (1998), 121–126.Graham R. L., Knuth D. E., Patashnik O., Concrete mathematics: A foundation for computer science, Addison–Wesley, Reading, MA, 1994.Graham R. L., Knuth D. E., Patashnik O., Concrete mathematics: A foundation for computer science, Addison–Wesley, Reading, MA, 1994.Hudelson M., Klee V., Larman D., “Largest j-simplices in d-cubes: some relatives of the Hadamard maximum determinant problem”, Linear Algebra Appl., 241–243 (1996), 519–598.Hudelson M., Klee V., Larman D., “Largest j-simplices in d-cubes: some relatives of the Hadamard maximum determinant problem”, Linear Algebra Appl., 241–243 (1996), 519–598.de Laplace M., Oeuvres compl´etes. V. 7, R´e´edite par Gauthier–Villars, Paris, 1886.de Laplace M., Oeuvres compl´etes. V. 7, R´e´edite par Gauthier–Villars, Paris, 1886.Mangano S., Mathematica cookbook, O’Reilly Media Inc., Cambridge, 2010.Mangano S., Mathematica cookbook, O’Reilly Media Inc., Cambridge, 2010.Nevskii M., “Properties of axial diameters of a simplex”, Discrete Comput. Geom., 46:2 (2011), 301–312.Nevskii M., “Properties of axial diameters of a simplex”, Discrete Comput. Geom., 46:2 (2011), 301–312.Scott P. R., “Lattices and convex sets in space”, Quart. J. Math. Oxford (2), 36 (1985), 359–362.Scott P. R., “Lattices and convex sets in space”, Quart. J. Math. Oxford (2), 36 (1985), 359–362.Scott P. R., “Properties of axial diameters”, Bull. Austral. Math. Soc., 39 (1989), 329–333.Scott P. R., “Properties of axial diameters”, Bull. Austral. Math. Soc., 39 (1989), 329–333.Sommerfeld A., “Eine besonders anschauliche Ableitung des Gaussischen Fehlergesetzes”, Festschrift Ludwig Boltzmann gewidmet zum 60, Geburstage, 20. Februar, 1904, Barth, Leipzig, 1904.Sommerfeld A., “Eine besonders anschauliche Ableitung des Gaussischen Fehlergesetzes”, Festschrift Ludwig Boltzmann gewidmet zum 60, Geburstage, 20. Februar, 1904, Barth, Leipzig, 1904.Stanley R. P., “Eulerian partitions of a unit hypercube”, Higher Combinatorics, Proceedings of the NATO Advanced Study Institute, Berlin, West Germany, September 1–10, 1976, Reidel, Dordrecht/Boston, 1977.Stanley R. P., “Eulerian partitions of a unit hypercube”, Higher Combinatorics, Proceedings of the NATO Advanced Study Institute, Berlin, West Germany, September 1–10, 1976, Reidel, Dordrecht/Boston, 1977.

The authors declare that there are no conflicts of interest present.