Какой простой способ найти реальные корни (кубического) полинома?

Question

это кажется мне очевидным вопросом, но я нигде не смог найти его на SO. У меня есть кубический полином, и мне нужно найти реальные корни функции. Что такое THE способ сделать это?

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

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

Я кодирую на C, поэтому нет import magic_poly_solver, пожалуйста.

Бонусный вопрос: как найти только корни внутри заданного интервала?

Answer 1

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

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

Одно слово предостережения:если дискриминант близок к нулю, будет численно кратный действительный корень, и метод Ньютона потерпит неудачу.Более того, поскольку в окрестности корня многочлен имеет вид (x - x0) ^ 2, вы потеряете половину значащих цифр (поскольку P (x) будет

Если вы хотите найти корни в данном интервале, проверьте Теорема Штурма .

Более общим (сложным) алгоритмом для решения полиномиального обобщенного алгоритма является алгоритм Дженкинса-Трауба .Это явно излишне, но хорошо работает с кубиками.Как правило, вы используете стороннюю реализацию.

Поскольку вы делаете C, использование GSL , безусловно, является вашей лучшей ставкой.

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

Answer 2

См. Решение квартик и кубик для графики . Автор D Herbison-Evans, опубликовано в Graphics Gems V .

Answer 3

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

К сожалению, невозможно решить, какие корни вы получите при итерации, хотя это зависит от начального значения.

Также см. здесь .

Answer 4

/*******************************************************************************
 * FindCubicRoots solves:
 *      coeff[3] * x^3 + coeff[2] * x^2 + coeff[1] * x + coeff[0] = 0
 *  returns:
 *      3 - 3 real roots
 *      1 - 1 real root (2 complex conjugate)
 *******************************************************************************/

int FindCubicRoots(const FLOAT coeff[4], FLOAT x[3]);

http://www.realitypixels.com/turk/opensource/index.html#CubicRoots