Algorithms

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]

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]

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]

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]

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]

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}}}

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

Skalna06

Direct solver for interval linear systems with affine-parametric dependency. For more information see [SKA06].