Calculation of exact bounds for the solution set of linear interval systems
From MaRDI portal
An algorithm for calculating the exact bounds for each component of the solution set of a linear interval system is described. This problem is known to be NP-hard. The proposed algorithm gives an error message if the solution is unbounded. The computations are done in \(p\) calls of a polynomial time algorithm, where \(p\) is the number of orthants intersecting the problem set. It is shown that the NP-hardness of the problem stems form the fact that the solution set may intersect exponentially many orthants.
Recommendations
- Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
- Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard
- Checking bounds on solutions of linear interval equations is NP-hard
- Enclosing solutions of linear interval equations is NP-hard
- scientific article; zbMATH DE number 804135
Cites work
- A Quadratically Convergent Krawczyk-Like Algorithm
- An Interval Arithmetic Approach for the Construction of an Almost Globally Convergent Method for the Solution of the Nonlinear Poisson Equation on the Unit Square
- Checking bounds on solutions of linear interval equations is NP-hard
- Checking robust nonsingularity is NP-hard
- Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
- Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
- Die Überschätzung des Wertebereichs einer Funktion in der Intervallrechnung mit Anwendungen auf lineare Gleichungssysteme
- Enclosing solutions of linear interval equations is NP-hard
- scientific article; zbMATH DE number 3649911 (Why is no real title available?)
- scientific article; zbMATH DE number 3880009 (Why is no real title available?)
- scientific article; zbMATH DE number 3766957 (Why is no real title available?)
- scientific article; zbMATH DE number 3471507 (Why is no real title available?)
- scientific article; zbMATH DE number 524107 (Why is no real title available?)
- scientific article; zbMATH DE number 714516 (Why is no real title available?)
- scientific article; zbMATH DE number 714524 (Why is no real title available?)
- scientific article; zbMATH DE number 733109 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 802437 (Why is no real title available?)
- scientific article; zbMATH DE number 3410518 (Why is no real title available?)
- Interval iteration for zeros of systems of equations
- Interval linear systems with symmetric matrices, skew-symmetric matrices and dependencies in the right hand side
- On the Solution Set of a Linear System with Inaccurate Coefficients
- Optimale Lösung von Intervallgleichungssystemen
- Systems of linear interval equations
Cited in
(33)- Interval estimations of solution sets to real-valued systems of linear or non-linear equations
- On the optimal solution set in interval linear programming
- Centered solutions for uncertain linear equations
- Parametric deconvolution of positive spike trains.
- On \(P\)-matrices
- On the solution sets of particular classes of linear interval systems
- Calculation of a sharp Lipschitz constant for a system of linear inequalities
- Checking bounds on solutions of linear interval equations is NP-hard
- Inner estimation of the united solution set of interval linear algebraic system
- Interval tensors and their application in solving multi-linear systems of equations
- Solving interval linear programming problems with equality constraints using extended interval enclosure solutions
- An algorithm for computing the hull of the solution set of interval linear equations
- Extremal results for algebraic linear interval systems
- scientific article; zbMATH DE number 5836227 (Why is no real title available?)
- Interval Polyhedra: An Abstract Domain to Infer Interval Linear Relationships
- scientific article; zbMATH DE number 2032311 (Why is no real title available?)
- Regularity radius: properties, approximation and a not a priori exponential algorithm
- Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
- Inverse linear programming with interval coefficients
- On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data
- Inverse of a fuzzy matrix of fuzzy numbers
- On solving vague systems of linear equations with pattern-shaped columns
- On solvability recognition for interval linear systems of equations
- A new methodology for solving fuzzy systems of equations: thick fuzzy sets based approach
- The vertex solution theorem and its coupled framework for static analysis of structures with interval parameters
- A general method for enclosing solutions of interval linear equations
- Bounding the solution set of overdetermined system of interval linear equations
- Absolute value equations with 2ⁿ solutions
- Basis stability in interval quadratic programming
- The bounds on components of the solution for consistent linear systems
- Direct methods for linear systems with inexact input data
- On regular and singular interval systems
- Interval linear systems: the state of the art
This page was built for publication: Calculation of exact bounds for the solution set of linear interval systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961705)
