bairstow.hpp File Reference

Bairstow's root-finding method with reference-based vectors. More...

#include <utility>
#include <vector>
#include "matrix2.hpp"
#include "vector2.hpp"

Include dependency graph for bairstow.hpp:

Go to the source code of this file.

Typedefs
using	Vec2 = ginger::Vector2< double >
using	Mat2 = ginger::Matrix2< Vec2 >
using	Vec2Ref = ginger::Vector2< double & >

Functions
auto	horner_ref (std::vector< double > &coeffs, std::vector< Vec2Ref > &vcoeffs, std::size_t degree, const Vec2 &vr) -> Vec2Ref
	Horner's rule (reference-based Vec2 version)
auto	bairstow (const std::vector< double > &coeffs, Vec2 &vr, const Options &options) -> std::pair< unsigned int, bool >
	Bairstow's method.
auto	makeadjoint_ref (const Vec2 &vr, const Vec2Ref &vp) -> Mat2
	Create adjoint matrix from two vectors (reference-based)
auto	delta_ref (const Vec2Ref &vA, const Vec2 &vr, const Vec2Ref &vp) -> Vec2
	Calculate Newton correction delta (reference-based)

Detailed Description

Bairstow's root-finding method with reference-based vectors.

Typedef Documentation

Mat2

using Mat2 = ginger::Matrix2<Vec2>

Vec2

using Vec2 = ginger::Vector2<double>

Vec2Ref

using Vec2Ref = ginger::Vector2<double&>

Function Documentation

bairstow()

auto bairstow ( const std::vector< double > &  coeffs, Vec2 &  vr, const Options &  options  ) -> std::pair< unsigned int, bool >

extern

Bairstow's method.

The bairstow function implements Bairstow's method for finding the roots of a real polynomial.

Bairstow's method finds quadratic factors of the form \(x^2 - rx - q\) of a real polynomial using Newton's method in 2D. At each iteration, the correction is:

\[ \begin{bmatrix} \Delta r \\ \Delta q \end{bmatrix} = -J^{-1} \begin{bmatrix} P(r,q) \\ Q(r,q) \end{bmatrix} \]

where \(P\) and \(Q\) are the remainders of synthetic division by \(x^2 - rx - q\).

Parameters

[in]	coeffs	The coeffs parameter is a vector representing the coefficients of the polynomial. Each element of the vector corresponds to the coefficient of a term in the polynomial, starting from the highest degree term and ending with the constant term. For example, if the polynomial is 3x^2 + 2x + 1, the coefficients vector would be {3, 2, 1}.
[in,out]	vr	vr is a vector of iterates, which represents the initial guesses for the roots of the polynomial. Bairstow's method will update these iterates iteratively until the desired tolerance is reached or the maximum number of iterations is reached.
[in]	options	The options parameter is an object of type Options which contains the maximum number of iterations (max_iters) and the tolerance (tolerance). These options are used to control the convergence criteria for Bairstow's method.

Returns

The function bairstow returns a std::pair<unsigned int, bool>. The first element of the pair represents the number of iterations performed, and the second element represents whether the method converged to a solution within the specified tolerance.

delta_ref()

auto delta_ref ( const Vec2Ref &  vA, const Vec2 &  vr, const Vec2Ref &  vp  ) -> Vec2

inline

Calculate Newton correction delta (reference-based)

Uses the adjoint matrix to compute the correction step in Bairstow's method:

\[ \begin{bmatrix} \Delta r \\ \Delta q \end{bmatrix} = -\frac{\operatorname{adj}(J)}{\det(J)} \, vA \]

Parameters

[in]	vA	Current remainder vector (reference wrapper)
[in]	vr	Direction vector r
[in]	vp	Vector p (reference wrapper)

Returns

Vec2 The correction delta

horner_ref()

auto horner_ref ( std::vector< double > &  coeffs, std::vector< Vec2Ref > &  vcoeffs, std::size_t  degree, const Vec2 &  vr  ) -> Vec2Ref

extern

Horner's rule (reference-based Vec2 version)

Horner's rule evaluates a polynomial at a given point \(x\). It rewrites the polynomial as nested multiplication:

\[ P(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + x a_n)\cdots)) \]

This allows evaluation using \(n\) multiplications and \(n\) additions.

Parameters

[in,out]	coeffs	coeffs is a reference to a vector of doubles. It is used to store the coefficients of a polynomial.
[in,out]	vcoeffs	vcoeffs is a reference to a vector of Vec2Ref objects.
[in]	degree	The parameter degree represents the size of the vector coeffs. It indicates the number of elements in the vector coeffs.
[in]	vr	vr is a Vec2 object, which represents a 2D vector. It has two components, vr.x() and vr.y(), which are used in the calculations inside the horner function.

Returns

a Vec2Ref object.

makeadjoint_ref()

auto makeadjoint_ref ( const Vec2 &  vr, const Vec2Ref &  vp  ) -> Mat2

inline

Create adjoint matrix from two vectors (reference-based)

Computes the adjugate matrix of the Jacobian in Bairstow's method:

\[ \operatorname{adj}(J) = \begin{bmatrix} s & -p \cdot r_y \\ -p & p \cdot r_x + s \end{bmatrix} \]

where \( (p, s) = vp \) and \( (r_x, r_y) = vr \).

Parameters

[in]	vr	Vector r (constant reference)
[in]	vp	Vector p (reference wrapper)

Returns

Mat2 The adjoint 2x2 matrix