2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Минимальное значение суммы
Сообщение08.03.2015, 16:43 


08/01/14
5
Сербия, Белград
Всем здоровья.

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

Теорема: Пусть $x_1, x_2, ..., x_n$ растущая последовательность чисел. Сумма $ \sum_{k=1}^n |x_k-a|$ будет минимальной, если $a$ - медиана этой последовательности. То есть если $n=2k$, то $a=(x_k+x_{k+1})/2$, если же $n=2k+1$, то $a=x_{k+1}$.

Доказательство:
Рассмотрим сначала случай, когда n=2. То сумма сводится к $|x_1-a|+|x_2-a|$, благодаря неравенству треугольника получаем:
$|x_1-a|+|x_2-a|\geqslant |x_2-x_1|=x_2-x_1 $, так как последовательно растущая.
Что подходит под теорему даже для любого $a\in [x_1,x_2]$. А медиана находится в этом промежутке.

Далее, пусть $n$- произвольное число. Тогда начнём уменьшать нашу сумму следующим образом. Сначала рассмотрим только крайние элементы суммы, то есть $|x_1-a|+|x_n-a|$, вспомним, что мы доказывали для $n=2$, получаем что $a$ где-то между этими числами. Теперь тоже самое повторим для следующей пары чисел (на одну ближе к середине) $|x_2-a|+|x_{n-1}-a|$, отсюда получаем, что $a$ теперь в новом интервале, который является подинтервалом предыдущего. И т.д. пока мы можем это делать, если $n=2k$, то получим $a\in[x_k,x_{k+1}]$.
Если же $n=2k+1$, то получим $a=x_{k+1}$.

Теперь нужно показать, что такая сумма действительно минимальна. Пусть $a$ не из этого интервала, тогда все слагаемые будут минимизированы кроме тех, начиная с которого $a$ не попадает в заданный интервал.

И пожалуй всё. Что здесь надо доделать? И верно ли это доказательство?

 Профиль  
                  
 
 Re: Минимальное значение суммы
Сообщение08.03.2015, 18:01 
Заслуженный участник
Аватара пользователя


28/04/14
968
спб
Не вдавался в подробности вашего решения. Но можно сделать проще. Как вы заметили для случая $n=2$ всё сводится к правильному применению неравенства треугольника. Т.е. так, чтобы полученная оценка снизу достигалась при каком-то $a$.
Пусть $a \in [x_k;x_{k+1}]$. Тогда $$\sum\limits_{p=1}^{n} |x_p-a| = ka - \sum_{s=1}^{k}x_s - (n-k)a + \sum_{p=k+1}^{n}x_p = (2k-n)a - \sum_{s=1}^{k}x_s + \sum_{p=k+1}^{n}x_p.$$
Отсюда видно, что в случае $n=2k$ сумма превращается в $\sum\limits_{p=1}^{k} |x_{k+p}-x_p|$. А это и есть оценка снизу на исходную сумму.
Если же $n=2k+1$, то сумма превращается в $-a - \sum\limits_{s=1}^{k}x_s + \sum\limits_{p=k+1}^{2k+1}x_p$. Отсюда опять же видно, что если положить $a=x_{k+1}$, то слагаемых в обоих суммах станет поровну и получится опять же оценка снизу с помощью неравенства треугольника.

 Профиль  
                  
 
 Re: Минимальное значение суммы
Сообщение08.03.2015, 19:36 
Заслуженный участник
Аватара пользователя


30/01/09
6591
В точке минимума производная минимизируемой функции меняет знак (но в самой точке минимума она не существует). Производная в точке $x\ne x_k$ равна разности количества точек $x_k$ слева и справа от $x$.

 Профиль  
                  
 
 Re: Минимальное значение суммы
Сообщение09.03.2015, 07:02 
Заслуженный участник
Аватара пользователя


23/11/06
4171
Xero в сообщении #987445 писал(а):
благодаря неравенству треугольника получаем:
$|x_1-a|+|x_2-a|\geqslant |x_2-x_1|=x_2-x_1 $, так как последовательно растущая.
Что подходит под теорему даже для любого $a\in [x_1,x_2]$. А медиана находится в этом промежутке.

Должно быть, Вы хотели сказать, что при любом $a\in [x_1,x_2]$ в неравенстве $|x_1-a|+|x_2-a|\geqslant |x_2-x_1|=x_2-x_1 $ нижняя граница достигается, т.е. правая часть $|x_1-a|+|x_2-a| =x_2-x_1 $ не зависит от $a\in [x_1,x_2]$ и меньше уже не бывает.

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

 Профиль  
                  
 
 Re: Минимальное значение суммы
Сообщение09.03.2015, 09:01 


08/09/13
210
Xero в сообщении #987445 писал(а):
Теперь нужно показать, что такая сумма действительно минимальна. Пусть $a$ не из этого интервала, тогда все слагаемые будут минимизированы кроме тех, начиная с которого $a$ не попадает в заданный интервал.

Вот это, по-моему, кривовато сформулировано. Если вы не можете доказать минимальность другой суммы тем же методом, то это не значит, что та сумма не минимальна.
Этого абзаца, кажется, вообще не требуется. Просто пусть нашлась лучшая точка $b$. Но у нас $|x_1-a|+|x_n-a| \le |x_1-b|+|x_n-b|$, и $|x_2-a|+|x_{n-1}-a| \le |x_2-b|+|x_{n-1}-b|$ и так далее... Так и получается, что $\sum \limits_{i=1}^{n} {|x_i-a|} \le \sum \limits_{i=1}^{n} {|x_i-b|}$
Но это недочёты формулировки. В целом добавляю голос за то, что доказательство верное.

Хотя, честно говоря, непонятно отчего весь сырбор с такими разборами сумм и прочим. Неформально можно изложить проще.
Пусть $n = 2k$. Поставим точку $a$ в значение медианы. После сдвигов $a$ влево или вправо, значение будет сохранятся, пока мы не дойдём до точки $x_k$ или $x_{k+1}$. После того, как мы дошли до какой-то из этих точек, у нас уже будет разное количество точек слева и справа, и сдвигая точку $a$ на $\varepsilon$ в ту же сторону мы будем изменять в одну сторону разное количество положительных и отрицательных величин (расстояний до точек), причём изменять всех на одно и то же $\varepsilon$, что, очевидно, даст прирост суммы.
Итого, в медиане локальный минимум, а в две стороны от неё сумма монотонна. Победа.
Для $n=2k+1$ рассуждения точно те же, только нет островка постоянства суммы.

 Профиль  
                  
 
 Re: Минимальное значение суммы
Сообщение09.03.2015, 09:08 
Заслуженный участник


11/05/08
32166
Несколько странное доказательство. Прежде всего, утверждение просто очевидно в силу да, картинки, т.е. выпуклости функции. А после того, как оно очевидно, напрашивается и естественное оформление: если количество узлов слева и справа от точки разное, то в этой точке просто производная не равна нулю (а если сама точка в узле, то одного знака обе односторонние производные, за исключением случая, когда это -- один из двух центральных узлов).

Это если доказательство вообще нуждается в формальном выписывании, в чём я сильно сомневаюсь. По-моему, картинки более чем достаточно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group