On the development of Steffensen's method and applications to Hammerstein equations

Abstract

We construct an analog of Steffensen's method for solving nonlinear operator equations. Proposed method is a kind of two stage iterative process. We study the order of convergence of the method. It is shown that the proposed analog of Stefensen's method, which does not use derivatives, has higher order of convergency then Newton method, other generalizations of chord method or other known modifications of Steffensen's method. Results of numerical experiments with Hammerstein equation are presented.

Introduction

where

is a mapping from X to X:

We construct an analog of Steffensen’s method for solving the operator equation (1) as follows x~(k+1) = x(k) x(k) = x~(k)

hF hF x~(k); x~(k) 1. for each fixed x0; x00 2 X operator F (x0; x00) is such that F (x0; x00)(x0 2. if the Frechet derivative F 0(x) exists then F (x; x) = F 0(x): Note, that functional F (x;0 x00) is obviously nonlinear with respect to x0; x00: Definition 1 does not defines a unique operator F (x0; x00); indeed the first divided difference could be specified in a numerous of ways. One of such specification is given in

Statement 1.[10] If there exists a continuous derivative 0(x) in the Gateau sense on the interval [x0; x00]; then we can define the first divided difference (x0; x00) as a Riemann’s abstract integral1 [11]: ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) here M2 is the maximum of the norm of the second derivative max k 00( )k; where M1 is the maximum of the norm of the Gateau derivative 0 on the segment [x0; x00]: Definition 2[9] For the operator (x) and each fixed x0; x00; x000 2 X the second divided difference (x0; x00; x000) is a bilinear operator from the space X to the space (X ! Y ) ; that is (x0; x00; x000) 2 X ! (X ! Y ) ; such that Using ( 5 ), one can get the following estimate:

Study of convergence

Let F (x) be a continues, we also assume that the operator of the first divided difference is invertible, i.e. in the domain of our interest there exist [F (x0; x00)] 1 = [E (x0; x00)] 1:

Theorem 1 (proof could be found in [14]). Let the following conditions hold:

X such that for each x0; x00; x000 2 the following three estimations hold

6 ; 2. there exists an open domain (a) [F (x0; x00)] 1 = [E Then a) all elements of the sequence x~(k) ; defined by the method ( 2 ) which starts from the certain x~(0), lie in the ball ( 7 ), b) the sequence x~(k)

has a limit x~ in the ball ( 7 ), and c) the estimation takes place x~ x~(k) 6

C1 C2BKM

Sk

(k = 0; 1; 2; : : : ): x x~(0)

6 R; X1 h2n : n=k x x~(0) 6 ; ( 7 ) ( 8 ) Theorem 2. Assume that 1. equation (1) has a solution in the ball (a) [F (x0; x00)] 1 = [E (x0; x00)] 1

6 B; (b) k (x0; x00)k 6 M ; (c) k (x0; x00) (x00; x000)k 6 K kx0 2. for each x0; x00; x000 from the ball x x~(0)

6 (1 + ) the following three estimations hold = maxfl2 2; M g; where l = p2CBKM; C is a constant; Then a) the solution x~ of equation (1) is unique in the ball ( 8 ), b) sequence x~(k) ; defined by the method ( 2 ), converges to x~ with the third order, i.e. the following estimation of the convergence rate holds x~ x~(k) 6 1 (l )3 l k (k = 0; 1; 2; : : : ):

Theorem 2 shows that under natural conditions, the generalized method ( 2 ), that does not use the derivatives, has a third order of convergence, that is, greater than Newton’s method or generalizations of the secant or Steffensen method. Theorems 1 and 2 impose less stringent conditions on the operator of the first divided difference than, e.g., in the papers [7, 15, 16] where some generalizations of the Steffensen’s method were studied. Moreover, there are no theorems of convergence with order in [7, 15, 16] for the case of operator equations. The The equation ( 9 ) could also be considered as a special case of the equation (1) where Let X = C [a; b] ; the functions g(t); K(t; s); f (s; x) are such that the conditions of theorem 2 are satisfied.

The operator of the first divided difference F (x1; x2) is given by

F (x1; x2) h = h(t)

K(t; s) Then using ( 10 ) we can determine that iterative process ( 2 ) for equation ( 9 ) requires at each step solution of a linear integral equation with kernel K(t; s) k(s) where k(s) = f s; x~(k)(s) f s;

x~(k)(s) x~(k)(s) x~(k)(s)

; F (x~(k)(t)) = x~(k)(t) g(t)

K(t; s)f (s; x~(k)(s))ds; F (x(k)(t)) = x(k)(t) g(t)

K(t; s)f (s; x(k)(s))ds: number of function computations at each iteration step for modifications of the Steffensen method [7] is at least one more than for a generalized method ( 2 ) that requires three function computations at each iteration step.

The formal measure of quality is the efficiency index. Method ( 2 ) has higher efficiency index then classical Newton’s or Steffensen’s method, and the same as the two-step Steffensen’s modification [15, 16].

Definition 3 The index of the efficiency of the iterative method is the quantity p1= , where p is the order of convergence of the method, is the number of calculations of the function at each iteration step. 3

Application to the nonlinear integral equations

We consider an integral equation of Hammerstein type and calculations of and

b Z a

b Z

b Z a b Z a The numerical solution of the integral equation ( 9 ) raises a number of problems, for example, difficulties connected with an exact calculation of the integral in ( 12 ) and ( 13 ) and difficulties connected with solution of linear integral equation. Therefore, we approximate integrals in ( 12 ) and ( 13 ) by quadrature formulas and replace a kernel by degradate one. Let

n(k) K(t; s) = X i=0 i(k)(t) i(k)(s) (t; s) 2 [a; b] [a; b] ; be a degenerate kernel close to K(t; s); and its approximation accuracy may vary depending on the number of iteration k: We take the operator ^ k as the operator of the form ( 10 ) in which K(t; s) is replaced by a degenerate kernel ( 14 ). Further we consider two quadrature formulas: where the nodes sl 2 [a; b] ; s0l 2 fslg; N 0 6 N: We replace the integral in the discrepancies ( 12 ), ( 13 ) using the first of the formulas ( 15 ). Then the process ( 2 ) for the equation ( 9 ) will be written so x~(k+1)(t) = x(k)(t) + x(k)(t) = x~(k)(t) +

k(t); k(t); k(t) = k(t) =

n(k) P^k(t) + X

n(k) Q^k(t) + X i=0 i=0 i(k)(t)ci(k); i(k)(t)di(k); ( 16 ) ( 17 ) ( 18 ) ( 19 ) ( 20 ) ( 21 ) (22) (23) (24) where

Q^k(t) = x(k)(t)

P^k(t) = x~(k)(t) ei(k) = i(k)(s) k(s)Q^k(s)ds

N0 X A0l i(k)(s0l) k(s0l)Q^k(s0l) = e^i(k); l=0 l=0 l=0 N X AlK(t; sl)f (sl; x(k)(sl))ds; N X AlK(t; sl)f (sl; x~(k)(sl))ds; l=0 l=0 N0 X A0l i(k)(s0l) k(s0l)P^k(s0l) = ^bi(k); N0

X A0l i(k)(s0l) k(s0l) j(k)(s0l) = a^i(jk); g(t) g(t) j=0 j=0

1 Z 0 k = 0; 1; 2; : : : ; the constants ci(k) are found from the linear system in which ci(k) =

n(k) bi(k) + X ai(jk)c(jk); i = 0; 1; : : : ; n(k); the constants di(k) are found from the linear system in which ai(jk) are calculated by the formula ( 21 ) and d(k) = i

n(k) ei(k) + X ai(jk)d(jk); i = 0; 1; : : : ; n(k); bi(k) =

i(k)(s) k(s)P^k(s)ds ai(jk) =

i(k)(s) k(s) j(k)(s)ds k(s) looks similar to ( 11 ). The second quadrature formula ( 15 ) is used to calculate the integrals ( 20 ), ( 21 ) and (23).

The simple fact of the matter is, it is more convenient to implement the process ( 16 ) for grid functions2 of approximations x~k+1(t) by setting t = ti = si; i = 0; 1; : : : ; N:

Example 1. Let us consider the integral equation in [18]: x(t) = 1 0:4854t + t2 + ts arctg x(s)ds; t 2 [0; 1]; 2A typical situation: instead of an exact solution functions we find a table of its approximate values (a skeleton), and then, if necessary, we make a replacement, for example, by spline interpolation. It is natural that the approximate solution obtained in this way belongs to a space that is narrower than the original solution space [17].

1 Z 0

1 Z 0 here g(t) = 1 0:4854t + t2; K(t; s) = ts; f (s; x(s)) = arctg x(s): The exact solution of equation (24) is x (t) = 1 + t2:

Let us verify that the conditions of Theorem 2 are satisfied. The first divided difference for the operator on the right-hand side of the equation (24) has the form is satisfied in the whole space C[0; 1]; then according to the definition 2 and statement 2 that is, the condition 2c) is satisfied.

Since k (x1; x2)k 6 1=2 the following expansion and inequality hold k[E

1 (x0; x00)] 1k = X k (x0; x00)kn 6 2; n=0 that is, the condition 2a) is satisfied.

We solved the equation (24) using the method ( 16 ). In the first series of numerical experiments, we investigated the influence of the initial approximation x~(0) on the rate of convergence (here it is measured as a number of iterations required to achieve a given accuracy 10 5).

Let us divide the segment [0; 1] uniformly into N = 10 parts and form the time grid ti; i = 0; :::; N: Let us put N 0 = N: We searched a approximate solution, ie, a grid function x~k(ti): We used the Simpson formulas with N = N 0 nodes as a quadrature formulas for ( 15 ). The stop criterion was taken as kx~(k+1) x~(k)k < 10 5: We considered the following initial conditions 1. x~(0)(t) 2. x~(0)(t) 3. x~(0)(t) 4. x~(0)(t) =

The results of the numerical experiments for ( 16 ) are presented in the table 1. In the first column, the nodes of the time grid tk are listed, in the second column the values of the exact solution at the grid nodes x (tk) are listed. Columns three through six are similar: the differences between the exact x (ti) and the approximate solution x~k(ti) in the grid nodes are indicated, here the index k corresponds to the iteration number when the required accuracy has been achieved. In the lower part of the table, the norms of the difference between the exact x (ti) and the approximate solutions x~k(ti) are given; and the norm-maximum was used.

It is seen from the table that even for nonsmooth initial approximations which oscillates with high frequency and amplitude the method converges, and it is necessary only one iteration to achieve the required accuracy. For the initial approximation x~(0)(t) = 20 + 10j sin(5 t)j the experiment also shows good smoothing properties of the method.

The results obtained for the initial approximation x~(0) = 1:5 (stop criterion is kx~(k+1) x~(k)k < 10 6) exceed the results of applying the Steffensen’s method [19] (k = 2) to this equation by the number of iterations, which in turn is better than Newton’s method [20] (results of comparison of the Steffensen’s method and the Newton’s method for the equation (24) are given in [19]).

Example 2. Let us consider the integral equation, see [21]:

The corresponding exact solution of the equation (25) is x(t) = t: We solved the equation (25) using the method ( 16 ), the initial approximation was taken as follow x~(0) = g(t): The degenerate kernel ( 14 ), which approximates K(t; s) = ets; was taken as the sum of n(k) terms of the Taylor expansion. As the quadrature formulas ( 15 ) the Simpson’s formulas were used with N = N 0 = 81: Stop criterion was taken as kQ^k(t)k < 10 6: The results of the numerical approximations ( 16 ) are given for three nodes in the table 2. From table 2 it is seen that the method ( 16 ) has converged in 3 iterations, while the analog of the Aitken-Steffensen method with a controlled step [21] converges in 9 iterations.

Note that application of the process ( 2 ) to the equation (25) requires at each iteration step to solve a linear system with N equations, while the iterative process ( 16 ) requires to solve a linear system with n(k) equations.

Acknowledgements References

This research is supported by Program 02.A03.21.0006 on 27.08.2013. [1] A. M. Ostrowski. Solution of equations and systems of equations. New York, 1960.

References

[2] I. T. Steffensen . Remarks on iteration. Scandinavian Actuarial Journal , 64 - 72 , 1933 .

[3] K. W. Chen . Generalization of Steffensen's method for operator gathers in Banach space . Commentationes Mathematicae Universitatis Carolinae , 005 : 47 - 77 , 1964 .

[4] S. Yu . Ul'm. Extension of steffensen's method for solving nonlinear operator equations . USSR Computational Mathematics and Mathematical Physics , 4 : 159 - 165 , 1964 .

[5] B. A. Bel 'tyukov. A method of solving non-linear functional equations . USSR Computational Mathematics and Mathematical Physics , 5 : 210 - 217 , 1965 .

[6] H. Koppel . On convergence of the generalized Steffensen's method . Izv. AN EstSSR , 4 : 531 - 538 , 1966 .

[7] S. Amat , S. Busquier (Eds.). Advances in Iterative Methods for Nonlinear Equations . Springer International Publishing, 2016 .

[8] I. F. Iumanova and S. I. Solodushkin . Adaptive Wegstein method for a coefficient inverse problem for one model of HIV infection . CEUR Workshop Proceedings , 1662 : 261 - 267 , 2016 .

[9] S. Yu . Ulm. On generalized divided refferences. I. Izv. AN EstSSR , 16 : 13 - 26 , 1967 .

[10] A. S. Sergeev . On the method of chords . Sibirskij matematiceskij zurnal , 2 ( 2 ): 282 - 289 , 1961 (in Russian). = А. С. Сергеев . О методе хорд . Сибирский математический журнал АН СССР , 2 ( 2 ): 282 - 289 , 1961 .

[11] S. Yu . Ulm. On generalized divided refferences . II. Izv. AN EstSSR , 16 ( 2 ): 146 - 156 , 1967 (in Russian). = С. Ю. Ульм. Об обобщенных разделенных разностях. II. Известия АН Эстонской ССР , 16 ( 2 ): 146 - 156 , 1967 .

[12] A. S. Sergeev . On the convergence of certain variants of the method of chords in normed spaces . Sbornik nauchnykh trudov Permskogo politekhnicheskogo instituta , 13 : 43 - 54 , 1963 (in Russian). = А. С. Сергеев . О сходимости некоторых вариантов метода хорд в нормированных пространствах . Сборник научных трудов Пермского политехнического института , 13 : 43 - 54 , 1963 .

[13] B. A. Bel 'tyukov. On the perturbed analog of the Aitken-Steffensen method for solving nonlinear operator equations . Sibirskij matematiceskij zurnal , 12 ( 5 ): 983 - 1000 , 1974 (in Russian). = Б. А. Бельтюков . О воз- мущенном аналоге метода Эйткена-Стеффенсена для решения нелинейных операторных уравнений . Сибирский математический журнал АН СССР , 12 ( 5 ): 983 - 1000 , 1974 .

[14] I. F. Yumanova . One specification of Steffensen's method for solving nonlinear operator equations . Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki , 26 :4: 579 - 590 , 2016 .

[15] S. Amat , S. Busquier . Convergence and Numerical Analysis of a Family of Two-Step Steffensen's Methods . Computers & Mathematics with Applications , 49 ( 1 ): 13 - 22 , 2005 .

[16] S. Amat , S. Busquier , C. Bermudez , A. A. Magrenan . Expanding the Applicability of a Third Order Newton-Type Method Free of Bilinear Operators . Algorithms , 8 ( 3 ): 669 - 679 , 2015 .

[17] V. M. Verzhbitsky . Foundations of numerical methods . = В. М. Вержбицкий. Основы численных методов. 3rd ed. Higher School , Moscow, 2009 (in Russian). 3-е изд . Высшая школа, Москва , 2009 .

[18] L. V. Kantorovich . Functional analysis and applied mathematics. Uspekhi Matematicheskikh Nauk , 3 ( 6 ): 89 - 185 , 1948 (in Russian). = Л. В. Канторович . Функциональный анализ и прикладная математика . Успехи Математических Наук , 3 ( 6 ): 89 - 185 , 1948 .

[19] B. A. Bel 'tyukov A method of solving non-linear functional equations . USSR Computational Mathematics and Mathematical Physics , 5 ( 5 ): 210 - 217 , 1965 .

[20] L. V. Kantorovich , G. P. Akilov . Functional analysis Nauka , Moscow, 1984 (in Russian). = Л. В. Канто- рович, Г. П. Акилов. Функциональный анализ. Москва , Наука, 1984 .

[21] B. A. Bel 'tyukov. An analogue of the Aitken-Steffensen method with controlled step . USSR Computational Mathematics and Mathematical Physics , 27 ( 3 ): 103 - 112 , 1987 .