ホーム > libalgo

三次方程式

概要

三次方程式 $ax^3 + bx^2 + cx + d = 0$ を二分法 (bisection.cc) と二次方程式の解の公式 (quadratic-equation.cc) を使って求めます.

三次方程式は両端が正負の無限大に発散するので,中間値の定理から少なくとも 1 つの実数解を持ちます.それを二分法によって求め $x_0$ とおくと,もとの方程式は $(x - x_0) (a’x^2 + b’x + c’) = 0$ と因数分解できます.展開して係数比較すると $a’, b’, c’$ は求まります.$a’x^2 + b’x + c’ = 0$ の解が残りの解です.

使い方

重解はまとめない.

実装

//@require bisection.cc
//@require quadratic-equation.cc
std::vector<ld> cubic_equation(ld a, ld b, ld c, ld d) {
    if (std::abs(a) < eps) return quadratic_equation(b, c, d);
    if (a < 0) a = -a, b = -b, c = -c, d = -d;
    static const ld INF = 1e9;
    ld x0 =
        bisection_method(-INF, INF, [&](ld x) { return a * x * x * x + b * x * x + c * x + d; });
    ld aa = 1, bb = b / a + x0, cc = c / a + bb * x0;
    auto res = quadratic_equation(aa, bb, cc);
    res.push_back(x0);
    std::sort(res.begin(), res.end());
    return res;
}

検証

AOJ 2220 (Submission)