NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
Classes | Namespaces | Typedefs | Functions
generalized.hpp File Reference

The generalized Schur decomposition (QZ) of a pencil A − λ B, as LAPACK's zgges and dgges: the operands scaled into range, the reduction to Hessenberg-triangular form (zgghrd, dgghrd), the QZ iteration (zhgeqz single-shift, dhgeqz double-shift with 2 × 2 blocks for conjugate pairs), and the reordering of the eigenvalues by exchanges of adjacent blocks (ztgexc/ztgsen, dtgexc/dtgex2/dtgsen). More...

#include <algorithm>
#include <array>
#include <cmath>
#include <complex>
#include <concepts>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <limits>
#include <optional>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
#include "matrix_functions.hpp"
#include "svd.hpp"
Include dependency graph for generalized.hpp:

Go to the source code of this file.

Classes

struct  numerical::detail::qz_form
 A complex pencil in generalized Schur form being formed: S and T (n × n, row-major) with A = Q S Zᴴ and B = Q T Zᴴ, Q and Z unitary (qt, zt). More...
 
struct  numerical::detail::real_qz_form
 A real pencil in generalized real Schur form being formed: S and T (n × n, row-major) with A = Q S Zᵀ and B = Q T Zᵀ, Q and Z orthogonal (qt, zt). More...
 
struct  numerical::detail::triangle_svd
 The singular value decomposition of the upper triangular [f g; 0 h] (svd_of_triangle). More...
 
struct  numerical::detail::pencil_pair
 The eigenvalues of a 2 × 2 pencil, scaled (pencil_eigenvalues): wr1 / scale1 and wr2 / scale2, or the pair (wr1 ± i wi) / scale1. More...
 
struct  numerical::detail::pencil_bounds
 The bounds of dlag2's WSIZE (pencil_wsize), fixed by the pencil's scales. More...
 
struct  numerical::detail::real_pencil_value
 A generalized eigenvalue (αr + i αi) / β of a real pencil, as LAPACK's dgges gives it. More...
 
struct  numerical::detail::small_square
 A square of order 4 at most, row-major in a fixed stride: the blocks dtgex2 exchanges and its transforms. More...
 
struct  numerical::detail::pencil_rotations
 The rotations dlagv2 applies to a 2 × 2 pencil: [csl snl; −snl csl] (A, B) [csr −snr; snr csr]. More...
 
struct  numerical::detail::block_exchange
 An exchange of two diagonal blocks as exchange_real_blocks plans it: the blocks after it, and the transforms of rows and columns, ‘S’ = LIᵀ S IR(IR‘ the columns’ transform). More...
 
class  numerical::generalized_schur
 The generalized Schur decomposition of a complex pencil A − λ B, A = Q S Zᴴ and B = Q T Zᴴ, as scipy.linalg.qz(a, b, output="complex") (LAPACK's zgges): Q and Z unitary, S and T upper triangular, T's diagonal real and non-negative; the generalized eigenvalues α_k / β_k on the diagonals (β_k = 0 an infinite one). Reordered as scipy.linalg.ordqz by sort or reorder. Each operand is first brought into the range [√safmin / ε, ε / √safmin] of its largest magnitude where it lies outside, as zgges scales it, and the form and the eigenvalues taken back. More...
 
class  numerical::real_generalized_schur
 The generalized real Schur decomposition of a real pencil A − λ B, A = Q S Zᵀ and B = Q T Zᵀ, as scipy.linalg.qz(a, b) (LAPACK's dgges): Q and Z orthogonal, T upper triangular with a non-negative diagonal, S quasi-triangular, a 2 × 2 diagonal block for each conjugate pair of eigenvalues, T diagonal and positive there; the eigenvalues (αr + i αi) / β (β = 0 an infinite one). More...
 
struct  numerical::detail::riccati_operands< T >
 The operands of an algebraic Riccati equation in the arithmetic of T, e and s absent when null. More...
 

Namespaces

namespace  numerical
 The NumericAL public API.
 
namespace  numerical::detail
 

Typedefs

using numerical::detail::riccati_terms = riccati_operands< std::complex< double > >
 The operands of an algebraic Riccati equation as complex matrices (the residuals and Newton's step).
 

Functions

double numerical::detail::modulus_one (const std::complex< double > &z)
 |Re z| + |Im z|, LAPACK's ABS1.
 
qz_form numerical::detail::hessenberg_triangular (const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b)
 a and b (n × n, row-major) to Hessenberg-triangular form, as LAPACK's zgges begins: B = Q R by the QR factorisation, A ← Qᴴ A, then zgghrd: each column of A from the first cleared below its subdiagonal from the bottom by rotations of rows, the fill each leaves below B's diagonal taken out by a rotation of columns; Q and Z accumulating them.
 
std::pair< std::complex< double >, std::complex< double > > numerical::detail::standardize (qz_form &f, std::size_t j)
 T(j, j) made real and non-negative, as zhgeqz standardises it: row j of T and S above the diagonal and column j of S, T and Z taking the phase.
 
std::vector< std::pair< std::complex< double >, std::complex< double > > > numerical::detail::qz_iteration (qz_form &f, std::size_t steps)
 The Hessenberg-triangular f to generalized Schur form, as LAPACK's zhgeqz (Schur form, Q and Z updated): single-shift QZ sweeps on the active block, the shift the eigenvalue of the trailing 2 × 2 of S T⁻¹ nearer its corner (an exceptional one every tenth iteration), a negligible subdiagonal entry of S splitting the block, a negligible diagonal entry of T chased down (or up, after two small subdiagonal entries) to split off an infinite eigenvalue.
 
double numerical::detail::frobenius_two (const std::array< std::complex< double >, 4 > &m)
 The Frobenius norm of the 2 × 2 block m.
 
bool numerical::detail::exchange_pencil_diagonal (qz_form &f, std::size_t j)
 Exchanges the diagonal entries j and j + 1 (from 1) of the triangular pencil f, as LAPACK's ztgex2: columns j, j + 1 rotated onto the right eigenvector of the second eigenvalue, then rows j, j + 1 back to triangular, the rotation from S's new first column where |S₂₂ T₁₁| ≥ |S₁₁ T₂₂|, else T's; Z and Q turning with them. The diagonal of T is then complex: standardize takes it back. Tried on the 2 × 2 blocks first and refused, f unchanged, unless it passes ztgex2's weak test (the new subdiagonal entries within 20 ε of the blocks' norms) and strong test (the blocks rebuilt from the rotations within the same bounds).
 
triangle_svd numerical::detail::svd_of_triangle (double f, double g, double h)
 The SVD of the upper triangular [f g; 0 h], as LAPACK's dlasv2: [csl snl; −snl csl] [f g; 0 h] [csr −snr; snr csr] = diag(ssmax, ssmin), |ssmax| ≥ |ssmin|, each accurate to a few ulps.
 
double numerical::detail::pencil_wsize (const pencil_bounds &b, double w) noexcept
 dlag2's WSIZE: the divisor that keeps an eigenvalue of magnitude w in range.
 
pencil_pair numerical::detail::pencil_eigenvalues (double a11, double a12, double a21, double a22, double b11, double b12, double b22, double safmin)
 The eigenvalues of the pencil A − w B, A (a11 a12 / a21 a22) and the upper triangular B (b11 b12 / 0 b22), as LAPACK's dlag2, with scalings that keep scale · w from overflowing or underflowing; a diagonal entry of B below safmin's square root times its largest perturbed up to it.
 
double numerical::detail::hypot3 (double x, double y, double z)
 √(x² + y² + z²) without overflow, LAPACK's dlapy3.
 
std::pair< real_pencil_value, real_pencil_value > numerical::detail::pair_values (real_qz_form &f, std::size_t ilast, const pencil_pair &pair, double b11, double b22)
 The conjugate pair of the standardized 2 × 2 block ending at ilast of f (T diagonal, b11 and b22), as dhgeqz computes α and β from pair (dlag2's): β the norms of the diagonal of T after the complex rotations that would triangularise the block, α = (wr ± i wi) β / scale.
 
void numerical::detail::double_shift_sweep (real_qz_form &f, std::size_t ifirst, std::size_t ilast, double ascale, double bscale, double safmin)
 One double-shift QZ sweep (Moler and Stewart) on rows and columns ifirst … ilast of f, as dhgeqz's: the shifts the eigenvalues of the trailing 2 × 2 of S T⁻¹ and its leading one's first column, the bulge chased by reflections of three rows (dlarfg) and of three columns (from the null vector of T's 2 × 2 below the bulge), a rotation pair for the last step.
 
real_qz_form numerical::detail::real_hessenberg_triangular (const matrix< double > &a, const matrix< double > &b)
 The real a and b to Hessenberg-triangular form, as LAPACK's dgges begins: B = Q R by the QR factorisation, A ← Qᵀ A, then dgghrd: each column of A from the first cleared below its subdiagonal from the bottom by rotations of rows, the fill each leaves below B's diagonal taken out by a rotation of columns; Q and Z accumulating them.
 
std::vector< real_pencil_value > numerical::detail::real_qz_iteration (real_qz_form &f, std::size_t steps)
 The Hessenberg-triangular f to generalized real Schur form, as LAPACK's dhgeqz (Schur form, Q and Z updated): double-shift QZ sweeps (Moler and Stewart) on the active block, the shifts the eigenvalues of its trailing 2 × 2 (dlag2; a single shift where they are real, an exceptional one every tenth iteration), a negligible subdiagonal entry of S splitting it, a negligible diagonal entry of T chased to split off an infinite eigenvalue; a 2 × 2 block of a conjugate pair standardized with T diagonal and positive (dlasv2), every T(j, j) non-negative. steps bounds the iterations (dhgeqz's 30 n).
 
small_square numerical::detail::small_product (const small_square &x, bool tx, const small_square &y, bool ty, std::size_t m)
 op(x) op(y) of order m, op the transpose where tx (ty).
 
double numerical::detail::small_norm (const small_square &x, std::size_t r0, std::size_t r1, std::size_t c0, std::size_t c1)
 The Frobenius norm of rows r0 … r1 − 1 and columns c0 … c1 − 1 of x.
 
small_square numerical::detail::small_qr (small_square x, std::size_t m, std::size_t k)
 The orthogonal Q (order m) of the Householder QR factorisation of the first k columns of x (m × k, k ≤ m), as LAPACK's dgeqr2 then dorg2r: its first k columns span theirs, Qᵀ x upper trapezoidal.
 
pencil_rotations numerical::detail::standardize_pencil (std::array< std::array< double, 2 >, 2 > &a, std::array< std::array< double, 2 >, 2 > &b)
 The 2 × 2 pencil (a, b), b upper triangular, standardized, as LAPACK's dlagv2: two real eigenvalues made triangular, a complex pair left with b diagonal and positive; both changed in place.
 
std::optional< std::pair< small_square, small_square > > numerical::detail::generalized_sylvester (const small_square &s, const small_square &t, std::size_t n1, std::size_t n2)
 The solution (R, L) (n1 × n2 each) of the generalized Sylvester equations S₁₁ R − L S₂₂ = S₁₂, T₁₁ R − L T₂₂ = T₁₂ of the m × m blocks of s and t (m = n1 + n2), as LAPACK's dtgsy2 solves them: by elimination with complete pivoting of their Kronecker form; nothing where a pivot falls below ε times the largest entry (dgetc2 would perturb it, and dtgex2 then refuses the exchange).
 
std::optional< block_exchange > numerical::detail::plan_single_exchange (small_square s, small_square t, double thresha, double threshb)
 Two 1 × 1 blocks' exchange, as LAPACK's dtgex2 makes it: columns turned onto the second eigenvalue's right eigenvector, then rows back to triangular, the rotation from S's new first column where |S₂₂ T₁₁| ≥ |S₁₁ T₂₂|, else T's. Nothing where the new subdiagonal entries pass thresha and threshb (the weak test).
 
std::optional< block_exchange > numerical::detail::plan_block_exchange (small_square s, small_square t, std::size_t n1, std::size_t n2, double thresha)
 The exchange of blocks of orders n1 and n2 (one of them 2), as LAPACK's dtgex2 makes it: orthogonal bases of the deflating subspaces the generalized Sylvester equations give (generalized_sylvester), T made triangular again by an RQ or a QR factorisation (the one that leaves the smaller block below S's diagonal), each 2 × 2 block standardized (standardize_pencil). Nothing where the equations have no solution or that block passes thresha (the weak test).
 
bool numerical::detail::exchange_real_blocks (real_qz_form &f, std::size_t j1, std::size_t n1, std::size_t n2)
 Exchanges the adjacent diagonal blocks of orders n1 and n2 (1 or 2) at j1 (from 1) of the real generalized Schur form f, as LAPACK's dtgex2: planned by plan_single_exchange or plan_block_exchange, then refused unless the blocks rebuilt from the transforms, ‘LI S’ IRᵀ, are within 20 ε‘ of the originals’ norms (the strong test, after the 2 × 2 blocks' standardization where dtgex2 makes it before: their rotations' rounding more); else the entries below the new blocks set to 0 and the rows and columns of S, T, Q and Z turned.
 
void numerical::detail::exchange_or_refuse (real_qz_form &f, std::size_t j1, std::size_t n1, std::size_t n2)
 exchange_real_blocks, a refusal thrown as real_generalized_schur::reorder reports it.
 
void numerical::detail::move_real_block_up (real_qz_form &f, std::size_t ifst, std::size_t ilst)
 Moves the diagonal block at ifst (from 1) of the real generalized Schur form f up to ilst, as LAPACK's dtgexc does it upwards: exchanged with each block above in turn (exchange_real_blocks), a 2 × 2 block that splits on the way moved as its two 1 × 1 ones; ifst and ilst taken to the first row of their blocks.
 
std::vector< real_pencil_value > numerical::detail::real_values (real_qz_form &f)
 The eigenvalues of the real generalized Schur form f after a reordering, as LAPACK's dtgsen gives them: a 2 × 2 block's pair by dlag2 (β its scale), a 1 × 1 block's from its diagonal, T(k, k) made non-negative (row k of S and T and column k of Q negated).
 
template<typename T >
std::pair< matrix< T >, double > numerical::detail::pencil_operand_in_range (const matrix< T > &m)
 m brought into the range [√safmin / ε, ε / √safmin] of its largest magnitude where it lies outside, as LAPACK's xgges scales A and B before the QZ iterations (their norms' squares, the shifts and the rotations stay in range): the matrix, and the factor that takes the scaled one back (1 where none).
 
template<typename T >
matrix< T > numerical::detail::scaled_back (const buffer< T > &m, std::size_t n, double factor)
 The entries of m multiplied by factor, n × n row-major (the scaled form taken back).
 
matrix< std::complex< double > > numerical::detail::triangular_pencil_vectors (const matrix< std::complex< double > > &s, const matrix< std::complex< double > > &t, const std::vector< std::pair< std::complex< double >, std::complex< double > > > &values, const matrix< std::complex< double > > &basis, bool left)
 The right (or, where left, the left) eigenvectors of the triangular pencil (s, t) whose diagonal is values, as LAPACK's ztgevc: for each (α, β), x with (β S − α T) x = 0 and x_k = 1 by back substitution (yᴴ (β S − α T) = 0 forward for a left one), then basis x made of unit 2-norm; a diagonal entry of β S − α T below ε (|β| ‖S‖ + |α| ‖T‖), or the smallest normal number, taken as that bound (SMIN), and α and β both zero (a singular pencil) given the unit vector of its place. The substitutions on the threads, each on its own; the basis applied to their nonzero parts by one product.
 
matrix< std::complex< double > > numerical::generalized_eigenvectors (const generalized_schur &d, bool left)
 The right (or, where left, the left) eigenvectors of the pencil d decomposes, as LAPACK's ztgevc and scipy.linalg.eig(a, b): for each eigenvalue (α, β) in the diagonals' order, x with (β S − α T) x = 0 and x_k = 1 by back substitution (yᴴ (β S − α T) = 0 forward for a left one), then Z x (Q y) made of unit 2-norm, as SciPy normalises ggev's; a diagonal entry of β S − α T below ε (|β| ‖S‖ + |α| ‖T‖) taken as that bound (ztgevc's SMIN, at least the smallest normal number), and an eigenvalue with α and β both zero (a singular pencil) given the unit vector of its place, as ztgevc gives it.
 
matrix< std::complex< double > > numerical::generalized_eigenvectors (const real_generalized_schur &d, bool left)
 The right (or, where left, the left) eigenvectors of the real pencil d decomposes, complex, as scipy.linalg.eig(a, b) gives them for a real pencil (each of unit 2-norm): each 2 × 2 block of S and T made triangular first by unitary rotations from both sides (the left one along T v, the right one along the block's eigenvector v), carried through S, T, Q and Z, then the complex pencil's vectors (generalized_eigenvectors). The columns in the diagonals' order, as d's values.
 
buffer< double > numerical::detail::scaling_balance (buffer< double > &m, std::size_t n)
 The scaling of LAPACK's ‘dgebal('S’)for the non-negativen × n\p m (row-major, scaled in place): rows and columns by powers of two until their 2-norms are within a factor of 2, a row or column of zeros left alone, the factors kept within the safe range. \return The scalesDofD⁻¹ M D`.
 
template<typename T >
double numerical::detail::norm_one (const matrix< T > &a)
 The 1-norm of a: its largest column sum of moduli.
 
void numerical::detail::refuse_boundary (bool continuous)
 Refuses a Riccati equation whose pencil has eigenvalues on (or too close to) the boundary.
 
template<typename T >
matrix< T > numerical::detail::stabilising_solution (const matrix< T > &top, const matrix< T > &bottom, bool continuous)
 X = U₂₁ U₁₁⁻¹ from the m leading Schur vectors' halves top (U₁₁) and bottom (U₂₁) of a Riccati equation's Hamiltonian (continuous) or symplectic matrix or pencil, as SciPy's checks have it.
 
template<typename T >
std::pair< buffer< T >, buffer< T > > numerical::detail::riccati_pencil (const riccati_operands< T > &terms, bool continuous)
 The extended pencil (H, J) of order 2m + n of SciPy's solve_continuous_are (continuous) or solve_discrete_are, row-major.
 
template<typename T >
buffer< double > numerical::detail::balance_pencil (buffer< T > &h, buffer< T > &j, std::size_t m, std::size_t order)
 Balances the pencil (H, J) of order 2m + n as SciPy does: ‘dgebal('S’)scaling of|H| + |J|off the diagonal, the first two blocks ofmthen givenDandD⁻¹from half the difference of their exponents (Benner's symplectic constraint), the pencil scaled toD⁻¹ (H, J) D. \return The scalesD`, all 1 when the scaling found none.
 
template<typename T >
matrix< T > numerical::detail::riccati (const riccati_operands< T > &terms, bool continuous, bool balanced)
 The stabilising solution of the continuous (continuous) or discrete algebraic Riccati equation by SciPy's algorithm: the extended pencil, balanced unless balanced is false, deflated by the QR factorisation of its last n columns, its generalized Schur form sorted with the eigenvalues in the left half-plane (inside the unit circle) first, and X = U₁₀ U₀₀⁻¹ from the leading m columns of Z (with E, of the QR factorisation of [Ẽ U₀₀; U₁₀]), returned as (X + Xᴴ)/2 in the original scaling. Ẽ is E as the balanced pencil holds it, D₁ E D₁⁻¹: the basis U is of the balanced pencil, so X̃ Ẽ U₀₀ = U₁₀ for X̃ = D₁⁻¹ X D₁⁻¹, and the unscaled E there (as SciPy has it) answers a wrong X or none.
 
matrix< std::complex< double > > numerical::detail::continuous_residual (const riccati_terms &terms, const matrix< std::complex< double > > &x, matrix< std::complex< double > > &closed)
 The residual Aᴴ X E + Eᴴ X A − (Eᴴ X B + S) R⁻¹ (Bᴴ X E + Sᴴ) + Q of the continuous equation at the Hermitian x, and the closed loop A − B K, K = R⁻¹ (Bᴴ X E + Sᴴ), into closed.
 
bool numerical::detail::entries_finite (std::initializer_list< const matrix< std::complex< double > > * > xs)
 Whether every entry of the matrices xs is finite.
 
double numerical::detail::continuous_backward_error (const riccati_terms &terms, const matrix< std::complex< double > > &x)
 The residual at x of the continuous equation without E (the Hamiltonian's), relative to its terms: ‖Res(X)‖₁ / (2 ‖A‖₁ ‖X‖₁ + ‖Bᴴ X + Sᴴ‖₁ ‖R⁻¹(Bᴴ X + Sᴴ)‖₁ + ‖Q‖₁) (continuous_residual); infinite where it is not finite.
 
matrix< std::complex< double > > numerical::detail::newton_refined (const riccati_terms &terms, matrix< std::complex< double > > &&x)
 One step of Newton's method on the continuous equation from the Schur method's x (Kleinman, 1968), in its correction form: A_Kᴴ Δ E + Eᴴ Δ A_K = −Res(X) for the closed loop A_K (continuous_residual), a Lyapunov equation solved for Y = Eᴴ Δ E as Fᴴ Y + Y F = −Res(X), F = E⁻¹ A_K; X + Δ kept only where its residual's 1-norm is smaller. The generalized Schur form of a badly scaled equation (a graded A) loses digits that a step from a solution so near the stabilising one gains back.
 
matrix< std::complex< double > > numerical::detail::answer_like (matrix< std::complex< double > > &&x, const matrix< std::complex< double > > &)
 x itself, for complex operands like.
 
matrix< double > numerical::detail::answer_like (const matrix< std::complex< double > > &x, const matrix< double > &)
 x's real part, for real operands like: the solution of a real equation is real.
 
void numerical::detail::require_hermitian (const matrix< std::complex< double > > &x, const char *name)
 Refuses x (named name in the message) unless Hermitian, as SciPy's _are_validate_args: ‖X − Xᴴ‖₁ within 100 spacings of ‖X‖₁.
 
template<typename T >
buffer< double > numerical::detail::balance_hamiltonian (buffer< T > &h, std::size_t m)
 The diagonal D of a symplectic balancing of the Hamiltonian h of order 2m (row-major, in place): h ← T⁻¹ h T, T = diag(D, D⁻¹), powers of 2 (each scaling exact). Each dᵢ scales column i and row m + i by f (their common entry by f²), row i and column m + i by 1/f (theirs by 1/f²): the power of 2 whose off-diagonal sum g₁ f + g₂ f² + s₁/f + s₂/f² is least (a convex function of log f), taken where it lowers the sum by a twentieth, swept until none does: each step lowers the matrix's off-diagonal sum, so the sweeps end.
 
template<typename T >
matrix< T > numerical::detail::hamiltonian_riccati (const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const matrix< T > *s, bool balanced)
 The stabilising solution of the continuous equation without E from the Schur form of the Hamiltonian H = [[Ã, −G], [−Q̃, −Ãᴴ]] (Laub, 1979), G = B R⁻¹ Bᴴ, Ã = A − B R⁻¹ Sᴴ and Q̃ = Q − S R⁻¹ Sᴴ in the arithmetic of T (a real H's real Schur form): its eigenvalues in the left half-plane moved first, X = U₂₁ U₁₁⁻¹ from their m Schur vectors, made Hermitian. A Schur form of order 2m by multishift QR where the pencil's QZ takes order 2m + n. Where balanced, H is first T⁻¹ H T, T = diag(D, D⁻¹) (balance_hamiltonian), still Hamiltonian, and X = D⁻¹ X̃ D⁻¹: a Q of 10¹⁰ beside a G of 1 left the unbalanced form's X wrong at 10⁻³.
 
template<typename T >
matrix< T > numerical::detail::solve_are (const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const matrix< T > *e, const matrix< T > *s, bool balanced, bool continuous)
 The checks of SciPy's _are_validate_args, then riccati on complex operands, the answer real for real ones.
 
template<typename T >
requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
matrix< T > numerical::solve_continuous_are (const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const std::type_identity_t< matrix< T > > *e=nullptr, const std::type_identity_t< matrix< T > > *s=nullptr, bool balanced=true)
 The stabilising solution X of the continuous algebraic Riccati equation Aᴴ X E + Eᴴ X A − (Eᴴ X B + S) R⁻¹ (Bᴴ X E + Sᴴ) + Q = 0 (E = I and S = 0 when e and s are null), as scipy.linalg.solve_continuous_are: without e and with R well-conditioned (its condition below 1/√ε), the Schur form of the Hamiltonian [[Ã, −G], [−Q̃, −Ãᴴ]] (Laub, 1979, in real arithmetic for real operands); else, as SciPy, the eigenvalues of the extended Hamiltonian pencil in the left half-plane moved first in its generalized Schur form (generalized_schur), R never inverted. Then one step of Newton's method, kept where it lowers the residual.
 
template<typename T >
requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
matrix< T > numerical::solve_discrete_are (const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const std::type_identity_t< matrix< T > > *e=nullptr, const std::type_identity_t< matrix< T > > *s=nullptr, bool balanced=true)
 The stabilising solution X of the discrete algebraic Riccati equation Aᴴ X A − Eᴴ X E − (Aᴴ X B + S) (R + Bᴴ X B)⁻¹ (Bᴴ X A + Sᴴ) + Q = 0 (E = I and S = 0 when e and s are null), as scipy.linalg.solve_discrete_are: the eigenvalues of the extended symplectic pencil inside the unit circle moved first in its generalized Schur form (generalized_schur), nothing inverted.
 

Detailed Description

The generalized Schur decomposition (QZ) of a pencil A − λ B, as LAPACK's zgges and dgges: the operands scaled into range, the reduction to Hessenberg-triangular form (zgghrd, dgghrd), the QZ iteration (zhgeqz single-shift, dhgeqz double-shift with 2 × 2 blocks for conjugate pairs), and the reordering of the eigenvalues by exchanges of adjacent blocks (ztgexc/ztgsen, dtgexc/dtgex2/dtgsen).

Definition in file generalized.hpp.