НГУ
http://forum.nsu.ru/

Численное находение всех корней уравнения
http://forum.nsu.ru/viewtopic.php?f=24&t=17462
Страница 1 из 2

Автор:  daf [ Вт авг 28, 2007 3:17 pm ]
Заголовок сообщения:  Численное находение всех корней уравнения

Есть ли численный алгоритм нахождения всех корней нелинейного уравнения?

Автор:  Pavel E. Alaev [ Вт авг 28, 2007 7:49 pm ]
Заголовок сообщения: 

Вы имеете в виду корни многочленов от одной переменной? Будем считать, что их коэффициенты - рациональные числа.

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

Автор:  daf [ Ср авг 29, 2007 12:53 pm ]
Заголовок сообщения: 

Я имею ввиду нахождение приближенного решения уравнения вида F(x) = 0( это необязательно многочлен) на задонном промежутке. К примеру, метод Ньютона позволяет найти по крайней мере одно решение(если оно существует). Но требуется нахождение всех! решений на отрезке.

Автор:  Коба [ Ср авг 29, 2007 1:17 pm ]
Заголовок сообщения: 

daf писал(а):
Я имею ввиду нахождение приближенного решения уравнения вида F(x) = 0( это необязательно многочлен) на заданном промежутке.


А F из какого класса? Если, например, F(x) = sin(1/x) или F --- функция Дирихле, то для неё тоже надо все корни искать?

Автор:  daf [ Чт авг 30, 2007 4:14 pm ]
Заголовок сообщения: 

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

Автор:  Коба [ Пт авг 31, 2007 1:23 am ]
Заголовок сообщения: 

daf писал(а):
Можно считать, что на заданном отрезке функция непрерывна, дифференцируема и имеет конечное количество решений.


Ех... Боюсь, что эта задача алгоритмически неразрешима.

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

P. S. Вообще, как я понимаю, главная сложность тут --- сформулировать корректную постановку задачи.

Автор:  daf [ Пт авг 31, 2007 3:49 pm ]
Заголовок сообщения: 

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

Автор:  Коба [ Пт авг 31, 2007 4:26 pm ]
Заголовок сообщения: 

daf писал(а):
Для практических целей это вполне подойдет.


Для практических целей неплохо бы понять, какими вычислительными ресурсами мы располагаем. А то в чём проблема? Разбить исходный отрезок на интервалы длины дельта, в каждом посчитать значение F и если в каком-то интервале вычисленное значение по модулю оказалось меньше некоторого допустимого эпсилон, выдать середину этого интервала в качестве решения :)

Автор:  salmin [ Сб сен 01, 2007 4:44 pm ]
Заголовок сообщения: 

спросите у Conwor, он помницо песал какой-то мегарешатель по какому-то мегаалгоритму. Не по Ньютону, но почему то вроде того.

Автор:  Pavel E. Alaev [ Сб сен 01, 2007 7:35 pm ]
Заголовок сообщения: 

daf писал(а):
Может так: найти все решения описанного ранее уравнения за исключением тех, которые отличаются хотя бы от одного из найденных не более чем на дельта.

Мне кажется, проблема в том, что Вы никак не сможете отличить корень функции F от точки, в которой она очень близко подходит к прямой y=0, но не доходит до неё, то есть "почти касается". Если функция F произвольная (с указанными выше условиями), то я думаю, что задача нерешаема в разумной постановке.

То, что для полиномов такой способ есть - довольно удивительный факт.

Если наложить ещё какие-то условия (например, ограниченность производной), то можно указать некоторый алгоритм, который в случае, когда корней нет, сможет это определить через конечное число шагов. Для этого нужно последовательно разбивать отрезок на наборы всё более мелких кусочков. Чтобы рассуждения об алгоритме были корректными, нужно ещё предполагать, например, что значения самой функции в рациональных точках тоже вычисляются с помощью некоторого алгоритма. Может быть, если наложить ещё ряд условий, можно будет решить и общую задачу.

Автор:  daf [ Пн сен 03, 2007 5:14 pm ]
Заголовок сообщения: 

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

Автор:  BSK [ Ср сен 05, 2007 11:14 am ]
Заголовок сообщения:  Re: Численное находение всех корней уравнения

daf писал(а):
Есть ли численный алгоритм нахождения всех корней нелинейного уравнения?

Еще вопрос. Как узнать, обращается ли в ноль на заданном отрезке заданная непрерывная функция?

Автор:  Pavel E. Alaev [ Ср сен 05, 2007 1:35 pm ]
Заголовок сообщения:  Re: Численное находение всех корней уравнения

BSK писал(а):
Еще вопрос. Как узнать, обращается ли в ноль на заданном отрезке заданная непрерывная функция?

Тут та же проблема. Мне кажется, её можно решать, только используя какие-то дополнительные сведения о функции.

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

Автор:  Коба [ Ср сен 05, 2007 3:49 pm ]
Заголовок сообщения: 

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

Автор:  abc_qmost [ Пт сен 07, 2007 4:21 pm ]
Заголовок сообщения:  Re: Численное находение всех корней уравнения

daf писал(а):
Есть ли численный алгоритм нахождения всех корней нелинейного уравнения?

У Вас конкретное уравнение? Если нет, то это чисто схоластический вопрос, с которым необходимо обращаться к философам.

Страница 1 из 2 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/