Root Finding — 求根アルゴリズム

概要

calx の求根モジュールは 3 つのカテゴリに分かれる。

1D 求根 — $f(x) = 0$ を満たす実数 $x$ を求める。二分法から Brent 法まで 10+ 種類
多項式求根 — $p(x) = 0$ の全根 (複素根含む) を求める。低次は公式解、高次は反復法
N-D 求根 — $\mathbf{F}(\mathbf{x}) = \mathbf{0}$ を満たすベクトル $\mathbf{x}$ を求める

ビルド

// 全モジュールまとめてインクルード
#include <math/roots/root_finding.hpp>

// 個別インクルードも可能
#include <math/roots/root_finding_1d.hpp>   // 1D 求根
#include <math/roots/root_finding_nd.hpp>   // N-D 求根
#include <math/roots/polynomial_roots.hpp>  // 多項式求根

ヘッダオンリー。リンクするライブラリは不要。

結果型

1D 求根関数は RootFindingResult<T> を返す。

メンバ	説明
`value`	根の近似値
`converged`	収束したか
`iterations`	反復回数
`error_estimate`	誤差の推定値

収束判定は ConvergenceCriteria<T> で制御する (許容誤差、最大反復回数)。

1D: 囲い込み法 (Bracketing)

区間 $[a, b]$ 内で $f(a)$ と $f(b)$ が異符号であることを前提とし、確実に収束する。

関数	収束次数	説明
`bisection(f, a, b)`	線形	二分法。最も単純で確実
`false_position(f, a, b)`	超線形	偽位置法 (Regula Falsi)
`ridders_method(f, a, b)`	$\sqrt{2}$	Ridders 法。二分法より速い
`brent_method(f, a, b)`	超線形	Brent 法。実用上の最良選択
`toms748(f, a, b)`	$\approx 1.84$	TOMS Algorithm 748。Brent の改良版

1D: 非区間法 (Non-bracketing)

初期値 $x_0$ (と任意で導関数) から反復する。収束は速いが初期値依存。

関数	収束次数	説明
`newton_raphson(f, f', x0)`	2次	Newton-Raphson 法。導関数が必要
`secant_method(f, x0, x1)`	$\approx 1.618$	割線法。導関数不要

1D: 高次収束法

関数	収束次数	説明
`halley_method(f, f', f'', x0)`	3次	Halley 法。2階導関数が必要
`schroder_method(f, f', f'', x0)`	3次	Schröder 法。重根に強い
`king_method(f, f', x0)`	4次	King 法。1階導関数のみで4次収束
`popovski_method(f, f', x0)`	4次	Popovski 法

多項式求根

全関数は std::vector<Complex<T>> を返す (実根は虚部 = 0)。根はベクトル空間の元ではなく単なる複素数の集合なので、 calx::Vector (線形代数用) ではなく STL の std::vector を使う。

低次 (公式解)

関数	説明
`solveLinear(p)`	1次: $ax + b = 0$
`solveQuadratic(p)`	2次: 判別式による分岐 (桁落ち対策済み)
`solveCubic(p)`	3次: Cardano の公式 + 三角関数法
`solveQuartic(p)`	4次: Ferrari の方法

高次 (反復法)

関数	説明
`jenkinsTraub(p)`	Jenkins-Traub 法。数値的に最も安定
`laguerre(p)`	Laguerre 法。3次収束
`durandKernerAberth(p)`	Durand-Kerner-Aberth 法。全根同時反復
`bairstow(p)`	Bairstow 法。実数演算のみで複素根を求める

統合ディスパッチャ

auto roots = findAllRoots(p);  // 次数に応じて最適なアルゴリズムを自動選択

findAllRoots は次数に応じて自動的にアルゴリズムを選択する:

1〜4 次: 公式解 (solveLinear / Quadratic / Cubic / Quartic)
5 次以上: Jenkins-Traub 法

N-D: 多変数求根

$\mathbf{F}: \mathbb{R}^n \to \mathbb{R}^n$ の零点を求める。

関数	説明
`newton_nd(F, J, x0)`	多変数 Newton 法。Jacobian が必要
`broyden(F, x0)`	Broyden 法。Jacobian 不要 (準 Newton 法)

使用例

#include <math/roots/root_finding.hpp>
#include <iostream>
using namespace calx;

int main() {
    // 1D: f(x) = x^2 - 2 の根を Brent 法で求める
    auto result = brent_method(
        [](double x) { return x * x - 2.0; },
        1.0, 2.0
    );
    std::cout << "sqrt(2) = " << result.value << std::endl;
    // 1.41421356...

    // 多項式: x^3 - 6x^2 + 11x - 6 = (x-1)(x-2)(x-3) の全根
    Polynomial<double> p = {-6.0, 11.0, -6.0, 1.0};
    auto roots = findAllRoots(p);
    for (auto& r : roots)
        std::cout << r << std::endl;
    // 1, 2, 3

    // 5次以上: Jenkins-Traub
    Polynomial<double> q = {1.0, 0.0, 0.0, 0.0, 0.0, 1.0};  // x^5 + 1
    auto roots5 = findAllRoots(q);
    for (auto& r : roots5)
        std::cout << r << std::endl;
}