View of The approximation of the solutions of equations using approximant sequences

Rev. Anal. Num´er. Th´eor. Approx., vol. 32 (2003) no. 1, pp. 21–30 ictp.acad.ro/jnaat

THE APPROXIMATION OF THE SOLUTIONS OF EQUATIONS USING APPROXIMANT SEQUENCES

ADRIAN DIACONU^∗

Abstract. We intend to characterize the convergence of a certain sequence that belongs to a subset of a Banach space towards the solution of an equation ob- tained by the annulment of a nonlinear mapping that is defined on this subset and that takes values in another linear normed space. This mapping has a Fr´echet derivative of a certain order which verifies the Lipschitz condition. We can es- tablish some conditions that are enough both for the existence of the equation’s solution and for a speed of convergence of a certain order for the approximant sequence.

MSC 2000. 65J15.

Keywords. Convergence of the approximant Sequences for operatorial equa- tions in Banach spaces.

1. INTRODUCTION

One of the most often used methods for the approximation of the solution of an equation is that of constructing a sequence that is convergent to that solution.

Let us consider X and Y two normed linear spaces, their normsk·k_X and respectivelyk·k_Y ,a setD⊆X,a function f :D→Y, θ_Y the null element of the space Y and, using these elements, the equation:

(1) f(x) =θ_Y.

To clarify these notions, we consider:

Definition 1. In addition to the data above, let us also considerp∈N,not null and (xn)_n∈N⊆D. We say that the sequence is an approximant sequence of the order p of a solution of the equation (1), if there exist α, β ≥0 so that for any n∈N we have:

(2)

kf(xn+1)k_Y ≤αkf(xn)k^p_Y , kx_n+1−xnk_X ≤βkf(xn)k_Y .

As we showed in [3] and [4], if (x_n)_n∈N is an approximant sequence of the order p, p ≥ 2, X is a Banach space, f : D → Y is continuous, and the

∗“Babe¸s-Bolyai” University, Faculty of Mathematics and Computer Science, str. M. Ko- g˘alniceanu 1, 3400 Cluj-Napoca, Romania, e-mail: [email protected].

constants α andβ from Definition 1 are chosen so that:

(3) ρ₀=α^p−11 kf(x₀)k_Y ,

S(x₀, δ) =x∈X : kx−x₀k_X ≤δ ⊆D with:

δ= βα^p−11 1−ρ^p−1₀ ,

then the approximant sequence is convergent towards the element ¯x which, together with all the terms of the sequence (xn)_n∈Nis placed in the ballS(x0, δ) and ¯x is a solution of the equation (1). For any n∈N we have the following inequalities:

(4)

kx_n−1−xnk_X ≤βα^p−11 ρ^p₀ⁿ,

k¯x−x_nk ≤ βα^p−11 ρ^p₀ⁿ 1−ρ^p₀^n(p−1)

These inequalities justify the fact of calling it an approximant sequence of the orderp.

In order to verify the inequalities (4) as well as the affirmations preceding them we have to make the inequalities (2) true. But this often proves to be difficult, and this is the reason for which we will try to replace them with more practical conditions. Nevertheless we will consider that the function f :D→Y admits Fr´echet derivatives up to the orderp included.

As a series of iterative methods known in practice use the inverse of the Fr´echet derivative of the first order of the mapping f⁰(x_n)⁻¹,an unpractical condition, as the existence of this mapping implies solving the linear equation f⁰(x_n)h = q; h ∈ X, q ∈ Y, we will try to eliminate the conditions about the inverse of the Fr´echet derivative from the hypothesis, but we will try to demonstrate this existence.

From the results that have inspired this research we will mention primar- ily the well-known theorem of L. V. Kantorovich for the case when the ap- proximant sequence (x_n)_n∈Nis generated by the Newton–Kantorovich method [5], [6]. In this case the existence of the mapping f⁰(x)⁻¹ ∈ (Y, X)^∗ is sup- posed only for x =x₀, as this is the initial point of the iterative method. In what the convergence of the same method is concerned, we also mention the result obtained by Mysovski, I. P. [7], where from a certain point of view the conditions of the convergence are simpler, but the existence of the mapping f⁰(x)⁻¹ and of a constantM >0 satisfying the inequality f⁰(x)⁻¹≤M for anyxan element of a certain ball centered in the initial elementx₀is imposed.

Then P˘av˘aloiu, I., in [8] and [9], generalizes these results for the convergence of a sequence generated by the relation of recurrence:

(5) x_n+1=Q(x_n),

where Q : X → X verifies certain conditions and n ∈ N. In the result ob- tained by P˘av˘aloiu, I., Mysovski’s condition mentioned above does not appear explicitly, but the use of the result in concrete cases makes it necessary.

We will proceed in the same way as in our papers [1], [2].

2. MAIN RESULT

Let us now note by (X^p, Y)^∗ the set of p-linear and continuous mappings defined on X^p =X× · · · ×X (the p times Cartesian product), taking values inY.

The fact that the mappingf^(p):D→(X^p, Y)^∗verifies the Lipschitz condi- tion is resumed to the existence of the constantL >0,so that for anyx, y∈D we have:

(6) f^(p)(x)−f^(p)(y)≤Lkx−yk_X, so that Lwill be called Lipschitz constant.

We can easily deduce the following inequality for anyx, y∈D we have:

(7) f(x)−f(y)−

p

P

i=1 1

i!f⁽ⁱ⁾(y)(x−y)ⁱ_Y ≤ _(p+1)!^L kx−yk^p+1_X . Then if we takex₀∈Dand δ >0 so that:

S(x₀, δ) =x∈X:kx−x₀k_X ≤δ ⊆D

and we define the numbers L₀, . . . , L_p, L_p+1 > 0 through L_p+1 = L and for any k∈ {0,1, . . . , p} we have:

(8) Lk=f^(k)(x0)+Lk+1δ, then for anyx∈S(x0, δ) andk∈ {0,1, . . . , p}we have:

(9) f^(k)(x)≤L_k+1δ

and for any x, y∈S(x₀, δ) andk= 1,2, . . . , p+ 1 we have:

f^(k−1)(x)−f^(k−1)(y)≤L_kkx−yk_X.

Under the conditions mentioned above, the following takes place:

Theorem 2. In addition to the data above we consider p ∈ N, δ > 0, (x_n)_n∈N⊆D.

Assume that:

i) X is a Banach space andS(x0, δ)⊆D, S(x0, δ) representing the ball with the centerx₀ and radius δ;

ii) the function f : D → Y admits Fr´echet derivatives up to the order p including it, and for f^(p) : D → (X^p, Y)^∗, L > 0 such that the following inequality holds for any x, y∈D we have the inequality:

f^(p)(x)−f^(p)(y)≤Lkx−yk_Y ;

iii) there exist the numbers a, b≥0 so that for any n∈N we have:

(10) f(xn) +

p

P

i=1 1

i!f⁽ⁱ⁾(xn)(xn+1−xn)ⁱ

Y ≤akf(x_n)k^p+1_Y and

(11) f⁰(x_n) (x_n+1−x_n)_Y ≤bkf(x_n)k_Y ; iv) the mapping f⁰(x0)∈(X, Y)^∗ is invertible;

v) using the notation:

(12)

ρ₀ =f(x₀)

Y, B₀=f⁰(x₀)⁻¹, h₀ =bL₂B₀²ρ₀, M =B₀e^1+2−2p+3, α=a+L^(bM)_(p+1)!^p+1

suppose the following inequalities hold:

(13) h₀ ≤ ¹₂, α^1pρ₀ < ¹₄, δ≥ _1−αρ^{bM ρ0}p 0

, then:

j) xn∈S(x0, δ), f⁰(x0)⁻¹ exists and f⁰(x0)⁻¹≥M, for anyn∈N; jj) equation (1) admits a solution x¯∈S(x₀, δ);

jjj) the sequence(xn)_n∈N is an approximant sequence of the order p+ 1of this solution of the equation(1);

jv) the following estimates hold for anyn∈N: (14) maxⁿkf(x_n)k_Y ,_{M b}¹ kx_n+1−x_nk_X^o≤α

(p+1)n−1

p kf(x₀)k^(p+1)_Y ⁿ and

(15) kx¯−xnk_X ≤M bα

(p+1)n−1

p kf(x0)k^(p+1)_Y ⁿ 1−(αkf(x₀)k^p_Y)^(p+1)n.

Proof. From the invertibility of the mapping f⁰(x0) ∈ (X, Y)^∗ we clearly deduce thatkf⁰(x0)k,kf⁰(x0)⁻¹k>0.

Let the sequences (ρ_n)_n∈N, (B_n)_n∈Nand (h_n)_n∈Nbe so thatρ₀ =kf⁰(x₀)k, B₀ =kf⁰(x₀)⁻¹k,and for any n∈N,we have:

hn=bL2B₀²ρn, ρn+1=αρ^p+1_n , Bn+1 = Bn

1−h_n. We will show that for anyn∈N the following statements are true:

a) xn∈S(x0, δ) ;

b) f⁰(x_n)⁻¹∈(Y, X)^∗ exists, andkf⁰(x_n)⁻¹k ≤B_n; c) kf(xn)k_Y ≤ρn=α^−1p α^1pρ0(p+1)ⁿ

;

d) hn≤minⁿ¹₂, β^−1p(βh₀)^(p+1)no,whereβ = _(4h⁴

0)^p; e) B₀ ≤B_n≤M.

Using the mathematical induction we notice that for n= 0 the statements a)–e) are evidently true from the hypotheses of the theorem with the notations we have introduced.

Let us suppose that for anyn≤kthe assertions a)–e) are true, and let us demonstrate them for n=k+ 1.

a) We notice that for any n∈N, n≤kwe have:

kx_n+1−x_nk_X ≤f⁰(x_n)⁻¹f⁰(x_n)(x_n+1−x_n)

Y ≤M bα^−1p α^1pρ₀^(p+1)n, from where:

kx_k+1−x₀k_X ≤M bα^−1pρ₀

k

X

n=0

α^1pρ₀^(p+1)n−1≤ M bρ₀ 1−αρ^p₀ ≤δ which shows thatx_k+1∈S(x₀, δ).

b) Let

H_K =f⁰(x_k)⁻¹ f⁰(x_k)−f⁰(x_k+1)∈(X, X)^∗,

its existence and its belonging to (X, X)^∗ being guaranteed by the hypothesis of the induction. It is obvious that:

kH_kk ≤B_kL₂kx_k+1−x_kk_X ≤bL₂B_k²ρ_k=h_k≤ ¹₂ <1,

and according to the Banach theorem we deduce that (IX −Hk)⁻¹ ∈(X, X)^∗ and:

k(IX−Hk)⁻¹k ≤ 1

1− kH_kk ≤ 1 1−h_k,

whereI_X :X →X represents the identical mapping of the spaceX.

Obviously f⁰(x_k+1) = f⁰(x_k) (I_X −H_k) and because f⁰(x_k)⁻¹ ∈ (Y, X)^∗ exists, the mappingf⁰(x_k+1)⁻¹= (I_X −H_k)⁻¹f⁰(x_k)⁻¹exist as well and:

kf⁰(xk+1)⁻¹k ≤ k(IX −Hk)⁻¹k · kf⁰(xk)⁻¹k ≤ Bk

1−h_k =Bk+1. c) Clearly:

kf(x_k+1)k_Y ≤f(x_k+1)−f(x_k)−

p

X

i=1 1

i!f⁽ⁱ⁾(x_k)(x_k+1−x_k)ⁱ

Y

+f(xk) +

p

X

i=1 1

i!f⁽ⁱ⁾(xk)(xk+1−xk)ⁱ

Y ≤

≤^ha+^{L(M b)}_(p+1)!^p+1ikf(x_k)k^p+1_Y

≤αρ^p+1_k

=ρ_k+1,

asα^p1ρ_k+1 = α^1pρ_k^p+1,soρ_k+1 =α^−1p α^1pρ₀^(p+1)k+1.

d) We have the equalities:

h_k+1 =L₂bB²_k+1ρ_k+1=L₂bαρ^p+1_{k 1−h}^Bk

k

2

=αρ^p_k ^hk

(1−h_k)². Since h_k≤ ¹₂ and ρ_k < ρ₀, we have h_k+1≤2αρ^p₀,soh_k+1 ≤ ¹₂. Also:

h_k+1 = αh_k

(1−h_k)² · h^p_k

bL2B_k^2p = α

(L₂b)^p · 1

B_k^2p · (h_k)^p+1 (1−h_k)². FromB_k ≥B₀ and _(1−h¹

k)² ≤4 we deduce that:

h_k+1 ≤ 4αh^p+1_k

(bL₂)^pB₀^2p < 4h^p+1_k

4^pρ^p₀ bL2B₀^2p =βh^p+1_k

and then, it the same way as in the proof of c) we deduce that h_k+1 = β^−1p β^1ph₀^(p+1)

k+1

.

e) Because of the relation:

B_k+1 = B_k 1−h_k

and from the condition h_k ∈]0,¹₂] which implies _1−h¹

k ≥ 1, B_k+1 ≥ B_k from whereBk+1≥B0.

Asβ^1ph₀= ^41/p₄ ≤1 we deduce that:

maxn∈N

nβ^−1p β^1ph₀^(p+1)

no

=β^−1p β^1ph₀=h₀ and the same initial relation implies:

B_k+1= B₀

(1−h₀) (1−h₁). . .(1−h_k)

≤B₀^h1 +_k+1¹

k

X

i=0 hi

1−hi

ik+1

≤B₀^h1 +_(k+1)(1−h¹

0) k

X

i=0

h_i^ik+1.

For anyk∈N we have:

h_k+1= αh_kρ^p_k

(1−h_k)² ≤2 α^p1ρ₀^p(p+1)

k

and:

k

X

i=0

h_i =h₀+ 2

k

X

i=1

α^1pρ₀^p(p+1)i−1

<h₀+ 2αρ^p₀

k

X

i=1

(αρ^p₀)ⁱ⁻¹

<h₀+ ^2αρ

p 0

1−αρ^p₀²

<¹₂ +^22p

2−2p+1

2^2p2−1

=¹₂ + 2^−2p+2. So, from h0 < ¹₂,we have:

B_k+1 ≤B₀ 1 +¹⁺²_k+1^−2p+3k+1 ≤B₀exp1 + 2^−2p+3=M.

From the above we deduce that the statements a)–e) are true forn=k+ 1.

According to the principle of mathematical induction these statements are true for any n∈N.

Now we will deduce that the sequence (xn)_n∈N is a Cauchy sequence, be- cause:

kx_n+m−xnk_X <M bα^−1p α^1pρ0(p+1)ⁿ m

X

i=1

(αρ^p₀)^(p+1)

i−1

< M b α^p1ρ0(p+1)ⁿ

α^1p1−(αρ₀)^(p+1)n .

The last inequality and the condition α^p1ρ0 < ¹₄ < 1, determine the fact that (x_n)_n∈N is a fundamental sequence in the Banach spaceX, so (x_n)_n∈N is convergent. If we note ¯x= limn→∞x_n∈X and if we make so thatm→ ∞in the previous inequality we deduce the inequality (15), from where for n= 0 we can deduce:

k¯x−x0k_X ≤ bM ρ0

1−αρ^p₀ ≤δ, so ¯x∈S(x0, δ).

From:

kf(xn)k_Y ≤α^−1p α^1pρ₀^(p+1)n

and the conditionα^1pρ0<1 we deduce that lim_n→∞kf(x_n)k_Y = 0,from where f(¯x) =θ_Y, so ¯x is a solution of the equation (1).

The inequalities:

kx_n+1−x_nk_X ≤M bkf(x_n)k_Y , kf(xn+1)k_Y ≤αkf(xn)k^p+1_Y ,

show that the sequence (xn)_n∈N is an approximant sequence of the orderpfor the solution ¯x. In this way the theorem is proved.

3. SPECIAL CASE

Now we will see how Theorem 2 is applied in the case of particular process of approximation.

Let us first suppose that the function f :D → Y admits for any x ∈ D a Fr´echet derivative of the first order, anL >0 exists so that:

f⁰(x)−f⁰(y)≤Lkx−yk_X

for any x, y ∈ D, and the sequence (x_n)_n∈N ⊆ D verifies for any n ∈ N the equality:

(16) f⁰(xn) (xn+1−xn) +f(xn) =θY.

Obviously, if for any n∈N, f⁰(x_n)⁻¹ exists, the relation (16) is equivalent to:

(17) xn+1 =xn−f⁰(xn)⁻¹f(xn),

form under which the Newton–Kantorovich method is well known. But the form (16) will be one of the conclusions of the statement that will be estab- lished.

It is clear that the inequalities (10) and (11) of the hypothesis iii) of Theo- rem 2 are verified fora= 0 and b= 1.

In this case p = 1, L2 =L, h0 = 2LB₀²ρ0, α = ^LM₂², M = kf⁰(x0)⁻¹ke³, and thus the inequality of hypothesis v) of Theorem 2 becomesρ₀< ¹₄.

As αρ0 = ^LM2h0

4LB₀² = ^e9₄^h0, we need the condition h0 < _e¹9 or B₀²ρ0 < _2e¹9L, condition that evidently also impliesh₀≤ ¹₂.

In what the radius of the ball on which the properties take place is con- cerned, it verifies the inequality δ≥ _1−αρ^{M ρ0}

0. Asαρ0 < ¹₄ we deduce that _1−αρ¹

0 < ¹₄ and so ifδ ≥ ^{3M ρ}₄ ⁰ the requirement is fulfilled. Also, M =kf⁰(x0)⁻¹ke³.

In this way we have the following:

Corollary 3. We consider the same elements as in Theorem 1. If the hypotheses i), ii) andiv)of this theorem are verified for p= 1,in addition the sequence verifies, for any n∈N,the equalities:

f⁰(xn) (xn+1−xn) +f(xn) =θ_Y, and the initial point x₀ ∈D verifies the inequality:

kf⁰(x0)⁻¹k²kf(x0)k_Y < 1 2e⁹L, then:

j) x_n∈S(x₀, δ),the mapping f⁰(x_n)⁻¹ ∈(Y, X)^∗ exists and:

xn+1 =xn−f⁰(xn)⁻¹f(xn), kf⁰(xn)⁻¹k ≤ kf⁰(x0)⁻¹ke³, for anyn∈N;

jj) equation (1) admits a solution x¯∈S(x0, δ);

jjj) the sequence(xn)_n∈N is an approximant sequence of the second order of the solution x¯ of this equation;

jv) the following evaluations take place:

maxkf(x_n)k_Y ,_M¹ kx_n+1−x_nk_X ≤ ^LM₂²²ⁿ⁻¹kf(x_n)k²_Yⁿ, k¯x−xnk_X ≤ M ρ0 ρ0LM²

2

2ⁿ

1− ρ₀^LM₂²²ⁿ ,

where M =kf⁰(x0)⁻¹ke³ and L >0 represent the Lipschitz constant of the mappingf⁰ :D→(X, Y)^∗.

Another case in which Theorem 2 is applied is the case of the Chebyshev method, that is to be studied in a forthcoming paper.

REFERENCES

[1] Diaconu, A.,Sur quelques m´ethodes it´eratives combin´ees,Mathematica,22(45), no. 2, pp. 247–261, 1980.

[2] Diaconu, A., Sur la mani`ere d’obtenir et sur la convergence de certaines m´ethodes it´eratives, “Babe¸s–Bolyai” University, Faculty of Mathematics and Phisics, Research Seminars, Seminar on Functional Analysis and Numerical Methods, Preprint Nr. 1, pp. 27–74, 1987.

[3] Diaconu, A.,On the approximation of the solution of equations in Banach spaces using approximant sequences,Proceeding of the Conference on Analysis, Functional Equations, Approximation and Convexity in Honor of Professor Elena Popoviciu, Cluj-Napoca, Oc- tober 15–16, pp. 62–72, 1999.

[4] Diaconu, A.,Remarks on the convergence of some iterative methods of the Traub type, Studia Univ. “Babe¸s–Bolyai”, Mathematica,XLII, no. 2, pp. 47–60, 1997.

[5] Kantorovich, L. V.,Functionalnˆıi analiz i pridcladnaia mathematica,U. M. N.III,6, (28), pp. 89–185, 1948 (in Russian).

[6] Kantorovich, L. V.,and Akilov, G. P., Functional Analysis, Editura S¸tiint¸ific˘a ¸si Enciclopedic˘a, Bucure¸sti, 1986 (in Romanian).

[7] Mysovski, I. P.,Na shodimosti metoda Newtona,Trudˆı mat. inst. V., A., Steklova,28, pp. 145–149, 1949 (in Russian).

[8] P˘av˘aloiu, I., Sur les proc´ed´es `a un ordre ´elev´e de convergence, Mathematica, Cluj, 12(35), no. 2, pp. 309–324, 1970.

[9] P˘av˘aloiu, I.,Introduction to Approximating the Solutions of Equations,Editura Dacia, Cluj-Napoca, 1976 (in Romanian).

Received by the editors: September 28, 1998.