题解 P1024 【一元三次方程求解】

其实公式法虽然赖皮但不失为一种好方法
$ $

0.前备知识:

一元三次方程的求解

对于 $$ax^3+bx^2+cx+d=0\ (a\ne0)$$

求解方法:第一步:配方,换元,去三次项系数

于是只需解形如 $$x'^3+px'+q=0$$
的方程。
$ $
$ $
$ $
又有 $$(a+b)^3=a^3+3a^2b+3ab^2+b^3$$ $$\qquad\quad=a^3+b^3+3ab(a+b)$$ 所以令a+b=X,有 $$X^3=a^3+b^3+3abX$$ 即 $$X^3+(-3ab)X+(-a^3-b^3)=0$$ 也就是说,要解 $$x'^3+px'+q=0$$
只需求出符合条件的a、b即可。这样就直接 $X=a+b$ ,解出结果。
$$\begin{cases}-3ab=p\\-a^3-b^3=q\end{cases}$$
即 $$\begin{cases}-27a^3b^3=p^3\\-a^3-b^3=q\end{cases}$$
而这很容易解决,解出 $p^3$ 和 $q^3$ 再开根即可。
(其实解出来符合条件的实数对(a,b)只有一组,三个解为 $$x_1=a+b$$ $$\quad\,\ x_2=\omega a+\overline{\omega}b$$ $$\quad\,\ x_3=\overline{ω}a+\omega b$$ 其中 $\omega$ 为三次单位根 $\frac{1+\sqrt{3}i}{2}$ , $\overline{\omega}$ 为三次单位根 $\frac{1-\sqrt{3}i}{2}$ )

$ $

1.由此可得出著名的卡尔丹公式:

对于 $ax^3+bx^2+cx+d=0(a≠0)$ , $$p=\frac{3ac-b^2}{3a^2},q=\frac{27a^2d-9abc+2b^3}{27a^3}$$
$$x_1=\sqrt[3]{-\frac{q}{2}\!+\!\sqrt{\left(\frac{q}{2}\right)^2\!\!+\!\left(\frac{p}{2}\right)^3}}\!\!+\sqrt[3]{-\frac{q}{2}\!-\!\sqrt{\left(\frac{q}{2}\right)^2\!\!+\!\left(\frac{p}{2}\right)^3}}\!-\frac{b}{3a}$$ $$\quad\ x_2=\omega\sqrt[3]{-\frac{q}{2}\!+\!\sqrt{\left(\frac{q}{2}\right)^2\!\!+\!\left(\frac{p}{2}\right)^3}}\!\!+\!\overline{\omega}\sqrt[3]{-\frac{q}{2}\!-\!\sqrt{\left(\frac{q}{2}\right)^2\!\!+\!\left(\frac{p}{2}\right)^3}}\!-\frac{b}{3a}$$ $$\quad\ x_3=\overline{\omega}\sqrt[3]{-\frac{q}{2}\!+\!\sqrt{\left(\frac{q}{2}\right)^2\!\!+\!\left(\frac{p}{2}\right)^3}}\!\!+\!\omega\sqrt[3]{-\frac{q}{2}\!-\!\sqrt{\left(\frac{q}{2}\right)^2\!\!+\!\left(\frac{p}{2}\right)^3}}\!-\frac{b}{3a}$$ 其中出现复数,把实部和虚部分别用一个double存储并分别处理即可。听说有种神奇的东西叫complex?
实际实现时,把 $\dfrac{q}{2}$ 和 $\dfrac{p}{3}$ 以及 $\sqrt{\left(\dfrac{q}{2}\right)^2\!\!+\!\left(\dfrac{p}{2}\right)^3}$ 作为一个整体存储。

$ $

2.代码:

略。(让 $\mathtt{dalao}$ 帮忙实现一下吧。)

$ $

3.性能分析:

1.比盛金公式慢,但精度好(盛金公式要用到误差很大的sincos
2.和二分相当且速度受数据范围、精度要求影响小

Update:2019/8/7,更新了一些排版上的bug,同时纠正了一个错误。手打公式不免可能出一些错误,望管理大大包容~
另吐槽: $\LaTeX$ 里的 $\omega$ 好丑

发表于 2019-03-10 22:51:17 in 题解