# Two Iterative Methods for Solving Linear Interval Systems

Authors: Esmaeil Siahlooei; Seyed Abolfazl Shahzadeh Fazeli
Journal: Applied Computational Intelligence and Soft Computing
 (2018)

---

## Abstract

Conjugate gradient is an iterative method that solves a linear systemAx=b, where A is a positive definite matrix. We present this new iterative method for solving linear interval systems Ãx̃=b̃, where Ã is a diagonally dominant interval matrix, as defined in this paper. Our method is based on conjugate gradient algorithm in the context view of interval numbers. Numerical experiments show that the new interval modified conjugate gradient method minimizes the norm of the difference of Ãx̃ and b̃ at every step while the norm is sufficiently small. In addition, we present another iterative method that solves Ãx̃=b̃, where Ã is a diagonally dominant interval matrix. This method, using the idea of steepest descent, finds exact solution x̃ for linear interval systems, where Ãx̃=b̃; we present a proof that indicates that this iterative method is convergent. Also, our numerical experiments illustrate the efficiency of the proposed methods.


---

## Body

## 1. Introduction

Solving system of linear equations is a well-known problem in linear algebra. Many practical problems are modeled as system of linear equations. These problems have been studied by many scientists and several methods have been proposed to solve them [1, 2]. But, in everyday life, measuring instruments just estimate values, and usually measured values are not accurate. Sometimes for more accuracy, intervals are used to represent the actual values. For example, the length of a metal rod is estimated between 24.221 and 24.222 centimeters, or temperature measured by a thermometer is between 27.6 and 27.7 Celsius.There are many types of uncertainty and there are many different mathematical systems that calculate uncertainties [3], e.g., rough sets theory [4], fuzzy numbers [5], probability theory [6], interval valued numbers [7], and dual fuzzy numbers [8]. In this paper, uncertainty is considered as interval numbers. Some articles used this model to solve their problems [9, 10].Using interval numbers in algebra was initially developed in the mid-1960s. In 1966, Moore presented his book on interval analysis [11]. Then Hansen offered a solution on interval linear algebraic equations [12]. Then many authors published their methods for solving linear interval systems, such as Neumaier, Abolmasoumi and Alavi, Nirmala, and Ganesan [13–15]. Nowadays, interval analysis methods have been applied to engineering problems, such as dynamic response analysis [16, 17], geotechnical structures [18], and control systems [19].In this paper, we introduce two new iterative methods for solving a linear interval system of equations that is a linear system involving uncertain coefficients appearing as interval numbers. The solution of this system is an interval vector.The present paper is organized as follows. The basic definitions related to interval numbers and linear interval systems are discussed in Section3. In Section 3.1, we introduce two additional interval operations. These are inverse operations of “−” and “+.” Section 3.2 recalls some properties of interval numbers and interval arithmetic. Also, it introduces some new properties on introduced operations. Next, we review conjugate gradient method and then present a new method for solving linear interval systems based on conjugate gradient method. Another new iterative method using steepest descent idea is proposed in Section 3.4. Section 4 shows the experimental results of the proposed methods and discusses the accuracy and efficiency of the new methods.


## 2. Interval Arithmetic

Interval numbers and arithmetic are explained in [7, 11, 13, 20]. We review main definition here. Given a,b∈R, where a≤b, the real bounded set (1)x~=x∣a≤x≤b=a,bis called aproper interval. The set of all proper intervals on R is denoted by IR. In this paper, all elements in IR are shown with a hat, i.e., x̃.Theinfimum andsupremum of x̃=a,b are x̲=a and x¯=b, respectively.Themagnitude is defined to be the maximum value of x for all x∈x̃. Thus(2)Magx̃=max⁡Absx∣x∈x̃=max⁡a,b.The width and midpoint of x̃ are denoted by w(x̃) and m(x̃), respectively, and defined as(3)wx̃=x¯-x̲(4)mx̃=x̲+x¯/2An interval number x̃ is defined as a subset of interval number ỹ when x̲≥y̲ and x¯≤y¯ and denoted by x̃⊆ỹ. Equality held when x̃=ỹ.Each real numbera∈R can be viewed as a special interval number ã=a,a. The interval a,a simply can be denoted by a without confusion.For each binary operation∗ which is defined on R, a binary operation ∗̃ is defined on IR as(5)x̃∗̃ỹ=x∗y∣x∈x̃,y∈ỹfor x̃,ỹ∈IR. Note that we will use operator ∗ for both interval and real numbers when there is no confusion.Therefore, basic interval arithmetic is defined in the following. Letx̃,ỹ∈IR; then(6)x̃+ỹ=x̲+y̲,x¯+y¯,(7)x̃-ỹ=x̲-y¯,x¯+y̲,(8)x̃×ỹ=min⁡x̲y̲,x̲y¯,x¯y̲,x¯y¯,max⁡x̲y̲,x̲y¯,x¯y̲,x¯y¯.(9)x̃/ỹ=x̃×1/ỹ:0∉ỹ,where(10)1/ỹ=1/y¯,1/y̲:0∉ỹ.Note that there is a simple alternative way to formulate the interval multiplication.Aninterval vector is a vector whose elements are interval numbers. Similarly, aninterval matrix is a matrix whose elements are interval numbers.Considers̃∈IRn, s∈Rn, Ã∈IRm×n, and A∈Rm×n. We say s∈s̃ if each element of vector s belongs to corresponding element of s̃ and A∈Ã if each element of matrix A belongs to the corresponding element of Ã.Norm of interval vectors̃ is defined in [21] as(11)norms̃=max1≤i≤nMags̃i.We define a square interval matrix asdiagonally magnitude dominant or for simplicitydiagonally dominant if(12)∀1≤i,j≤naij∈ãij:Absaii≥∑i≠jAbsaijProposition 1.
Interval matrixÃ∈IRn×n is diagonally dominant if and only if(13)∀1≤i,j≤nMigãii≥∑i≠jMagãijProof.
Equation (13) directly follows (12); just set aii=Mig(ãii) and aij=Mag(ãij) when i≠j.
If (13) holds then (14)∀aii∈ãii:Absaii≥Migãii,and(15)∀aij∈ãij:Magãii≥Absaij.Finally,(16)∀1≤i,j≤naij∈ãij:Absaii≥Migaii≥∑i≠jMagãij∑i≠jAbsaij.General matrix form of linear interval systems can be written as follows:(17)Ãx̃=b̃,where Ã is an interval matrix, x̃ is an interval vector solution, and b̃ is an interval vector.
To solve a linear interval system, there exist some different approaches [22–24]. Four of the well-known approaches are as follows:(1)
Find an interval vectorx̃ such that, for all x∈x̃, A∈Ã and b∈b̃ exist such that Ax=b (united solution set).(2)
Find an interval vectorx̃ such that, for all x∈x̃, for all A∈Ã, b∈b̃ exists such that Ax=b (tolerable solution set). Equivalently,(18)∀x∈x̃:Ãx⊆b̃(3)
Find an interval vectorx̃ such that, for all x∈x̃, for all b∈b̃, A∈Ã exists, such that Ax=b (controllable solution set). Equivalently,(19)∀x∈x̃:b̃⊆Ãx(4)
Find an interval vectorx̃ such that multiplication Ãx̃ is equal to b̃ (exact solution set).
United solutions are studied in [13, 25, 26]. In [22, 27] methods have been published to find tolerable solutions. Also, some methods have been developed to obtain controllable solutions [14, 28] and exact solutions [12, 14, 29–31] of interval linear systems.
Our proposed method calculates a solution forÃx̃=b̃ in the sense of the exact solution, where Ã is a diagonally dominant interval matrix.


## 3. Materials and Methods

### 3.1. Inverse Operations for “+” and “×”

Suppose we are given an equationã+x̃=ã, where ã is a known interval number, and x̃ is an unknown interval number, how can one find x̃?Obviouslyx̃=[0,0]=0 is the solution to this equation. However, ã-ã=[a̲-a¯,a¯-a̲] which is not equal to [0,0] unless a̲=a¯. If the operation “−” is inverse of the operation “+,” then x̃ must equal ã-ã. But x̃=0,0 and ã-ã≠0,0 unless a̲=a¯.As it can be observed, the operator “−” is not inverse of the operation “+.” Similarly, it can be observed that the operation “/” is not inverse of the operation “×.” Therefore, we propose the inverse of operations “+” and “×.”Before introducing inverse operations for “+” and “×,” we need another general type of intervals that is defined in [32, 33]. Ageneral closed intervala,b is identified by two real numbers a,b∈R and is defined as(20)a,b=x∈R∣a≤b∨b≤a.Thegeneral interval number space over real numbers is denoted by IR∗. Obviously, IR⊆IR∗. All definitions (supremum, infimum, and magnitude) and operations in IR∗ are defined the same as IR but computation over IR∗ is more complicated than IR. The arithmetic over IR∗ is well discussed in [20, 32, 33]. For example, [1,3]+[3,1]=[4,4] as in (7), or [1,2]×[3,1]=[3,2] as in (8). The width of a general interval number can be negative; for example, w([3,2])=-1. Also, according to definition of subset, [2,-2]⊆[0,0].In this paper, bygeneral interval, we mean general closed intervals.Forã,b̃∈IR∗, the operation “⊖” is defined in [20, 33] as(21)ã⊖b̃=a̲-b̲,a¯-b¯For ã,b̃∈IR, we define the operation “⊘” as(22)ã⊘b̃=-∞,+∞a̲=a¯=0,b̲=b¯=00,0a̲=a¯=0,b̲≠0orb¯≠0undefined∃x≠0,x∈ã,b̲=b¯=0undefined0∉a,0∈ba̲/b̲,a¯/b¯a̲≥0,b̲>00,a¯/b¯a̲=0,b̲=0a̲/b¯,a¯/b¯a̲≤0≤a¯,b̲≥0a̲/b¯,a¯/b̲a¯≤0,b̲>0a̲/b¯,0a¯=0,b̲=0ã⊘-b̃b¯≤0a̲/b¯,a¯/b¯a̲≥0,b̲<0<b¯max⁡a̲/b¯,a¯/b̲,min⁡a¯/b¯,a̲/b̲a̲≤0≤a¯,b̲<0<b¯a¯/b̲,a̲/b̲a¯≤0,b̲<0<b¯Note that this definition can handle many cases where 0 belongs to b̃, and just in three cases compute undefined or unbounded solution. This property lets us design algorithms with high stability and consistent when working with interval values that contain 0.In the following two theorems, we show that operations “⊖” and “⊘” are inverse of operations “+” and “×,” respectively [34].Theorem 2.
Givenã,b̃∈IR, then the interval equation ã+x̃∗=b̃ has a unique solution x̃∗=b̃⊖ã, where x̃∗∈IR∗. The equation ã+x̃∗=b̃ has a unique solution in IR if x̃∗∈IR; otherwise the equation ã+x̃∗=b̃ has no solution in IR but has exactly one in IR∗.Proof.
a ̃ + x ̃ = b ̃ ⇔ a ̲ , a ¯ + x ∗ ̲ , x ∗ ¯ = b ̲ , b ¯ . That is, b̲=a̲+x∗̲, which solves x∗̲=b̲-a̲. Similarly, x∗¯=b¯-a¯; therefore, we have x̃∗=b̃⊖ã, where x̃∗=[x∗̲,x∗¯].
Therefore ifã,b̃,x̃∈IR and ã+x̃=b̃, then x̃ can be found with this inverse operation uniquely.Theorem 3.
Givenã,b̃∈IR, then the interval equation ã×x̃∗=b̃ has a solution x̃∗=b̃⊘ã, where x̃∗∈IR∗. The equation ã×x̃∗=b̃ has a solution in IR if x̃∗∈IR; otherwise the equation ã×x̃∗=b̃ has no solution in IR but has in IR∗.Remark. Solution x̃∗ is not usually unique; e.g., the interval equation [-1,1]×x̃∗=[-2,2] has solutions [-1,2],[-2,0],[-2,2]. Actually, this equation has unlimited solutions. All intervals [u,2] and [-2,v] where -2≤u≤0 and 0≤v≤2 can be solution of this equation.In cases thatx̃∗ is not unique, x̃∗ is considered as the longest interval as possible. In the above example, x̃ must be [-2,2].Proof.
Supposeã×x̃=b̃. Before starting the proof, note that multiplication result, b̃, depends on the sign of ã and x̃. Table 1 shows sign of b̃ related to sign of ã and x̃ and also shows formulas of multiplication result.
Suppose that, givenã,b̃∈IR, ã×x̃=b̃, and a¯≤0 and 0∈b̃. Now, from Table 1, it is observed that the following must occur:  b̲≤0≤b¯ and b̃=[a¯x̲,a¯x¯]. Then(23)ãx̃=b̃⇔b̃=a̲x¯,a̲x̲⇔b̲=a̲x¯⇔x¯=b̲/x̲b¯=a̲x̲⇔x̲=b¯/x̲⇔x̃=b̃⊘ã.This means in this case x̃ is uniquely calculated by inverse operations of “×.” For other cases except cases with condition 0∈ã, one can provide similar proofs.
For cases with condition0∈ã, there is an ambiguity. From Table 1, there are three cases in column 0∈ã. They have the same conditions b̲≤0≤b¯. The solution can be in forms 0≤x̲, 0∈x̃, and 0≥x¯, respectively. The solution should be in form of 0∈x̃, because it is the longest possible interval solution and includes both of the others. Now, find x̲ and x¯. If xs̃ with condition 0∈xs̃ is the solution of ã×x̃=b̃, then b̃=mina¯xs̲,a̲xs¯,maxa̲xs̲,a¯xs¯. It follows that(24)b̲=min⁡a¯xs̲,a̲xs¯⇒b̲≤a¯xs̲⇒xs̲≥b̲/a¯,and(25)b¯=max⁡a̲xs̲,a¯xs¯⇒b¯≥a̲xs̲⇒xs̲≥b¯/a̲.Then,(26)xs̲≥max⁡b̲/a¯,b¯/a̲.If xs̲≠maxb̲/a¯,b¯/a̲, then xs̲>maxb̲/a¯,b¯/a̲, and a¯xs̲>maxb̲/,a¯b¯/a̲≥b̲. This contradicts with b¯=maxa̲xs̲,a¯xs¯. Hence(27)xs̲=max⁡b̲/a¯,b¯/a̲.Similarly,(28)xs¯=min⁡b¯/a¯,b̲/a̲,and therefore, we have xs̃=b̲⊘a̲.
In addition, special caseã=[0,0] should be considered separately. If ã=[0,0] and b̃≠[0,0], no x̃ exists such that ã×x̃=b̃. If ã=b̃=[0,0], then x̃ is free and expression ã×x̃=b̃ is consistent for all x̃. At this point x̃ is considered as [-∞,+∞].Table 1
Interval multiplication in detail.
a ̃ x ̃ = b ̃ 0 ≤ a ̲ 0 ∈ a ̃ a ¯ ≤ 0 0 ≤ x ̲ a _ x _ , a ¯ x ¯ a _ x ¯ , a ¯ x ¯ a _ x ¯ , a ¯ x _ 0 ≤ b _ , b ¯ b _ ≤ 0 ≤ b ¯ b _ , b ¯ ≤ 0 0 ∈ x ̃ a ¯ x _ , a ¯ x ¯ min ⁡ a _ x ¯ , a _ x ¯ , max ⁡ a ¯ x ¯ , a _ x _ a _ x ¯ , a _ x _ b _ ≤ 0 ≤ b ¯ b _ ≤ 0 ≤ b ¯ b _ ≤ 0 ≤ b ¯ x ¯ ≤ 0 a ¯ x _ , a _ x ¯ a ¯ x _ , a _ x _ a ¯ x ¯ , a _ x _ b _ , b ¯ ≤ 0 b _ ≤ 0 ≤ b ¯ 0 ≤ b _ , b ¯


### 3.2. Some Properties of the Interval Arithmetic Operations

In this section, first we recall some basic properties of interval arithmetic. Forã,b̃,c̃,d̃∈IR the following rules hold [35]:(29)ã+b̃=b̃+ã(30)ã×b̃=b̃×ã(31)ã+b̃+c̃=ã+b̃+c̃(32)ã×b̃×c̃=ã×b̃×c̃(33)ã±c̃⊆b̃±d̃whenã⊆b̃,c̃⊆d̃(34)wa≤wbwhenã⊆b̃For ã,b̃,c̃∈IR we have(35)ãb̃+c̃⊆ãb̃+ãc̃.In relation (35), equality holds when a̲=a¯ or b̲×c̲≥0.Proposition 4.
Considerã,b̃,c̃∈IR; then(36)ã⊖b̃+c̃=ã⊖b̃⊖c̃Proof.
Letd̃=(ã⊖b̃)⊖c̃; then (ã⊖b̃)=c̃+d̃ and ã=b̃+c̃+d̃, so(37)ã⊖b̃+c̃=b̃+c̃+d̃⊖b̃+c̃=d̃+b̃+c̃⊖b̃+c̃=d̃=ã⊖b̃⊖c̃,Proposition 5.
Forã,b̃,c̃∈IR we have(38)ãb̃⊖ãc̃⊆ãb̃⊖c̃,and equality holds when a̲=a¯ or c̲×(b̲-c̲)≥0.Proof.
Letd̃=b̃⊖c̃ and then b̃=c̃+d̃. So(39)ãb̃=ãc̃+d̃⊆ãc̃+ãd̃ãb̃⊆ãc̃+ãb̃⊖c̃ãb̃⊖ãc̃⊆ãb̃⊖c̃.Obviously equality holds when a̲=a¯ or d̲×c̲≥0, where d̲=b̲-c̲, which implies property (36).Proposition 6.
Forã,b̃,c̃∈IR we have (40)b̃⊖c̃⊘ã⊆b̃⊘ã⊖c̃⊘ãProof.
(41) a ̃ b ̃ ⊖ a ̃ c ̃ ⊆ a ̃ b ̃ ⊖ c ̃ ,and using definition of ⊘ we have(42)ãb̃⊖ãc̃⊘ã⊆b̃⊖c̃.Define B̃=ãb̃ and C̃=ãc̃; then b̃=B̃⊘ã and c̃=C̃⊘ã. So,(43)B̃⊖C̃⊘ã⊆B̃⊘ã⊖C̃⊘ã,and hence (40) holds.


### 3.3. Modified Conjugate Gradient Method for Linear Interval Systems

Conjugate gradient method is one of the most useful techniques in solving iterative methods for solving linear system of equations, whose matrix is symmetric and positive definite. The conjugate gradient method was proposed by Hestenes and Stiefel in 1952 as an iterative method for solving linear systems with positive definite coefficient matrices [36]. The conjugate gradient algorithm for linear system of equations can be briefly described as follows.Consider systemAx=b with solution y. Start with an initial estimate x0 of y. At step i use xi to new estimate xi+1 of y which is closer to y. At each step residual ri=b-Axi is computed and used as a measure of the goodness of the estimate xi. The algorithm is detailed below for solving Ax=b, where A is a symmetric, positive definite matrix.We generalize this method for linear interval systems when the interval matrixÃ is symmetric, Ãij=Ãji for all 1<=i,j<=n, and b̃ is an interval vector. There are articles describing and analyzing conjugate gradient method such as [37–39]. These articles illustrated which operator was used in original role, or acted in inverse operator. The new algorithm is obtained from original conjugate gradient method by modifying and replacing all operations with related interval operations; also all operators acting in the role of inverse operators are replaced by inverse of interval operators. In addition, we use interval vector norm instead of real vector norm.In the first modification on conjugate gradient, we change some operation “−,” with inverse operation “⊖” whenever needed. In Step 2 of Algorithm 1, “−” is applied for computing difference of b and A×x0. In Step 7 operation “−” is used, but at proof of conjugate gradient method in [39], ri is replaced with expression ri+1+(αi×Api). So, the operation “+” is summed over ri+1 and αi×Api. This means “−” in Step 7 is used for inverse of “+.” Therefore we use the operation “⊖” instead of “−” in steps 2 and 7.Algorithm 1:Conjugate gradient algorithm.
(1) functionCGA,b,x0,n ⊳  Input:  A∈Rn×n,b∈Rn,x0∈Rn ⊳  Output: x0∈Rn (2)  p0=r0=b-Ax0 (3)  i=0 (4)  repeat (5) αi=riTripiTApi (6) xi+1=xi+(αi×pi) (7) ri+1=ri-(αi×Api) (8) βi=ri+1Tri+1riTri (9) pi+1=ri+1+βipi (10) i=i+1 (11)  until(ri is sufficiently small) (12)  x=x0The second modification is similar to the first modification. We change operation “/” with inverse operation “⊘.” In steps 5 and 8 of Algorithm 1 operation “/” is used as inverse of multiplication in proof of conjugate gradient [39].The third modification,norm(r̃i)2, is used instead of ri′ri. In real linear algebra, expression ri′ri equals square of norm2 of ri, and value of ri′ri is related to amount of error. We replace this with norm(r̃i)2 that has the same meaning. The interval modified conjugate gradient method is the result of these modifications and is shown in Algorithm 2.Algorithm 2:Interval modified conjugate gradient algorithm.
(1) functionICGÂ,b̂,x̂0,n,θ,δ ⊳  Input:  Â∈IRn×n,b̂∈IRn,x̂0∈IRn,θ.δ∈R ⊳  Output:  x̂∈IRn (2)  p̂0=r̂0=b̂⊖(A×x̂0) (3)  i=0 (4)  Nr=normr̂02 (5)  repeat (6)   û=Â×p̂i (7)   α̂i=Nr⊘(p̂iT×û) (8)   x̂i+1=x̂i+(α̂i×p̂i) (9)   r̂i+1=r̂i⊖(α̂i×p̂i) (10)  Mr=norm(r̂i+1) (11)   if  Mr<θ  then (12)    break (13)   β=Mr2/Nr (14)   p̂i+1=r̂i+1+(β×p̂i) (15)   Nr=Mr2 (16)   if  normx̂i⊖x̂i+1<δ  then (17)      break (18)   i=i+1 (19)  until return  x̂i


### 3.4. Interval Steepest Descent Method for Linear Interval Systems

First, we definederivative on interval functions. In differential algebra, the derivative of f(x) with respect to x measures the sensitivity to change value of f(x) with respect to x. In mathematical terms(44)f′x=limh→0⁡fx+h-fxhAccording to this, the derivative of an interval function f(x̃) with respect to x̃ is denoted as f′(x̃) or f′x̃(x̃) or d/dx̃f(x̃) and is defined by the following formula:(45)f′x̃=limh̃→0,0⁡fx̃+h̃⊖fx̃⊘h̃Let x̃∈IRn and f(x̃)=f(x̃1,x̃2,…,x̃n) be a IRn→IR function. The partial derivative of a multivariable interval function is a derivative with respect to one variable when all other variables are fixed. The partial derivative f with respect to x̃i is denoted as f′x̃i(x̃) and is defined as (46)f′x̃ix̃=limh̃→0,0⁡f′x̃ix̃1,…,x̃i+h̃,…,x̃n⊖f′x̃ix̃1,…,x̃i,…,x̃n⊘h̃.Immediately from definitions (44) and (45) and the properties discussed, one can obtain the following properties of derivative and partial derivative of interval functions:(47)x̃′=1(48)f′ỹx̃=0(49)f±g′x̃=f′x̃±g′x̃(50)t̃×f′x̃⊆t̃×f′x̃,t̃∈IR(51)f×g′x̃⊆f′x̃×gx̃+g′x̃×fx̃Now consider the linear interval system Ãx̃=b̃ when Ã∈IRn×n is a symmetric interval matrix, and b̃∈IRn is a known interval vector. Let Φ(x̃) be an interval function(52)Φx̃=12x̃TÃx̃⊖x̃Tb̃.The gradient of Φ(x̃) with respect to x̃ is the vector of partial derivatives as(53)∇x̃Φx̃=Φ′x̃1x̃Φ′x̃2x̃⋮Φ′x̃nx̃.Let f(x̃)=x̃Tb̃ and g(x̃)=x̃TÃx̃. Then(54)fx̃=∑i=1nb̃ix̃iso, for any k (1≤k≤n)(55)fx̃k′x̃=ddx̃k∑i=1nb̃ix̃i⊆ddx̃k∑i≠kb̃ix̃i+ddx̃kb̃kx̃k=0+b̃k⇒fx̃k′x̃⊆b̃kAnd,(56)gx̃=∑i=1n∑j=1nx̃iÃijx̃jso, for all k (1≤k≤n)(57)g′x̃kx̃=ddx̃k∑i=1n∑j=1nx̃iÃijx̃j=ddx̃k∑i≠k∑j≠kx̃iÃijx̃j+∑i≠kx̃iÃikx̃k+∑j≠kx̃kÃkjx̃j+x̃kÃkkx̃k⇒g′x̃kx̃⊆0+∑i≠kx̃iÃik+∑j≠kÃkjx̃j+Ãkkx̃k+x̃kÃkk=2×∑i=1nÃkix̃i⇒g′x̃kx̃⊆2×ÃkTx̃Note that Φ(x̃)=1/2g(x̃)⊖f(x̃). Then(58)Φx̃k′x̃⊆12gx̃k′x̃⊖fx̃k′x̃⊆ÃkTx̃⊖b̃kand then, from (52)(59)∇x̃Φx̃=Φ′x̃1x̃Φ′x̃2x̃⋮Φ′x̃nx̃⊆Ã1Tx̃⊖b̃1Ã2Tx̃⊖b̃2⋮ÃnTx̃⊖b̃n=Ãx̃⊖b̃Assume x̃∗ is the solution of linear interval system Ãx̃=b̃; then(60)2×Φx̃=x̃TÃx̃⊖2x̃Tb̃=x̃TÃx̃⊖x̃Tb̃⊖x̃Tb̃⊆x̃TÃx̃⊖b̃⊖x̃Tb̃⇒Φx̃⊆12x̃TÃx̃⊖b̃⊖x̃Tb̃.So,(61)Φx̃∗⊆120,0⊖x̃∗Tb̃⇒wΦx̃∗≤-12wx̃∗Tb̃=constant  valueNow, consider x̃∈IRn and d∈Rn, where kth element of d is (-w(Ãx̃⊖b̃)k) and other elements of d are zero (1≤k≤n). Note that d indicates the opposite of direction w(∇x̃Φ(x̃)). Then(62)Φx̃+α̃d=12x̃+α̃dTÃx̃+α̃d⊖x̃+α̃dTb̃⊆12α̃2dTÃd+α̃dTÃd+12α̃2x̃TÃx̃⊖α̃dTb̃⊖x̃Tb̃.The derivative of Φ(x̃+α̃d) with respect to α̃ is(63)Φ′α̃x̃+α̃d⊆dTÃx̃+α̃dTÃd⊖dTb̃.If dTÃx̃+α̃dTÃd⊖dTb̃ equals zero, then one can obtain α̃ as(64)α̃=dTb̃⊖dTÃx̃⊘dTÃd=dkbk⊖dkÃx̃k⊘dk2ãkk=bk⊖Ãx̃k⊘dkãkk⇒α̃=r̃k⊘dkãkkNow α̃ moves Φ(x̃) to Φ(x̃+α̃d) with respect to direction d when x̃ is fixed. So Φ(x̃+α̃d)⊆Φ(x̃) and also w(Φ(x̃+α̃d))≤w(Φ(x̃)).(65)Φx̃+α̃d⊖Φx̃⊆12α̃dTÃα̃dT+α̃dTÃx̃⊖α̃dTb⊆12α̃dTÃα̃dT+α̃dTÃx̃⊖b=12α̃dTÃα̃dT⊖α̃dTr̃=12α̃α̃dk2ãkk⊖α̃dkrk⊆12r̃k⊘dkãkkdkr̃k⊘dkãkkdkãkk)⊖r̃k⊘dkãkkdkrk=12r̃kr̃k⊘ãkk⊖r̃kr̃k⊘ãkk=0,0⊖12r̃kr̃k⊘ãkk⊆0,0⇒Φx̃+α̃d⊆Φx̃In the following, we assume that x̃0 is a given vector as initial guess. If set x̃n+1=x̃n+α̃ndn, then Φx̃n+1⊆Φ(x̃n), where α̃n=(dnTb̃⊖dnÃx̃n)⊘(dnTÃdn), have(66)wΦx̃n+1≤wΦx̃nand then(67)wΦx̃0≥wΦx̃1≥wΦx̃2≥…≥wΦx̃∗The descending series {w(Φ(x̃i))} converges to w(Φ(x̃∗)). So, {x̃i} converges to x̃∗.The steepest descent algorithm for intervals is shown in Algorithm3.Algorithm 3:Interval steepest descent algorithm.
(1) functionISDÂ,b̂,x̂0,n,θ,δ ⊳  Input:  Â∈IRn×n,b̂∈IRn,x̂0∈IRn,θ.δ∈R ⊳  Output:  x̂∈IRn (2) x̂=x̂0 (3) repeat (4) x̂old=x̂ (5) for  k=1→ndo (6) r̂=Âx̂⊖b̂ (7) d̂=0n×1 (8) dk=-w(r̂k) (9) â=(r̂k)⊘(d̂kα̂kk) (10) x̂=x̂+âd (11) r̂=Âx̂⊖b̂ (12) if  norm(w(r))̂<θ  then (13) return  x̂ (14) if  norm(x̂old⊖x̂)<δ  then (15) return  x̂ (16) until


## 3.1. Inverse Operations for “+” and “×”

Suppose we are given an equationã+x̃=ã, where ã is a known interval number, and x̃ is an unknown interval number, how can one find x̃?Obviouslyx̃=[0,0]=0 is the solution to this equation. However, ã-ã=[a̲-a¯,a¯-a̲] which is not equal to [0,0] unless a̲=a¯. If the operation “−” is inverse of the operation “+,” then x̃ must equal ã-ã. But x̃=0,0 and ã-ã≠0,0 unless a̲=a¯.As it can be observed, the operator “−” is not inverse of the operation “+.” Similarly, it can be observed that the operation “/” is not inverse of the operation “×.” Therefore, we propose the inverse of operations “+” and “×.”Before introducing inverse operations for “+” and “×,” we need another general type of intervals that is defined in [32, 33]. Ageneral closed intervala,b is identified by two real numbers a,b∈R and is defined as(20)a,b=x∈R∣a≤b∨b≤a.Thegeneral interval number space over real numbers is denoted by IR∗. Obviously, IR⊆IR∗. All definitions (supremum, infimum, and magnitude) and operations in IR∗ are defined the same as IR but computation over IR∗ is more complicated than IR. The arithmetic over IR∗ is well discussed in [20, 32, 33]. For example, [1,3]+[3,1]=[4,4] as in (7), or [1,2]×[3,1]=[3,2] as in (8). The width of a general interval number can be negative; for example, w([3,2])=-1. Also, according to definition of subset, [2,-2]⊆[0,0].In this paper, bygeneral interval, we mean general closed intervals.Forã,b̃∈IR∗, the operation “⊖” is defined in [20, 33] as(21)ã⊖b̃=a̲-b̲,a¯-b¯For ã,b̃∈IR, we define the operation “⊘” as(22)ã⊘b̃=-∞,+∞a̲=a¯=0,b̲=b¯=00,0a̲=a¯=0,b̲≠0orb¯≠0undefined∃x≠0,x∈ã,b̲=b¯=0undefined0∉a,0∈ba̲/b̲,a¯/b¯a̲≥0,b̲>00,a¯/b¯a̲=0,b̲=0a̲/b¯,a¯/b¯a̲≤0≤a¯,b̲≥0a̲/b¯,a¯/b̲a¯≤0,b̲>0a̲/b¯,0a¯=0,b̲=0ã⊘-b̃b¯≤0a̲/b¯,a¯/b¯a̲≥0,b̲<0<b¯max⁡a̲/b¯,a¯/b̲,min⁡a¯/b¯,a̲/b̲a̲≤0≤a¯,b̲<0<b¯a¯/b̲,a̲/b̲a¯≤0,b̲<0<b¯Note that this definition can handle many cases where 0 belongs to b̃, and just in three cases compute undefined or unbounded solution. This property lets us design algorithms with high stability and consistent when working with interval values that contain 0.In the following two theorems, we show that operations “⊖” and “⊘” are inverse of operations “+” and “×,” respectively [34].Theorem 2.
Givenã,b̃∈IR, then the interval equation ã+x̃∗=b̃ has a unique solution x̃∗=b̃⊖ã, where x̃∗∈IR∗. The equation ã+x̃∗=b̃ has a unique solution in IR if x̃∗∈IR; otherwise the equation ã+x̃∗=b̃ has no solution in IR but has exactly one in IR∗.Proof.
a ̃ + x ̃ = b ̃ ⇔ a ̲ , a ¯ + x ∗ ̲ , x ∗ ¯ = b ̲ , b ¯ . That is, b̲=a̲+x∗̲, which solves x∗̲=b̲-a̲. Similarly, x∗¯=b¯-a¯; therefore, we have x̃∗=b̃⊖ã, where x̃∗=[x∗̲,x∗¯].
Therefore ifã,b̃,x̃∈IR and ã+x̃=b̃, then x̃ can be found with this inverse operation uniquely.Theorem 3.
Givenã,b̃∈IR, then the interval equation ã×x̃∗=b̃ has a solution x̃∗=b̃⊘ã, where x̃∗∈IR∗. The equation ã×x̃∗=b̃ has a solution in IR if x̃∗∈IR; otherwise the equation ã×x̃∗=b̃ has no solution in IR but has in IR∗.Remark. Solution x̃∗ is not usually unique; e.g., the interval equation [-1,1]×x̃∗=[-2,2] has solutions [-1,2],[-2,0],[-2,2]. Actually, this equation has unlimited solutions. All intervals [u,2] and [-2,v] where -2≤u≤0 and 0≤v≤2 can be solution of this equation.In cases thatx̃∗ is not unique, x̃∗ is considered as the longest interval as possible. In the above example, x̃ must be [-2,2].Proof.
Supposeã×x̃=b̃. Before starting the proof, note that multiplication result, b̃, depends on the sign of ã and x̃. Table 1 shows sign of b̃ related to sign of ã and x̃ and also shows formulas of multiplication result.
Suppose that, givenã,b̃∈IR, ã×x̃=b̃, and a¯≤0 and 0∈b̃. Now, from Table 1, it is observed that the following must occur:  b̲≤0≤b¯ and b̃=[a¯x̲,a¯x¯]. Then(23)ãx̃=b̃⇔b̃=a̲x¯,a̲x̲⇔b̲=a̲x¯⇔x¯=b̲/x̲b¯=a̲x̲⇔x̲=b¯/x̲⇔x̃=b̃⊘ã.This means in this case x̃ is uniquely calculated by inverse operations of “×.” For other cases except cases with condition 0∈ã, one can provide similar proofs.
For cases with condition0∈ã, there is an ambiguity. From Table 1, there are three cases in column 0∈ã. They have the same conditions b̲≤0≤b¯. The solution can be in forms 0≤x̲, 0∈x̃, and 0≥x¯, respectively. The solution should be in form of 0∈x̃, because it is the longest possible interval solution and includes both of the others. Now, find x̲ and x¯. If xs̃ with condition 0∈xs̃ is the solution of ã×x̃=b̃, then b̃=mina¯xs̲,a̲xs¯,maxa̲xs̲,a¯xs¯. It follows that(24)b̲=min⁡a¯xs̲,a̲xs¯⇒b̲≤a¯xs̲⇒xs̲≥b̲/a¯,and(25)b¯=max⁡a̲xs̲,a¯xs¯⇒b¯≥a̲xs̲⇒xs̲≥b¯/a̲.Then,(26)xs̲≥max⁡b̲/a¯,b¯/a̲.If xs̲≠maxb̲/a¯,b¯/a̲, then xs̲>maxb̲/a¯,b¯/a̲, and a¯xs̲>maxb̲/,a¯b¯/a̲≥b̲. This contradicts with b¯=maxa̲xs̲,a¯xs¯. Hence(27)xs̲=max⁡b̲/a¯,b¯/a̲.Similarly,(28)xs¯=min⁡b¯/a¯,b̲/a̲,and therefore, we have xs̃=b̲⊘a̲.
In addition, special caseã=[0,0] should be considered separately. If ã=[0,0] and b̃≠[0,0], no x̃ exists such that ã×x̃=b̃. If ã=b̃=[0,0], then x̃ is free and expression ã×x̃=b̃ is consistent for all x̃. At this point x̃ is considered as [-∞,+∞].Table 1
Interval multiplication in detail.
a ̃ x ̃ = b ̃ 0 ≤ a ̲ 0 ∈ a ̃ a ¯ ≤ 0 0 ≤ x ̲ a _ x _ , a ¯ x ¯ a _ x ¯ , a ¯ x ¯ a _ x ¯ , a ¯ x _ 0 ≤ b _ , b ¯ b _ ≤ 0 ≤ b ¯ b _ , b ¯ ≤ 0 0 ∈ x ̃ a ¯ x _ , a ¯ x ¯ min ⁡ a _ x ¯ , a _ x ¯ , max ⁡ a ¯ x ¯ , a _ x _ a _ x ¯ , a _ x _ b _ ≤ 0 ≤ b ¯ b _ ≤ 0 ≤ b ¯ b _ ≤ 0 ≤ b ¯ x ¯ ≤ 0 a ¯ x _ , a _ x ¯ a ¯ x _ , a _ x _ a ¯ x ¯ , a _ x _ b _ , b ¯ ≤ 0 b _ ≤ 0 ≤ b ¯ 0 ≤ b _ , b ¯


## 3.2. Some Properties of the Interval Arithmetic Operations

In this section, first we recall some basic properties of interval arithmetic. Forã,b̃,c̃,d̃∈IR the following rules hold [35]:(29)ã+b̃=b̃+ã(30)ã×b̃=b̃×ã(31)ã+b̃+c̃=ã+b̃+c̃(32)ã×b̃×c̃=ã×b̃×c̃(33)ã±c̃⊆b̃±d̃whenã⊆b̃,c̃⊆d̃(34)wa≤wbwhenã⊆b̃For ã,b̃,c̃∈IR we have(35)ãb̃+c̃⊆ãb̃+ãc̃.In relation (35), equality holds when a̲=a¯ or b̲×c̲≥0.Proposition 4.
Considerã,b̃,c̃∈IR; then(36)ã⊖b̃+c̃=ã⊖b̃⊖c̃Proof.
Letd̃=(ã⊖b̃)⊖c̃; then (ã⊖b̃)=c̃+d̃ and ã=b̃+c̃+d̃, so(37)ã⊖b̃+c̃=b̃+c̃+d̃⊖b̃+c̃=d̃+b̃+c̃⊖b̃+c̃=d̃=ã⊖b̃⊖c̃,Proposition 5.
Forã,b̃,c̃∈IR we have(38)ãb̃⊖ãc̃⊆ãb̃⊖c̃,and equality holds when a̲=a¯ or c̲×(b̲-c̲)≥0.Proof.
Letd̃=b̃⊖c̃ and then b̃=c̃+d̃. So(39)ãb̃=ãc̃+d̃⊆ãc̃+ãd̃ãb̃⊆ãc̃+ãb̃⊖c̃ãb̃⊖ãc̃⊆ãb̃⊖c̃.Obviously equality holds when a̲=a¯ or d̲×c̲≥0, where d̲=b̲-c̲, which implies property (36).Proposition 6.
Forã,b̃,c̃∈IR we have (40)b̃⊖c̃⊘ã⊆b̃⊘ã⊖c̃⊘ãProof.
(41) a ̃ b ̃ ⊖ a ̃ c ̃ ⊆ a ̃ b ̃ ⊖ c ̃ ,and using definition of ⊘ we have(42)ãb̃⊖ãc̃⊘ã⊆b̃⊖c̃.Define B̃=ãb̃ and C̃=ãc̃; then b̃=B̃⊘ã and c̃=C̃⊘ã. So,(43)B̃⊖C̃⊘ã⊆B̃⊘ã⊖C̃⊘ã,and hence (40) holds.


## 3.3. Modified Conjugate Gradient Method for Linear Interval Systems

Conjugate gradient method is one of the most useful techniques in solving iterative methods for solving linear system of equations, whose matrix is symmetric and positive definite. The conjugate gradient method was proposed by Hestenes and Stiefel in 1952 as an iterative method for solving linear systems with positive definite coefficient matrices [36]. The conjugate gradient algorithm for linear system of equations can be briefly described as follows.Consider systemAx=b with solution y. Start with an initial estimate x0 of y. At step i use xi to new estimate xi+1 of y which is closer to y. At each step residual ri=b-Axi is computed and used as a measure of the goodness of the estimate xi. The algorithm is detailed below for solving Ax=b, where A is a symmetric, positive definite matrix.We generalize this method for linear interval systems when the interval matrixÃ is symmetric, Ãij=Ãji for all 1<=i,j<=n, and b̃ is an interval vector. There are articles describing and analyzing conjugate gradient method such as [37–39]. These articles illustrated which operator was used in original role, or acted in inverse operator. The new algorithm is obtained from original conjugate gradient method by modifying and replacing all operations with related interval operations; also all operators acting in the role of inverse operators are replaced by inverse of interval operators. In addition, we use interval vector norm instead of real vector norm.In the first modification on conjugate gradient, we change some operation “−,” with inverse operation “⊖” whenever needed. In Step 2 of Algorithm 1, “−” is applied for computing difference of b and A×x0. In Step 7 operation “−” is used, but at proof of conjugate gradient method in [39], ri is replaced with expression ri+1+(αi×Api). So, the operation “+” is summed over ri+1 and αi×Api. This means “−” in Step 7 is used for inverse of “+.” Therefore we use the operation “⊖” instead of “−” in steps 2 and 7.Algorithm 1:Conjugate gradient algorithm.
(1) functionCGA,b,x0,n ⊳  Input:  A∈Rn×n,b∈Rn,x0∈Rn ⊳  Output: x0∈Rn (2)  p0=r0=b-Ax0 (3)  i=0 (4)  repeat (5) αi=riTripiTApi (6) xi+1=xi+(αi×pi) (7) ri+1=ri-(αi×Api) (8) βi=ri+1Tri+1riTri (9) pi+1=ri+1+βipi (10) i=i+1 (11)  until(ri is sufficiently small) (12)  x=x0The second modification is similar to the first modification. We change operation “/” with inverse operation “⊘.” In steps 5 and 8 of Algorithm 1 operation “/” is used as inverse of multiplication in proof of conjugate gradient [39].The third modification,norm(r̃i)2, is used instead of ri′ri. In real linear algebra, expression ri′ri equals square of norm2 of ri, and value of ri′ri is related to amount of error. We replace this with norm(r̃i)2 that has the same meaning. The interval modified conjugate gradient method is the result of these modifications and is shown in Algorithm 2.Algorithm 2:Interval modified conjugate gradient algorithm.
(1) functionICGÂ,b̂,x̂0,n,θ,δ ⊳  Input:  Â∈IRn×n,b̂∈IRn,x̂0∈IRn,θ.δ∈R ⊳  Output:  x̂∈IRn (2)  p̂0=r̂0=b̂⊖(A×x̂0) (3)  i=0 (4)  Nr=normr̂02 (5)  repeat (6)   û=Â×p̂i (7)   α̂i=Nr⊘(p̂iT×û) (8)   x̂i+1=x̂i+(α̂i×p̂i) (9)   r̂i+1=r̂i⊖(α̂i×p̂i) (10)  Mr=norm(r̂i+1) (11)   if  Mr<θ  then (12)    break (13)   β=Mr2/Nr (14)   p̂i+1=r̂i+1+(β×p̂i) (15)   Nr=Mr2 (16)   if  normx̂i⊖x̂i+1<δ  then (17)      break (18)   i=i+1 (19)  until return  x̂i


## 3.4. Interval Steepest Descent Method for Linear Interval Systems

First, we definederivative on interval functions. In differential algebra, the derivative of f(x) with respect to x measures the sensitivity to change value of f(x) with respect to x. In mathematical terms(44)f′x=limh→0⁡fx+h-fxhAccording to this, the derivative of an interval function f(x̃) with respect to x̃ is denoted as f′(x̃) or f′x̃(x̃) or d/dx̃f(x̃) and is defined by the following formula:(45)f′x̃=limh̃→0,0⁡fx̃+h̃⊖fx̃⊘h̃Let x̃∈IRn and f(x̃)=f(x̃1,x̃2,…,x̃n) be a IRn→IR function. The partial derivative of a multivariable interval function is a derivative with respect to one variable when all other variables are fixed. The partial derivative f with respect to x̃i is denoted as f′x̃i(x̃) and is defined as (46)f′x̃ix̃=limh̃→0,0⁡f′x̃ix̃1,…,x̃i+h̃,…,x̃n⊖f′x̃ix̃1,…,x̃i,…,x̃n⊘h̃.Immediately from definitions (44) and (45) and the properties discussed, one can obtain the following properties of derivative and partial derivative of interval functions:(47)x̃′=1(48)f′ỹx̃=0(49)f±g′x̃=f′x̃±g′x̃(50)t̃×f′x̃⊆t̃×f′x̃,t̃∈IR(51)f×g′x̃⊆f′x̃×gx̃+g′x̃×fx̃Now consider the linear interval system Ãx̃=b̃ when Ã∈IRn×n is a symmetric interval matrix, and b̃∈IRn is a known interval vector. Let Φ(x̃) be an interval function(52)Φx̃=12x̃TÃx̃⊖x̃Tb̃.The gradient of Φ(x̃) with respect to x̃ is the vector of partial derivatives as(53)∇x̃Φx̃=Φ′x̃1x̃Φ′x̃2x̃⋮Φ′x̃nx̃.Let f(x̃)=x̃Tb̃ and g(x̃)=x̃TÃx̃. Then(54)fx̃=∑i=1nb̃ix̃iso, for any k (1≤k≤n)(55)fx̃k′x̃=ddx̃k∑i=1nb̃ix̃i⊆ddx̃k∑i≠kb̃ix̃i+ddx̃kb̃kx̃k=0+b̃k⇒fx̃k′x̃⊆b̃kAnd,(56)gx̃=∑i=1n∑j=1nx̃iÃijx̃jso, for all k (1≤k≤n)(57)g′x̃kx̃=ddx̃k∑i=1n∑j=1nx̃iÃijx̃j=ddx̃k∑i≠k∑j≠kx̃iÃijx̃j+∑i≠kx̃iÃikx̃k+∑j≠kx̃kÃkjx̃j+x̃kÃkkx̃k⇒g′x̃kx̃⊆0+∑i≠kx̃iÃik+∑j≠kÃkjx̃j+Ãkkx̃k+x̃kÃkk=2×∑i=1nÃkix̃i⇒g′x̃kx̃⊆2×ÃkTx̃Note that Φ(x̃)=1/2g(x̃)⊖f(x̃). Then(58)Φx̃k′x̃⊆12gx̃k′x̃⊖fx̃k′x̃⊆ÃkTx̃⊖b̃kand then, from (52)(59)∇x̃Φx̃=Φ′x̃1x̃Φ′x̃2x̃⋮Φ′x̃nx̃⊆Ã1Tx̃⊖b̃1Ã2Tx̃⊖b̃2⋮ÃnTx̃⊖b̃n=Ãx̃⊖b̃Assume x̃∗ is the solution of linear interval system Ãx̃=b̃; then(60)2×Φx̃=x̃TÃx̃⊖2x̃Tb̃=x̃TÃx̃⊖x̃Tb̃⊖x̃Tb̃⊆x̃TÃx̃⊖b̃⊖x̃Tb̃⇒Φx̃⊆12x̃TÃx̃⊖b̃⊖x̃Tb̃.So,(61)Φx̃∗⊆120,0⊖x̃∗Tb̃⇒wΦx̃∗≤-12wx̃∗Tb̃=constant  valueNow, consider x̃∈IRn and d∈Rn, where kth element of d is (-w(Ãx̃⊖b̃)k) and other elements of d are zero (1≤k≤n). Note that d indicates the opposite of direction w(∇x̃Φ(x̃)). Then(62)Φx̃+α̃d=12x̃+α̃dTÃx̃+α̃d⊖x̃+α̃dTb̃⊆12α̃2dTÃd+α̃dTÃd+12α̃2x̃TÃx̃⊖α̃dTb̃⊖x̃Tb̃.The derivative of Φ(x̃+α̃d) with respect to α̃ is(63)Φ′α̃x̃+α̃d⊆dTÃx̃+α̃dTÃd⊖dTb̃.If dTÃx̃+α̃dTÃd⊖dTb̃ equals zero, then one can obtain α̃ as(64)α̃=dTb̃⊖dTÃx̃⊘dTÃd=dkbk⊖dkÃx̃k⊘dk2ãkk=bk⊖Ãx̃k⊘dkãkk⇒α̃=r̃k⊘dkãkkNow α̃ moves Φ(x̃) to Φ(x̃+α̃d) with respect to direction d when x̃ is fixed. So Φ(x̃+α̃d)⊆Φ(x̃) and also w(Φ(x̃+α̃d))≤w(Φ(x̃)).(65)Φx̃+α̃d⊖Φx̃⊆12α̃dTÃα̃dT+α̃dTÃx̃⊖α̃dTb⊆12α̃dTÃα̃dT+α̃dTÃx̃⊖b=12α̃dTÃα̃dT⊖α̃dTr̃=12α̃α̃dk2ãkk⊖α̃dkrk⊆12r̃k⊘dkãkkdkr̃k⊘dkãkkdkãkk)⊖r̃k⊘dkãkkdkrk=12r̃kr̃k⊘ãkk⊖r̃kr̃k⊘ãkk=0,0⊖12r̃kr̃k⊘ãkk⊆0,0⇒Φx̃+α̃d⊆Φx̃In the following, we assume that x̃0 is a given vector as initial guess. If set x̃n+1=x̃n+α̃ndn, then Φx̃n+1⊆Φ(x̃n), where α̃n=(dnTb̃⊖dnÃx̃n)⊘(dnTÃdn), have(66)wΦx̃n+1≤wΦx̃nand then(67)wΦx̃0≥wΦx̃1≥wΦx̃2≥…≥wΦx̃∗The descending series {w(Φ(x̃i))} converges to w(Φ(x̃∗)). So, {x̃i} converges to x̃∗.The steepest descent algorithm for intervals is shown in Algorithm3.Algorithm 3:Interval steepest descent algorithm.
(1) functionISDÂ,b̂,x̂0,n,θ,δ ⊳  Input:  Â∈IRn×n,b̂∈IRn,x̂0∈IRn,θ.δ∈R ⊳  Output:  x̂∈IRn (2) x̂=x̂0 (3) repeat (4) x̂old=x̂ (5) for  k=1→ndo (6) r̂=Âx̂⊖b̂ (7) d̂=0n×1 (8) dk=-w(r̂k) (9) â=(r̂k)⊘(d̂kα̂kk) (10) x̂=x̂+âd (11) r̂=Âx̂⊖b̂ (12) if  norm(w(r))̂<θ  then (13) return  x̂ (14) if  norm(x̂old⊖x̂)<δ  then (15) return  x̂ (16) until


## 4. Results and Discussion

In this section, some numerical examples show how our iterative methods can solve interval systems. Accuracy of produced solutions is measured by a kind of norm of residual vector(68)ri=Ãxĩ⊖b,̃where xĩ is the produced solution in ith iteration. The norm used in this section is then maximum of magnitude of all residual vector elements.We examine our methods with a famous system and then examine them with random matrices with several dimensions. Our results illustrate the effectiveness of our algorithms.Example 7.
Consider the linear interval systemÃx̃=b̃ [22, 40](69)Ã=3.74.3-1.5,-0.50,0-1.5,-0.53.7,4.3-1.5,0.50,0-1.5,-0.53.7,4.3,b̃=-14,14-9,9-3,3.Let x̃0=[0,0,0]T be initial estimation and θ=10-3 be tolerance. Interval modified conjugate gradient method finds the estimation x̃ at iteration 13. However, interval steepest descent finds solution ỹ at iteration 4(70)x̃=-2.92653,2.92653-0.94373,0.94373-0.36839,0.36839,ỹ=-2.92639,2.92639-0.94373,0.94373-0.36846,0.36846.Accuracy of results is determined by the residual vectors as follows:(71)Magb̃⊖Ax̃=0.3190440.4360950.31904410-4,Magb̃⊖Aỹ=0.9238640.322278010-3Also when θ=10-7 the accuracy of the obtained results of two methods is(72)Magb̃⊖Ax̃=0.395090.566480.3950910-7,Magb̃⊖Aỹ=0.467240.16299010-7when x̃ and ỹ are found at 26th and 11th iterations, respectively.Tables2 and 3 show values x̃i and ỹi with their maximum of the magnitude of the residual vector at ith iteration, respectively.Table 2
Intermediate results of interval modified conjugate gradient method.
i x i m a x ( M a g ( r i ) ) 1 [ [-1.62482,1.62482], [-1.04453,1.04453], [-0.34818,0.34818]]⊤ 5.44647 5 [ [-2.89491,2.89491], [-0.98549,0.98549], [-0.33668,0.33668]]⊤ 0.08503 10 [ [-2.92550,2.92550], [-0.94522,0.94522], [-0.36736,0.36736]]⊤ 0.0037181 20 [ [-2.92667,2.92667], [-0.94353,0.94353], [-0.36853,0.36853]]⊤ 0.0000036325 26 [ [-2.92668,2.92668], [-0.94353,0.94353], [-0.36856,0.36856]]⊤ 0.000000056648Table 3
Intermediate results of interval steepest descent method.
i y i m a x ( M a g ( r i ) ) 1 [[-3.25581,3.25581], [-0.95728,0.95728], [-0.36374,0.36374]]⊤ 1.43591 3 [[-2.92551,2.92551], [-0.94435,0.94435], [-0.36825,0.36825]]⊤ 0.00379605 7 [[-2.92667,2.92667], [-0.94353,0.94353], [-0.36853,0.36853]]⊤ 0.000013318 11 [[-2.92668,2.92668], [-0.94353,0.94353], [-0.36854,0.36854]]⊤ `0.000000046723The method presented in [13, 15, 25, 26, 30] could not solve this system where 0 belongs to their elements to the right-hand side vector, because their methods cannot resolve divide-by-zero issues.This system is solved in [22, 40], and solutions obtained by them are (73)z̃1=-2.3802,-1.7730-2.0827,-1.8280-0.8482,-0.8482,z̃2=-1.6700,6.3800-2.7700,6.4000-2.400,3.400,respectively.Note that(74)Az̃1=-9.3209,-3.4360-7.6451,-1.9210-2.7333,-0.0142,Az̃2=-16.7810,31.5890-26.5811,33.6251-19.9201,18.7750.It is to be noted that the solutions obtained from our methods are better than other techniques.Example 8.
Consider the linear interval systemÃx̃=b̃, where Ã is a random diagonally dominant interval matrix(75)Ã=3.6178,6.4222-0.0924,0.6944-0.1140,0.79610.1062,0.58940.3416,0.4521-0.4482,0.75780.3220,0.35084.0697,6.6729-0.0517,0.2525-0.1653,0.7593-0.2746,0.5602-0.0344,0.0681-0.6805,0.71930.0603,0.68293.7386,6.7575-0.1892,0.5012-0.1225,0.21060.2003,0.4770-0.5043,0.65410.0249,0.3366-0.2728,0.82163.7887,6.9165-0.1346,0.44850.3347,0.4588-0.0464,0.5994-0.2883,0.59300.1657,0.3306-0.3346,0.77994.0636,6.4148-0.0716,0.21090.1975,0.2994-0.0125,0.20480.0754,0.1017-0.2637,0.4392-0.0188,0.09964.0029,6.4124,b̃=-5.6444,5.6444-3.8203,3.8203-1.7073,1.7073-3.8776,3.8776-4.6594,4.6594-2.6347,2.6347.This system has exact solution(76)x̃s=-0.7089,0.7089-0.4365,0.4365-0.0625,0.0625-0.4072,0.4072-0.5563,0.5563-0.3263,0.3263.We considered(77)x̃0=0,0,0,0,0,0,0,0,0,0,-1,1⊤,as initial solution and θ=10-3 as tolerance.The generalized conjugate gradient method, after7 iterations obtained, is(78)x̃1=-0.70881,0.70881-0.43651,0.43651-0.06252,0.06252-0.40720,0.40720-0.55632,0.55632-0.32634,0.32634.while the value of magnitudes of residual (Ãx̃1⊖b) is 5.94044×10-5.Whenθ=10-7, interval modified conjugate gradient method after 26 iterations obtained x̃2 while magnitude of Ãx̃2⊖b is 7.67731×10-8.Interval steepest descent method obtained estimationsỹ1 and ỹ2 at iterations 6 and 12 when θ=10-3 and θ=10-7, respectively. The accuracy of ỹ1 and ỹ1 is(79)maxMagb̃⊖Ãỹ1=9.59448×10-4,maxMagb̃⊖Ãỹ2=7.42146×10-8The results of these experiments are shown in Figure 1. This figure shows the convergence of the two proposed methods. As it can be seen, the interval steepest descent method has faster convergence than interval modified conjugate gradient method.Figure 1
Tightness of solutions and convergences of our methods.This example illustrates that our methods can solve systems where some of their elements have0 in their intervals, without producing divide-by-zero error.Example 9.
Consider Example8 with a different(80)b̃=0,5.64440,3.82030,1.70730,3.87760,4.65940,2.6347,which has the exact solution(81)0,0.70890,0.43650,0.06250,0.40720,0.55630,0.3263.Using interval modified conjugate gradient method, we obtain(82)x̃=0.0000,0.709520.0000,0.436670.0000,0.059020.0000,0.407370.0000,0.556690.0000,0.32652.Using interval steepest descent method, we obtain(83)ỹ=0,0.708980,0.436500,0.062480,0.407190,0.556290,0.32629.Let the system considered in Example 8 be given with another b̃(84)b̃=1.2542,5.64431.6069,3.82020.4887,1.70720.9962,3.87751.4827,4.65931.1532,2.6346which has the exact solution(85)0.2692,0.70890.3419,0.43650.0425,0.06250.1877,0.40720.3158,0.55630.2591,0.3263.Using interval modified conjugate gradient method and interval steepest descent method, we obtain(86)x̃=0.26950,0.708730.34162,0.436540.04248,0.064750.18786,0.407230.31583,0.556380.25722,0.32627and(87)ỹ=0.26976,0.708920.34186,0.436510.04240,0.062510.18768,0.407200.31580,0.556300.25905,0.32630.Example 10.
We examined the two proposed methods with a number of random linear interval systemsÃx̃=b̃ when Ã∈IRn×n is a random interval symmetric diagonally dominant matrix. Tables 4 and 5 show the number of iterations needed by our presented methods to find the solution with tolerances θ=10-3 and θ=10-7 for random interval systems with various dimensions.
Note that there are infinite random matrices with dimensionn×n, and number of iterations just does not depend on n. It depends on n, the coefficient matrix, and right-hand side vector. However, each row of these tables just shows number of iterations for random linear systems. These matrices are not special matrices, and these tables show a good view of dependency of dimension and approximation of number of iterations. These tables also show needed iterations in interval steepest descent are less than the interval modified conjugate gradient method.Table 4
Iterations needed in interval steepest descend method solving random linear interval systems.
n θ = 10 - 3 θ = 10 - 7 5 10 18 10 13 33 15 6 19 20 16 36 25 14 35 30 18 40 35 14 32 40 15 36 45 14 34 50 18 40 75 16 35 100 18 44Table 5
Iterations needed in interval modified conjugate gradient method solving random linear interval systems.
n θ = 10 - 3 θ = 10 - 7 5 8 23 10 21 37 15 24 52 20 27 63 25 34 87 30 52 120 35 80 186 40 91 240 45 67 247 50 84 289 75 167 412 100 183 542


## 5. Conclusion

In this paper, we presented two operators “⊖” and “⊘” as inverse operators of “+” and “×” in interval arithmetic. The proposed operation “⊘” can solve many equations in the form ãx̃=b̃, where 0∈b̃, without concerning divide-by-zero.Using these two operators, we proposed two iterative methods for computing exact solution of linear interval systems. The first method, based on the conjugate gradient method, replaced real operations with interval operations. The second method uses steepest descent idea to solve linear interval systems. We presented the interval functionΦ(x̃). Then using analysis of Φ(x̃), it was proved that the second method is convergent.Our proposed methods are using operations “⊖” and “⊘,” solving systems, specially systems which have 0 belonging to some of their elements without the divide-by-zero issues. This is the main advantage of our methods. Also, our results showed the efficiency and fast convergence of the proposed methods. In addition, one can control and improve the accuracy of the solution, by control of the tolerance parameter θ.The important application of interval number and interval analysis is in the modeling of uncertain values. There are many uncertain values in fields of engineering sciences that can be modeled in interval numbers. Uncertainty in some of these problems can be modeled in interval numbers, for example, the interval methods applied to linear state feedback control of uncertain values [41], reliability optimization under parameter uncertainty [42], decision-making under uncertainty [43], and perturbation analysis [44]. Our next research is to consider the applicability of our method to some of the engineering problems.



---

*Source: 2797038-2018-10-08.xml*