НГУ

Форумы НГУ
Текущее время: Вс сен 22, 2019 11:13 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Вт авг 28, 2007 3:17 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт авг 28, 2007 3:12 pm
Сообщения: 5
Есть ли численный алгоритм нахождения всех корней нелинейного уравнения?


Последний раз редактировалось daf Ср авг 29, 2007 12:57 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 28, 2007 7:49 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Вы имеете в виду корни многочленов от одной переменной? Будем считать, что их коэффициенты - рациональные числа.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср авг 29, 2007 12:53 pm 
Не в сети
Редкий гость

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср авг 29, 2007 1:17 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
daf писал(а):
Я имею ввиду нахождение приближенного решения уравнения вида F(x) = 0( это необязательно многочлен) на заданном промежутке.


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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт авг 30, 2007 4:14 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт авг 28, 2007 3:12 pm
Сообщения: 5
Можно считать, что на заданном отрезке функция непрерывна, дифференцируема и имеет конечное количество решений.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт авг 31, 2007 1:23 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
daf писал(а):
Можно считать, что на заданном отрезке функция непрерывна, дифференцируема и имеет конечное количество решений.


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

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

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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт авг 31, 2007 3:49 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт авг 28, 2007 3:12 pm
Сообщения: 5
Может так: найти все решения описанного ранее уравнения за исключением тех, которые отличаются хотя бы от одного из найденных не более чем на дельта. Для практических целей это вполне подойдет. Но и в этом случае ничего толкового на ум не приходит.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт авг 31, 2007 4:26 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
daf писал(а):
Для практических целей это вполне подойдет.


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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 01, 2007 4:44 pm 
Не в сети
Плодовитый автор

Зарегистрирован: Сб мар 18, 2006 10:52 pm
Сообщения: 742
Откуда: Алексей Салмин
спросите у Conwor, он помницо песал какой-то мегарешатель по какому-то мегаалгоритму. Не по Ньютону, но почему то вроде того.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 01, 2007 7:35 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
daf писал(а):
Может так: найти все решения описанного ранее уравнения за исключением тех, которые отличаются хотя бы от одного из найденных не более чем на дельта.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 5:14 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт авг 28, 2007 3:12 pm
Сообщения: 5
Наложить какие - то дополнительные условия на функцию (к примеру ограниченность производной) достаточно сложно, поскольку реально имею дело с достаточно большой системой уравнений, большинство уравнений сильно отличаются друг от друга. По-видимому, предется ограничиться нахождением точек, где функция достаточно близко подходит к абсциссе (буду надеяться, что там по божьей воли есть решение). Другого варианта мне не видится.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Ср сен 05, 2007 11:14 am 
Не в сети
Постоянный посетитель

Зарегистрирован: Пн окт 16, 2006 1:20 pm
Сообщения: 195
daf писал(а):
Есть ли численный алгоритм нахождения всех корней нелинейного уравнения?

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Ср сен 05, 2007 1:35 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
BSK писал(а):
Еще вопрос. Как узнать, обращается ли в ноль на заданном отрезке заданная непрерывная функция?

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср сен 05, 2007 3:49 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Как мне кажется, прежде всего следует уточнить возможные способы задания функции, нули которой необходимо найти.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пт сен 07, 2007 4:21 pm 
Не в сети
Редкий гость

Зарегистрирован: Вс авг 05, 2007 3:59 pm
Сообщения: 4
daf писал(а):
Есть ли численный алгоритм нахождения всех корней нелинейного уравнения?

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


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

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB