2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 15:45 


20/08/14
2167
Россия, Москва
Poika
Честно говоря не помню где про это читал, кажется это довольно известный результат, надеюсь товарищи подскажут хорошую книгу.

-- 27.03.2017, 15:58 --

Для начала можно например здесь посмотреть вывод "метода золотого сечения".

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 19:16 


26/03/13
31
Прочитал про золотое сечение, посидел подумал, и кажется, что действительно деля отрезок на 2 неравные части в соотношении золотого сечения, набыстрейшим образом найдем участок содержащий разрыв. Но как это обосновать? Возможно ли это доказать математически? Я уверен, что это уже доказали, но нигде не могу найти доказательства.
Сейчас еще нашел теорию итераций Ньютона, кажется она тоже решает моюзадачу, но пока не разобрался как она работает.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 19:44 


20/08/14
2167
Россия, Москва
Poika в сообщении #1204037 писал(а):
набыстрейшим образом

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

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

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 19:53 


26/03/13
31
Да, я тут подумал, и пришел к выводу, что делить пополам лучше чем золотым сечением.
Надо еще подумать про метод итераций Ньютона.
К какому бы решению я бы не пришел, очень хотелоось бы иметь его математичекой доказательство...

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 20:34 


20/08/14
2167
Россия, Москва
Да вроде не так уж это сложно.
Пойдите с конца, с последнего цикла проверки кусочков. Предположим рассматриваем разбиение на одинаковые кусочки числом $n$. Тогда в худшем случае надо провести $n-1$ измерений для каждого шага разбиения. В лучшем случае 1, в среднем (наиболе вероятно) $n/2$. Задайтесь минимальным размером кусочка (=1). Тогда на последнем цикле разбиений длина всех кусочков будет $n$. На предпоследнем цикле размер будет уже $n^2$, а общее количество проверок $2(n-1)$ (в худшем случае). Ещё на цикл ранее размер уже $n^3$, количество проверок $3(n-1)$. Зависимость легко прослеживается. Ну а всего циклов разбиений будет $L \le n^k$, $k$ - количество циклов разбиений. Отсюда $k=\log_n L$, а количество проверок $k(n-1)=(n-1)\log_n L$. Что при фиксированном $L$ как раз и приводит к формуле Legioner93. Правда если $L$ не является точной степенью $n$, то возможны варианты разбиений, но в любом случае $n=2$ останется оптимальным.
Для разбиений на неравные кусочки доказательство будет примерно аналогичным, только задействуются ещё и вероятности нахождения обрыва в каждой из частей разбиения. Ну и результат получится чуть другим (если я не ошибся, то как раз разбиение на два кусочка в пропорции золотого сечения будет оптимальным).
PS. Это не полноценное доказательство, в паре мест я походу "срезал путь", но как основа пойдёт.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение28.03.2017, 23:36 


26/03/13
31
Спасибо большое за помощь! Я понял Ваше доказательство.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу Пред.  1, 2

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



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

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


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

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