Оценка сложности дихотомии

[temp]

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

[незваный гость]

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

[temp]

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

[PAV]

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

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

[temp]

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

[PAV]

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

[незваный гость]

Поправьте меня, но дихотомия обычно применяется для монотонной функции.

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

[maxal]

незванный гость писал(а):

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

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

[незваный гость]

maxal писал(а):

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

Да.

[temp]

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

[PAV]

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

[temp]

Цитата:

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

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

[Werwolf]

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

[maxal]

Werwolf писал(а):

А если дихотомию использовать для того, есть ли корень

Это как?

[temp]

maxal писал(а):

Werwolf писал(а):

А если дихотомию использовать для того, есть ли корень

Это как?

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