Эффективный алгоритм

← →
ArtemESC © (2005-10-17 20:37) [0]

Доброго времени суток...
Не могу надыбать эффективный алгоритм нахождения корней
уравнения, представимого в виде многочлена...
Из справочника мат.анализа нашел только Xn+1 = Xn - f (x)/f"(x) -
но похоже это не то. Может кто знает?

← →
fedotawa (2005-10-17 20:43) [1]

Численными методами. См. гуугле, а также книги про лошадей с нестандартным количеством ног.

← →
Lamer@fools.ua © (2005-10-17 20:44) [2]

>Из справочника мат.анализа нашел только Xn+1 = Xn - f (x)/f"(x)

Это метод Ньютона, если не ошибаюсь. Если производную f"(x) заменить приблизительным значением: (f(Xn) - f(Xn-1)) / (Xn - Xn-1), то получится метод секущих-хорд, если опять же не ошибаюсь.

← →
имя (2005-10-17 20:48) [3]

Удалено модератором

← →
Думкин © (2005-10-18 05:36) [4]

> ArtemESC © (17.10.05 20:37)

Почему не то? Там есть условия при которых такой итерационный способ приведет к ответу. Вы их читали?
А так конечно - найдите корень x^2+1=0.

← →
ArtemESC © (2005-10-18 15:57) [5]

>>Думкин
Дело в том что корней может быть больше одного,
а значит после нахождения первого корня нужно
будет делить многочлены - серъезная потеря точности,
хотя даже и не факт что найденное число является корнем
(пример: x^2+1=0). Может есть методы
проверки, имеет ли данное уравнение решение?

← →
pasha_golub © (2005-10-18 16:06) [6]

ArtemESC © (18.10.05 15:57) [5]

> Дело в том что корней может быть больше одного,

Корни надо отделить. Найти такие интервалы на которых будет один и только один корень.

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

1. [a;b] є R
2. f(a) * f(b) < 0
3. f - диференциируема и строго монотонна

← →
ArtemESC © (2005-10-18 20:18) [7]

А нет ли чего по проще?

← →
MBo © (2005-10-19 06:18) [8]

>А нет ли чего по проще?
Да, конечно.
Найти собственные значения "companion" матрицы, для которой данный полином является характеристическим ;)

← →
Думкин © (2005-10-19 06:53) [9]

> MBo © (19.10.05 06:18) [8]

Издеваешься?

> ArtemESC © (18.10.05 15:57) [5]

Есть круги Гершгорена. Для отделения. Хотя всегда при чесленном имеется одно - точнсть вычислений. А вот как вам такое уравнение:
(X- 1.0000000000000001)*(X+ 1.0000000000000001) = 0
Отделите?
Численное решение(любое) - это метод тыка. Суть только одна - тык тот должен быть какм ожно более удачным.

> pasha_golub © (18.10.05 16:06) [6]

Достаточные <> необходимые. И в достаточных другой признак применяют - с использованием той самой ненужной второй производной.

← →
Думкин © (2005-10-19 06:55) [10]

(X- 1.0000000000000000)*(X+ 1.0000000000000002) = 0

Имелось в виду.

← →
Думкин © (2005-10-19 06:56) [11]

Тьфу.
(X + 1.0000000000000000)*(X+ 1.0000000000000002) = 0
Так разумеется. Совсем тупеешь. :(

>Думкин © (19.10.05 06:53) [9]
> MBo © (19.10.05 06:18) [8]
>Издеваешься?
Нет. Хлопец начнет корни полинома пятнадцатой степени искать ньютоноподобными методами - и все, приплыли из-за потери точности, даже при уточнении (polishing) корней. (Хотя сам я 9-ю степень вполне успешно решал, правда, что немаловажно - для "неплохих" коэфициентов полинома )

А для Eigenvalue problem нумерикалистами наработаны изощренные методы.

Эффективный алгоритм Найти похожие ветки