Arg516.dvi


CUBO A Mathematical Journal
Vol.12, No¯ 01, (149–159). March 2010

An Improved Convergence and Complexity Analysis

for the Interpolatory Newton Method

Ioannis K. Argyros

Cameron University, Department of Mathematical Sciences,

Lawton, OK 73505, USA

email : iargyros@cameron.edu

ABSTRACT

We provide an improved compared to [5]–[7] local convergence analysis and complexity for
the interpolatory Newton method for solving equations in a Banach space setting. The re-
sults are obtained using more precise error bounds than before [5]–[7] and the same hypothe-
ses/computational cost.

RESUMEN

Nosotros entregamos aqúı un análisis de convergencia local y complejidad para el método
de interpolación de Newton para resolver ecuaciones en espacios de Banach. Los resultados
mejoran los de [5]–[7] e son obtenidos usando mas precisas cotas de error y las mismas hipotesis
y costo computacional.

Key words and phrases: Newton’s method, local convergence, Banach space, interpolatory New-

ton method, complexity, radius of convergence.

Math. Subj. Class.: 65G99, 65H10, 65B05, 47H17, 49M15.



150 Ioannis K. Argyros CUBO
12, 1 (2010)

1 Introduction

In this study we are concerned with the problem of approximating a simple solution α of the

equation

F (x) = 0, (1.1)

where F is an operator defined on a convex subset D of a Banach space X with values in a Banach

space Y over the real or complex fields of dimension N ,

dim(X) = dim(Y ) = N, 1 ≤ N ≤ +∞.

We consider interpolatory iteration In for approximating x
∗ defined as follows: Let xi be an

approximation to α and let wi be the interpolatory polynomial of degree ≤ n − 1 such that

w
(j)
i (xi) = F

(j)(xi), j = 0, 1, . . . , n − 1 (n ≥ 2). (1.2)

The next approximation x∗i+1 is a zero of wi. For n = 2 we obtain Newton’s method:

x∗i+1 = xi − F
′(xi)

−1F (xi) (i ≥ 0). (1.3)

We approximate xi+1 by applying a number of Newton iterations to wi(x) = 0. Let {xi} be the

interpolatory Newton iteration INn given by:

z0 = xi

zj+1 = zj − w
′

i(zj )
−1wi(zj ), j = 0, 1, . . . , k − 1 (1.4)

xi+1 = zk, k = [log 2n].

A local convergence analysis and the corresponding complexity of method (1.4) was studied

in the elegant paper by Traub and Wozniakowski [7]. Relevant works can be found in [1]–[7], and

the references there.

Here we are motivated by paper [7] and optimization considerations. In particular using more

precise estimates on the distances ‖xi − α‖ (i ≥ 0) we show that under the same hypotheses and

computational cost as in [5]–[7], we can provide a larger convergence radius, sharper error bounds

on the distances and consequently a finer complexity for method (1.4).

Numerical examples are introduced which compare favorably with results to the corresponding

ones in [5]–[7].

2 Local Convergence Analysis of Method (1.4)

Let Γ ≥ 0. We introduce the closed ball U = U (α, Γ) = {x ∈ X | ‖x−α‖ ≤ Γ}, and the parameters

Aj = Aj (Γ) = sup
x∈U

∥

∥

∥

∥

F ′(α)−1
F (j)(x)

j!

∥

∥

∥

∥

, (j ≥ 2) (2.1)



CUBO
12, 1 (2010)

An Improved Convergence And Complexity Analysis ... 151

provided that F (j) exists.

Moreover we introduce the parameter A by

A = A(Γ) = sup
x∈U

‖F ′(α)−1[F ′(x) − F ′(α)]‖

2‖x − α‖
. (2.2)

The foundation of our approach and what makes it more precise than the corresponding one in

[7] is the fact that we use (2.2) instead of (2.1) (for j = 2) to obtain upper bounds on the crucial

quantity ‖w′j (x)
−1F ′(α)‖.

Indeed, on the one hand note that

A ≤ A2 (2.3)

holds in general and A2
A

can be arbitrarily large [1], [2]. On the other hand see (2.28), (2.46), and

Remark 2.4.

Let us set

a =
A

A2
, A2 6= 0. (2.4)

Note that a ∈ [0, 1].

We showed in [3] the following improvement of Theorem 2.1 in [6] and Theorem 2.1 in [5]

respectively:

Theorem 2.1. If F is twice differentiable in U , (2.2) holds and

A2Γ ≤
1

2(1 + a)
, (2.5)

xi ∈ U, (2.6)

then the next approximation x∗i+1 generated by Newton method (1.3) is well defined, and satisfies

for all i ≥ 0:

‖x∗i+1 − α‖ ≤
A2

1 − 2aA2
‖xi − α‖

2 ≤
1

2
‖xi − α‖ (2.7)

and

x∗i+1 − α =
1

2
F ′(α)−1F ′(α)(xi − α)

2 + O(‖xi − α‖
2). (2.8)

Theorem 2.2. If F is n-times differentiable, n ≥ 3 in U , (2.2) holds, and

nAnΓ
n−1

1 − aA2Γ
<

(

2

3

)n−1

(2.9)

xi ∈ U,

then the polynomial wi has a unique zero in U
∗ = U ∗

(

α, Γ
2

)

and defining x∗i+1 as the zero of wi in

U ∗ the following estimates hold for all i ≥ 0

‖x∗i+1 − α‖ ≤
An(1 + ‖x

∗

i+1 − α‖/‖xi − α‖)
n

1 − aA2‖x
∗

i+1 − α‖
‖xi − α‖

n ≤
1

2
‖xi − α‖, (2.10)



152 Ioannis K. Argyros CUBO
12, 1 (2010)

and

x∗i+1 − α =
(−1)n

n!
F ′(α)−1F (n)(α)(xi − α)

n + O(‖xi − α‖
n). (2.11)

We can show the main local convergence theorem for method (1.4):

Theorem 2.3. If F is n-times differentiable, n ≥ 3 in U , (2.2) holds, and

0 ≤ Ã2Γ ≤
1

3 + 2a
(2.12)

where,

Ã2 =
A2 +

n(n−1)
2

An(2Γ)
n−2

1 − aA2Γ − nAn
(

3
2

)n−1
Γn−1

(2.13)

x0 ∈ U, (2.14)

then sequence {xi} (i ≥ 0) generated by interpolary-Newton iteration INn is well defined, remains

in U for all i ≥ 0, converges to α so that the following estimates hold for all i ≥ 0:

ei+1 = ‖xi+1 − α‖ ≤

{

1

2
+

3

2

(

1

2

)k
}

ei, (2.15)

ei+1 ≤ ci,ne
n
i (2.16)

where,

ci,n =

(

1 +
e∗i+1
ei

)

[

An
1 − aA2e

∗

i+1

+ (Ã2(1 + Hi))
2k−1

]

((

1 +
e∗i+1
ei

)

ei

)2k−n

, (2.17)

for

e∗i+1 = ‖x
∗

i+1 − α‖, Hi = O(ei), 0 ≤ Hi ≤
3 + 2a

2
, k = [log 2n], (2.18)

lim
i→∞

ci,n = An + δÃ
n−1
2 where δ = 0

if 2k > n and δ = 1, if 2k = n, (2.19)

xi+1 − α = Fn(xi − α)
n + bi,k + O(‖xi − α‖

n), (2.20)

where

bi,1 = F2(xi − α)
2, (2.21)

bi,j+1 = F2b
2
i,j , j = 1, 2, . . . , k − 1, (2.22)

and

Fj =
(−1)j

j!
F ′(α)−1F (j)(α) for j = 2 and n. (2.23)



CUBO
12, 1 (2010)

An Improved Convergence And Complexity Analysis ... 153

The proof is similar to Theorem 3.1 in [7], but there are differences where we use (2.2) instead

of (2.1) (for i = 2).

Proof. We shall first show using induction on j ≥ 0 that w′j (zj) is invertible and zj ∈ U .

Set

F (j)(x) − w
(j)
i (x) = R

(j)
n (x; xi), x ∈ U, j = 0, 1, 2, (2.24)

where,

‖F ′(α)−1R(j)n (x; xi)‖ ≤ j!

(

n

j

)

An‖x − xi‖
n−1. (2.25)

We can write

w′i(x) = F
′(x) − R′n(x; xi)

= F ′(α)[I + F ′(α)−1{F ′(x) − F ′(α)} − F ′(α)−1R′n(x; xi)] (2.26)

and in view of (2.2), (2.12) and (2.24) for x ∈ U we get in turn

‖F ′(α)−1[w′j (x) − F
′(α)]‖ ≤ 2aA2‖x − α‖ + nAn‖x − xi‖

n−1 (2.27)

≤ 2aA2Γ + nAn(2Γ)
n−1 ≤

2

3 + 2a
< 1. (2.28)

It follows from (2.28) and the Banach Lemma on invertible operators [4] that w′i(x) is invertible

for all x ∈ U , and

‖w′i(x)
−1F ′(α)‖ ≤

1

1 − 2aA2‖x − α‖ − nAn‖x − xi‖n−1
. (2.29)

Since the denominator in (2.13) is positive we get

nAnΓ
n−1

1 − aA2Γ
<

(

2

3

)n−1

(2.30)

and from Theorem 2.2 wi has a unique zero x
∗

i+1 in U
∗ and (2.10) holds.

Using (2.24) and (2.29) we get for x ∈ U
∥

∥

∥

∥

w′j (x
∗

i+1)
−1 w

′′

i (x)

2

∥

∥

∥

∥

≤ ‖w′i(x
∗

i+1)
−1F ′(α)‖

∥

∥

∥

∥

F ′(α)−1
w′′i (x)

2

∥

∥

∥

∥

≤
A2 +

n(n−1)
2

An‖x − xi‖
n−2

1 − 2aA2‖x
∗

i+1 − α‖ − nAn‖x
∗

i+1 − xi‖
n−1

≤
A2 +

n(n−1)
2

An(2Γ)
n−2

1 − aA2Γ − nAn
(

3
2
Γ
)n−1

= Ã2. (2.31)

It follows from Theorem 3.1 and (2.12) that for z1 = xi − F
′(xi)

−1F (xi)

‖z1 − α‖ ≤
1

2
‖xi − α‖. (2.32)



154 Ioannis K. Argyros CUBO
12, 1 (2010)

Since x∗i+1 ∈ U
∗, ‖z1 − x

∗

i+1‖ ≤ Γ, we shall show

zj+1 ∈ Dj =

{

x : ‖x − x∗i+1‖ ≤
1

2
‖zj − x

∗

i+1‖

}

∩ U. (2.33)

Set

wi(x) = wi(zj ) + w
′

i(zj )(x − zj) + R2(x; zj ), (2.34)

where,

R2(x; y) =

∫ 1

0

w′′i (y + t(x − y))(x − y)
2(1 − t)dt. (2.35)

Note that zj+1 is the solution of equation

x = H(x) = x∗i+1 + w
′(xi+1)

−1
{

R2(x; zj ) − R2(x; x
∗

i+1)
}

. (2.36)

We shall show H is contractive on Dj .

It follows from (2.12), (2.31) and (2.36):

‖H(x) − x∗i+1‖ ≤ Ã2(‖x − zj‖
2 + ‖x − x∗i+1‖

2)

≤
2 + 3a

2
Ã2‖zj − x

∗

i+1‖ ≤
1

2
‖zj − x

∗

i+1‖. (2.37)

Moreover we have

‖H(x) − α‖ ≤ ‖x∗i+1 − α‖ + ‖H(x) − x
∗

i+1‖ ≤

(

1

2
+

1

2

)

Γ = Γ. (2.38)

It follows by the contraction mapping principle [4], (2.37) and (2.38) that zj+1 is the unique zero

of H in Dj . It follows that xi+1 = zk ∈ U , and

‖xi+1 − α‖ ≤ ‖xi+1 − x
∗

i+1‖ + ‖x
∗

i+1 − α‖

≤

(

1

2

)k

‖z0 − x
∗

i+1‖ +
1

2
‖xi − α‖

≤

[

3

2

(

1

2

)k

+
1

2

]

‖xi − α‖ ≤
7

8
‖xi − α‖, (2.39)

which shows xi ∈ U and (2.15) hold true.

Set ej = ‖zj − x
∗

i+1‖ and x = zj+1 in (2.36). Then we get

ej+1 ≤
Ã2
(

1 +
ej+1
ej

)2

1 − Ã2ej+1
e2j ≤ Ã2(1 + Hi)ej , (2.40)

where Hi = O(ej ) and 0 ≤ Hi ≤
2+3a

2
compare to (2.7). In view of ej = O(ej ) we can set



CUBO
12, 1 (2010)

An Improved Convergence And Complexity Analysis ... 155

Hi = O(ei). It follows from (2.10) and (2.40)

ei+1 ≤ ‖xi+1 − x
∗

i+1‖ + ‖x
∗

i+1 − α‖ = ek + ‖x
∗

i+1 − α‖

≤
[

Ã2(1 + Hi)
]2k−1

‖xi − x
∗

i+1‖
2k

+
An

1 − aA2e
∗

i+1

(

1 +
e∗i+1
ei

)n

eni

≤

(

1 +
e∗i+1
ei

)n
(

An
1 − aA2e

∗

i+1

+
[

Ã2(1 + Hi)
]2k−1

[(

1 +
e∗j+1
ei

)

ei

]2k−n
)

eni = ci,ne
n
i . (2.41)

In view of
e
∗

i+1

ei
and Hi tending to zero we get

lim
i→∞

ci,n = An + δÃ
n−1
2 , (2.42)

where δ = 0 if 2k > n and δ = 1 otherwise. Hence, (2.16) holds.

Furthermore, we have

zj+1 − x
∗

i+1 = w
′

i(x
∗

i+1)
−1 w

′′

i (x
∗

i+1)

2
(zj − x

∗

i+1)
2 + O(ẽ3j )

= F ′(α)−1
F ′′(α)

2
(zj − x

∗

i+1)
2 + O(e∗i+1ẽ

2
j + ẽ

3
j )

= F2(zj − x
∗

i+1)
2 + O(ẽ2j ). (2.43)

Therefore, we get

zk − x
∗

i+1 = F2
(

F2 · · · · (F2(xi − x
∗

i+1)
2)2 · · ·

)2
+ O(e2ki )

= F2
(

F2 · · · · (F2(xi − α)
2)2 · · ·

)2
+ O(e2ki ). (2.44)

In view of (2.21), (2.22), and (2.44) we have

zk − x
∗

i+1 = bi,k + O(e
2k
i ). (2.45)

In view of (2.11) and (2.45) we deduce

xi+1 − α = zk − x
∗

i+1 + x
∗

i+1 − α = bi,k + Fn(xi − α)
n + O(eni ), (2.46)

which shows (2.20).

That completes the proof of the theorem.

Remark 2.4. The less precise estimate (using (2.1) for j = 2 instead of sharper (2.2) that is

actually needed)

‖F ′(α)−1[w′j (x) − F
′(α)]‖ ≤ 2A2‖x − α‖ + nAn‖x − xi‖

n−1 (2.47)



156 Ioannis K. Argyros CUBO
12, 1 (2010)

was used in [7] instead of (2.28), together with

0 ≤ Ã2Γ ≤
1

5
(2.48)

instead of weaker (2.12).

If A = A2 our results Theorem 2.1, Theorem 2.2 and Theorem 2.3 reduce to the corresponding

Theorem 2.1 in [6], Theorem 2.1 in [5] and Theorem 3.1 in [7] respectively. Otherwise our results

constitute improvements with advantages already stated in the Introduction.

We now give conditions under which INn enjoys a “type of global convergence”.

Let

F (x) =

∞
∑

i=1

1

ι!
F (i)(xi − α)

i (2.49)

be analytic in D = U 0(α, R), and

‖F ′(α)−1F (i)(α)‖

ι!
≤ Ki−1 (2.50)

for i ≥ 2 and R ≥ 1
K

.

As in [7], one way to find K is to use Cauchy’s formula

‖F ′(α)−1F (i)(α)‖

ι!
≤

M

Ri
, (2.51)

where,

M = sup
x∈D

‖F ′(α)−1F (x)‖. (2.52)

Let K = max
[

1
R

, M
R2

]

. Then
M

R
≤ KR ≤ (KR)i−1 (2.53)

and
M

Ri
≤ Ki−1. (2.54)

We can show:

Theorem 2.5. If (2.2) and (2.50) hold then the interpolary Newton method (1.4) converges

provided that x0 ∈ U (α, Γn), where

Γn =
xn
K

(2.55)

and xn, 0 < xn < x∞, satisfies the equation

(3 + 2a)

[

x

(1 − x)3
+

n(n − 1)

4(1 − x)2

(

2x

1 − x

)n−1
]

= 1 −
ax

(1 − x)3
−

n

(1 − x)2

[

3x

2(1 − x)

]n−1

(2.56)



CUBO
12, 1 (2010)

An Improved Convergence And Complexity Analysis ... 157

and xn → x∞, where

x∞ ≥ .12 (2.57)

is the positive solution of equation
x

(1 − x)3
=

1

4 + 2a
. (2.58)

Proof. In view of (2.50) we have for

f (x) =
x

1 − Kx
, (2.59)

that

‖F ′(α)−1F (i)(x)‖ ≤ f (i)(‖x − α‖). (2.60)

Using

f (i)(x) =
i!Ki−1

(1 − Kx)i+1
(i ≥ 2), (2.61)

we get

Ai(Γ) ≤
Ki−1

(1 − KΓ)i+1
(i ≥ 2). (2.62)

It follows from (2.13) and (2.62) that

Ã2Γ ≤

[

KΓ
(1−KΓ)3

+
n(n−1)

4(1−KΓ)2

(

2KΓ
1−KΓ

)n−1
]

1 − aKΓ
(1−KΓ)3

− n
(1−KΓ)2

(

3KΓ
2(1−KΓ)

)n−1
=

1

3 + 2a
. (2.63)

Letting KΓ = x we see that x satisfies equation (2.56). It is simple calculus to show that x = x(n)

is an increasing function of n and x∞ = lim
n→∞

x(n) satisfies equaiton (2.58).

Remark 2.6. If A = A2 (i.e. a = 1) our Theorem 2.5 reduces to Theorem 3.2 in [7]. Otherwise it

is an improvement, since the limit of sequence x(n) in [7] is .12 which is smaller than ours implying

by (2.55) that we provide a larger radius of convergence.

In particular if R is related to 1
K

, say R = c1
K

, then

Γn =
xn
K

=
xn
c1R

≤
x∞
c1R

. (2.64)

The rest of the results introduced in [7] are improved. In particular with the notation introduced

in [7] we have for

I: ei = Gie
n
i−1, Gi ≤ G,

G = G(n) =



























A2
1 − 2aA2Γ

, n = 2

(1 + q)n
[

An

1 − aA2
Γ
2

+

(

7

2
Ã2

)2k−1

[(1 + q)Γ]2
k
−n, n > 2

(2.65)



158 Ioannis K. Argyros CUBO
12, 1 (2010)

where Ã2 is given by (2.13), q =
1
2

+ 3
2

(

1
2

)k
, and K = [log 2n].

II: If the total number of arithmetic operations necessary to solve a system of N linear equa-

tions is O(nβ ), β ≤ 3, then

d(INn) =























O

(

N β[log 2n] + N 2
(

N + n − 2

n − 2

)

([log 2n] − 1

)

for N ≥ 2,

(3 + 2a)[log 2n] + O(1), for n = 1.

(2.66)

Remark 2.7. If A = A2 our results reduce to the ones in [7]. Otherwise they constitute an

improvement.

We complete this study with an example to show that strict inequality can hold in (2.3):

Example 2.8. Let X = Y = R, x∗ = 0 and define function F on U = U (0, 1) by

F (x) = ex − 1. (2.67)

Using (2.1), (2.2), (2.4) and (2.66) we obtain

A =
e − 1

2
<

e

2
= A2 (2.68)

and

a = .632120588. (2.69)

It follows from (2.5) that our radius of convergence is given by

ΓA = .112699836. (2.70)

The corresponding radius ΓT W given in Theorem 2.1 in [6] or [7] is:

ΓT W =
1

4A2
= .09196986. (2.71)

That is

ΓT W < ΓA. (2.72)

Received: October, 2008. Revised: January, 2009.

References

[1] Argyros, I.K., A unifying local-semilocal convergence analysis and applications for two-

point Newton-like methods in Banach space, J. Math. Anal. Applic., 298 (2004), 374–397.



CUBO
12, 1 (2010)

An Improved Convergence And Complexity Analysis ... 159

[2] Argyros, I.K., Approximate Solution of Operator Equations with Applications, World

Scientific Publ. Comp., River Edge, New Jersey, 2005.

[3] Argyros, I.K., An improved convergence and complexity analysis of Newton’s method for

solving equations, (to appear).

[4] Kantorovich, L.V. and Akilov, G.P., Functional Analysis in Normed Spaces, Moscow,

1959.

[5] Ortega, J.M. and Rheinboldt, W.C., Iterative Solution of Nonlinear Equations in Sev-

eral Variables, Academic Press, New York, 1970.

[6] Traub, J.F. and Wozniakowski, H., Strict lower and upper bounds on iterative compu-

tational complexity . In Analytic Computational Complexity, J.F. Traube, Ed., Academic

Press, New York, 1976, pp. 15–34.

[7] Traub, J.F. and Wozniakowski, H., Convergence and complexity of Newton iteration

for operator equations, J. Assoc. Comput. Machinery, 26, No. 2 (1979), 250–258.