Метод касат-ных

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Дрюль
Сообщения: 18
Зарегистрирован: 15 окт 2004, 15:14

Метод касат-ных

Сообщение Дрюль » 18 янв 2005, 17:24

Запрограммировал метод Ньютона. Возник вопрос: есть уравнение; как определить сколько у него корней? Как можно вычислять начальные приближения? (у меня все корни уточняются от единицы).

Absurd
Сообщения: 1213
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Сообщение Absurd » 18 янв 2005, 18:21

Количество корней равно степени уравнения.
Т.е у уравнений первой степени - 1 корень, у уравнений второй степени - два корня итд.
2B OR NOT(2B) = FF

Дрюль
Сообщения: 18
Зарегистрирован: 15 окт 2004, 15:14

Сообщение Дрюль » 18 янв 2005, 18:33

Есть например уравнение ln(sin x)^cos x + sinh x = 0.
У него cos(x) корней?

evgeny_d
Сообщения: 62
Зарегистрирован: 23 мар 2004, 08:31

Сообщение evgeny_d » 19 янв 2005, 09:20

Дрюль,
речь шла о полиномах a+ax+ax^2+...+ax^n - n корней в комплексных числах (енто называется полнотой поля С, если я все правильно помню)

А вообще метод Ньютона - это метод локального поиска, как ни крути... и все корни он даже у полинома найти не сможет.
Указать методу, откуда искать - дело исследователя.

Сколько корней имеет произвольное уравнение f(x)=0 ИМХО в общем случае сказать невозможно (а для метода Ньютона, по-моему, достаточно только дифференцируемости f(x)).

Eugie
Сообщения: 707
Зарегистрирован: 17 фев 2004, 23:59
Откуда: SPb

Сообщение Eugie » 19 янв 2005, 19:21

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

Аватара пользователя
AiK
Сообщения: 2271
Зарегистрирован: 13 фев 2004, 18:14
Откуда: СПб
Контактная информация:

Сообщение AiK » 19 янв 2005, 19:31

Eugie, на сколько я помню, классики рекомендуют комбинировать метод Ньютона с другими, более медленно сходящимися методами, например с методом бисекции (деления отрезка пополам). Однако ж даже для этого метода необходимо делать предварительные предположения о корнях.
Даже самый дурацкий замысел можно воплотить мастерски

Eugie
Сообщения: 707
Зарегистрирован: 17 фев 2004, 23:59
Откуда: SPb

Сообщение Eugie » 19 янв 2005, 19:46

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

Аватара пользователя
AiK
Сообщения: 2271
Зарегистрирован: 13 фев 2004, 18:14
Откуда: СПб
Контактная информация:

Сообщение AiK » 19 янв 2005, 20:03

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

Eugie
Сообщения: 707
Зарегистрирован: 17 фев 2004, 23:59
Откуда: SPb

Сообщение Eugie » 19 янв 2005, 20:21

если у тебя задан интервал, то на этом интервале нахождение всех корней гарантировано, скажем, методом хорд. Разумеется, если у тебя шаг меньше расстояния между соседними корнями
То-то и оно, что 'если'... И найдешь ты один корень на интервале, а их может быть несколько.
Короче, нет универсальных методов, увы, и особенно это касается численных методов. Поэтому и приходится постоянно делать оговорки о точности.

evgeny_d
Сообщения: 62
Зарегистрирован: 23 мар 2004, 08:31

Сообщение evgeny_d » 20 янв 2005, 09:21

Вообще-то за примером далеко ходить не надо.
cos(n*x) на интервале [0,PI]
При n=1 - 1 корень
При n=2 - 2 корня
и т.п.

Если берем некоторое покрытые (сетку) с интервалом e, то всегда найдется такое n, что в одной "ячейке" сетки окажется более одного корня... да и вообще сколько угодно корней.

Мультистарт из равномерно раскиданных узлов имеет смысл делать только в случае, если функция удовлетворяет условию Липшица с некоторой константой K, но это, как говорится, уже совсем другая история %)

Ответить