# Algorithms

Algorithms used to solve interval linear systems.

## Enclosure computation

### Direct methods

IntervalLinearAlgebra.GaussianEliminationType
GaussianElimination <: AbstractDirectSolver

Type for the Gaussian elimination solver of the square interval linear system $Ax=b$. For more details see section 5.6.1 of [HOR19]

Notes

• An object of type GaussianElimination is a callable function with method

  (ge::GaussianElimination)(A::AbstractMatrix{T},
b::AbstractVector{T}) where {T<:Interval}

Examples

julia> A = [2..4 -1..1;-1..1 2..4]
2×2 Matrix{Interval{Float64}}:
[2, 4]  [-1, 1]
[-1, 1]   [2, 4]

julia> b = [-2..2, -1..1]
2-element Vector{Interval{Float64}}:
[-2, 2]
[-1, 1]

julia> ge = GaussianElimination()
GaussianElimination linear solver

julia> ge(A, b)
2-element Vector{Interval{Float64}}:
[-1.66667, 1.66667]
[-1.33334, 1.33334]
source
IntervalLinearAlgebra.HansenBliekRohnType
HansenBliekRohn <: AbstractDirectSolver

Type for the HansenBliekRohn solver of the square interval linear system $Ax=b$. For more details see section 5.6.2 of [HOR19]

Notes

• Hansen-Bliek-Rohn works with H-matrices without precondition and with strongly regular matrices using InverseMidpoint precondition

• If the midpoint of $A$ is a diagonal matrix, then the algorithm returns the exact hull.

• An object of type Hansen-Bliek-Rohn is a callable function with method

  (hbr::HansenBliekRohn)(A::AbstractMatrix{T},
b::AbstractVector{T}) where {T<:Interval}

Examples

julia> A = [2..4 -1..1;-1..1 2..4]
2×2 Matrix{Interval{Float64}}:
[2, 4]  [-1, 1]
[-1, 1]   [2, 4]

julia> b = [-2..2, -1..1]
2-element Vector{Interval{Float64}}:
[-2, 2]
[-1, 1]

julia> hbr = HansenBliekRohn()
HansenBliekRohn linear solver

julia> hbr(A, b)
2-element Vector{Interval{Float64}}:
[-1.66667, 1.66667]
[-1.33334, 1.33334]
source

### Iterative methods

IntervalLinearAlgebra.GaussSeidelType
GaussSeidel <: AbstractIterativeSolver

Type for the Gauss-Seidel solver of the interval linear system $Ax=b$. For details see Section 5.7.4 of [HOR19]

Fields

• max_iterations – maximum number of iterations (default 20)
• atol – absolute tolerance (default 0), if at some point $|xₖ - xₖ₊₁| < atol$ (elementwise), then stop and return $xₖ₊₁$. If atol=0, then min(diam(A))*1e-5 is used.

Notes

• An object of type GaussSeidel is a function with method

  (gs::GaussSeidel)(A::AbstractMatrix{T},
b::AbstractVector{T},
[x]::AbstractVector{T}=enclose(A, b)) where {T<:Interval}

#### Input

• A – N×N interval matrix
• b – interval vector of length N
• x – (optional) initial enclosure for the solution of $Ax = b$. If not given, it is automatically computed using enclose

Examples

julia> A = [2..4 -1..1;-1..1 2..4]
2×2 Matrix{Interval{Float64}}:
[2, 4]  [-1, 1]
[-1, 1]   [2, 4]

julia> b = [-2..2, -1..1]
2-element Vector{Interval{Float64}}:
[-2, 2]
[-1, 1]

julia> gs = GaussSeidel()
GaussSeidel linear solver
max_iterations = 20
atol = 0.0

julia> gs(A, b)
2-element Vector{Interval{Float64}}:
[-1.66668, 1.66668]
[-1.33334, 1.33334]
source
IntervalLinearAlgebra.JacobiType
Jacobi <: AbstractIterativeSolver

Type for the Jacobi solver of the interval linear system $Ax=b$. For details see Section 5.7.4 of [HOR19]

Fields

• max_iterations – maximum number of iterations (default 20)
• atol – absolute tolerance (default 0), if at some point $|xₖ - xₖ₊₁| < atol$ (elementwise), then stop and return $xₖ₊₁$. If atol=0, then min(diam(A))*1e-5 is used.

Notes

• An object of type Jacobi is a function with method

  (jac::Jacobi)(A::AbstractMatrix{T},
b::AbstractVector{T},
[x]::AbstractVector{T}=enclose(A, b)) where {T<:Interval}

#### Input

• A – N×N interval matrix
• b – interval vector of length N
• x – (optional) initial enclosure for the solution of $Ax = b$. If not given, it is automatically computed using enclose

Examples

julia> A = [2..4 -1..1;-1..1 2..4]
2×2 Matrix{Interval{Float64}}:
[2, 4]  [-1, 1]
[-1, 1]   [2, 4]

julia> b = [-2..2, -1..1]
2-element Vector{Interval{Float64}}:
[-2, 2]
[-1, 1]

julia> jac = Jacobi()
Jacobi linear solver
max_iterations = 20
atol = 0.0

julia> jac(A, b)
2-element Vector{Interval{Float64}}:
[-1.66668, 1.66668]
[-1.33335, 1.33335]
source
IntervalLinearAlgebra.LinearKrawczykType
LinearKrawczyk <: AbstractIterativeSolver

Type for the Krawczyk solver of the interval linear system $Ax=b$. For details see Section 5.7.3 of [HOR19]

Fields

• max_iterations – maximum number of iterations (default 20)
• atol – absolute tolerance (default 0), if at some point $|xₖ - xₖ₊₁| < atol$ (elementwise), then stop and return $xₖ₊₁$. If atol=0, then min(diam(A))*1e-5 is used.

Notes

• An object of type LinearKrawczyk is a function with method

  (kra::LinearKrawczyk)(A::AbstractMatrix{T},
b::AbstractVector{T},
[x]::AbstractVector{T}=enclose(A, b)) where {T<:Interval}

#### Input

• A – N×N interval matrix
• b – interval vector of length N
• x – (optional) initial enclosure for the solution of $Ax = b$. If not given, it is automatically computed using enclose

Examples

julia> A = [2..4 -1..1;-1..1 2..4]
2×2 Matrix{Interval{Float64}}:
[2, 4]  [-1, 1]
[-1, 1]   [2, 4]

julia> b = [-2..2, -1..1]
2-element Vector{Interval{Float64}}:
[-2, 2]
[-1, 1]

julia> kra = LinearKrawczyk()
LinearKrawczyk linear solver
max_iterations = 20
atol = 0.0

julia> kra(A, b)
2-element Vector{Interval{Float64}}:
[-2, 2]
[-2, 2]
source

## Exact characterization

IntervalLinearAlgebra.LinearOettliPragerType
LinearOettliPrager <: AbstractDirectSolver

Type for the OettliPrager solver of the interval linear system $Ax=b$. The solver first converts the system of interval equalities into a system of real inequalities using Oettli-Präger theorem [OET64] and then finds the feasible set by solving a LP problem in each orthant using LazySets.jl.

Notes

• You need to import LazySets.jl to use this functionality.

• An object of type LinearOettliPrager is a function with methods

  (op::LinearOettliPrager)(A::AbstractMatrix{T},
b::AbstractVector{T}) where {T<:Interval}

#### Input

• A – N×N interval matrix
• b – interval vector of length N

Examples

julia> A = [2..4 -2..1;-1..2 2..4]
2×2 Matrix{Interval{Float64}}:
[2, 4]  [-2, 1]
[-1, 2]   [2, 4]

julia> b = [-2..2, -2..2]
2-element Vector{Interval{Float64}}:
[-2, 2]
[-2, 2]

julia> polytopes = solve(A, b, LinearOettliPrager());

julia> typeof(polytopes)
Vector{HPolytope{Float64, SparseArrays.SparseVector{Float64, Int64}}}
source
IntervalLinearAlgebra.NonLinearOettliPragerType
NonLinearOettliPrager <: AbstractIterativeSolver

Type for the OettliPrager solver of the interval linear system $Ax=b$. The solver first converts the system of interval equalities into a system of real inequalities using Oettli-Präger theorem [OET64] and then finds the feasible set using the forward-backward contractor method [JAU14] implemented in IntervalConstraintProgramming.jl.

Fields

• tol – tolerance for the paving, default 0.01.

Notes

• You need to import IntervalConstraintProgramming.jl to use this functionality.

• An object of type NonLinearOettliPrager is a function with methods

  (op::NonLinearOettliPrager)(A::AbstractMatrix{T},
b::AbstractVector{T},
[X]::AbstractVector{T}=enclose(A, b)) where {T<:Interval}

(op::NonLinearOettliPrager)(A::AbstractMatrix{T},
b::AbstractVector{T},
X::IntervalBox) where {T<:Interval}

#### Input

• A – N×N interval matrix
• b – interval vector of length N
• X – (optional) initial enclosure for the solution of $Ax = b$. If not given, it is automatically computed using enclose

Examples

julia> A = [2..4 -2..1;-1..2 2..4]
2×2 Matrix{Interval{Float64}}:
[2, 4]  [-2, 1]
[-1, 2]   [2, 4]

julia> b = [-2..2, -2..2]
2-element Vector{Interval{Float64}}:
[-2, 2]
[-2, 2]

julia> solve(A, b, NonLinearOettliPrager(0.1))
Paving:
- tolerance ϵ = 0.1
- inner approx. of length 1195
- boundary approx. of length 823
source