Универсальное пособие по математике, включающее в себя математический анализ, линейную алгебру, теорию оптимизации и евклидову геометрию.
Занятия в школе начались с урока математики. Профессор сразу же начал с практического задания и предложил задачу:
На плоскости был нарисован квадрат, и на каждой из сторон последнего отметили по одной точке. Потом квадрат был стёрт, а четыре отмеченные точки остались. Как по ним найти вершины квадрата, то есть восстановить квадрат?
Осторожные ученики уточнили:
- А у нас есть циркуль и линейка?;)
Профессор их успокоил:
- Конечно, всё, что хотите: циркуль, линейка, система координат и т.д. и т.п.
Глубокое обучение
Первым руку поднял датасайнтист из отдела глубокого обучения:
- Квадрат - это четырехугольник, с этим никто не станет спорить? Чтобы восстановить стертый квадрат нужно найти положение его вершин. Давайте начнем с четырех случайных точек на плоскости и посмотрим, насколько мы ошиблись. У нас будет два источника ошибок. Первый источник ошибок возникает потому, что случайные точки будут вершинами произвольного четырехугольника, а не квадрата. Второй источник ошибок - отмеченные точки не будут лежать на сторонах нашего четырехугольника. Эти ошибки можно охарактеризовать с помощью некоторых неотрицательных функций от положения пробных вершин. Мы найдем, как нужно сдвинуть пробные вершины, чтобы уменьшить суммарную ошибку. А потом повторим процесс много раз, пока у нас не получится квадрат, на сторонах которого лежат отмеченные точки!
Профессор с интересом слушал предложенное решение, а потом предложил попробовать применить этот метод, пока другие ученики размышляют над решением. Он запустил Wolfram Mathematica и начал набирать код:
s = 1; phi = Pi/6; "Пусть сторона квадрата равна 1, а сам квадрат повернут на произвольный угол относительно координатных осей. Для начала я возьму угол в 30 градусов";
"Одну вершину квадрата ABFG я помещу в начало координат, без потери общности и сложности. Координаты остальных вершин я найду, зная длину стороны и ориентацию квадрата";
A = {0, 0};
B = s*{Cos[phi], Sin[phi]};
G = s*{-Sin[phi], Cos[phi]};
F = B + G;
"Теперь отметим 4 случайные точки на каждой стороне. Для этого прибавим к координатам каждой вершины случайный сдвиг вдоль стороны";
{x1, y1} = A + RandomReal[{0.1, 0.9}] (B - A);
{x2, y2} = B + RandomReal[{0.1, 0.9}] (F - B);
{x3, y3} = F + RandomReal[{0.1, 0.9}] (G - F);
{x4, y4} = G + RandomReal[{0.1, 0.9}] (A - G);
- И вот что у меня получилось на плоскости, - профессор показал на экран.
- Будем считать, что координаты ABGF я вам не сказал. Данные с которыми вы работаете это координаты x1,y1 и т.д.
Ученик застучал по клавиатуре:
- Чтобы выбрать случайные точки At, Bt, Ft, Gt , я возьму отмеченные точки за основу и отступлю от них на случайные вектора
At = {x1, y1} + {RandomReal[{-0.4, 0.4}], RandomReal[{-0.4, 0.4}]};
Bt = {x2, y2} + {RandomReal[{-0.4, 0.4}], RandomReal[{-0.4, 0.4}]};
Ft = {x3, y3} + {RandomReal[{-0.4, 0.4}], RandomReal[{-0.4, 0.4}]};
Gt = {x4, y4} + {RandomReal[{-0.4, 0.4}], RandomReal[{-0.4, 0.4}]};
- Скорректированные положения точек будут зависеть от 8 переменных (координаты корректирующих сдвигов xag, yag и т.д., буква g здесь связана с градиентом - потому что его мы и будем искать):
Ag = At + {xag, yag};
Bg = Bt + {xbg, ybg};
Fg = Ft + {xfg, yfg};
Gg = Gt + {xgg, ygg};
- Теперь зададим функции ошибок. Кто-нибудь мне подскажет, какие свойства определяют квадрат, а то я сходу не вспомню?
Руку поднял геометр в античной тоге:
- У квадрата, все углы прямые, а также, прямой угол между диагоналями.
- Отлично, тогда отклонение от прямоугольности будет даваться скалярными произведениями векторов смежных сторон:
AngDev =((Ag-Bg).(Fg-Bg))^2+((Fg - Bg).(Fg - Gg))^2
+((Fg-Gg).(Ag-Gg))^2+((Ag-Gg).(Ag-Bg))^2;
- Отклонения возьмем в квадрате, чтобы всем прямым углам соответствовало минимальное (нулевое) значение. То же самое с диагоналями:
DiagDev = ((Bg - Gg) . (Ag - Fg))^2;
- А теперь нужно определить значение второй ошибки. Если наши точки 1, 2, 3, 4 попали на стороны скорректированного четырехугольника (он еще не сразу станет квадратом) AgBgFgGg, то расстояние от этих точек до соответствующих прямых dist(1,AgBg) обнулится. Значит ошибки попадания точек на сторону, это сумма квадратов расстояния от отмеченных точек до пробных прямых. А как же выразить это расстояние формулой? Я геометрию совсем не помню, подскажите?
Слово опять взял геометр.
- Очень просто. Если мы возьмем треугольник с вершинами 1, Ag,Bg и найдем его площадь, то она будет равна половине основания AgBg умножить на высоту. А высота и будет искомым расстоянием от точки 1 до прямой AgBg. Площадь через координаты вершин можно вычислить как детерминант матрицы 2 на 2, столбцы которой есть два смежных вектора определяющих треугольник. Тогда квадрат расстояния от отмеченной точки до пробной прямой будет отношением квадрата площади, поделить квадрат длины AgBg.
Датасайнтист схватывал все на лету и сразу же задал еще 4 функции ошибки (первая получилась такой):
Point1Dev=((Bg-{x1, y1})[[1]](Ag-{x1, y1})[[2]]-(Bg-{x1, y1})[[2]](Ag-{x1, y1})[[1]])^2/((Bg-Ag).(Bg - Ag));
а остальные аналогично.
- Вот всю работу и сделали, - сказал довольный ученик потирая руки. Теперь уж сам компьютер найдет значение ошибки и градиент
Error = AngDev+DiagDev+Point1Dev+Point2Dev+Point3Dev+Point4Dev;
GradError=Simplify[{D[Error, xag], D[Error, yag], D[Error, xbg], D[Error, ybg], D[Error, xfg], D[Error, yfg], D[Error, xgg], D[Error, ygg]}];
- А я только загоню последовательные поправки на положение пробных точек в цикл, пока ошибка станет не меньше желаемой точности эпсилон.
cnt = 0; cs = {0, 0, 0, 0, 0, 0, 0, 0};eps=0.1;
subst= {xag->cs[[1]],yag->cs[[2]],xbg->cs[[3]],ybg->cs[[4]], xfg->cs[[5]],yfg-> cs[[6]],xgg->cs[[7]],ygg->cs[[8]]};
While[
cnt<1500 && ((Error /.subst) > 0.0001 eps) , cnt++;
GradStep=-eps GradError /.subst; cs = cs + GradStep;
Ptg[cnt]=ListPlot[{At+{cs[[1]], cs[[2]]}, Bt+{cs[[3]], cs[[4]]}, Ft+{cs[[5]], cs[[6]]}, Gt +{cs[[7]], cs[[8]]}}, PlotStyle->{Green, PointSize[Large]}]
];
Он запустил расчеты и вот что у него получилось
Это был триумф! Но строгий учитель попросил сделать еще несколько попыток. Оказалось, что градиентный спуск может частенько привести совсем не туда
Ученик сообразил, что лучше брать стартовые точки так, чтобы отмеченные точки оказались внутри от пробного четырехугольника. А еще лучше взять не произвольный четырехугольник, а квадрат. Он вернулся за свою парту и с энтузиазмом продолжил оттачивать детали решения.
Гармония алгебры
В это время свое решение созрело у специалиста по линейной алгебре...
- Запишем уравнения прямых, проходящих через отмеченные точки
- Так как мы ищем стороны квадрата, смежные стороны перпендикулярны, а противолежащие стороны параллельны. Поэтому наклоны прямых связаны простым соотношением:
- Значит, по сути нам нужно найти один параметр - k - и задача будет решена. Вот что будет с моими четырьмя прямыми, если я буду менять k.
- Мы можем найти точки пересечения смежных прямых, которые будут кандидатами на роль вершин квадрата. Давайте найдем точку пересечения первой и второй прямой. Запишем для этого систему уравнений
- Складывая и вычитая уравнения, с соответствующими множителями мы получим координаты точки пересечения (которая должна быть вершиной квадрата).
Ученик, конечно, подробно выполнил на доске все действия, но мы приведем только ответ (а решение - упражнение:))
- Решать же уравнения для нахождения пересечений первой и четвертой прямой, а также второй и третьей не надо. Можно просто сделать замену индексов.
- Квадрат у нас получится, если |AB|=|AG|. Выглядит это условие сперва громоздко
Но это уравнение довольно сильно упрощается, так, что остается только алгебраическое уравнение второй степени на угловой коэффициент k
и в невырожденных случаях мы получаем два решения
- Раз мы теперь знаем k, то в уравнениях (1) нам все известно и мы можем построить прямые, задающие стороны квадрата. Одно из решений соответствует случаю, когда отмеченные точки, оказываются на прямых, но снаружи маленького квадрата (см. рисунок ниже)
- Вот это крастота! - восхитился датасайнтист. Вместо оптимизации функции 8 переменных, всего лишь решение системы двух линейных уравнений, и одного квадратного уравнения! Да и вырожденные случаи легче анализировать, и с подбором пробных точек не надо мучаться! Круто!
Классика вечна
Профессор же заметил, что геометр в античной тоге не выглядит восхищенным и скучая смотрит в потолок.
- Может быть у тебя есть свое решение? - иронично спрашивает профессор?
- Конечно, и целых два. Одно короткое, а другое в 1 действие, - встряхнувшись ответил ученик.
- Начну я с короткого. Давайте, все таки отмеченные точки обозначим классически - буквами ABCD. И, напоминаю, что у нас есть циркуль и линейка, а не только компьютер с математическим софтом.
Чертим две окружности с диаметрами AB и CD. Чертим диаметры этих окружностей перпендикулярные к AB и CD. Проводим прямую через конечные точки этих перпендикулярных диаметров лежащие внутри ABCD (эта прямая будет - сюрприз - диагональю). Точки пересечения этой прямой с окружностями вне ABCD есть две вершины искомого квадрата. Квадрат легко восстанавливается по одной вершине и четырем точкам на сторонах. От вырожденных случаев (видимо их тут немало) прошу меня освободить, как классика.
Остальные ученики спешно строили предстатвленный чертеж и пытались разобраться откуда вылезла диагональ. А профессор спросил:
- Это было решение короткое, а как восстатновить квадрат в одно действие.
- Подумайте ка сами, а вот вам zero knowledge доказательство, что я знаю как это сделать:
ЕЙ ОКУЛЯР СПАС РИМ КОЧКИ ИЗ ДЛИН В ТЕНИ В ПРОВОД ПАРАДНОЙ.
- Это анаграмма полного решения. Если вы решение найдете, я вам расшифрую анаграмму! Читайте Евклида, и будет вам счастье!
Обобщение
- В целом, это закономерно, что в классической геометрической задаче наиболее эффективно оказалось геометрическое решение - начал подводить итоги занятия профессор.
- А подумайте-ка дома, что будет, если я, вместо квадрата, возьму другой правильный многоугольник. Треугольник, пятиугольник и так далее? Какие решения сумеют выжить после такой сильной деформации? Сдается мне, что лишь градиентный спуск поможет восстановить произвольный правильный многоугольник по произвольным точкам на каждой стороне.