METHODS FOR DETERMINATION AND APPROXIMATION OF THE DOMAIN OF ATTRACTION IN THE CASE OF AUTONOMOUS DISCRETE DYNAMICAL SYSTEMS

METHODS FOR DETERMINATION AND APPROXIMATION OF THE DOMAIN OF ATTRACTION IN THE CASE OF AUTONOMOUS DISCRETE DYNAMICAL SYSTEMS

ST. BALINT, E. KASLIK, A. M. BALINT, AND A. GRIGIS Received 15 October 2004; Accepted 18 October 2004

A method for determination and two methods for approximation of the domain of attrac- tionDa(0) of the asymptotically stable zero steady state of an autonomous,R-analytical, discrete dynamical system are presented. The method of determination is based on the construction of a Lyapunov functionV, whose domain of analyticity isDa(0). The first method of approximation uses a sequence of Lyapunov functionsVp, which converge to the Lyapunov functionVonDa(0). EachVpdefines an estimateNpofDa(0). For anyx∈ Da(0), there exists an estimateNp^xwhich containsx. The second method of approxima- tion uses a ballB(R)⊂Da(0) which generates the sequence of estimatesMp=f^−p(B(R)).

For anyx∈Da(0), there exists an estimateMp^xwhich containsx. The cases∂0f<1 and ρ(∂0f)<1≤ ∂0fare treated separately because significant differences occur.

Copyright © 2006 Hindawi Publishing Corporation. All rights reserved.

1. Introduction

Let be the following discrete dynamical system:

xk+1=fxk

k=0, 1, 2,..., (1.1)

where f :Ω→Ωis an R-analytic function defined on a domain Ω⊂Rⁿ, 0∈Ωand f(0)=0, that is,x=0 is a steady state (fixed point) of (1.1).

Forr >0, denote byB(r)= {x∈Rⁿ:x< r}the ball of radiusr.

The steady statex=0 of (1.1) is “stable” provided that given any ballB(ε), there is a ballB(δ) such that ifx∈B(δ) then f^k(x)∈B(ε), fork=0, 1, 2,...[4].

If in addition there is a ballB(r) such thatf^k(x)→0 ask→ ∞for allx∈B(r) then the steady statex=0 is “asymptotically stable” [4].

The domain of attractionDa(0) of the asymptotically stable steady statex=0 is the set of initial statesx∈Ωfrom which the system converges to the steady state itself, that is,

Da(0)=

x∈Ω|f^k(x)−−−→^k→∞ 0. (1.2)

Hindawi Publishing Corporation Advances in Difference Equations Volume 2006, Article ID 23939, Pages1–15 DOI10.1155/ADE/2006/23939

Theoretical research shows that theDa(0) and its boundary are complicated sets [5–9].

In most cases, they do not admit an explicit elementary representation. The domain of attraction of an asymptotically stable steady state of a discrete dynamical system is not necessarily connected (which is the case for continuous dynamical systems). This fact is shown by the following example.

Example 1.1. Let be the functionf :R→Rdefined byf(x)=(1/2)x−(1/4)x²+ (1/2)x³+ (1/4)x⁴. The domain of attraction of the asymptotically stable steady statex=0 isDa(0)= (−2.79,−2.46)∪(−1, 1) which is not connected.

Different procedures are used for the approximation of theDa(0) with domains hav- ing a simpler shape. For example, in the case of [4, Theorem 4.20, page 170] the domain which approximates theDa(0) is defined by a Lyapunov functionV built with the ma- trix∂0f of the linearized system in 0, under the assumption∂0f<1. In [2], a Lya- punov function V is presented in the case when the matrix∂0f is a contraction, that is,∂0f<1. The Lyapunov functionV is built using the whole nonlinear system, not only the matrix∂0f.V is defined on the wholeDa(0), and more, theDa(0) is the nat- ural domain of analyticity ofV. In [3], this result is extended for the more general case whenρ(∂0f)<1 (whereρ(∂0f) denotes the spectral radius of∂0f.) This last result is the following.

Theorem 1.2 (see [3]). If the function f satisfies the following conditions:

f(0)=0,

ρ∂0f<1, (1.3)

then 0 is an asymptotically stable steady state.Da(0) is an open subset ofΩand coincides with the natural domain of analyticity of the unique solutionV of the iterative first-order functional equation

Vf(x)−V(x)= −x²,

V(0)=0. (1.4)

The functionV is positive onDa(0) andV(x)^x→→^x0+∞, for anyx⁰∈∂Da(0), (∂Da(0) de- notes the boundary ofDa(0)) or forx → ∞.

The functionV is given by V(x)=

∞ k=0

f^k(x)² for anyx∈Da(0). (1.5)

The Lyapunov functionV can be found theoretically using relation (1.5). In the fol- lowings, we will shortly present the procedure of determination and approximation of the domain of attraction using the functionV presented in [2,3].

The region of convergenceD0of the power series development ofVin 0 is a part of the domain of attractionDa(0). IfD0is strictly contained inDa(0), then there exists a point x⁰∈∂D0such that the functionVis bounded on a neighborhood ofx⁰. Let be the power

series development ofVinx⁰. The domain of convergenceD1of the series centered inx⁰ gives a new partD1\(D0D1) of the domain of attractionDa(0). At this step, the part D0 D1ofDa(0) is obtained.

If there exists a pointx¹∈∂(D0 D1) such that the functionVis bounded on a neigh- borhood ofx¹, then the domainD0 D1is strictly included in the domain of attraction Da(0). In this case, the procedure described above is repeated inx¹.

The procedure cannot be continued in the case when it is found that on the boundary of the domainD0 D1 ··· Dp obtained at stepp, there are no points having neigh- borhoods on whichV is bounded.

This procedure gives an open connected estimateDof the domain of attractionDa(0).

Note that f^−k(D),k∈Nis also an estimate ofDa(0), which is not necessarily connected.

The procedure described above is illustrated by the following examples.

Example 1.3. Let be the f :R→Rdefined by f(x)=x². Due to the equalityf^k(x)=x^2k the domain of attraction of the asymptotically stable steady statex=0 isDa(0)=(−1, 1).

The Lyapunov function isV(x)=_∞

k=0x^2k+1. The domain of convergence of the series is D0=(−1, 1) which coincides withDa(0).

Example 1.4. Let be the function f :Ω=(−∞, 1)→Ωdefined by f(x)=x/(e+ (1−e)x).

Due to the equality f^k(x)=x/(e^k+ (1−e^k)x) the domain of attraction of the asymp- totically stable steady statex=0 isDa(0)=(−∞, 1). The power series expansion of the Lyapunov functionV(x)=_∞

k=0|f^k(x)|²in 0 is V(x)=^∞

m=2

(m−1) ∞ k=0

e^−2k1−e^−km−2x^m. (1.6)

The radius of convergence of the series (1.6) is

r0=_mlim

→∞^m

(m−1)

∞ k=0

e^−2k1−e^−km−2=1, (1.7)

therefore the domain of convergence of the series (1.6) isD0=(−1, 1)⊂Da(0). More, V(x)→ ∞asx→1 andV(−1)<∞. The radius of convergence of the power series ex- pansion ofV in−1 is

r₋1=_mlim

→∞^m

^∞

k=1

e^ke^k−1^m−2(m−3)e^k+ 2

2e^k−1^{m+2 =}1, (1.8)

therefore the domain of convergence of the power series development ofVin−1 isD₋1= (−2, 0) which gives a new part ofDa(0).

Numerical results for more complex examples are given in [2,3].

2. Theoretical results when the matrixA=∂0f is a contraction (i.e.,A<1) The function f can be written as

f(x)=Ax+g(x) for anyx∈Ω, (2.1)

whereA=∂0f andg:Ω→Ωis anR-analytic function such thatg(0)=0 and limx→0(g(x) /x)=0.

Proposition 2.1. IfA<1, then there existsr >0 such thatB(r)⊂Ωandf(x)<x for anyx∈B(r)\ {0}.

Proof. Due to the fact that limx→0(g(x)/x)=0 there existsr >0 such thatB(r)⊂Ω and

g(x)<1− A

x for anyx∈B(r)\ {0}. (2.2) Let bex∈B(r)\ {0}. Inequality (2.2) provides that

f(x)=Ax+g(x)≤ Ax+g(x)<A+ 1− A

x = x (2.3)

therefore,f(x)<x.

Definition 2.2. LetR >0 be the largest number such thatB(R)⊂Ωandf(x)<xfor anyx∈B(R)\ {0}.

If for anyr >0,B(r)⊂Ωandf(x)<xfor anyx∈B(r)\ {0}, thenR=+∞and B(R)=Ω=Rⁿ.

Lemma 2.3. (a)B(R) is invariant to the flow of system (1.1).

(b) For anyx∈B(R), the sequence (f^k(x))k∈Nis decreasing.

(c) For anyp≥0 andx∈B(R)\ {0},ΔVp(x)=Vp(f(x))−Vp(x)<0, where Vp(x)=

p k=0

f^k(x)² for x∈Ω. (2.4)

Proof. (a) Ifx=0, then f^k(0)=0, for anyk∈N. Forx∈B(R)\ {0}, we havef(x)<

x, which implies thatf(x)∈B(R), that is,B(R) is invariant to the flow of system (1.1).

(b) By induction, it results that forx∈B(R) we have f^k(x)∈B(R) andf^k+1(x) ≤ f^k(x), which means that the sequence (f^k(x))k∈Nis decreasing.

(c) In particular, for p≥0 and x∈B(R), we have f^p+1(x) ≤ f(x)<x and

therefore,ΔVp(x)= f^p+1(x)²− x²<0.

Corollary 2.4. For any p≥0, there exists a maximal domainGp⊂Ωsuch that 0∈Gp

and forx∈Gp\ {0}, the (positive definite) functionVpverifiesΔVp(x)<0. In other words, for any p≥0, the functionVp defined by (2.4) is a Lyapunov function for (1.1) onGp. Moreover,B(R)⊂Gpfor anyp≥0.

Theorem 2.5. B(R) is an invariant set included in the domain of attractionDa(0).

Proof. Let bex∈B(R)\ {0}. We have to prove that limk→∞f^k(x)=0.

The sequence (f^k(x))k∈Nis bounded: f^k(x) belongs toB(R). Let be (f^kj(x))j∈Na con- vergent subsequence and let be limj→∞f^kj(x)=y⁰. It is clear thaty⁰∈B(R).

It can be shown that

f^k(x)≥y⁰ for anyk∈N. (2.5)

For this, observe first that f^kj(x)→y⁰ and (f^kj(x))k∈N is decreasing (Lemma 2.3).

These imply thatf^kj(x) ≥ y⁰for anykj. On the other hand, for anyk∈N, there exists kj∈N such that kj≥k. Therefore, as the sequence (f^k(x))k∈N is decreasing (Lemma 2.3), we obtain thatf^k(x) ≥ f^kj(x) ≥ y⁰.

We show now thaty⁰=0. Suppose the contrary, that is,y⁰=0.

Inequality (2.5) becomes

f^k(x)≥y⁰>0 for anyk∈N. (2.6) By means ofLemma 2.3, we have thatf(y⁰)<y⁰.

Therefore, there exists a neighborhoodUf(y⁰)⊂B(R) of f(y⁰) such that for anyz∈ Uf(y⁰) we havez<y⁰. On the other hand, for the neighborhoodUf(y⁰) there ex- ists a neighborhoodUy⁰⊂B(R) of y⁰such that for any y∈Uy⁰, we have f(y)∈Uf(y⁰). Therefore:

f(y)<y⁰ for anyy∈Uy⁰. (2.7) As f^kj(x)→y⁰, there exists ¯jsuch that f^kj(x)∈Uy⁰, for any j≥j. Making¯ y= f^kj(x) in (2.7), it results that

f^kj+1(x)=ff^kj(x)<y⁰ for j≥j¯ (2.8) which contradicts (2.6). This means thaty⁰=0, consequently, every convergent subse- quence of (f^k(x))k∈Nconverges to 0. This provides that the sequence (f^k(x))k∈Nis con- vergent to 0, andx∈Da(0).

Therefore, the ballB(R) is contained in the domain of attraction ofDa(0).

Forp≥0 andc >0 let beN_p^cthe set N_p^c=

x∈Ω:Vp(x)< c. (2.9) Ifc=+∞, thenN^c_p=Ω.

Theorem 2.6. Let bep≥0. For anyc∈(0, (p+ 1)R²], the setN^c_pis included in the domain of attractionDa(0).

Proof. Let bec∈(0, (p+ 1)R²] andx∈N_p^c. ThenVp(x)=p

k=0f^k(x)²< c≤(p+ 1)R², therefore, there exists k∈ {0, 1,...,p}such thatf^k(x)²< R². It results that f^k(x)∈

B(R)⊂Da(0), therefore,x∈Da(0).

Remark 2.7. It is obvious that forp≥0 and 0< c< cone hasN_p^c⊂N_p^c. Therefore, for a givenp≥0, the largest part ofDa(0) which can be found by this method isNp^cp, where

cp=(p+ 1)R². In the followings, we will use the notation Np instead ofNp^cp. Shortly, Np= {x∈Ω:Vp(x)<(p+ 1)R²}is a part ofDa(0). Let us note thatN0=B(R).

Remark 2.8. IfR=+∞(i.e.,Ω=Rⁿandf(x)<x, for anyx∈R\ {0}), thenNp= Rⁿfor anyp≥0 andDa(0)=Rⁿ.

Theorem 2.9. For the sets (Np)p∈N, the following properties hold:

(a) for anyp≥0, one hasNp⊂Np+1; (b) for anyp≥0, the setNpis invariant to f;

(c) for anyx∈Da(0), there existsp^x≥0 such thatx∈Np^x. Proof. (a) Let bep≥0 andx∈Np. ThenVp(x)=p

k=0f^k(x)²<(p+ 1)R², therefore, there exists k∈ {0, 1,...,p}such that f^k(x)²< R². It results that f^k(x)∈B(R) and therefore f^m(x)∈B(R), for anym≥k. Form=p+ 1 we obtainf^p+1(x)< R, hence Vp+1(x)=Vp(x) +f^p+1(x)²<(p+ 1)R²+R²=(p+ 2)R². Therefore,x∈Np+1.

(b) Let be x∈Np. If x< R then f^m(x)< R for any m≥0 (by means of Lemma 2.3). This implies that Vp(f(x))=p

k=0f^k(f(x))²=p+1

k=1f^k(x)²<(p+ 1)R², meaning that f(x)∈Np.

Let us suppose thatx ≥R. Asx∈Np, we have thatVp(x)=p

k=0f^k(x)²<(p+ 1)R², therefore, there existsk∈ {0, 1,...,p}such thatf^k(x)< R. It results that f^k(x)∈ B(R) and thereforef^m(x)∈B(R), for anym≥k. Form=p+ 1 we obtainf^p+1(x)< R.

This implies that Vp

f(x)=Vp(x) +f^p+1(x)²− x²<(p+ 1)R²+R²−R²=(p+ 1)R² (2.10)

therefore f(x)∈Np.

(c) Suppose the contrary, that is, there existx∈Da(0) such that for any p≥0,x /∈ Np. Therefore,Vp(x)≥(p+ 1)R² for any p≥0. Passing to the limit for p→ ∞in this inequality, provides thatV(x)= ∞. This means x∈∂Da(0) which contradicts the fact that x belongs to the open setDa(0). In conclusion, there exists p^x≥0 such that x∈

Np^x.

Forp≥0 let beMp= f^−p(B(R))= {x∈Ω: f^p(x)∈B(R)}, obtained by the trajectory reversing method.

Theorem 2.10. The following properties hold:

(a)Mp⊂Da(0) for anyp≥0;

(b) for anyp≥0,Mpis invariant to f; (c)Mp⊂Mp+1for anyp≥0;

(d) for anyx∈Da(0), there existsp^x≥0 such thatx∈Mp^x.

Proof. (a) AsMp=f^−p(B(R)) andB(R)⊂Da(0) (seeTheorem 2.5) it is clear thatMp⊂ Da(0).

(b) and (c) follow easily by induction, usingLemma 2.3.

(d)x∈Da(0) provides that f^p(x)→0 asp→ ∞. Therefore, there existsp^x∈Nsuch that f^p(x)∈B(R), for anyp≥p^x. This provides thatx∈Mpfor anyp≥p^x.

Both sequences of sets (Mp)p∈Nand (Np)p∈Nare increasing, and are made up of esti- mates ofDa(0). From the practical point of view, it is important to know which sequence converges more quickly. The next theorem provides that the sequence (Mp)p∈Nconverges more quickly than (Np)p∈N, meaning that for p≥0, the setMp is a larger estimate of Da(0) thenNp.

Theorem 2.11. For anyp≥0, one hasNp⊂Mp.

Proof. Let bep≥0 andx∈Np. We have thatVp(x)=p

k=0f^k(x)²<(p+ 1)R², there- fore, there existsk∈ {0, 1,...,p}such thatf^k(x)< R. This implies that f^m(x)∈B(R), for anym≥k. Form=pwe obtain f^p(x)∈B(R), meaning thatx∈Mp. 3. Theoretical results whenA=∂0f is a convergent noncontractive matrix

(i.e.,ρ(A)<1≤ A)

Proposition 3.1. Ifρ(A)<1≤ A, then there existp≥2 andrp>0 such thatB(rp)⊂Ω andf^p(x)<xfor anyp∈ {p,p+ 1,..., 2p−1}andx∈B(rp)\ {0}.

Proof. We have thatρ(A)<1 if and only if limp→∞A^p=0 (see [1]), which provides (to- gether withA ≥1) that there exists p≥2 such thatA^p<1 for any p≥p. Let be p≥2 fixed with this property.

The formula of variation of constants for anypgives:

f^p(x)=A^px+

p−1 k=0

A^p−k−1gf^k(x) ∀x∈Ω, p∈N. (3.1)

Due to the fact that for anyk∈Nwe have limx→0(g(f^k(x))/x)=0, there existsrp>0 such that for anyp∈ {p, p+ 1,..., 2p−1}the following inequality holds:

p₋1 k=0

A^p−k−1gf^k(x)<1−A^px for x∈Brp

\ {0}. (3.2) Let bex∈B(rp)\ {0}andp∈ {p,p+ 1,..., 2p−1}. Using (3.1) and (3.2) we have

f^p(x)= A^px+

p−1 k=0

A^p−k−1gf^k(x)

≤A^px+

p−1 k=0

A^p−k−1gf^k(x)

<A^p+ 1−A^px = x.

(3.3)

Therefore,f^p(x)<xforp∈ {p, p+ 1,..., 2p−1}andx∈B(rp)\ {0}. Definition 3.2. Let p≥2 be the smallest number such thatA^p<1 for anyp≥p(see the proof ofProposition 3.1). LetR > 0 the largest number be such thatB(R) ⊂Ωand f^p(x)<xforp∈ {p, p+ 1,..., 2p−1}andx∈B(R) \ {0}.

If for anyr >0, we have thatB(r)⊂Ωandf^p(x)<xfor any p∈ {p, p+ 1,..., 2p−1}andx∈B(r)\ {0}, thenR=+∞andB(R) =Ω=Rⁿ.

Lemma 3.3. (a) For anyx∈B(R) and p∈{p,p+ 1,..., 2p−1}, the sequence (f^kp(x))k∈N

is decreasing.

(b) For anyp≥pandx∈B(R) \ {0},f^p(x)<x.

(c) For any p≥pandx∈B(R) \ {0},ΔVp(x)=Vp(f(x))−Vp(x)<0, where Vp is defined by (2.4).

Proof. (a) Ifx=0, then f^p(0)=0, for anyp≥0.

Let bex∈B(R) \ {0}. We know thatf^p(x)<xfor anyp∈ {p,p+ 1,..., 2p−1}. It results that f^p(x)∈B(R) for any p∈ {p, p+ 1,..., 2p−1}. This implies that for any k∈Nwe havef^kp(x)<xandf^(k+1)p(x) ≤ f^kp(x), meaning that the sequence (f^kp(x))k∈Nis decreasing.

(b) Let bex∈B(R) \ {0}. Inequalityf^p(x)<xis true for any p∈ {p, p+ 1,..., 2p−1}.

Let bep≥2p. There exists q∈Nand p∈ {p, p+ 1,..., 2p−1}such thatp=qp+ p. Using (a), we have that f^p(x)∈B(R) and f^qp(y)≤ y, for anyy∈B(R), therefore

f^p(x)=f^qpf^p(x)≤f^p(x)<x (3.4)

(c) results directly from (b).

Corollary 3.4. For anyp≥p, there exists a maximal domain Gp⊂Ωsuch that 0∈Gp

and for anyx∈Gp\ {0}, the (positive definite) functionVp verifiesΔVp(x)<0. In other words, for anyp≥p, the function Vpis a Lyapunov function for (1.1) onGp. More,B(R) ⊂ Gpfor anyp≥p.

Lemma 3.5. For anyk≥p, there exists qk∈Nsuch that

f^(qk+3)p(x)≤f^k(x)≤f^qkp(x) for anyx∈B R. (3.5)

Proof. Let bek≥p. There exists a unique qk∈Nand a uniquepk∈ {p, p+ 1,..., 2p−1} such thatk=qkp+pk.Lemma 3.3provides that for anyx∈B(R) we have that f^qkp(x)∈ B(R) and f^pk(x) ≤ x. It results that

f^k(x)=f^pkf^qkp(x)≤f^qkp(x) for anyx∈BR¯. (3.6)

On the other hand, we have (qk+ 3)p=k+ (3p−pk). As (3p−pk)∈ {p+ 1,p+ 2,..., 2p} andk≥p, Lemma 3.3 provides that for anyx∈B(R) we have that f^k(x)∈B(R) and

f^3p−pk(x) ≤ x. Therefore

f^(qk+3)p(x)=f^3p−pkf^k(x)≤f^k(x) for anyx∈B R. (3.7)

Combining the two inequalities, we get that

f^(qk+3)p(x)≤f^k(x)≤f^qkp(x) for anyx∈B R (3.8)

which concludes the proof.

Theorem 3.6. B(R) is included in the domain of attraction Da(0).

Proof. Let bex∈B(R) \ {0}. We have to prove that limk→∞f^k(x)=0.

The sequence (f^k(x))k_∈Nis bounded (seeLemma 3.3). Let be (f^kj(x))j_∈Na convergent subsequence and let be limj→∞f^kj(x)=y⁰.

We suppose, without loss of generality, thatkj≥pfor any j∈N.Lemma 3.5provides that for anyj∈Nthere existsqj∈Nsuch that

f^(qj+3)p(x)≤f^kj(x)≤f^qjp(x). (3.9)

As (f^qjp(x))j∈Nand (f^(qj+3)p(x))j∈N are subsequences of the convergent sequence (f^qp(x))q∈N(decreasing, according toLemma 3.3), it results that they are convergent.

The double inequality (3.9) provides that limj→∞f^qjp(x) = y⁰. Therefore, limq→∞

f^qp(x) = y⁰. It can be shown that

f^k(x)≥y⁰ for anyk≥p. (3.10)

For this, remark that limq→∞f^qp(x) = y⁰and (f^qp(x))q∈Nis decreasing (Lemma 3.3), which implies thatf^qp(x) ≥ y⁰for anyq∈N. On the other hand,Lemma 3.5 provides that for anyk≥pthere existsqksuch thatf^(qk+3)p(x) ≤ f^k(x). Therefore, f^k(x) ≥ f^(qk+3)p(x) ≥ y⁰, for anyk≥p.

We show now thaty⁰=0. Suppose the contrary, that is,y⁰=0.

Inequality (3.10) becomes

f^k(x)≥y⁰>0 for anyk≥p. (3.11)

By means ofLemma 3.3, we have thatf^p(y⁰)<y⁰.

There exists a neighborhoodU_f^p_(y⁰₎⊂B(R) of f^p(y⁰) such that for anyz∈U_f^p_(y⁰₎we havez<y⁰. On the other hand, for the neighborhoodU_f^p_(y⁰)there exists a neigh- borhoodUy⁰⊂B(R) of y⁰such that for anyy∈Uy⁰, we havef^p(y)∈U_f^p_(y⁰₎. Therefore:

f^p(y)<y⁰ for anyy∈Uy⁰. (3.12)