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.
Exponential and integrating factor integrators
1 · Prerequisites
- Absolute and Conditional Convergence; Rearrangement; Products
- Algebraic Closure, Embeddings, and Separability
- Algebraic Extensions, Extension Degree, and Finite Fields
- Binary Operations, Monoids, Groups and Subgroups
- Bounded Linear Operators and Quotient Spaces
- Compactness in Metric Spaces
- Completeness, Completion, and Uniform Continuity
- Complex Norms and Realification
- Complexification, Realification and Real Structures
- Composition Series, the Jordan–Hölder Theorem and Solvable Groups
- Congruences, the Integers Modulo n and the Chinese Remainder Theorem
- Construction of the Natural Numbers
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Continuity, IVT, EVT, and Uniform Continuity
- Cosets, Index and Lagrange's Theorem
- Countability and Uncountability
- Cyclic Groups and Direct Products
- Determinants of Matrices over a Commutative Ring
- Diagonalisation and the Minimal Polynomial
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Divisibility, Greatest Common Divisors and Bézout's Identity
- Dual Spaces, Bilinear and Quadratic Forms, and Sylvester's Law of Inertia
- Eigenvalue Iterations and the QR Algorithm
- Eigenvalues, Eigenvectors and the Characteristic Polynomial
- Filters and Ultrafilters
- Finite Counting, Factorials and Binomial Coefficients
- Finite Dimensional Normed Spaces and Riesz Lemma
- Finite Probability and the Probabilistic Method
- Foundations of the Real Numbers for Analysis
- Global ODE and Log-density Integration Error
- Group Actions, Orbits, Stabilisers and Cayley's Theorem
- Group Homomorphisms and the Isomorphism Theorems
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- Inner Product Spaces, Gram-Schmidt, Projections and Adjoints
- Krylov Subspaces, Arnoldi and GMRES
- Limits of Real Functions
- limsup, liminf, and Subsequential Limits
- Linear Independence, Bases and Dimension
- Linear Transformations, Rank-Nullity and Quotient Spaces
- Matrices, the Matrix of a Linear Map, and Change of Basis
- Matrix exponential and phi function actions
- Metric Spaces
- Monotone Functions, Discontinuities, and Continuity Sets
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- Normal Subgroups and Quotient Groups
- Normed and Banach Spaces
- Norming and Separation under Hahn–Banach
- One-step ODE Consistency and Local Error
- Order, Zorn's Lemma, and the Axiom of Choice
- Picard-Lindelöf and First-Order Ordinary Differential Equations
- Polynomial Rings, the Division Algorithm and Roots
- Power Series and Real-Analytic Functions
- Primes, Euclid's Lemma and the Fundamental Theorem of Arithmetic
- Properties of the Integral and the Working FTC
- Relations, Functions, and Quotients
- Rings, Subrings, Integral Domains and Fields
- Rⁿ as a Normed Space; Vector-Valued Functions
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Sequences and Series of Functions; Uniform Convergence
- Series: Convergence and the Nonnegative Tests
- Simple Field Extensions and the Construction of the Complex Numbers
- Splitting Fields
- Strongly Continuous Semigroups and Hille Yosida
- Suprema and Infima
- Sylow's Theorems, p-Groups and Nilpotent Groups
- Symmetric Groups, Cycle Decomposition and the Sign Homomorphism
- The Complex Exponential and Euler's Formula
- The Derivative and the Mean Value Theorems
- The Determinant of a Linear Operator, Cofactors and Cramer's Rule
- The Exponential Function
- The Fundamental Theorem of Algebra
- The Fundamental Theorem of Finite Abelian Groups
- The Galois Correspondence
- The Logarithm and General Powers
- The Riemann Integral: Definition and Integrability
- The Spectral Theorem, Positive Operators and Singular Value Decomposition
- The ZFC Axioms and the Basic Set Constructions
- Topology of ℝ
- Triangularisation, Generalised Eigenspaces and Jordan Canonical Form
- Vector Spaces, Linear Subspaces, Span and Direct Sums
2 · Summary
For a semilinear system with a fixed finite matrix , these methods integrate the linear part exactly and approximate only the nonlinear forcing. Variation of constants supplies the step formulas, while the series definitions and integral representations of and remain valid when is singular or zero. The selected explicit two-stage ETD2 formula uses an exponential-Euler predictor.
The local-defect and transformed-stability lemmas give global order one for exponential Euler and order two for ETD2 on a common compact tube. The global constants may depend on , the time interval, and the tube. The certified-action procedure accounts for exponential and -function approximation, field evaluation, and arithmetic errors at each step, returns its measured work counters, and its global theorem propagates the sum of the action-error bounds.
The results are finite-dimensional and fixed-matrix statements. They do not establish stiffness-uniform bounds over changing matrices or a convergence theorem for unbounded operators or PDEs; those require additional domain and commutator hypotheses. See exponential-and-integrating-factor-integrators-examples for diagonal stiff, nonnormal, zero-matrix phi, imaginary-time decay, and real-time skew-Hermitian unitary examples. Prerequisite interfaces are global-ode-and-density-error and matrix-exponential-and-phi-function-actions.
3 · Logical flowchart
4 · Definitions, theorems and proofs
Variation of constants for a finite-matrix semilinear system
Statement
Let , , , and let be open after identifying with . Let and let be a continuously differentiable solution of the first-order system where is continuous. With the vector integral taken componentwise after identifying with ,
Facts & Assumptions
Given: The finite matrix, interval, curve, and semilinear differential equation in the Statement.
First-order systems, initial value problems, and solutions on intervals: a solution is differentiable and satisfies its differential equation at every time in its interval.
A bounded linear operator between normed spaces, The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, and Every finite-dimensional normed space is Banach: a finite matrix is a bounded operator on the complete finite-dimensional space , so The exponential series of a bounded operator applies and gives and .
The derivative and the Riemann integral of a vector-valued function: an intrinsic derivative and a componentwise integral: a curve in and its integral are interpreted coordinatewise in the real vector space ; an integral with equal limits is zero.
A continuous function on is Riemann integrable, by Heine-Cantor and Riemann's criterion: every continuous real coordinate of a finite-dimensional vector curve on a closed bounded interval is integrable.
If is differentiable with integrable then ; and a bounded derivative makes Lipschitz: for and a differentiable finite-dimensional real vector curve with integrable derivative, .
Rectangular matrix multiplication and the identity matrix , including zero-sized shapes and Sums, scalar multiples, products and quotients: , , , and when : matrix multiplication is a finite sum of scalar products, so its derivative obeys the product rule.
Integrable functions on form a set closed under sums and scalar multiples, and : a fixed finite-dimensional linear map commutes with componentwise vector integration.
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: for , set . Applying the scalar coordinate map componentwise identifies real-linearly with , and . It carries each real-time difference quotient to the corresponding realified quotient and preserves its limit, while matrix-vector multiplication becomes the corresponding real coordinate arithmetic. Thus the real differentiation and integration suppliers apply without changing the norm.
Proof
If , then by [F2] and the integral is zero by [F3], proving the identity. Assume henceforth . By [F8], the componentwise realification preserves the Euclidean norm, and the equation in the Statement is a real first-order system to which [F1] applies. Put . By the product rule [F6], [F1], and [F2], , since commutes with every power in the series for .
The derivative in step 1.1 is continuous because the exponential and are continuous. Thus [F3]–[F4] make it integrable componentwise, and [F5] gives .
Multiply the last identity by . By [F7], this fixed linear map commutes with the componentwise integral, and [F2] gives and . Rearranging yields the claimed formula.
A skew-Hermitian matrix exponential is unitary
Statement
Let , , and . Then for every , Thus is unitary and preserves the Euclidean norm.
Facts & Assumptions
Given: A finite complex matrix with and the matrix exponential .
The adjoint is characterised by and In orthonormal bases, the matrix of the adjoint is the conjugate transpose of the matrix: the adjoint of a matrix is its conjugate transpose and .
Sums, scalar multiples, products and quotients: , , , and when : entrywise conjugation commutes with differentiation in real time, and finite matrix products along a real parameter obey the product rule.
The mean value theorem, as the case of Cauchy's: for continuous on with and differentiable on there is with : a real-valued function with zero derivative on an interval is constant there.
The norm induced by a real or complex inner product and The standard formulas on and on are inner products: the complex Euclidean norm satisfies .
Rectangular matrix multiplication and the identity matrix , including zero-sized shapes: matrix multiplication and have their standard coordinate meanings.
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: for , the map is real-linear and satisfies . It commutes with real-time difference quotients and preserves limits, so entrywise real differentiation and the zero-derivative argument apply.
Proof
By [F1], . The coordinate identification [F7] makes entrywise real differentiation legitimate; taking conjugate transposes and using [F2], [F3], and gives .
Apply the product rule [F3] to ; its derivative is .
Each real and imaginary coordinate of has zero derivative, so [F4] makes every coordinate constant. Evaluating at with [F1] and [F6] gives for all . By [F5] and matrix multiplication, .
Integral representations of the first two phi functions
Statement
For every and , the series-defined functions The phi-function family by everywhere-convergent series satisfy The integrals are componentwise. These formulas define the values at directly and do not use division by .
Facts & Assumptions
Given: and .
The scalar and matrix phi series converge absolutely: these series converge absolutely in operator norm.
A bounded linear operator between normed spaces, The operator norm as the least bound and as the unit-sphere or unit-ball supremum, Every finite-dimensional normed space is Banach, and The exponential series of a bounded operator: a finite matrix acts as a bounded operator on the complete finite-dimensional space, and its exponential series converges locally uniformly in operator norm.
The derivative and the Riemann integral of a vector-valued function: an intrinsic derivative and a componentwise integral, The standard formulas on and on are inner products, Integrable functions on form a set closed under sums and scalar multiples, and , and For and integrable when , ; for , is integrable: componentwise complex-vector integrals agree with real integrals in , finite sums may be integrated termwise, and .
The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv|| and The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: the matrix operator norm is the maximum over unit vectors and .
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: for , the componentwise map is real-linear and satisfies . Thus [F4] applies to these complex matrix-valued integrands with the stated Euclidean norm.
Proof
By [F6], the componentwise complex integrals are the real vector integrals to which [F4] applies. For , a unit vector, and either weight or , [F5] bounds the exponential-series tail applied to by , which tends to zero by [F3]. By [F4], the norm of the integral of the weighted tail applied to is at most the same tail, uniformly in unit . Taking the maximum over unit by [F5] proves that the finite partial-sum integrals converge in operator norm to the corresponding matrix integral. The finite sums may be integrated term by term by componentwise linearity.
Substituting gives .
For each integer , . Therefore the first integral equals by [F1]; the equality is legitimate because the phi series converges absolutely by [F2].
The second integral is consequently by [F1], with convergence justified by [F2]. At the same series gives and , respectively, so no quotient or invertibility assumption is involved.
Exponential Euler and the two-stage ETD2 step maps
Definition
Let , , , and , with . The inputs and all displayed stages must lie in . The functions are the finite-matrix series of The phi-function family by everywhere-convergent series, whose convergence is supplied by The scalar and matrix phi series converge absolutely.
The exponential Euler map is
For the two-stage exponential time-differencing Runge–Kutta map ETD2, first form the exponential Euler predictor and then set These are exact mathematical step maps; an implementation must separately account for every approximate matrix-function action and arithmetic error.
One-step stability after removing the exact linear flow
Statement
Fix , , and define These constants are finite by continuity of the finite-matrix exponential. Let be -Lipschitz in its state variable on a common tube containing all states and stages below. For and an admissible , define the transformed maps Then and
Facts & Assumptions
Given: The finite matrix, interval, methods, Lipschitz constant, and tube in the Statement.
Exponential Euler and the two-stage ETD2 step maps: and have the displayed exponential Euler and ETD2 formulas, with the predictor .
A bounded linear operator between normed spaces, The operator norm as the least bound and as the unit-sphere or unit-ball supremum, Every finite-dimensional normed space is Banach, and The exponential series of a bounded operator: finite-matrix exponentials are continuous, differentiable and satisfy .
The norm induced by a real or complex inner product, The standard formulas on and on are inner products, and The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: is the Euclidean vector norm and the induced operator norm.
The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2 and For and integrable when , ; for , is integrable: products obey , and vector integrals obey .
The exponential series of a bounded operator: for finite on the finite-dimensional Banach space , for . For , nonnegativity of gives , so scalar exponential monotonicity (The exponential function is strictly increasing) gives . Both sets contain at and are therefore bounded above by ; Dedekind completeness: the least-upper-bound property supplies finite suprema.
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: for , is real-linear and satisfies . Thus the real vector-integral estimate [F5] applies to the complex-valued integrands with the same norms.
On the stated tube, , and all transformed inputs and ETD2 predictor stages considered in the Statement remain admissible.
Proof
By [F6], the defining sets are nonempty and bounded, so and are finite. Substituting into the exponential Euler formula and using [F2]–[F3] gives . For , [A1] and [F4] bound the integrand difference by ; by [F7] the real integral norm inequality [F5] applies and integration over length proves the first inequality.
Let . The same identity as in step 1.1 gives , hence [F3] and the first bound imply .
Applying [F2] to both ETD2 coefficients gives . By [A1] and step 2.1, the bracket difference for has norm at most . Multiplying by the kernel bound and applying [F7] to use the real integral norm bound [F5] gives coefficient , since both weight integrals equal . As , this is at most .
Exponential Euler has a second-order local defect
Statement
In the finite-matrix setting of Exponential Euler and the two-stage ETD2 step maps, let and let solve on , with admissible states and stages. Put . Suppose is continuously differentiable with , and let . Then the exact-start local defect of the exponential Euler map satisfies
Facts & Assumptions
Given: The exact semilinear solution, its forcing curve , the finite matrix, and the bounds in the Statement.
If is differentiable with integrable then ; and a bounded derivative makes Lipschitz: a continuously differentiable vector curve with derivative norm bounded by is -Lipschitz on its closed interval, including its endpoints.
The norm induced by a real or complex inner product, The standard formulas on and on are inner products, The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, and For and integrable when , ; for , is integrable: the induced Euclidean matrix norm bounds its action on vectors, and .
The forcing derivative obeys the stated bound , and for .
A bounded linear operator between normed spaces, The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, Every finite-dimensional normed space is Banach, and The exponential series of a bounded operator: for finite on , . For , nonnegativity of gives , so scalar exponential monotonicity (The exponential function is strictly increasing) gives . The set defining contains at and is therefore bounded above by ; completeness of (Dedekind completeness: the least-upper-bound property) supplies its finite supremum.
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: for , is real-linear and satisfies . It maps real-time difference quotients to realified difference quotients and preserves their limits, so and its derivative are legitimate real vector data for [F4] with the same norm bound.
Proof
By [F6], is finite. Subtract [F1] from [F2] and replace the constant forcing term by its integral form [F3]. The local defect is .
By [F4], [F7], and [A1], . The semigroup factor has norm at most ; [F5] bounds the norm of step 1.1 by .
The two-stage ETD2 method has a third-order local defect
Statement
In the finite-matrix setting of Exponential Euler and the two-stage ETD2 step maps, let and let on , with admissible states and stages. Let . Suppose , , , is -Lipschitz in its state variable on a tube containing the exact path and predictor, and . Set . Then the exact-start defect of satisfies
Facts & Assumptions
Given: The exact solution, forcing curve, Lipschitz tube, and bounds in the Statement.
Variation of constants for a finite-matrix semilinear system: the exact endpoint is the exponential-linear term plus .
Exponential Euler and the two-stage ETD2 step maps: the ETD2 predictor is and its correction uses at and at .
Exponential Euler has a second-order local defect: the exact-start predictor obeys .
If is differentiable with integrable then ; and a bounded derivative makes Lipschitz and For and integrable when , ; for , is integrable: Taylor integral remainders and their norms are bounded componentwise.
The norm induced by a real or complex inner product, The standard formulas on and on are inner products, and The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: vector and induced matrix norms are the Euclidean norms used in the bounds.
The second derivative bound , state Lipschitz bound , and semigroup bound hold on the complete path and predictor tube.
A bounded linear operator between normed spaces, The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, Every finite-dimensional normed space is Banach, and The exponential series of a bounded operator: for finite on , . For , nonnegativity of gives , so scalar exponential monotonicity (The exponential function is strictly increasing) gives . The set defining contains at and is therefore bounded above by ; completeness of (Dedekind completeness: the least-upper-bound property) supplies its finite supremum.
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: for , is real-linear and satisfies . It preserves real-time difference quotients and their limits, so the real vector-valued FTC and integral norm bound in [F4] apply to the complex forcing curve with the same norms.
Proof
By [F7], the real vector-valued FTC in [F4] applies to the complex curve and preserves its norm. Write . Twice integrating the bound on from [F4] gives and , with and . Therefore .
By [L1] and [A1], the endpoint forcing difference satisfies .
Substituting [F3] into [F2] shows the ETD2 correction equals . Subtracting this from [F1] gives .
By [F6], is finite. By [A1], [F4]–[F5], [F7], and step 1.1, the interpolation contribution in step 2.1 is at most . Its stage contribution is at most . Adding these bounds proves the claimed estimate.
Certified-action implementation of exponential Euler and ETD2
Definition
Inputs: , , , a state , a step with , a method choice or , a field , a nonnegative state-Lipschitz bound on an admitted tube containing the input and, when method is selected, the exact and computed ETD2 predictor stages, a certified semigroup bound for with and , finite Arnoldi budgets , , , certified field-evaluation, membership, scalar-enclosure, and vector-arithmetic providers, and a finite integer cap for all nested backend/provider calls in this step. Each service call must terminate for the supplied finite budgets, supply a finite pre-call upper bound for its total nested call count, and return its actual call count and work counters. The step is admissible only when the initial state and every evaluated stage have certified membership in and, for method , the exact ETD2 predictor also has certified membership in ; every needed service-call bound must fit within the remaining .
Arnoldi configuration inputs: a nonnegative breakdown threshold , a choice of exact-arithmetic Arnoldi or a finite-precision Arnoldi backend, and a reduced-action configuration provider for Arnoldi projection for exponential and phi-function actions. For each generated reduced request , supplies the exactly represented call time , a rational upper bound on , rational upper bounds on and , a positive rational tolerance, integer budgets and , and certified Taylor, scalar-scaling, and final-projection arithmetic providers. Here for the direct exponential request and for an augmented request. These configuration services obey the same finite-termination and nested-count contracts as the other providers. If an exact call time or any required bound or configuration is unavailable, the action request returns inconclusive.
For each nonzero Arnoldi action request with matrix , positive time , and input , the backend must certify a relation with , when , , , , , with , and with . Its reduced-action certificate may be used only when the reduced scaled-Taylor call has success: Scaled Taylor action has a finite normwise truncation and roundoff certificate then bounds that call's error, and any subsequent scaling error is included. The backend also returns a final-projection error , an actual work record, and its total nested-call count. Missing or uncertified bounds, work counters, or call counts make that request inconclusive. In exact Arnoldi, the exact relation, initial representation, and orthonormal basis supply the corresponding relation bounds.
For each positive-time request, compute the full action-error bound from Arnoldi action error is the semigroup-weighted residual integral using If any required quantity or its upward-rounded arithmetic enclosure is missing, return inconclusive. Define an action request for as follows. If , return the exact zero vector with bound zero and zero action work before constructing any augmented matrix. For and , call Arnoldi projection for exponential and phi-function actions with matrix , time , input , index , and budget . For and , use Phi recurrence and augmented-matrix action identities: let have ones on its superdiagonal, let be the first and last coordinate vectors in , set and call Arnoldi projection for exponential and phi-function actions with matrix , time , input , index , and budget . Every nonzero call also receives threshold , the supplied Arnoldi mode/backend, and reduced-action configuration provider ; pass each generated to for the index-zero reduced call. Here ; the zero-phi-input shortcut was applied to before forming this augmented request. By Phi recurrence and augmented-matrix action identities, the top coordinates of equal . In either nonzero case compute the full action-error bound using its certified Arnoldi relation and successful reduced-action certificate, then project to the requested vector; coordinate projection cannot increase the Euclidean error. Here .
The calling implementation instruments each Arnoldi projection for exponential and phi-function actions request and its nested providers, then returns the actual work counters and total nested-call count with that action result. The work record is : counts actual products with , including the upper-left multiplication inside each augmented product; counts products with every other matrix, including augmented and reduced matrices and final projection matrices; records the backend's declared matrix-function work for dense implementations. These are type-specific counters rather than a sum. The algorithm sums each field across every service call and returns the totals. Each backend/provider call contributes its actual nested-call count to ; a call may begin only when its certified pre-call upper count fits in . If a count is missing, inconsistent, or exceeds its pre-call bound, return inconclusive with the accrued counters. Set Use and as the respective operator-norm bounds for and . Their validity, and termination and work-counter accounting under the stated service contracts, are proved separately in Certified action bounds control one exponential-integrator step ↗.
Outputs: a candidate next state when available, a nonnegative one-step action-error bound only with certified status, the actual work counters described above, total nested-call count , and status certified, inconclusive, or invalid-input.
Procedure:
- Initialize all work counters and to zero. Reject malformed dimensions, budgets, method choice, time step, Arnoldi threshold/mode/reduced-action configuration, semigroup/evaluation/arithmetic configuration, or a certified-false membership check for the input state or, when method is selected, the exact ETD2 predictor with
invalid-input. If any needed membership check or service-call upper bound cannot be certified, or the global call budget cannot fit a required service call, returninconclusive. A failed provider response with no sound bound isinconclusive. - Evaluate as with a certified error , reserving its pre-call upper count first and then adding its actual count to . Request and , reserving and accumulating their call/work counters. A zero phi input is handled by before any Arnoldi call. If a request is inconclusive, return inconclusive without accepting a step. Denote the candidates by and and their bounds by .
- For method , form . If bounds the scalar/vector arithmetic error in this combination and its provider call fits the remaining call cap, accumulate its counters and set
- For method , first form the predictor candidate using a certified arithmetic provider and accumulate its work/call counters. Check for certified membership in the domain and admitted tube before evaluating . A certified-false membership result returns
invalid-input; an inconclusive membership result returnsinconclusive. If bounds the predictor arithmetic error, set . Evaluate as with a certified error , reserving and accumulating its service counters. Request and ; if either request is inconclusive, return inconclusive without accepting a step. With their action-error bounds , form where and are the two candidates. If bounds the final combination arithmetic error and its provider call fits the remaining call cap, accumulate its counters and set - Before returning
certified, verify all action calls have certified Arnoldi relations, reduced-action statussuccess, and certified final projections; all field-evaluation and arithmetic bounds are finite; all returned work/call counters are present and within their pre-call bounds; and the displayed scalar calculations have certified upward enclosures. If any check fails, returninconclusiveand do not accept the step. Return the accrued work record and with every status.
Every scalar bound computation, including , , and , is rounded upward with a certified enclosure; if its enclosure is missing or fails to dominate the exact expression, return inconclusive. The returned work record is the sum of the actual counts supplied by the services for the action requests and arithmetic/evaluation operations. The finite call cap and each finite nested-action budget are checked before calls; the exact mathematical map is not a zero-cost oracle.
Certified action bounds control one exponential-integrator step
Statement
Suppose Certified-action implementation of exponential Euler and ETD2 returns certified status with per-action, field-evaluation, arithmetic, and semigroup bounds as in its Definition. Let or be the corresponding exact map of Exponential Euler and the two-stage ETD2 step maps, and let be the returned candidate map. Then the algorithm's reported value satisfies
For the algorithm's semigroup data, satisfies For every admissible input whose services obey the declared finite-termination, pre-call upper-count, and valid returned-count/work-record contracts, the algorithm terminates with one of its stated statuses. It returns a total nested-call count , and each component of its work record is the sum of the actual corresponding service counters accrued before return. These are counts of the declared work, without a wall-clock bound.
Facts & Assumptions
Given: A certified algorithm run and the exact method map with the same input data. For the termination and accounting clause, take any admissible input with the finite-service, pre-call upper-count, and valid returned-count/work-record contracts in the Statement.
Phi recurrence and augmented-matrix action identities: for , the top block of is exactly .
Arnoldi action error is the semigroup-weighted residual integral: for positive action time , a certified relation bounds the action error by an initial-mismatch term, the residual integral, the reduced-action error multiplied by , and the final-projection error.
Certified-action implementation of exponential Euler and ETD2, The Euclidean logarithmic norm of a complex matrix: each nonzero action request supplies , , , , and certified Arnoldi/reduced/projection data; its action bound is . Here is the logarithmic norm. For , the candidate’s top coordinates approximate and coordinate projection cannot increase Euclidean error.
Exponential Euler and the two-stage ETD2 step maps: the exact maps are and .
Integral representations of the first two phi functions: and , with componentwise matrix integrals.
The norm induced by a real or complex inner product, The standard formulas on and on are inner products, The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, and The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: , and induced matrix norms bound actions on vectors.
The exponential function is strictly increasing: the scalar exponential is increasing, so certified upper bounds on exponents give upper bounds on their exponentials.
Cauchy–Schwarz: , with equality exactly for linearly dependent vectors: coordinate functionals satisfy for unit coordinate vectors.
Scaled Taylor action has a finite normwise truncation and roundoff certificate and Arnoldi projection for exponential and phi-function actions: reduced_action_status=success requires a successful scaled-Taylor call; its returned error bound is valid by the theorem, and for the certified scaling error is added to form . Thus the reduced-action premise required by [F2] is met whenever the outer algorithm accepts a request.
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: the componentwise map is real-linear and satisfies . Thus For and integrable when , ; for , is integrable applies to continuous complex-vector curves through this norm-preserving realification. Componentwise linearity (Integrable functions on form a set closed under sums and scalar multiples, and ) permits a fixed matrix/vector action to pass through these integrals. The exponential curves are continuous by The exponential series of a bounded operator.
Certified-action implementation of exponential Euler and ETD2: the procedure has a finite sequence of method branches, initializes its work record and nested-call counter to zero, starts each service only when its pre-call upper count fits the remaining cap, adds each returned actual count and work record, and returns the accrued counters with every status.
The field-evaluation errors, Lipschitz constant, semigroup bound, and arithmetic errors used by the algorithm are valid upper bounds; for ETD2, the exact and computed predictors lie in the common admitted tube where the Lipschitz bound applies.
Proof
For a nonzero action request, [F11] makes the scaled-Taylor output certificate a valid ; put in [F2]. By [F8] and , ; [F10] gives . Since , [F9] bounds the initial term in [F2] by and its integral by . The reduced and final projection terms are at most by [F7]. Thus [F3]'s bounds the full exponential-action error. For a zero input, the algorithm returns the exact zero action with bound zero.
For , put . Then and : for this follows from , and for it follows from . The semigroup bound in [A1] and scalar monotonicity [F9] therefore give . For each unit vector , [F5] and componentwise linearity in [F12] yield and the analogous identity with weight for . These curves are continuous by [F12]. Apply the norm inequality in [F12] and the matrix-action inequality in [F7]: the two norms are at most and . Taking the operator-norm maximum over unit vectors in [F7], valid since is an input condition, proves both asserted phi bounds.
For exponential Euler, the exact formula [F4] applies to and to . [F3] supplies action-error bounds for and the full augmented action whose top block is by [F1]; coordinate projection cannot increase its error. Replacing by changes the phi action by at most by step 1.2 and [A1]. Multiplication by and the certified combination error give the exponential-Euler .
For ETD2, the predictor's difference from the exact predictor is at most by the triangle inequality, using the exponential-Euler estimate from step 2.1. Therefore the exact stage forcing differs from the evaluated by at most , using [A1].
Using the phi bounds proved in step 1.2, in the final ETD2 update, the action at contributes at most ; the action at contributes at most ; and the stage action contributes at most . Each phi action certificate follows from [F1] and step 1.1. The exponential action contributes . Multiplying the three phi terms by , adding the certified final arithmetic error , and applying the triangle inequality gives exactly the ETD2 in [F3].
Under the stated service contracts, each started backend/provider call terminates, including every call nested inside an Arnoldi or reduced-action request. Outside these services the procedure has a fixed finite sequence of branches: at most two action requests for method and four for method , together with finitely many field, membership, enclosure, and vector-arithmetic requests. A missing certificate or insufficient pre-call allowance returns immediately, and every started service returns in finite time by its contract, so the entire algorithm terminates. For the counters, begin with and . Before a service starts, its certified upper count satisfies ; its valid returned actual count obeys , so the update gives . Induction over the finitely many completed top-level services proves the count bound, with their nested work already included in their returned records. At each such update, the algorithm also adds the actual service work record componentwise to . The same finite induction makes each component exactly the sum of its accrued actual counters; an early return retains these accrued totals. Zero-input action shortcuts contribute zero action work. This proves termination and the advertised accounting without adding calls or presuming that a missing mathematical certificate succeeds.
Fixed-matrix global orders and certified-action error propagation
Statement
Let , , , , , and let be open after realification, with . Let solve Suppose the exact path, every numerical state, and every ETD2 predictor lie in a common compact time-state tube with positive margin. Also assume the hypotheses of One-step stability after removing the exact linear flow hold on this tube: compared inputs in each time fiber and both associated ETD2 predictor states are admissible, and is -Lipschitz between the states and stages used there. Finally, let be with and . Assume and put These finite-matrix suprema are finite; in particular . Define For an exact-action exponential-Euler run use ; for exact-action ETD2 use . If for and , then exact initial data give
Now let a certified-action implementation return candidates and certified one-step action-error bounds as in Certified action bounds control one exponential-integrator step. Starting from , its error obeys Thus local orders one and two imply fixed-, finite-dimensional global orders one and two when exact actions are used or when . The constants may depend on , , the tube, and the derivative bounds. The bounds are not asserted uniformly over varying matrices or growing dimensions; no unbounded-operator/PDE convergence theorem follows without the additional domain and commutator hypotheses such a theorem requires.
Facts & Assumptions
Given: The matrix, grid, solution, tube, regularity, Lipschitz and semigroup bounds, and numerical action certificates in the Statement.
First-order systems, initial value problems, and solutions on intervals: the exact solution is differentiable and satisfies .
Exponential Euler has a second-order local defect: the exact-start exponential-Euler defect is at most .
The two-stage ETD2 method has a third-order local defect: the exact-start ETD2 defect is at most .
One-step stability after removing the exact linear flow: after the change , the exponential-Euler and ETD2 one-step maps have stability constants and in the form .
Certified action bounds control one exponential-integrator step: when the action algorithm is certified, .
A bounded linear operator between normed spaces, The operator norm as the least bound and as the unit-sphere or unit-ball supremum, Every finite-dimensional normed space is Banach, The exponential series of a bounded operator, and Sums, scalar multiples, products and quotients: , , , and when : on the matrix exponential is continuous and differentiable, with and the semigroup law, and finite-dimensional products obey the product rule.
The exponential addition formula and The exponential function is strictly increasing: and whenever .
The norm induced by a real or complex inner product, The standard formulas on and on are inner products, The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, and The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: the vector norm is Euclidean, the matrix norm is induced, and .
The Euclidean inner product on and Cauchy-Schwarz with its equality case, the triangle inequality for , the parallelogram law and polarisation: the realified time-state space with its standard Euclidean norm is a normed space.
A compact set and a disjoint closed set have a positive norm-distance gap: a compact subset of an open subset of a finite-dimensional normed space has positive distance from its closed complement when that complement is nonempty; if it is empty, every positive radius is a margin.
Metric continuity characterisations, with countable choice for the sequential converse: a continuous map between metric spaces has open preimages of open sets.
is the real coordinate plane, with coordinate arithmetic, The standard formulas on and on are inner products, and The norm induced by a real or complex inner product: for , the componentwise map is real-linear, with . It preserves real-time difference quotients and their limits, so the real one-step theorem applies to the realified system and its transformed state without changing the error norm.
The exponential series of a bounded operator gives for . Since , scalar monotonicity (The exponential function is strictly increasing) gives . Thus the set defining contains at and has that finite upper bound; Dedekind completeness: the least-upper-bound property supplies its finite supremum. Likewise , so the assumed semigroup bound and the same scalar monotonicity give and a finite supremum for its nonempty defining set.
Global error from uniform one-step defect and stability: on a common compact tube, exact-start local defect , one-step stability , and exact initial values imply the fixed-time global bound .
The transformed open domain and compact tube satisfy the hypotheses stated above; the realified norm and coordinate calculus are as in [F13].
Proof
By [F13], the complex state equation and the transformed equation are real finite-dimensional systems with the same Euclidean error norm. Set . The product rule and [F1], [F6] give . Conjugating the exact numerical map and exact endpoint by cancels their common linear term and multiplies their difference by . Hence [F2], [F3], and [F9] give transformed exact-start defects at most and .
By [F14], both amplification suprema used here are finite. Set , open as the preimage of under the continuous map by [F6], [F9], [F10], and [F12]. The map continuously sends to a compact tube in containing the transformed exact path, states, and stages; [F10]–[F11] give positive margin. Its stability is by [F4], and its local constant is by step 1.1. Thus [L1] applies with exact initial data.
For certified actions, put and . Stability [F4], local defect [F2] or [F3] transformed by [F6] and step 1.1, and perturbation bound [F5] transformed using [F9] by give by the triangle inequality , with .
Applying [L1] as in step 2.1 yields . Since and [F9] with the definition of bounds multiplication by , this gives the first displayed bound.
Induction in step 2.2 gives : the base case is the empty sum, and multiplying the bound for by and adding the defect and action terms gives the formula for .
Since by [F7], each power in step 3.2 is at most by [F8] and . Also , so . Thus . Multiplication by and [F9] with the bound give the certified-action estimate for every , hence for their maximum.
5 · Examples, counterexamples and false statements
None yet.
Sources
- Marlis Hochbruck and Alexander Ostermann, Exponential Integrators, Acta Numerica 19 (2010), §1
- ISEM Team 2011/12, Operator Semigroups for Numerical Analysis, 15th Internet Seminar on Evolution Equations
- Marlis Hochbruck and Alexander Ostermann, Exponential Integrators, Acta Numerica 19 (2010)
- Jitse Niesen and Will M. Wright, A Krylov Subspace Algorithm for Evaluating the Phi-Functions Appearing in Exponential Integrators, arXiv:0907.4631v2