nlothik

х0,у0 - координата центра
х0*n=summ (x1+x2+...xn)
y0*n=summ (y1+y2+...yn)

квадрат расстояния до центра от точки (xi,yi) - ai = (xi-x0)2+(yi-y0)2
в квадрате то есть. не умею ставить.

то есть сумма кварратов рассстояний равна

S=(x12+...xn2)+(y12+...yn2)+n*x02+n*y02-2x0(x1+...xn)-2y0(y1...yn)

упростим до S'=nx02+ny02-2nx02-2ny02

первые два члена суммы выброшены за ненадобностью, они от выбора центра не зависят.

S'= |nx02+ny02|

нетрудно заметить, что S'=summ(x)2/n+summ(y)2/n

теперь предположим. что S' - не минимально. тогда х0 и у0 не будут являться центром, в понимании условия задачи.

ерунду написал.

переведем в плоскость.
там визуально понятно, но аккуратно доказать пока не удалось

так, погнали:
если взять точки на прямой и найти среднее арифметическое, то слева и справа будут два подмножества.
у каждого из них если точка, самая близкая к среднему.
так вот если взять условную точку, и двигать ее между краями подмножеств, то сумма расстояний меняться не будет.
а вот сумма квадратов - будет.
потому что сдвигаясь влево или вправо от среднего получим, что с одной стороны сумма квадратов растет быстрее, чем с другой убывает.
потому что Х2 растет после единицы быстрее, чем убывает от 1 до 0.

формально по прежнему не могу.

количество измерений тут роли не играет.

По-моему, ты всё правильно в самом первом ответе написал.

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

> неа, в начале последний вывод вообще неочевиден

Почему неочевиден? Там же как день ясно, что координаты должны совпадать со средним арифметическим.

ну там в последнем преобразовании х0 заменили на среднее арифметическое.
поэтому вывод звучит так: если х0 это среднее арифметическое то очевидно что центр именно там ))

Угу -- что надо сделать, чтобы минимизировать сумму квадратов? Надо найти ту точку, где производная равна нулю. Выписываем всё, понимаем, что если она равна нулю, то координаты точки есть координаты всех остальных точек, поделенные на их количество. Т.е. арифметическое среднее. Всё правильно ты написал, зря критику на себя наводишь. Спасибо!

>>S'= |nx02+ny02|

нетрудно заметить, что S'=summ(x)2/n+summ(y)2/n
-
производные сталбыть.

это штрих ))

Сначала проверим на простом примере.
Пусть у нас две точки. Координаты (х,у) 1.1 / 1.-1
Среднее у нее будет (1+1)/2, = 1, 1-1 = (1.0)
Ну, вроде верно.

>>сумма квадратов дистанций от всех точек до этой точки
-
именно квадратов? А ничего, что если совпадает сумма квадратов, то должна совпадать и сумма модулей, а значит можно сразу выкинуть квадраты и смотреть только на расстояние.

Но тем не менее посчитаем.
Дистанция между двумя точками будет sqrt (dx**2 + dy**2). Патамучто прямоугольный треугольник и евонная (ихняя) гипотенуза.
-
Дальше надо написать формулу для подсчета такого координат для N-ной группы точек и из него вывести дистанцию для N-ной точки.
После чего посмотреть, линейная ли это формула, ну взять там производную, посмотреть критические точки. После этого взять координаты точки x+1, y+1, и показаьть что для любой такой точки дистанция будет расти.
Собственно, если при изменении неких x,y поведение функции меняется с падения (дистанции) на рост (дистанции), то это будет точка перегиба и в ней что-то там творится с первой и второй производной.
Как-то так.

Можно так, но ИМХО, с производной от функции суммы квадратов понагляднее. Спасибо!

возьми прямую с точками 1 2 3 8 9 10.

сумма расстояний до любой точки между 3 и 8 одинаковая.

а если квадраты - то разница видна

Написать эту сумму квадратов и продифференцировать?

Угу, именно так в итоге и поступил!