Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite Riccati candidate, Newton-Kleinman, and doubling wrappers return a status

Statement

Use admitted inputs and the finite solver/arithmetic/evaluator controllers stipulated by each of Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms, Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration, and Finite-budget structure-preserving doubling iteration for the DARE. Then each procedure terminates with its declared output or status, retaining its specified failure diagnostics.

Candidate extraction makes one matching Schur or QZ reduction, at most one stable-block reordering call, and at most n graph-column certificate passes followed by finite acceptance checks. Exact Newton–Kleinman makes at most N policy evaluations; its safeguarded mode inspects at most N(L+1) trial gains and makes at most N point-certificate calls for the current cost matrices. SDA makes at most N solve/update passes, at most nN point-certificate calls for recurrence solves, and at most m(N+1) calls for residual solves (R∈Fm×m), followed by finite symmetry/residual reporting. Early failures may shorten these counts. These conclusions are conditional on the declared finite controller contracts; they do not derive termination of an unspecified certificate-producing routine from an enclosure theorem.

Successful ordering concerns the represented computed form. The original Riccati residual, symmetry, positivity and closed-loop checks remain separate. This finite-status result asserts no convergence for arbitrary inexact proposals and no rounded PSD or structured-backward-error guarantee.

Facts & Assumptions

Given: The three procedures' admitted finite matrix data, their finite Schur/QZ, reordering, outer-iteration and line-search budgets, and exactly the finite solver/verifier interfaces supplied in their Definitions.

[A1]

For candidate extraction, every supplied arithmetic/evaluator controller has the finite execution and explicit failure behavior declared in its Definition. For Newton–Kleinman the finite line-search controller and each point-certificate call return their result or status; for SDA each point certificate, exact factorization, and arithmetic operation returns its result or failure in finite work. These are the existing operational hypotheses, not inferred root-finding or precision-success guarantees.

[F1]

Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms calls its matching reduction, then stable-block reordering, then its finite verified graph solve and outward acceptance diagnostics.

[F3]

Finite-budget stable block reordering has exact adjacent-swap correctness and status proves finite status return, selected invariant/right-deflating subspace on an ordered return, and transport of the original unstructured reduction residual.

[F4]

A uniform approximate inverse and residual enclose every linear solution and Verified point and uniform linear residual certificate data supply the interpretation of usable verified linear-solve and inverse/residual data. Outward-rounded operations are inclusion-isotone and enclose DAG evaluations gives enclosure soundness for finite DAG evaluations.

[F5]

Certified QZ residuals give a backward error bound for both pencil matrices concerns the specified nearby unstructured pencil, not a structured Riccati perturbation.

[F6]

Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration has at most N outer updates, at most L+1 safeguarded trials per pass, and at most one current-cost point-certificate call per pass. Finite precision point linear solve certificate with explicit status has a finite status, and The point linear solve certifier returns a sound solution ball on success gives the solution ball on a certified return. Finite Bartels–Stewart statuses and successful-pivot uniqueness proves finite policy-solve status return and uniqueness on successful exact solves.

[F7]

Finite-budget structure-preserving doubling iteration for the DARE uses exact elimination for recurrence and residual solves in exact mode. Finite mode uses at most n point-certificate calls per recurrence solve and at most m calls for each residual diagnostic at initialization and after each update, since R+B∗HjB has order m. An unavailable residual does not change recurrence status. The point solver has finite status by [F6]. The residual/feedback conventions are Standard CARE and DARE data, equations, and conventions.

Proof

1.1givenA1F1F2algebra

Each candidate-extraction branch calls only its matching finite Schur or QZ routine. The finite controls and declared status behavior are covered by [F1]–[F2]. Any reduction, regularity, range or budget failure immediately propagates its inconclusive status; no convergence-until-success loop is present.

1.2givenA1F6algebra

Exact Newton–Kleinman performs at most N policy evaluations. Each admitted Bartels–Stewart call has the complete per-pass control packet and returns a finite success or failure status by [F6]; failure stops immediately and success is followed by one finite gain update. Hence exact mode returns within its declared outer budget.

1.3A1F4F6algebra

Each safeguarded outer pass clears finitely many positive integer denominators from the rational current-cost system, preserving its solution while making the stored point-call data dyadic, or returns range-failure. It inspects the finite list of L+1 gains and makes one current-cost point-certificate call. Each trial then uses finitely many outward operations to verify its inverse, residual and stability bounds. By [A1] each call and outward check returns its enclosure or status in finite work, with certified balls interpreted by [F4] and [F6]. A trial passes the certified acceptance inequality or is rejected; if no trial passes, the routine returns safeguard-inconclusive without changing the current gain. At most N outer passes therefore make at most N(L+1) trial inspections and N point-certificate calls. No assertion of convergence for arbitrary inexact proposals follows from this finite search.

1.4givenA1F6F7algebra

Each SDA pass j<N requests one solve with I+GjHj and, in finite mode, at most n point-certificate calls for its columns. The finite-mode initialization solves the order-m system RV=B∗ on finite dyadic encodings by finite exact rational elimination, forms BV,C∗C, and rounds finitely many components or returns its declared failure; it makes no point-certificate call. At initialization and after each update, form Sj=R+B∗HjB exactly. In exact mode its possibly non-dyadic entries are handled by the finite exact elimination rule, as are the recurrence solves; the residual is then evaluated exactly. In finite mode Sj is dyadic, so its order-m residual solve uses at most m point-certificate calls followed by outward residual evaluation. By [A1] and [F6] all these operations return a result or failure in finite work. An unavailable residual is reported without changing recurrence status. Failure of the recurrence solve immediately returns its declared range/inverse status; success is followed by the fixed finite matrix updates. Thus every pass and final report terminate.

2.1A1F1F3F4F5step 1.1algebra

On successful reduction, reordering inspects finitely many blocks and returns ordered or an explicit status by [F3]. On an ordered return its first required factor columns are the selected subspace of the represented computed form, with only the original unstructured residual certificate transported. Under [A1] the graph-block bound and verified solve [F4] terminate; missing invertibility or a failed solve takes the stated inconclusive branch. Residual, symmetry, positivity and closed-loop diagnostics use finitely many matrix/enclosure operations, and failure or unavailable evidence takes its explicit return. The enclosure interpretation in [F4] does not itself produce a terminating verifier; that is the supplied contract [A1]. The QZ diagnostic retains precisely the limitation in [F5]. Thus the wrapper returns in finite work with ordering and equation-level acceptance kept separate.

3.1A1F7step 2.1step 1.2step 1.3step 1.4algebra∎

There are at most N such passes. The final symmetry defects and, when its solve is available, the standard DARE residual use finite-dimensional arithmetic under [A1] and the conventions [F7]. Therefore the exact and finite-arithmetic paths return their declared output/status by the cap. The recorded raw matrices and defects supply no rounded PSD or structured-backward-error claim without separate checks, just as the candidate and safeguarded branches retain their original acceptance restrictions.

Depends on

Used by

Nothing in the library uses this result yet.

Cited to discharge well-definedness by Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms, Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration and Finite-budget structure-preserving doubling iteration for the DARE.

Dependency tree · two levels

51 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources