Аналитически:
- Общая формула Кардано для кубического есть (для приведённого к виду $t^3+pt+q=0$): корни выражаются через кубические корни
$$t=u+v,u^3,v^3=-\frac{q}{2}\pm \sqrt{{\left(\frac{q}{2}\right)}^2+{\left(\frac{p}{3}\right)}^3}.$$ Но при трёх действительных корнях («casus irreducibilis») подкоренные выражения отрицательны и появляются комплексные промежуточные величины, поэтому на практике удобнее тригонометрическая форма.
- Для уравнения $x^3-3x+1=0$ имеем $p=-3,q=1$. Пусть
$$r=2\sqrt{-\frac{p}{3}}=2,\varphi =\frac{1}{3}\arccos \left(\frac{3q}{2p}\sqrt{-\frac{3}{p}}\right)=\frac{2\pi }{9}.$$ Тогда три действительных корня
$$x_k=r\cos (\varphi -\frac{2\pi k}{3}),k=0,1,2,$$ т.е.
$$x_1=2\cos \frac{2\pi }{9},x_2=2\cos \frac{4\pi }{9},x_3=2\cos \frac{8\pi }{9}$$ (приблизительно $x\approx 1.53209,0.34730,-1.87939$). Это точное и стабильное аналитическое выражение для данного случая.
Численные методы (когда использовать и достоинства/недостатки):
- Метод деления пополам (bisection): гарантированно сходится к корню, монотонно уменьшая интервал; скорость линейная. Использовать для надёжного обнаружения и брукетирования корней (когда известен знак на концах интервала).
- Ньютон (Newton–Raphson): квадратичная сходимость близко к ненулевому простому корню; требуется вычисление $f^{\prime }(x)=3x^2-3$ и хорошее начальное приближение. Уязвим к сходимости к другому корню или расползанию, если начальное приближение далеко или $f^{\prime }$ близко к нулю.
- Секант: не требует производной, скорость суперлинейная (~1.618), полезен если производная неудобна или вычислительно дорога.
- Brent (комбинированный метод: bisection + secant + inverse quadratic interpolation): надёжен и быстрый на практике — предпочтителен, если нужно автоматически и стабильно найти корень с брекетом.
- Методы для всех корней: метод Дженкинса–Траба или численное нахождение собственных значений компаньон-матрицы (QR) — хороши, если нужно все корни полинома; Durand–Kerner/Weierstrass для одновременного поиска всех корней.
- Для комплексных корней или вырожденных (многократных) ситуаций: Muller's метод, модифицированный Newton для кратных корней, или специальные алгоритмы с регуляризацией.
Рекомендация для данного уравнения:
- Получить точные выражения тригонометрически (см. выше) или — если нужны десятичные значения — быстро: брукетирование знаками на отрезках $(-2,-1),(0,1),(1,2)$ + Brent или сначала bisection, затем Newton для «полировки» (полиному вычисление производной тривиально).
Критерии остановки (практические):
- По разности приближений: $|x_{n+1}-x_n|<{\epsilon }_x$.
- По невязке: $|f(x_n)|<{\epsilon }_f$.
- Комбинированный критерий: одновременно $|x_{n+1}-x_n|<{\epsilon }_x$ или $|f(x_n)|<{\epsilon }_f$ и число итераций < N_max.
- Для полинома полезно контролировать относительную погрешность: $|x_{n+1}-x_n|<{\epsilon }_{\text{rel}}|x_{n+1}|$.
- Практические значения для двойной точности: ${\epsilon }_x\sim 10^{-12}÷10^{-14}$, ${\epsilon }_f\sim 10^{-12}÷10^{-14}$; или stricter до порядка машинного эпсилона $\sim 10^{-16}$ при необходимости. Обязательно устанавливать предел по итерациям (например $N_{\max }=50$–100) и проверять, не застряла ли итерация в точке с малым производным.
Коротко: для данного уравнения — аналитическое трёхкосинусное решение предпочтительно; для численных задач — брекетирование + Brent (или bisection→Newton) как универсальная и быстрая стратегия; использовать сочетание критерия по $|\Delta x|$ и $|f(x)|$ и лимит итераций.