Abstract

The aim of this paper is to obtain a unified treatment of some iterative methods. We obtain some conditions for which a given equation admits a unique solution in a certain ball. The main obtained result refers to the convergence of the modified chord method.

Authors

Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

Keywords

?

PDF

Cite this paper as:

I. Păvăloiu, A unified treatment of the modified Newton and chord methods, Carpathian J. Math. 25 (2009) no. 2, pp. 192-196.

About this paper

Publisher Name

Universitatea Tehnica din Cluj-Napoca

Print ISSN

1584-2851

Online ISSN

1843-4401

Google Scholar Profile

References

[1] Berinde, V., Iterative Approximation of Fixed Point, Lecture Notes in Mathematics, Springer, 2007
[2] Krasnoselskij, M. A., Vainikko, G. M., Zabreiko, P. P., Rutitki, Ia. B. and Otetenko, BIA, Priblijenie resenie operatornıh uravnenii, Iydatelstva Nauka, Glavnaia Redactia Fizico-Mathematicescoi Literaturı, Moskva, 1969
[3] Pavaloiu, I., La resolution des equations par interpolation, Mathematica 23 (46) (1981), No. 1, 61-72
[4] Rus, A. I., Petrusel, A. and Petrusel, Gabriela, Fixed Point Theory. Cluj University Press, 2008

Paper (preprint) in HTML form

A unified treatment of the modified Newton and chord methods

A unified treatment of the modified Newton and chord methods

Ion Păvăloiu
Abstract

The aim of this paper is to obtain a unified treatment of some iterative methods. We obtain some conditions for which a given equation admits a unique solution in a certain ball. The main obtained result refers to the convergence of the modified chord method.

1 Introduction

Let X be a Banach space and DX. Given x0D, we consider the ball S(x0,ρ)={xXxx0ρ},with ρ, ρ>0 and we assume that S(x0,ρ)D.

In this paper we shall study certain aspects of the problems regarding the existence, uniqueness, and the approximation of the solution of an operatorial equation of the form

(1) f(x)=0

where f:DX.

LetA:XX be a linear and continuous operator. For the approximation of the solution x¯ of equation (1) we shall consider the sequence (xn)n0 given by (2)

(2) xn+1=xnAf(xn),n=0,1,,x0D.

In the following we shall obtain conditions under which equation (1) has a unique solution in the ball S(x0,ρ), and, moreover, the sequence (xn)n0 generated by (2) is convergent and limxn=x¯.

We shall apply the obtained results to the unified study of the convergence of some sequences of the form (2), namely generated by the modified Newton method, and the modified chord method. For the modified Newton method we shall retrieve in this way a known result, which for the modified chord method the result is new.

2 Existence, uniqueness and approximation

Regarding the existence and uniqueness of solution of equation (1) in the ball S(x0,ρ), and the convergence of sequence (2), the following result holds:

Theorem 1

If x0D, ρ, A and f verify the following assumptions:

i1.

S(x0,ρ)D;

ii1.

appliction A is invertible;

iii1.

there exists q, 0<q<1 such that x,yS(x0,ρ) one has:

(3) A[f(x)f(y)A1(xy)]qxy;
iv1.

the following relation holds:

(4) Af(x0)ρ(1q),

then the following hold true:

j1.

equation (1) has a unique solution x¯S(x0,ρ);

jj1.

sequence (xn)n0 generated by (2) is convergent and limxn=x¯;

jjj1.

the following hold true:

(5) x¯xnqn1qx1x0,n=1,2,,;
(6) x¯xn+1q1qxn+1xn,n=0,1,,

Proof. Consider the operator h:XX given by

(7) h(x)=xAf(x).

In the following we shall prove that the image of the ball S(x0,ρ) by h remains in S(x0,ρ), and moreover,h is a contraction on this ball.

In this sense we notice that h may be written as

(8) h(x)=x0Af(x0)A[f(x)f(x0)A1(xx0)].

By (8) and (3) for y=x0 and by 𝐢𝐯1. we get

(9) h(x)x0ρ(1q)+qxx0ρ,

for all xS(x0,ρ). By (9) it follows that for all xS(x0,ρ), h(x) given by (7) belongs to S(x0,ρ).

Consider now y1, y2S. By (7) we get:

h(y2)h(y1) =y2y1+A[f(y1)f(y2)])
=A[f(y1)f(y2)A1(y1y2)].

whence, taking into account (3) it follows

h(y2)h(y1)qy2y1for all y1,y2S(x0,ρ),

i.e., h is a contraction on S(x0,ρ). Consequently, h has a unique fixed point x¯S(x0,ρ). Since A is a linear invertible operator by (3) it follows that equation (1) has the unique solution x¯S(x0,ρ).

Properties 𝐣𝐣1 and 𝐣𝐣𝐣1 are immediate consequences of the fact that X is a Banach space and h is a contraction on the invariant ball S(x0,ρ) (see [1], [4]).Denoting ρ=Af(x0) then it can easily seen that

(10) p1+qx¯x0p1q.

These relations are obtained from (8) for x=x¯ and x¯=h(x¯).

From (10), if we replace x0=xn and p=Af(xn) we obtain lower and upper error bounds at the n-th step:

(11) Af(xn)1+qx¯xnAf(xn)1q

The last relations offer a posteriori error bounds.  

3 The modified chord method

We consider now the divided differences of f at some given points in D. Let (X) denote the set of linear operators from X to X.

Definition [3]. The linear operator α(x,y)L(X) is called first order divided difference of f at the points x,yX if

a)

α(x,y)(xy)=f(x)f(y);

b)

if f is Fréchet differentiable at y then α(y,y)=f(y).

We shall use in the following the usual notation α(x,y)=[y,x;f]. In order to approximate the solution of equation (1) we consider the sequence (xn)n0 given by

(12) xn+1=xn[x0,x¯0;f]1f(xn),n=0,1,,x0,x¯0D.

We obtain the following result.

Theorem 2

If x0,x¯0D, ρ and f verify the conditions

i2.

x¯0S(x0,ρ);

ii2.

the linear operator [x0,x¯0;f] is invertible

iii3.

there exists q, 0<q<1 such that for all x,yS(x0,ρ) one has

(13) [x0,x¯0;f]1{[y,x;f][x0,x¯0;f]}q;

the following relation holds:

p1=[x0,x¯0:f]1f(x0)ρ(1q),

then the following hold true:

j1.

equation (1) has a unique soltution x¯S;

jj2.

sequence (xn)n0generated by (12) is convergent and limxn=x¯;

jjj3.

the following relations are true:

(14) x¯xnqn1qx1x0,n=1,2,,;
(15) x¯xn+1q1qxn+1xn;n=0,1,,
(16) p11+qx¯x0p11q;
(17) [x0,x¯0;f]1f(xn)1+q x¯xn
[x0,x¯;f]1f(xn)1q<n=0,1,,

Proof. We shall prove that this result is a consequence of Theorem 1 and of relations (10) and (11). In this sense it suffices to show that relation (3) follows from (13) for A=[x0,x¯0;f]1.

The definition of the divided differences, leads to the equality

[x0,x¯0;f]1{f(x)f(y)[x0,x¯0;f](xy)}
=[x0,x¯0;f]1{[y,x;f][x0,x¯0;f]}(xy),

whence, by (13), it follows for A=[x0,x¯0;f]1,

[x0,x¯0;f]1[f(x)f(y)[x0,x¯0;f](xy)]
qxy.

It is obvious that Theorem 2 is a consequence of Theorem 1 and of relations (10) and (11).  

4 The modified Newton method

Assume that f is Fréchet differentiable at all points xD. Let x0D and f(x0)(X). Assume that f(x0) is invertible.

In order to approximate x¯ we shall consider the sequence (xn)n0 generated by the modified Newton method.

(18) xn+1=xn[f(x0)]1f(xn),x0D,n=0,1,

Concerning the convergence of this sequence the following result holds:

Theorem 3

. [2]. If x0D, ρ, ρ>0 and f verify

i3.

S(x0,ρ)D;

ii3.

f is Fréchet differentiable at all points xS(x0,ρ), and f(x0) is a linear continuous operator;

iii3.

the operator f(x0) is invertible

iv3.

there exists q, 0<q<1 such that for all xS(x0,ρ) one has.

(19) [f(x0)]1[f(x)f(x0)]q;
v3.

one has

p¯=[f(x0)]1f(x0)ρ(1q),

then the following relations hold:

j3.

equation (1) has a unique solution x¯S(x0,ρ);

jj3.

the sequence (xn)n0 given by (18) is convergent and limxn=x¯;

jjj3.

the following estimations hold true:

(20) x¯xnqn1qx1x0,n=1,2,,
(21) x¯xn+1q1qxn+1xn,n=0,1,,
(22) p¯1+qx¯x0p¯1q.
(23) [f(x0)]1f(xn)1+qx¯xnf(x0)]1f(xn)1q.

Proof. It is sufficient to show that relation (19) implies relation (3) for A=[f(x0)]1.

Let g:S(x0,ρ)X be an operator differentiable at all points xS(x0,ρ). Then it is known (see, e.g.,[2]) that for all x,yS(x0,ρ) one has

(24) g(x)g(y)xysup0<θ<1f(y+θ(xy)).

Let now take g given by

(25) g(x)=[f(x0)]1[f(x)f(x0)x],

then

(26) g(x)=[f(x0)]1[f(x)f(x0)].

If we take into account (25) and (26), by (24) we get

[f(x0)]1[f(x)f(y)f(x0)(xy)]
xysup.[f(x0)]1[f(y+θ(xy))f(x0)]
qxy,

which shows that (3) is verified for A=f(x0)1. Theorem 3 is a consequence of Theorem 1, and therefore properties 𝐣3𝐣𝐣𝐣3are true.  

References

  • [1] Berinde, Vasile, Iterative Approximation of Fixed Point, Lecture Notes in Mathematics, Springer (2007).
  • [2] Krasnoselskij, M.A., Vainikko, G.M., Zabreiko, P.P., Rutiţki, Ia. B., Oteţenko, BIA, Priblijenie resenie operatornîh uravnenii. Iydatelstva Nauka, Glavnaia Redactia Fizico-Mathematicescoi Literaturî, Moskva, 1969.
  • [3] Păvăloiu, Ion, La résolution des equations par intérpolation, Mathematica, 23(46), 1, (1981), pp. 61-72.
  • [4] Rus, A. Ioan, Petruşel, Adrian, Petruşel Gabriela. Fixed Point Theorhy. Cluj University Press. (2008).
2009

Related Posts