Моделирование и анализ данных
2022. Том 12. № 4. С. 94–104
doi:10.17759/mda.2022120407
ISSN: 2219-3758 / 2311-9454 (online)
О визуализации решений некоторых экстремальных задач
Аннотация
В статье обсуждается задача нахождения прямой на плоскости, сумма квадратов расстояний до которой от n данных точек этой плоскости будет наименьшей. Показывается, как свести эту задачу к решению аналогичной задачи для трех точек, решением которой служит прямая, содержащая большую ось эллипса Штейнера треугольника с вершинами в этих точках. Высказывается также гипотеза о связи рассматриваемой тематики с задачей об областях притяжения в теории фракталов.
Общая информация
Ключевые слова: визуализация, Экстремальные задачи, эллипс, фракталы, обучение математике
Рубрика издания: Методика преподавания
Тип материала: научная статья
DOI: https://doi.org/10.17759/mda.2022120407
Получена: 07.11.2022
Принята в печать:
Для цитаты: Куланин Е.Д., Степанов М.Е. О визуализации решений некоторых экстремальных задач // Моделирование и анализ данных. 2022. Том 12. № 4. С. 94–104. DOI: 10.17759/mda.2022120407
Полный текст
- ВВЕДЕНИЕ.
Настоящей заметкой мы продолжаем серию статей [1]-[4], посвященных решению экстремальных задач.
- ЗАДАЧА О НАХОЖДЕНИИ МИНИМАЛЬНОЙ ПРЯМОЙ.
Рассмотрим сначала известную задачу нахождения прямой на плоскости, сумма квадратов расстояний до которой от n данных точек этой плоскости будет наименьшей, следуя в основном изложению в [5]. Эта прямая имеет следующий механический смысл: если поместить в данные точки одинаковые массы, то она совпадет с осью, относительно которой полученная система масс имеет наименьший момент инерции.
Пусть z1, z2 , … , zn - комплексные числа, соответствующие данным n точкам на комплексной плоскости. Составим многочлен P(z) = (z – z1)(z – z2) … (z – zn), корнями которого являются числа z1, z2, … zn . После раскрытия скобок получим P(z) = zn – c1zn-1 + c2zn-2 – … (-1) n cn ,
где c1 = z1 + z2 + … + zn , c2 = z1 z2 + z1 z3 + … + zn-1zn , cn = (-1) n z1 z2 … zn .
Среднее арифметическое корней многочлена обозначим через g:
g = (z1 + z2 + … + zn)/n , откуда c1 = z1 + z2 + … + zn = ng (1)
и найдем среднее арифметическое корней производной многочлена P(z): P‘(z) = nzn-1 – (n-1)c1zn-2 + … (-1) n-1 cn-1.
По теореме Виета сумма корней многочлена P‘(z) равна (n-1)c1/n = (n-1)ng/n = (n-1)g , т.е. среднее арифметическое корней z‘1, z‘2 , … , z‘n многочлена P‘(z) равно (z‘1+ z‘2 + … +z‘n)/(n-1) и, таким образом, средние арифметические корней многочлена P(z) и его производной P‘(z) совпадают.
Если поместить в данные точки одинаковые массы, то можно сказать, что центры тяжести корней многочлена P(z) и его производной P‘(z) совпадают.
Понятно, что число g будет единственным корнем (n-1)-ой производной многочлена P(z). Действительно, P(n-1)(z) = n(n-1) … 2z - c1(n-1)(n-2) … 2 = 0, откуда после сокращения на (n-1)! = 1*2* … *(n-1) получим nz - c1 = 0,
z = c1/n = g. Обозначим через u и v корни многочлена P(n-2)(z), т.е. корни уравнения n(n-1)z2 – 2(n-1) c1z + 2c2 = 0. Тогда по теореме Виета
u + v = 2(n-1)c1 /(n(n-1)) = 2c1/n = 2g, (2)
uv = 2c2/(n(n-1)) = 2(z1 z2 + z2 z3 + … +zn-1zn)/(n(n-1)), откуда
z1 z2 + z2 z3 + … +zn-1zn = n(n-1)uv/2. (3)
Выразим сумму квадратов корней многочлена P(z) через корни u и v (n-2)-ой производной этого многочлена:
(z1 + z2 + … + zn) 2 = (z12 + z22 + … + z2n) + 2(z1 z2 + z2 z3 + … +zn-1zn), откуда, учитывая (1) и (3), получим
z12 + z22 + … + z2n = (z1 + z2 + … + zn) 2 - 2(z1 z2 + z2 z3 + … +zn-1zn) = n2g2 - n(n-1)uv. Отсюда легко найти сумму квадратов (z1 – g) 2 + (z2 – g) 2 + … + (zn – g) 2 = z12 + z22 + … + z2n - 2g(z1 + z2 + … + zn) + ng 2 = n2g2 - n(n-1)uv – 2g*ng + ng 2 = ng 2(n-1) – n(n -1)uv = n(n -1)(g2 – uv).
Поскольку g = (u + v)/2 (см.(2)), то g2 – uv = ((u + v)/2) - uv =
(u2 + v2 - 2uv)/4 = (u – v) 2 /4, т.е. n(n-1)(g2 – uv) = n(n-1)(u – v) 2 /4 и
(z1 – g) 2 + (z2 – g) 2 + … + (zn – g) 2 = n(n-1)(u – v) 2 /4.
Обозначим через (xk ; yk) координаты комплексного числа zk – g (k = 1, 2, …, n) в декартовой системе координат, начало которой совпадает с точкой g, а ось абсцисс проходит через точки u и v (рис.1). Тогда при делении zk – g на xk + iyk из аргумента комплексного числа zk – g будет вычитаться угол, образуемый вектором zk – g с осью uv (рис.1), поэтому аргументы чисел
(zk – g)/(xk + iyk) равны аргументу числа v – u.
Рис.1
Учитывая, что │zk – g│ = │ xk + iyk │, получим:
(zk – g)/(xk + iyk) = … = (zk – g)/(xk + iyk) = (v – u)/(2c), 2c = │v – u│,
откуда (xk + iyk) 2 = 4с2 (zk – g) 2/(u – v) 2 , k = 1, 2, … , n и (x1 + iy1) 2 + … + (xn + iyn) 2 = 4с2/(u – v) 2((z1 – g) 2 + (z2 – g) 2 + … + (zn – g) 2) = (4с2/(u – v) 2)n(n-1)(u – v) 2 /4 = n(n-1)c 2
Итак, (x1 + iy1) 2 + … + (xn + iyn) 2 = n(n-1)c 2. (3)
Раскрыв скобки в левой части равенства (3), получим:
x12 - y12 + … + xn2 - yn2 + 2i(x1y1 + … + xnyn) = n(n-1)c 2, а выражение n(n-1)c 2 является действительным числом, то
x12 - y12 + … + xn2 - yn2 = n(n-1)c 2, x1y1 + … + xnyn = 0. (4)
Учитывая то, что мы приняли g за начало новой системы координат, имеем:
x1 + x2 + … + xn = 0, y1 + y2 +… + yn = 0. (5)
Пусть xcosα +ysinα – p = 0 – нормальное уравнение искомой минимальной прямой, где α – угол между нормалью к прямой и осью абсцисс, р – расстояние от начала координат до этой прямой.
Рис.2
Так как φ – внешний угол прямоугольного треугольника OAB, то φ = π/2 + α (рис.2), откуда α = φ - π/2, cosα =cos(φ - π/2) = sinφ, sinα = sin(φ - π/2) = -sin(π/2 - φ) = -cosφ и, таким образом, нормальное уравнение прямой примет вид
x sinφ - ycosφ – p = 0, (6)
где φ – угол между искомой прямой и осью абсцисс uv новой системы координат. Обозначим через dk расстояния от точек zk до прямой (6) (k = 1, 2, …, n). Тогда dk = │xk sinφ - ykcosφ – p│и d12 + … + dn2 = │x1 sinφ - y1cosφ – p│2 + … + │xn sinφ - yncosφ – p│2 =
(x1 sinφ - y1cosφ – p)2 + … + (xn sinφ - yncosφ – p)2 = (x12 + … + xn2) sin2φ +
(y12 + … + yn2) cos2φ + np2 – 2(x1y1 + … + xnyn)sinφcosφ -2psinφ(x1 + x2 + … + xn) + 2pcosφ(y1 + y2 +… + yn). Три последних слагаемых равны нулю, поскольку согласно (4) и (5) x1y1 + … + xnyn = 0, x1 + x2 + … + xn = 0, y1 + y2 +… + yn = 0.
Итак, d12 + … + dn2 = (x12 + … + xn2) sin2φ + (y12 + … + yn2) cos2φ + np2 =
(1/2) (x12 + … + xn2) sin2φ + (1/2) (x12 + … + xn2)(1- cos2φ) + (1/2) (y12 + … + yn2) cos2φ +(1/2) (y12 + … + yn2) (1 - sin2φ) + np2 = (1/2) (x12 + y12 … + xn2 + yn2) + (1/2) (x12 + … + xn2)(sin2φ - cos2φ) + (1/2) (y12 + … + yn2)(cos2φ- sin2φ) + np2 = (1/2) (x12 + y12 … + xn2 + yn2) - (1/2) (x12 + … + xn2) cos2φ +(1/2)(y12 + … + yn2)cos2φ + np2 = (1/2) (x12 + y12 … + xn2 + yn2) - (1/2)(x12 - y12 + … + xn2 - yn2) cos2φ + np2 = (1/2) (x12 + y12 … + xn2 + yn2) - (1/2)n(n-1)c 2cos2φ + np2 ≥ (1/2) (x12 + y12 … + xn2 + yn2) - (1/2)n(n-1)c 2, причем равенство в последнем неравенстве достигается только в случае φ = 0, p = 0 .
Таким образом, минимальная прямая, т.е. прямая в плоскости n данных точек, для которой сумма расстояний от этих точек является наименьшей, проходит через корни u и v (n-2)-ой производной P(n-2)(z) многочлена P(z).
Рассмотрим случай n=3. Тогда первое из соотношений (4), а именно
x12 - y12 + … + xn2 - yn2 = n(n-1)c 2 примет вид x12 - y12 + x22 - y22 + x32 - y32 = 3*2*c 2 = 6c 2. (7)
Положим x12 + x22 + x32 = 6a 2, а y12 + y22 + y32 = 6b 2. (8)
Тогда равенство (7) преобразуется в x12 - y12 + x22 - y22 + x32 - y32 = (x12 + x22 + x32) - (y12 + y22 + y32) =6a 2 - 6b 2 =
6(a 2 - b 2) = 6c 2, откуда a 2 - b 2 = c 2, где 2c = │v - u│. (9)
Таким образом, фокусы эллипса с уравнением x2/a 2 + y2/b 2 = 1, (10)
где a, b и c определяются равенствами (8) - (9) совпадают с точками u и v.
Покажем, что середины сторон треугольника АВС, где А(x1; y1), В(x2; y2),
С(x3 ; y3) лежат на этом эллипсе. Пусть Мa , Мb , Мc - середины сторон ВС, СА, АВ треугольника АВС соответственно. Тогда Мa ((x2 + x3)/2; (y2 + y3)/2),
Мb ((x1 + x3)/2; (y1 + y3)/2), Мc ((x1 + x2)/2; (y1 + y2)/2). Поскольку начало выбранной нами системы координат совпадает с центром тяжести треугольника АВС, то x1 + x2 + x3 = 0, y1 + y2 + y3 = 0. (11)
Кроме того, с учетом (4), имеем x1y1 + x2y2 + x3y3 = 0, (12)
откуда x3y3 = - x1y1 - x2y2 , но согласно (11) y3 = - y1 - y2 , поэтому x3(-y1 - y2) = - x1y1 - x2y2 или x3y1 + x3y2 = x1y1 + x2y2 , x3y1 - x1y1 = x2y2 - x3y2 , y1(x3 - x1) = y2 (x2 - x3) , т.е. y1/(x2 - x3) = y2/(x3 - x1).
Аналогично, y2/(x3 - x1) = y3/(x1 - x2). Итак, y1/(x2 - x3) = y2/(x3 - x1) = y3/(x1 - x2) = k и y1 = k(x2 - x3), y2= k(x3 - x1), y3= k(x1 - x2) . (13)
Но согласно (8) y12 + y22 + y32 = 6b 2, поэтому
k2((x2 - x3)2 + (x3 - x1)2 + (x1 - x2)2) = 6b 2,
k2(2(x12 + x22 + x32) -2(x1x2 + x2x3 + x1x3)) = 6b 2 .
После возведения в квадрат обеих частей равенства x1 + x2 + x3 = 0 (см.(11)), получим x12 + x22 + x32 + 2(x1x2 + x2x3 + x1x3) = 0, откуда
2(x1x2 + x2x3 + x1x3) = -x12 - x22 - x32 и
k2(2(x12 + x22 + x32) -2(x1x2 + x2x3 + x1x3)) = k2(2(x12 + x22 + x32) + x12 + x22 + x32) = 3k2(x12 + x22 + x32) = 3k2 *6a 2 = 6b 2, т.е. 3k2a 2 = 6b 2, k2 = b 2/3a 2. (14)
Найдем значение выражения x12/a 2 + y12/b 2, учитывая (13) и (14):
x12/a 2 + y12/b 2 = x12/a 2 + k2(x2 - x3)2 /b 2 = x12/a2 + b2(x2 - x3)2 /3a2b 2 = (3x12 +(x2 - x3)2)/3a2 = (2x12 + x12 + (x2 - x3)2)/3a2 = (2x12 + (-x2 - x3)2 + (x2 - x3)2)/3a2 = 2(x12 + x22 + x32)/3a2 = 2*6a2/3a2 = 4. Итак, x12/a 2 + y12/b 2 = 4. (15)
Подставим теперь в уравнение (10) координаты точки Мa ((x2 + x3)/2; (y2 + y3)/2), заменив x2 + x3 и y2 + y3 на -x1 и - y1 соответственно (см. (11) и (15)): (-x1/2) 2/a2 + (-y1/2) 2/b2 = (1/4)(x12/a2 + y12 /b2) = (1/4)*4 = 1.
Таким образом, координаты точки Мa удовлетворяют уравнению (10), т.е. точка Мa лежит на этом эллипсе. Точно так же можно убедиться в том, что и середины Мb и Мc сторон АС и АВ тоже лежат на эллипсе (10) с центром в центре тяжести треугольника АВС и фокусами в точках u и v, совпадающих с корнями производной кубического многочлена, корнями которого являются вершины треугольника АВС. Поскольку любой треугольник можно перевести аффинным преобразованием в правильный треугольник, то при таком преобразовании центр тяжести треугольника АВС перейдёт в центр правильного треугольника, а середины сторон треугольника АВС – в середины сторон правильного треугольника, а наш эллипс – во вписанную окружность правильного треугольника. Итак, рассматриваемый эллипс касается сторон треугольника АВС в их серединах. Такой эллипс называется вписанным эллипсом Штейнера. Прямая, проходящая через фокусы эллипса Штейнера, и дает решение задачи о минимизации суммы квадратов расстояний от вершин треугольника до произвольной прямой в плоскости этого треугольника. В общем случае эта минимальная прямая наклонена как к сторонам треугольника, так и к осям системы координат.
Приведем теперь определение эллипса Штейнера, вернее двух эллипсов Штейнера – вписанного и описанного.
Пусть заданы правильный треугольник А0В0С0 и произвольный треугольник АВС. Существует аффинное преобразование, которое переводит вершины первого треугольника в соответствующие вершины второго. Образ вписанной в правильный треугольник окружности называется вписанным эллипсом Штейнера. Образ описанной вокруг правильного треугольника окружности называется описанным эллипсом Штейнера. Различные задачи, связанные с эллипсами Штейнера, рассматриваются в статье авторов [10].
Для того, чтобы сделать картинку более наглядной, рассмотрим обратную задачу: пусть дан эллипс. Найти треугольники, для которых прямая, содержащая большую ось этого эллипса является минимальной.
Выберем систему координат Oxy так, чтобы её начало совпало с центром эллипса, а его фокусы лежали на оси Ox. Тогда координаты точек должны удовлетворять соотношениям (11) - (12): x1 + x2 + x3 = 0, y1 + y2 + y3 = 0,
x1y1 + x2y2 + x3y3 = 0. Легко подобрать следующее целочисленное решение этих уравнений: x1 = 1, y1 = 5, x2 = 2, y2 = -4, x3 = -3, y3 = -1.
Для того, чтобы координаты середин сторон треугольника АВС также были целочисленными, достаточно удвоить найденные координаты.
Тогда А(10; 2), В(-8; 4), С(-2; 6), Мa (-5; -1); Мb(4; -2), Мс(1; 3).
Треугольник, имеющий такие координаты вершин, вместе с его вписанным эллипсом Штейнера изображен на рис.3.Минимальная прямая этого треугольника совпадает с осью Ox.
Рис.3
То, что ось Ox действительной прямой, легко проверить непосредственно. Сумма квадратов расстояний от вершин А, В, С до оси Ox равна 22 + 42 + 62 = 56. Понятно, что минимальная прямая должна проходить через центр тяжести треугольника АВС, т. е. через начало координат О. Сумма квадратов расстояний от вершин А, В, С до оси Oy равна 102 + 82 + 22 = 168 > 56. Уравнение любой прямой, проходящей через начало координат и отличной от оси Oy, имеет вид y = kx, поэтому d12 + d22 + d32 = ((kx1 - y1) 2 + (kx2 - y2) 2 + (kx3 - y3) 2)/(k2 + 1) =
(4/(k2 + 1))*((5k - 1) 2 + (-4k - 2) 2 + (-k + 3) 2) = 4(42k2 + 14)/(k2 + 1) =
56(3k2 + 1)/(k2 + 1) = 56(k2 + 1 +2k2)/(k2 + 1) = 56(k2 + 1)/(k2 + 1) + 56*2k2/(k2 + 1) = 56 + 112k2/(k2 + 1) ≥ 56, причем минимум, равный 56, достигается при k = 0. В этом случае y = 0, т.е. минимальная прямая действительно совпадает с осью Ох.
- ПРИМЕНЕНИЯ В МАТЕМАТИЧЕСКОЙ СТАТИСТИКЕ.
Заметим, что в математической статистике минимальная прямая называется главной компонентой. Основы метода главных компонент (англ.
Principal component analysis, PCA) были заложены знаменитым английским ученым, основателем математической статистики Карлом Пирсоном (1857-1936) в статье [6]. Именно в этой статье и была поставлена задача нахождения прямой, минимизирующей сумму квадратов расстояний от n данных точек плоскости до этой прямой. В настоящее время метод главных компонент разросся до обширной прикладной дисциплины, занимающейся в том числе и вопросами визуализации данных ([7]-[8]).
- ГИПОТЕЗА ОТНОСИТЕЛЬНО ПРОБЛЕМЫ А.КЭЛИ ДЛЯ КОМПЛЕКСНЫХ ПОЛИНОМОВ.
Рассмотрим в заключение некоторую гипотезу относительно проблемы А.Кэли (1821-1895) для комплексных полиномов. В заметке «Комплексная проблема Ньютона-Фурье», опубликованной в 1879г., Кэли предложил применить метод, названный им методом Ньютона-Фурье к комплексным многочленам.
В действительном случае метод Ньютона состоит в построении рекуррентной последовательности {xk-p(xk)/p’(xk), k = 0, 1, 2, … (16)
В формулировке Кэли « … задача состоит в разделении плоскости на области так, чтобы, выбрав по желанию точку Р (начальную точку x0 в (16)), где бы то ни было внутри одной области, мы в конечном счете пришли бы к точке А (равной корню, т.е. р(А) = 0); где бы то ни было внутри другой области пришли бы к точке В и так далее для каждой из нескольких точек, представляющих корни нашего уравнения.
В случае квадратного уравнения решение оказывается простым и изящным, но уже следующий сменяющий его случай кубического уравнения, по-видимому, представляет значительную трудность [9]. Действительно, для квадратных уравнений данная последовательность всегда сходится к ближайшему корню, за исключением случая, когда начальная точка z0 лежит на серединном перпендикуляре отрезка с концами, совпадающими с корнями данного квадратного уравнения. В этом случае точки zк будут все время оставаться на этом серединном перпендикуляре, совершая хаотическое движение. Для многочленов более высоких степеней, например, кубических, эта задача так и осталась нерешенной, хотя еще в 1879г. Артур Кэли собирался представить решение в следующей публикации, но она, увы, так никогда и не появилась [9].
Компьютерные эксперименты для кубических многочленов показали, что существуют хорошие по отношению к методу Ньютона многочлены, т.е. такие, для которых почти все начальные точки сходятся к одному из корней, и плохие, для которых начальные точки не сходятся ни к одному из корней уравнения. Однако оказалось, что центр тяжести корней может служить хорошей контрольной точкой: если последовательность с начальной точкой в центре тяжести корней сходится к одному из корней многочлена, то этот многочлен хороший. Если же после достаточно большого числа итераций она не подходит близко ни к одному из корней, то велика вероятность того, что многочлен плохой [9].
Поскольку минимальная прямая проходит через центр тяжести корней и фокусы эллипса Штейнера, совпадающие с корнями производной кубического многочлена, то естественно предположить, что существует какая-то связь между проблемой Ньютона-Фурье для кубического многочлена и геометрией треугольника с вершинами в корнях этого кубического многочлена. Тогда эта связь будет иметь место и для многочленов высших степеней, так как центр тяжести корней многочлена степени n совпадает с центром тяжести корней его производной (n-3)-го порядка, т.е. с центром тяжести корней кубического многочлена.
К сожалению, авторы не имеют доступа к быстродействующей вычислительной технике и мониторам с высоким разрешением и, таким образом, не имеют возможности экспериментально проверить эту гипотезу.
Литература
- Куланин Е.Д., Нуркаева И.М. О двух геометрических задачах на экстремум. Математика в школе. 2019. № 4. С. 35-40.
- Куланин Е.Д., Степанов М. Е., Нуркаева И.М. Пропедевтика решения экстремальных задач в школьном курсе математики. Моделирование и анализ данных. 2019. № 4. С.127-144.
Информация об авторах
Метрики
Просмотров
Всего: 172
В прошлом месяце: 9
В текущем месяце: 0
Скачиваний
Всего: 44
В прошлом месяце: 0
В текущем месяце: 0