2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Оценка сложности дихотомии
Сообщение19.06.2006, 11:05 
Насколько я понял, сложность в худшем случае нахождения корней уравнения на отрезке методом деления пополам, будет экспоненциальная, а преподаватель мне упорно твердит, что не может быть. Кто не прав?

 
 
 
 
Сообщение19.06.2006, 17:08 
Аватара пользователя
:evil:
Не правы Вы. По "определению", сложность -- количество шагов, которое нужно сделать, чтобы достичь результат (в Вашем случае -- заказанную точность). Оцените, за сколько итераций Вы достигаете $\varepsilon$.

 
 
 
 
Сообщение20.06.2006, 12:44 
В том случае, если, например есть два корня, лежащие в промежутке [i,i+\varepsilon], то 2^n, то есть заданная точность не позволяет определить эти корни и придется проверять все, а это - сумма геометрической прогресси. :?:

 
 
 
 
Сообщение20.06.2006, 14:12 
Аватара пользователя
Если предполагать, что корней может быть любое количество и требуется найти их все, то, конечно, надо проверять вообще все отрезки, на которые производится деление. Тут, собственно, делить пополам ни к чему.

Задача состоит в том, чтобы локализовать некоторый один корень.

 
 
 
 
Сообщение20.06.2006, 15:58 
В том то и смысл, что, если один корень, то все понятно. К примеру, дано задание - методом дихотомии найти хотя бы один корень уравнения на отрезке [a,b] с заданной точностью. В случае, когда корней нет или их нельзя найти с заданной точностью, и получается эксаоненциальная сложность. Я именно это и имел в виду.

 
 
 
 
Сообщение20.06.2006, 16:17 
Аватара пользователя
Мне всегда казалось, что когда мы действуем методом деления пополам, то изначально дан отрезок, в концах которого значения разных знаков, и требуется локализовать один корень. Разве не так?

 
 
 
 
Сообщение20.06.2006, 16:52 
Аватара пользователя
:evil:
Поправьте меня, но дихотомия обычно применяется для монотонной функции.

Для немонотонной функции она бессмысленна (с таким же успехом можно идти линейно по интервалу; да и кстати тоже ничего не узнать).

 
 
 
 
Сообщение20.06.2006, 21:56 
Аватара пользователя
незванный гость писал(а):
:evil:
Поправьте меня, но дихотомия обычно применяется для монотонной функции.

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

 
 
 
 
Сообщение20.06.2006, 22:21 
Аватара пользователя
:evil:
maxal писал(а):
Ее можно применять, например, для отыскания корня функции, принимающей на концах интервала значения разных знаков.

Да.

 
 
 
 
Сообщение21.06.2006, 11:31 
Именно это я и доказывал, что если корней на отрезке нет или невозможно отыскать с заданной точностью, то метод дихотомии применять не стоит, проще последовательно проверить все интервалы, потому что сложность дихотомии в этом случае экспоненциальная. Но мне упорно твердили, что не может быть. Я понимаю, что вопрос изначально глупый, но я уже подумал, что может это я - дебил и чего то совсем недопонимаю. Поэтому и решил посовещаться со "старшими товарищами" :) .

 
 
 
 
Сообщение21.06.2006, 11:45 
Аватара пользователя
Есть сильное подозрение, что вы с преподавателем говорите немного о разных вещах и не до конца понимаете друг друга. Скорее всего, он по умолчанию считает, что (а) значения функции на концах исходного интервала разных знаков; (б) задача состоит в локализации одного корня (который в силу предположения (а) заведомо существует, функция разумеется предполагается непрерывной). В противном случае метод деления пополам просто не имеет смысла.

 
 
 
 
Сообщение21.06.2006, 14:56 
Цитата:
Есть сильное подозрение, что вы с преподавателем говорите немного о разных вещах и не до конца понимаете друг друга. Скорее всего, он по умолчанию считает, что (а) значения функции на концах исходного интервала разных знаков; (б) задача состоит в локализации одного корня (который в силу предположения (а) заведомо существует, функция разумеется предполагается непрерывной). В противном случае метод деления пополам просто не имеет смысла.

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

 
 
 
 
Сообщение21.06.2006, 15:13 
Тогда достаточно тупо в таком случае применять дихотомию, так как суть ее в том, чтобы уменшить задачу в 2 раза и прийти к упрощенному варианту. Поэтому получается логарифмическая сложность. А если дихотомию использовать для того, есть ли корень, то сложность получается экспоненциальная, притом алгоритм сам по себе неэфективен, то есть корень найдем или не найдем, как уж повезет.

 
 
 
 
Сообщение21.06.2006, 15:27 
Аватара пользователя
Werwolf писал(а):
А если дихотомию использовать для того, есть ли корень

Это как?

 
 
 
 
Сообщение21.06.2006, 15:54 
maxal писал(а):
Werwolf писал(а):
А если дихотомию использовать для того, есть ли корень

Это как?

Делить отрезки до значения \varepsilon и проверять значения функции на концах каждого. Убиться можно. :)

 
 
 [ Сообщений: 18 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group