Oб оптимальной интерполяции линейными функциями на n-мерном кубе
https://doi.org/10.18255/1818-1015-2018-3-291-311
Аннотация
Пусть \(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.\)
Об авторах
Михаил Викторович НевскийРоссия
д-р физ.-мат. наук, доцент, НОМЦ Центр интегрируемых систем
Алексей Юрьевич Ухалов
Россия
кандидат физ.-мат. наук, НОМЦ Центр интегрируемых систем
Список литературы
1. Есипова Е. М., “Геометрические характеристики симплексов, обладающих свойством равноотсечения”, Современные проблемы математики и информатики, 17, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2017, 49– 61
2. Кудрявцев И. С., Озерова Е. А., Ухалов А.Ю., “Новые оценки для норм минимальных проекторов”, Современные проблемы математики и информатики, 17, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2017, 74–81
3. Невский М. В., “Ортогональное проектирование и минимальная линейная интерполяция на n-мерном кубе”, Модел. и анализ информ. систем, 14:3 (2007), 8– 28
4. Невский М. В., Хлесткова И. В., “К вопросу о минимальной линейной интерполяции”, Современные проблемы математики и информатики, 9, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2008, 31–37
5. Невский М. В., “Об одном соотношении для минимальной нормы интерполяционного проектора”, Модел. и анализ информ. систем, 16:1 (2009), 24–43
6. Невский М. В., “Об одном свойстве n-мерного симплекса”, Матем. заметки, 87:4 (2010), 580–593
7. Невский М. В., Геометрические оценки в полиномиальной интерполяции, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2012
8. Невский М. В., Ухалов А.Ю., “О числовых характеристиках симплекса и их оценках”, Модел. и анализ информ. систем, 23:5 (2016), 602–618
9. Невский М. В., Ухалов А.Ю., “Новые оценки числовых величин, связанных с симплексом”, Модел. и анализ информ. систем, 24:1 (2017), 34–50
10. Невский М. В., Ухалов А.Ю., “Об n-мерных симплексах, удовлетворяющих включениям S ⊂ [0, 1]n ⊂ nS”, Модел. и анализ информ. систем, 24:5 (2017), 578– 595
11. Невский М. В., Ухалов А.Ю., “О минимальном коэффициенте поглощения для n-мерного симплекса”, Модел. и анализ информ. систем, 25:1 (2018), 140–150
12. Сегё Г., Ортогональные многочлены, Гос. изд-во физ.-мат. литературы, М., 1962
13. Суетин П. К., Классические ортогональные многочлены, Наука, М., 1979
14. Холл M., Комбинаторика, Мир, М., 1970
15. 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.
16. Comtet L., “Permutations by number of rises; Eulerian numbers”, Advanced Combinatorics: The Art of Finite and Infinite Expansions”, Reidel, Dordrecht, Netherlands, 1974.
17. Ehrenborg R., Readdy M., Steingrimsson E., “Mixed volumes and slices of the cube”, Journal of Combinatorial Theory. Series A., 81 (1998), 121–126.
18. Graham R. L., Knuth D. E., Patashnik O., Concrete mathematics: A foundation for computer science, Addison–Wesley, Reading, MA, 1994.
19. 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.
20. de Laplace M., Oeuvres compl´etes. V. 7, R´e´edite par Gauthier–Villars, Paris, 1886.
21. Mangano S., Mathematica cookbook, O’Reilly Media Inc., Cambridge, 2010.
22. Nevskii M., “Properties of axial diameters of a simplex”, Discrete Comput. Geom., 46:2 (2011), 301–312.
23. Scott P. R., “Lattices and convex sets in space”, Quart. J. Math. Oxford (2), 36 (1985), 359–362.
24. Scott P. R., “Properties of axial diameters”, Bull. Austral. Math. Soc., 39 (1989), 329–333.
25. Sommerfeld A., “Eine besonders anschauliche Ableitung des Gaussischen Fehlergesetzes”, Festschrift Ludwig Boltzmann gewidmet zum 60, Geburstage, 20. Februar, 1904, Barth, Leipzig, 1904.
26. 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.
Рецензия
Для цитирования:
Невский М.В., Ухалов А.Ю. Oб оптимальной интерполяции линейными функциями на n-мерном кубе. Моделирование и анализ информационных систем. 2018;25(3):291-311. https://doi.org/10.18255/1818-1015-2018-3-291-311
For citation:
Nevskii M.V., Ukhalov A.Yu. On Optimal Interpolation by Linear Functions on an n-Dimensional Cube. Modeling and Analysis of Information Systems. 2018;25(3):291-311. (In Russ.) https://doi.org/10.18255/1818-1015-2018-3-291-311