О визуализации решений некоторых экстремальных задач

21

Аннотация

В статье обсуждается задача нахождения прямой на плоскости, сумма квадратов расстояний до которой от n данных точек этой плоскости будет наименьшей. Показывается, как свести эту задачу к решению аналогичной задачи для трех точек, решением которой служит прямая, содержащая большую ось эллипса Штейнера треугольника с вершинами в этих точках. Высказывается также гипотеза о связи рассматриваемой тематики с задачей об областях притяжения в теории фракталов.

Общая информация

Ключевые слова: визуализация, Экстремальные задачи, эллипс, фракталы, обучение математике

Рубрика издания: Методика преподавания

Тип материала: научная статья

DOI: https://doi.org/10.17759/mda.2022120407

Получена: 07.11.2022

Принята в печать:

Для цитаты: Куланин Е.Д., Степанов М.Е. О визуализации решений некоторых экстремальных задач // Моделирование и анализ данных. 2022. Том 12. № 4. С. 94–104. DOI: 10.17759/mda.2022120407

Полный текст

  1. ВВЕДЕНИЕ.

Настоящей заметкой мы продолжаем серию статей [1]-[4], посвященных решению экстремальных задач.

  1. ЗАДАЧА О НАХОЖДЕНИИ МИНИМАЛЬНОЙ ПРЯМОЙ.

Рассмотрим сначала известную задачу нахождения прямой на плоскости, сумма квадратов расстояний до которой от 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 , т.е. среднее арифметическое корней   z1, z2 , … , zn       многочлена P(z) равно  (z1+ z2 + …  +zn)/(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 - c= 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φ + np=

(1/2) (x12   + … + xn2) sin2φ + (1/2) (x12   + … + xn2)(1- cos2φ) + (1/2) (y12 + … + yn2) cos2φ +(1/2) (y12 + … + yn2) (1 - sin2φ) + np= (1/2) (x12 + y12 … + xn2 + yn2) + (1/2) (x12   + … + xn2)(sin2φ - cos2φ) + (1/2) (y12 + … + yn2)(cos2φ- sin2φ) + np=  (1/2) (x12 + y12 … + xn2 + yn2) - (1/2) (x12   + … + xn2) cos2φ +(1/2)(y12 + … + yn2)cos2φ  + np=                                                                                                 (1/2) (x12 + y12 … + xn2 + yn2) - (1/2)(x12 - y12  + … + xn2 - yn2) cos2φ + np=                                                                                                 (1/2) (x12 + y12 … + xn2 + yn2) - (1/2)n(n-1)c 2cos2φ + np≥                                       (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, т.е. минимальная прямая действительно совпадает с осью Ох.  

  1. ПРИМЕНЕНИЯ В МАТЕМАТИЧЕСКОЙ СТАТИСТИКЕ.

  Заметим, что в математической статистике минимальная прямая называется главной компонентой. Основы метода главных компонент (англ.

Principal component analysis, PCA) были заложены знаменитым английским ученым, основателем математической статистики Карлом Пирсоном (1857-1936) в статье [6]. Именно в этой статье и была поставлена задача   нахождения прямой, минимизирующей сумму квадратов расстояний от n данных точек плоскости до этой прямой. В настоящее время метод главных компонент разросся до обширной прикладной дисциплины, занимающейся в том числе и вопросами визуализации данных ([7]-[8]).

  1. ГИПОТЕЗА ОТНОСИТЕЛЬНО ПРОБЛЕМЫ А.КЭЛИ ДЛЯ КОМПЛЕКСНЫХ ПОЛИНОМОВ.

 Рассмотрим в заключение некоторую гипотезу относительно проблемы А.Кэли (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)-го порядка, т.е. с центром тяжести корней кубического многочлена.

   К сожалению, авторы не имеют доступа к быстродействующей вычислительной технике и мониторам с высоким разрешением и, таким образом, не имеют возможности экспериментально проверить эту гипотезу.

Литература

  1. Куланин Е.Д., Нуркаева И.М. О двух геометрических задачах на экстремум. Математика в школе. 2019. № 4. С. 35-40.
  2. Куланин Е.Д., Степанов М. Е., Нуркаева И.М. Пропедевтика решения экстремальных задач в школьном курсе математики. Моделирование и анализ данных.  2019. № 4. С.127-144.
  1. Куланин Е.Д., Нуркаева И.М. Еще раз о задаче Мавло. Математика в школе. 2020. № 2. С. 76-79.
  2. Куланин Е.Д., Степанов М. Е., Нуркаева И.М. О различных подходах к решению экстремальных задач. Моделирование и анализ данных. 2020. Т.11. №1. С.40 - 60.
  3. Чезаро Э. Элементарный учебник алгебраического анализа и исчисления  бесконечно малых. Часть первая. ОНТИ, Л-М: 1936.
  4. Pearson K. On lines and planes of closest fit to systems of points in space,  Philosophical Magazine, (1901) 2, 559—572; http://pca.narod.ru/
  5. Зиновьев А. Ю. Визуализация многомерных данных, Красноярск, Изд. КГТУ, 2000.
  6. (Электронный ресурс) URL: https://dic.academic.ru/dic.nsf/ruwiki/1105612?ysclid=la3pdtnhsn961871750
  7. Пайтген Х.-О., Рихтер П.Х. Красота фракталов. Образы комплексных динамических систем. М: «Мир», 1993.
  8. Куланин Е.Д., Степанов М. Е. Всестороннее рассмотрение математических понятий как методический прием. Моделирование и анализ данных. 2022.  Т.12. №4.   

Информация об авторах

Куланин Евгений Дмитриевич, кандидат физико-математических наук, профессор, Московский государственный психолого-педагогический университет (ФГБОУ ВО МГППУ), Москва, Россия, ORCID: https://orcid.org/0000-0001-6093-7012, e-mail: lucas03@mail.ru

Степанов Михаил Евграфович, кандидат педагогических наук, доцент, Московский государственный психолого-педагогический университет (ФГБОУ ВО МГППУ), Москва, Россия, ORCID: https://orcid.org/0000-0003-4803-8211, e-mail: mestepanov@yandex.ru

Метрики

Просмотров

Всего: 93
В прошлом месяце: 9
В текущем месяце: 5

Скачиваний

Всего: 21
В прошлом месяце: 1
В текущем месяце: 1