A Shaving Method for Interval Linear Systems of Equations
We propose an iterative improvement method for an enclosure of the solution set of a system of interval linear equations. The method sequentially cuts off (shaves) parts of a given enclosure that contain no solution, yielding thus tighter enclosures. Sinc
- PDF / 211,743 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 194 Views
ract. We propose an iterative improvement method for an enclosure of the solution set of a system of interval linear equations. The method sequentially cuts off (shaves) parts of a given enclosure that contain no solution, yielding thus tighter enclosures. Since shaving can be done independently in the coordinates, the procedure is easily parallelized. Our approach is convenient for problems with wide input intervals, where traditional methods give poor enclosures. Finally, we present a limited computational study.
Keywords: Interval systems
1
· Interval matrix · Parallelization
Introduction
Solving systems of linear equations is a fundamental problem in linear and numerical algebra, and many other disciplines. Taking into account uncertain measurements, errors and other inexactness, and handling these uncertainties by the ranges of admissible values, we immediately face the problem of solving systems with interval coefficients. Considering all possible evaluations of interval data, the objective is to determine or at least tightly enclose all emerging solutions. It is known that computing the optimal bounds for the solution is an NP-hard problem [2,6] (even with a prescribed accuracy). That is why developing efficient algorithms for computing reasonably tight enclosures was a subject of intensive research. Nowadays, there are many methods published [2,4,7–9,14], but there is still enough open space for improvement. In this paper, we propose a method, that, given an initial enclosure, iteratively cuts off some parts provably containing no solution. This approach is called shaving, which is borrowed from the area of constraint satisfaction problems [3,16]. Notation. The ith row of a matrix A is denoted by Ai∗ , the jth column by A∗j , and the unit vector by ei := (0, . . . , 0, 1, 0, . . . , 0)T . The vector e = (1, . . . , 1)T is the vector of ones. An interval matrix is defined as R. Wyrzykowski et al. (Eds.): PPAM 2013, Part II, LNCS 8385, pp. 573–581, 2014. c Springer-Verlag Berlin Heidelberg 2014 DOI: 10.1007/978-3-642-55195-6 54,
574
M. Hlad´ık and J. Hor´ aˇcek
A = [A, A] = {A ∈ Rm×n | A ≤ A ≤ A}, where A ≤ A are fixed matrices. The set of all m × n interval matrices is denoted by IRm×n . By 1 1 (A + A), AΔ := (A − A) 2 2 we denote the midpoint and radius of A, respectively. Interval arithmetic is defined, e.g., in books [7,8]. Ac :=
Interval Linear Systems. An interval linear system of equations is a family of systems Ax = b, A ∈ A, b ∈ b, where A ∈ IRn×n and b ∈ IRn are given. The corresponding solution set is defined as Σ := {x ∈ Rn | ∃A ∈ A ∃b ∈ b : Ax = b}. Any interval vector x ∈ IRn containing Σ is called an enclosure of Σ. There are various methods for computing more or less tight enclosures of the solution set; see [2,4,7–9,14]. A linear relaxation method with iterative contraction of the enclosure was presented in [1]. Notice that a more general concept of solutions, so called AE-solutions, was studied, e.g., in [11,15].
2
A Shaving Method
Let x 0 ∈ IRn be an initial enclosure of the solution set
Data Loading...
