LMCAS::ode_root_detail 命名空间参考

命名空间
namespace	anonymous_namespace{ode_characteristic_roots.cpp}

类
struct	CharRoot
struct	Complex

类型定义
using	RealPolynomial = std::vector<double>

函数
RealPolynomial	approximate_polynomial_gcd (RealPolynomial lhs, RealPolynomial rhs)
std::pair< RealPolynomial, RealPolynomial >	divide_polynomials (const RealPolynomial &dividend, const RealPolynomial &divisor)
Result< std::vector< CharRoot > >	find_characteristic_roots (const std::vector< double > &coeffs, const std::string &operation)
	使用数值方法求解特征多项式的所有根.
bool	is_exact_zero_polynomial_root (const RealPolynomial &coefficients, const Complex &root)
RealPolynomial	monic_polynomial (RealPolynomial polynomial)
RealPolynomial	polynomial_derivative (const RealPolynomial &polynomial)
bool	polynomial_remainder_is_small (const RealPolynomial &remainder, const RealPolynomial &dividend)
double	polynomial_root_backward_error (const RealPolynomial &coefficients, const Complex &root)
double	polynomial_scale (const RealPolynomial &polynomial)
void	trim_polynomial (RealPolynomial &polynomial)

---

类说明

LMCAS::ode_root_detail::CharRoot

struct LMCAS::ode_root_detail::CharRoot

在文件 ode_polynomial_utils.hpp 第 12 行定义.

LMCAS::ode_root_detail::CharRoot 的协作图:

类成员
double	imag_part
bool	is_complex
int	multiplicity
double	real_part

类型定义说明

RealPolynomial

using LMCAS::ode_root_detail::RealPolynomial = std::vector<double>

在文件 ode_polynomial_utils.hpp 第 10 行定义.

函数说明

approximate_polynomial_gcd()

RealPolynomial LMCAS::ode_root_detail::approximate_polynomial_gcd ( RealPolynomial lhs, RealPolynomial rhs )

inline

在文件 ode_polynomial_utils.hpp 第 150 行定义.

                                            {
    lhs = monic_polynomial(std::move(lhs));
    rhs = monic_polynomial(std::move(rhs));
    for (int iteration = 0; iteration < 8 && rhs.size() > 1; ++iteration) {
        auto division = divide_polynomials(lhs, rhs);
        RealPolynomial remainder = std::move(division.second);
        if (remainder.size() == 1 && remainder.front() == 0.0) {
            return rhs;
        }
        lhs = std::move(rhs);
        rhs = monic_polynomial(std::move(remainder));
    }
    return {1.0};
}

引用了 approximate_polynomial_gcd(), divide_polynomials(), monic_polynomial() , 以及 LMCAS::rhs.

被这些函数引用 approximate_polynomial_gcd() , 以及 LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::repeated_characteristic_roots().

函数调用图:

这是这个函数的调用关系图:

divide_polynomials()

std::pair< RealPolynomial, RealPolynomial > LMCAS::ode_root_detail::divide_polynomials ( const RealPolynomial & dividend, const RealPolynomial & divisor )

inline

在文件 ode_polynomial_utils.hpp 第 98 行定义.

                                                                   {
    if (divisor.empty() || divisor.front() == 0.0 ||
        dividend.size() < divisor.size()) {
        return {{0.0}, dividend};
    }
 
    RealPolynomial remainder = dividend;
    RealPolynomial quotient(
        dividend.size() - divisor.size() + 1, 0.0);
    for (size_t i = 0; i < quotient.size(); ++i) {
        const double factor = remainder[i] / divisor.front();
        quotient[i] = factor;
        for (size_t j = 0; j < divisor.size(); ++j) {
            remainder[i + j] -= factor * divisor[j];
        }
    }
    remainder.erase(
        remainder.begin(), remainder.begin() + quotient.size());
    if (remainder.empty()) {
        remainder.push_back(0.0);
    }
    trim_polynomial(quotient);
    trim_polynomial(remainder);
    return {std::move(quotient), std::move(remainder)};
}

引用了 divide_polynomials() , 以及 trim_polynomial().

被这些函数引用 approximate_polynomial_gcd(), divide_polynomials(), LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::recover_root_multiplicities() , 以及 LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::repeated_characteristic_roots().

函数调用图:

这是这个函数的调用关系图:

find_characteristic_roots()

Result< std::vector< CharRoot > > LMCAS::ode_root_detail::find_characteristic_roots	(	const std::vector< double > &	coeffs,
		const std::string &	operation )

使用数值方法求解特征多项式的所有根.

对于一、二次多项式使用解析公式；对于三至六次多项式使用 Durand-Kerner 迭代。迭代前通过多项式与其导数的近似 GCD 识别并提取重根。

在文件 ode_characteristic_roots.cpp 第 338 行定义.

{
    int n = static_cast<int>(coeffs.size()) - 1;
    if (n <= 0) {
        return Result<std::vector<CharRoot>>::failure(
            CasErrc::NumericFailure,
            "characteristic polynomial has no roots", operation);
    }
 
    std::vector<CharRoot> roots;
    double leading = coeffs[0];
    if (leading == 0.0) {
        return Result<std::vector<CharRoot>>::failure(
            CasErrc::NumericFailure,
            "characteristic polynomial has no usable leading coefficient",
            operation);
    }
    std::vector<double> norm_coeffs(coeffs.size());
    for (size_t i = 0; i < coeffs.size(); ++i) {
        norm_coeffs[i] = coeffs[i] / leading;
        if (!std::isfinite(norm_coeffs[i])) {
            return Result<std::vector<CharRoot>>::failure(
                CasErrc::NumericFailure,
                "characteristic polynomial normalization is non-finite",
                operation);
        }
    }
 
    if (n == 1) {
        roots.push_back({-norm_coeffs[1], 0.0, 1, false});
        return roots;
    }
    if (n == 2) {
        return quadratic_characteristic_roots(norm_coeffs, operation);
    }
    auto scale_result = characteristic_root_scale(norm_coeffs, operation);
    if (!scale_result) {
        return Result<std::vector<CharRoot>>::failure(scale_result.error());
    }
    const double root_scale = scale_result.value();
    std::vector<double> solver_coeffs = norm_coeffs;
    for (int i = 1; i <= n; ++i) {
        for (int power = 0; power < i; ++power) {
            solver_coeffs[i] /= root_scale;
        }
    }
 
    auto repeated = repeated_characteristic_roots(solver_coeffs, operation);
    if (!repeated) {
        return repeated;
    }
    if (!repeated.value().empty()) {
        return restore_root_scale(std::move(repeated.value()), root_scale, operation);
    }
    auto candidates = iterate_characteristic_roots(solver_coeffs, operation);
    if (!candidates) {
        return Result<std::vector<CharRoot>>::failure(candidates.error());
    }
    auto classified = classify_characteristic_roots(
        solver_coeffs, candidates.value(), operation);
    if (!classified) {
        return classified;
    }
    return restore_root_scale(std::move(classified.value()), root_scale, operation);
}

引用了 find_characteristic_roots(), LMCAS::NumericFailure , 以及 LMCAS::roots().

被这些函数引用 find_characteristic_roots(), LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::repeated_characteristic_roots(), LMCAS::solve_euler_ode_impl(), LMCAS::solve_higher_order_ode_impl() , 以及 LMCAS::solve_linear2_homogeneous().

函数调用图:

这是这个函数的调用关系图:

is_exact_zero_polynomial_root()

bool LMCAS::ode_root_detail::is_exact_zero_polynomial_root ( const RealPolynomial & coefficients, const Complex & root )

inline

在文件 ode_polynomial_utils.hpp 第 49 行定义.

                                                             {
    return root.re == 0.0 && root.im == 0.0 && coefficients.back() == 0.0;
}

引用了 LMCAS::ode_root_detail::Complex::im, is_exact_zero_polynomial_root() , 以及 LMCAS::ode_root_detail::Complex::re.

被这些函数引用 is_exact_zero_polynomial_root() , 以及 polynomial_root_backward_error().

函数调用图:

这是这个函数的调用关系图:

monic_polynomial()

RealPolynomial LMCAS::ode_root_detail::monic_polynomial ( RealPolynomial polynomial )

inline

在文件 ode_polynomial_utils.hpp 第 125 行定义.

                                                                  {
    trim_polynomial(polynomial);
    if (polynomial.empty() || polynomial.front() == 0.0) {
        return {0.0};
    }
    const double leading = polynomial.front();
    for (double& coefficient : polynomial) coefficient /= leading;
    return polynomial;
}

引用了 monic_polynomial() , 以及 trim_polynomial().

被这些函数引用 approximate_polynomial_gcd() , 以及 monic_polynomial().

函数调用图:

这是这个函数的调用关系图:

polynomial_derivative()

RealPolynomial LMCAS::ode_root_detail::polynomial_derivative ( const RealPolynomial & polynomial )

inline

在文件 ode_polynomial_utils.hpp 第 135 行定义.

                                      {
    if (polynomial.size() <= 1) {
        return {0.0};
    }
    RealPolynomial derivative;
    derivative.reserve(polynomial.size() - 1);
    const size_t degree = polynomial.size() - 1;
    for (size_t i = 0; i < degree; ++i) {
        derivative.push_back(
            polynomial[i] * static_cast<double>(degree - i));
    }
    return derivative;
}

引用了 polynomial_derivative().

被这些函数引用 polynomial_derivative() , 以及 LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::repeated_characteristic_roots().

函数调用图:

这是这个函数的调用关系图:

polynomial_remainder_is_small()

bool LMCAS::ode_root_detail::polynomial_remainder_is_small ( const RealPolynomial & remainder, const RealPolynomial & dividend )

inline

在文件 ode_polynomial_utils.hpp 第 166 行定义.

                                                                     {
    return polynomial_scale(remainder) <=
           std::max(1.0, polynomial_scale(dividend)) * 1e-7;
}

引用了 LMCAS::e(), polynomial_remainder_is_small() , 以及 polynomial_scale().

被这些函数引用 polynomial_remainder_is_small(), LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::recover_root_multiplicities() , 以及 LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::repeated_characteristic_roots().

函数调用图:

这是这个函数的调用关系图:

polynomial_root_backward_error()

double LMCAS::ode_root_detail::polynomial_root_backward_error ( const RealPolynomial & coefficients, const Complex & root )

inline

在文件 ode_polynomial_utils.hpp 第 54 行定义.

                                                             {
    Complex value{coefficients.front(), 0.0};
    double scale = std::abs(coefficients.front());
    const double root_magnitude = root.magnitude();
    for (size_t i = 1; i < coefficients.size(); ++i) {
        value = value * root + Complex{coefficients[i], 0.0};
        scale = scale * root_magnitude + std::abs(coefficients[i]);
    }
    if (!std::isfinite(value.re) || !std::isfinite(value.im) ||
        !std::isfinite(scale)) {
        return INFINITY;
    }
    if (scale == 0.0) {
        // At an exact zero root with zero constant term, both the residual
        // and its coefficientwise bound vanish: no perturbation is needed.
        // A nonzero root can instead underflow the bound, which is not proof.
        return is_exact_zero_polynomial_root(coefficients, root)
                   ? 0.0 : INFINITY;
    }
    return value.magnitude() / scale;
}

引用了 is_exact_zero_polynomial_root(), LMCAS::ode_root_detail::Complex::magnitude(), polynomial_root_backward_error() , 以及 LMCAS::value.

被这些函数引用 LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::classify_characteristic_roots(), LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::iterate_characteristic_roots(), polynomial_root_backward_error() , 以及 LMCAS::ode_root_detail::anonymous_namespace{ode_characteristic_roots.cpp}::quadratic_characteristic_roots().

函数调用图:

这是这个函数的调用关系图:

polynomial_scale()

double LMCAS::ode_root_detail::polynomial_scale ( const RealPolynomial & polynomial )

inline

在文件 ode_polynomial_utils.hpp 第 77 行定义.

                                                                 {
    double scale = 0.0;
    for (double coefficient : polynomial) {
        scale = std::max(scale, std::abs(coefficient));
    }
    return scale;
}

引用了 polynomial_scale().

被这些函数引用 polynomial_remainder_is_small(), polynomial_scale() , 以及 trim_polynomial().

函数调用图:

这是这个函数的调用关系图:

trim_polynomial()

void LMCAS::ode_root_detail::trim_polynomial ( RealPolynomial & polynomial )

inline

在文件 ode_polynomial_utils.hpp 第 85 行定义.

                                                        {
    const double scale = polynomial_scale(polynomial);
    const double tolerance = std::max(1.0, scale) * 1e-10;
    auto first = polynomial.begin();
    while (first + 1 != polynomial.end() && std::abs(*first) <= tolerance) {
        ++first;
    }
    polynomial.erase(polynomial.begin(), first);
    if (polynomial.empty()) {
        polynomial.push_back(0.0);
    }
}

引用了 LMCAS::e(), polynomial_scale() , 以及 trim_polynomial().

被这些函数引用 divide_polynomials(), monic_polynomial() , 以及 trim_polynomial().

函数调用图:

这是这个函数的调用关系图: