• 검색 결과가 없습니다.

Assuming that a given nonlinear function f : R → R has a zero α with integer multiplicity m ≥ 1 and is sufficiently smooth in a small neighborhood of α, we define extended leap- frogging Newton’s method

N/A
N/A
Protected

Academic year: 2022

Share "Assuming that a given nonlinear function f : R → R has a zero α with integer multiplicity m ≥ 1 and is sufficiently smooth in a small neighborhood of α, we define extended leap- frogging Newton’s method"

Copied!
11
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

Volume 22, No. 2, June 2009

A STUDY ON CONVERGENCE OF EXTENDED LEAP-FROGGING NEWTON’S METHOD LOCATING

MULTIPLE ZEROS

Young Hee Geum*

Abstract. Assuming that a given nonlinear function f : R → R has a zero α with integer multiplicity m ≥ 1 and is sufficiently smooth in a small neighborhood of α, we define extended leap- frogging Newton’s method. We investigate the order of conver- gence and the asymptotic error constant of the proposed method as a function of multiplicity m. Numerical experiments for various test functions show a satisfactory agreement with the theory pre- sented in this paper and are throughly verified via Mathematica programming with its high-precision computability.

1. Introduction

Traub[10] and Kasturiarachi[6] introduced leap-frogging Newton’s me thod that is also called the Newton-secant method. They investigated convergence behavior of the method for a simple zero. For a given non- linear equation f (x) = 0, unlike the usual approach as shown in [10], Geum[5] has adopted a different approach to show the correct asymp- totic error constant as 14(f00(α)/f0(α))2 with cubic convergence at a simple root α.

In this paper, we describe extended leap-frogging Newton’s method and its convergence properties for a multiple root with inetger multiplic- ity. Our main aim is to express the asymptotic error constant[1-3,8,9] for the method in terms of the root multiplicity. We show that it converges cubically[4,7] to a simple root and quadratically to a multiple root.

Received March 23, 2009; Revised May 20, 2009; Accepted May 21, 2009.

2000 Mathematics Subject Classification: Primary 65H05, 65H99.

Key words and phrases: leap-frogging Newton’s method, cubic convergence, as- ymptotic error constant, multiple root, simple root.

Research of Y. H. Geum was supported by the Korean Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2006-352-00006).

(2)

Let f : R → R have a root α with integer multiplicity m ≥ 1 and be sufficiently smooth in a small neighborhood of α. We rewrite f (x) = 0 in the form x = g(x) with g : R → R which is sufficiently smooth in a small neighborhood of α. Suppose that the iterative function g(x) is defined by

g(x) =

½ x − H(x), if x 6= α

x − limx→αH(x), if x = α, (1.1) where

H(x) = λf (x)2

f0(x) · (f (x) − f (z)), z = x − mh(x), (1.2) h(x) =

½ f (x)/f0(x), if x 6= α limx→αf (x)/f0(x), if x = α,

and λ is a constant parameter to be chosen for maximal order of con- vergence. Hence our proposed numerical method is given by

xn+1 = g(xn), n = 0, 1, 2, · · · , (1.3) and is called extended leap-frogging Newton’s method. As expected with λ = m = 1, it becomes leap-frogging Newton’s method.

The following lemma describing some local properties of h(x) can be easily proved by repeated use of L’Hospital’s rule and Leibnitz’s rule for differentiation.

Lemma 1.1. In view of multiplicity of α, let c=ff(m+1)(m)(α)(α), d =

f(m+2)(α)

f(m)(α) . Then the function h(x) and its derivatives up to order 3 evaluated at α are found to be the following:

(i) h(α) = 0 (ii) h0(α) = m1

(iii) h00(α) = −m2(m+1)2 c (iv) h000(α) = m2(m+1)6

n1

mc2m+22 d o

From Eq.(1.1), we need to investigate some local properties of g(x) in a small neighborhood of α. From the definition of g(x) as described in Eq.(1.1), we rewrite

(g − x) · f0(x)(f (x) − f (z)) = −λ · f (x)2. (1.4)

(3)

Using Eq.(1.4), our aim is to establish some relationships between λ, m, g0(α), g00(α) and g000(α), for maximal order of convergence. The next lemma is useful to calculate g0(α), g00(α) and g000(α).

Lemma 1.2. Let f : R → R have a multiple root α with multiplicity m ≥ 1 and be sufficiently smooth in a small neighborhood of α. Let z(x) = x − mh(x) and h(x) be defined by Eq.(1.1). Let p ≥ 0 be an integer. Then the following hold:

(i) If m = 1, then dp

dxpf (z)

¯¯

¯¯

¯x=α

=







0, if p = 0, 1

f00(α), if p = 2

−f0(α)h000(α), if p = 3

−f0(α)h(4)(α) + 3f00(x)h00(α)2, if p = 4

(1.5)

(ii) If m ≥ 2, then dp dxpf (z)

¯¯

¯¯

¯x=α

= [f (z)](p)|x=α= 0 f or 0 ≤ p ≤ m + 1 (1.6) Proof. We first try to get an insight for f (z) with lower values of p as follows.

If p = 0, then

f (z)|x=α= f (z(α)) = f (α) = 0.

If p = 1, then

f0(z) · z0|x=α= f0(α) · z0(α) = f0(α) · (1 − mh0)(α) = f0(α) · 0 = 0.

If p = 2, then

f00(z) · z02|x=α+ f0(z) · z00|x=α = 0.

If p = 3, then f000(z) · z03

¯¯

¯¯

¯x=α

+(1 + 2)f00(z) · z0· z00|x=α+ f0(z) · z000|x=α = 0.

If p = 4, then

f(4)(z) · z04+ (1 + 2 + 3)f(3)(z) · z02· z00+ (1 + 2)f00(z) · (z0· z000+ z002) +f00(z) · z0· z000+ f0(z) · z(4)

¯¯

¯¯

¯x=α

= 0.

Continuing in this manner, we get the following expression when m ≥ k and p = k + 1:

(4)

· f (z)

¸(p)

x=α

= f(k+1)(z) · z0(k+1)+k(k + 1)

2 f(k)(z) · z0(k−1)· z00 +

k−1X

j=1

f(j)(z) · φj(z(1), z(2), · · · z(k+1))

¯¯

¯¯

x=α

= 0,

where φj(z(1), z(2), · · · z(k+1)) is a nonlinear function of variables z(1), z(2),

· · · z(k+1) and φj|x=α has a finite value.

Now we put k = m and have [f (z)](p)x=α = 0 for (0 ≤ p ≤ m + 1) , when m ≥ 2. But when m = 1, we get the following relations by direct computation:

[f (z)](p)|x=α =







0, if p = 0, 1

f00(α), if p = 2

−f0(α)h000(α), if p = 3

−f0(α)h(4)(α) + f00(x)h00(α)2, if p = 4, from which the proof is completed.

2. Convergence analysis

In this section, we investigate the order of convergence p and the asymptotic error constant η of extended leap-frogging Newton’s method.

We differentiate 2m times both sides of Eq(1.6) with respect to x and substitute x = α to obtain

·

(g − x) · f0(x) {f (x) − f (z)}

¸(2m)

x=α

= −λ

· f (x)2

¸(2m)

x=α

= X2m r=0

µ2m r

(g − x)(2m−r)(x) · [f0(x) · {f (x) − f (z)}](r)

¯¯

¯¯

x=α

= −λ X2m r=0

µ2m r

f(r)(x) · f(2m−r)(x)

¯¯

¯¯

x=α

. (1.7)

In the third of Eq.(1.7) with 0 ≤ r ≤ 2m − 1 , we calculate the range of value r such that [f0(x) · f (x) − f (z)](r)x=α 6= 0. We find f (α) = f0(α) =

· · · = f(m−1)(α) = 0, f(m)(α) 6= 0 in view of multiplicity m. Therefore, we have ·

f (z)

¸(p)

x=α

=

½ f00(α), if m = 1, p = 2

0, otherwise.

(5)

When m ≥ 2, for 0 ≤ p ≤ m + 1, we find

r ≥ m − 1 + m = 2m − 1.

If r = 2m − 1, we have

·

f0(x) · {f (x) − f (z)}

¸(2m−1)

x=α

=

µ2m − 1 m − 1

f(m)(α) · f(m)(α).

We evaluate Eq.(1.7) at x = α by Lemma 1.2. In Eq.(1.7), all the terms of the left side vanishes except for the values of r = 2m − 1 to yield:

2m · (g0− 1) ·

µ2m − 1 m − 1

f(m)(α)2 = −λ µ2m

m

· f(m)(α)2.

Next we determine the value λ such that g0(α) = 0 when m ≥ 2 and find

λ = (2m)!

m!(m − 1)!

Á(2m)!

m!m! = m. (1.8)

We put m = 1 in Eq.(1.7) to obtain X2

r=0

µ2 r

(g − x)(2−r)

¯¯

¯¯

x=α

·

·

f0(x) {f (x) − f (z)}

¸(r)

x=α

= −2λf0(α)2 µ2

1

(g0− 1) ·

·

f0(x) {f (x) − f (z)}

¸

x=α

= 2(−1) · f0(α)2 = −2λf0(α)2. Thus

λ = 1. (1.9)

Combining Eq.(1.8) with Eq.(1.9), we choose λ = m for all integers m ≥ 1. To find g00(α), we first differentiate 2m + 1 times both sides of Eq(1.4) with respect to x and substitute x = α as follows.

·

(g − x) · f0(x) · {f (x) − f (z)}

¸(2m+1)

x=α

= −2λ

½ f (x)2

¾(2m+1)

x=α

=

2m+1X

r=0

µ2m + 1 r

(g − x)(2m+1−r)

¯¯

¯¯

x=α

·©

f0(x)[f (x) − f (z)]ª(r)

x=α

= −2λ

2m+1X

r=0

µ2m + 1 r

f (x)(r)· f (x)(2m+1−r)

¯¯

¯¯

x=α

. (1.10)

When 0 ≤ r ≤ 2m in the left side of Eq.(1.10), we choose the range of value r such that [f0(x) · {f (x) − f (z)}](r)x=α 6= 0.

(6)

When m ≥ 2, we get (i) r = 2m − 1

·

f0(x) · {f (x) − f (z)}

¸(2m−1)

x=α

=

µ2m − 1 m − 1

· f(m)(α)2. (ii) r = 2m

·

f0(x) · {f (x) − f (z)}

¸(2m)

x=α

=

·µ2m m

¶ +

µ 2m m − 1

¶¸

f(m)(α) · f(m+1)(α).

Therefore, we let g0(α) = 0 in the left side of Eq.(1.10) to find the following.

(2m + 1)(g0(α) − 1) ·

·µ2m m

¶ +

µ 2m m − 1

¶¸

f(m)(α)f(m+1)(α) + (2m + 1)2m

2

µ2m − 1 m

g00(α)f(m)(α)2

= −λ

·µ2m + 1 m

f(m)(α)f(m+1)(α) +

µ2m + 1 m + 1

f(m+1)(α)f(m)(α)

¸ . Hence we obtain with λ = m after some algebraic manipulation:

g00(α) = 2 m(m + 1)

f(m+1)(α)

f(m)(α) , m ≥ 2.

When m = 1, substituting m = 1 into Eq.(1.10) yields X3

r=0

µ3 r

(g − x)(3−r)

¯¯

¯¯

x=α

·[f0(x) {f (x) − f (z)}

¸(r)

x=α

= −6f0(α)f00(α) = 3g00(α)f00(α)2− 3 · 2f0(α)f00(α) and

g00(α) = 0.

Hence we need to further investigate g000(α) with m = 1. Differentiating 4 times both sides of Eq(1.6) with respect to x and substituting x = α leads us to the equation below:

X4 r=0

µ4 r

(g − x)(4−r)|x=α·

·

f0(x) {f (x) − f (z)}

¸(r)

x=α

= −λ X4 r=0

µ4 r

f (α)(r)f (α)(4−r)

(7)

= µ4

1

g000(α) · f0(α)2+ µ4

2

g00(α) ·

·

f0(x) {f (x) − f (z)}(2)x=α

¸

+ µ4

3

(g0(α) − 1) ·

·

f0(x) {f (x) − f (z)}(3)x=α

¸

= −λ

½µ4 1

f0(α)f000(α) + µ4

2

f00(α)2+ µ4

3

f000(α)f0(α)

¾ .

After substituting λ = m = 1 into the above equation and rearranging, we obtain

g000(α) = 3 2

à f00(α)

f0(α)

!2 .

As a result of the preceeding discussion, we state the main theorem regarding the convergence of extended leap-frogging Newton’s method.

Theorem 2.1. Let f : R → R have a zero α with integer multiplicity m ≥ 1 and be sufficiently smooth in a small neighborhood of α. Let x0 be an initial guess chosen in a sufficiently small neighborhood of α.

Then extended leap-frogging Newton’s method(1.3) has order p and its asymptotic error constant η as follows:

p =

½ 2, if m ≥ 2

3, if m = 1

η =







1 m(m+1)

f(m+1)(α)

f(m)(α) , if m ≥ 2

14 ·

³f00(α) f0(α)

´2

, if m = 1.

3. Algorithm, numerical results and discussions

The symbolic and computational ability of Mathematica[11] leads us to a zero-finding algorithm based on the analysis studied in Sections 1 and 2.

Algorithm 3.1 (Zero-Finding Algorithm)

Step 1. For k ∈ N ∪ {0}, construct iteration scheme (1.1) with the given function f at a multiple zero α as stated in Section 1.

Step 2. Set the minimum number of precision digits. With exact zero α or most accurate zero, supply the theoretical asymptotic error constant

(8)

η. Set the error range ², the maximum iteration number nmax and the initial value x0. Compute f (x0) and |x0− α |.

Step 3. Compute xn+1 in (1.1) for 0 ≤ n ≤ nmax and display the computed values of n, xn, f (xn), |xn− α|, |en+1/enp| and η.

In these experiments, we choose 250 as the minimum number of digits of precision by assigning $MinPrecision=250 in Mathematica to achieve the specified nominal accuracy. We set the error bound ² to 0.5 × 10−235 for | xn−α | < ² and evaluate the nthorder derivative of the complicated nonlinear functions using the Mathematica command D[f, {x, n}].

As an example for the convergence of extended leap-frogging New- ton’s method, we first illustrate the order of convergence and the as- ymptotic error constant with a function

f (x) = (1 + x2) cos(πx/8)

having a simple real zero α = 4.0. We choose x0 = 3.49 as an ini- tial guess. Table 1 lists the numerical results for approximated zeros of f (x) computed with Mathematica programming and verifies cubic con- vergence apparently. As a second example, we illustrate the order of convergence and the asymptotic error constant with a function

f (x) = n

x10−√

3x3cos(πx/6) + 1/(x2+ 1) o

(x − 1)

having a multiple real zero α = 1 of multiplicity 2. We choose x0= 0.92 as an initial guess. Table 2 shows a good agreement with the theory developed in this paper.

Table 1. Convergence for f (x) = (1 + x2) cos(πx/8)

n xn f (xn) | xn− α | en+1/en3 η

0 3.49000000000000 2.62205 0.510000 0.2214532872

1 3.94534313747757 0.355535 0.0546569 0.4120350583 2 3.99996137559441 0.000257847 0.0000386244 0.2365525937 3 3.99999999999999 8.51915 × 10−14 1.27611 × 10−14 0.2214635569 4 4.00000000000000 3.07223 × 10−42 4.60199 × 10−43 0.2214532872 5 4.00000000000000 1.44088 × 10−127 2.15833 × 10−128 0.2214532872 6 4.00000000000000 0.0 × 10−248 0.0 × 10−249

As another numerical example to confirm the convergence, we take f (x) = (−1 + e−30+7x+x2)(−3 + x)2

with a zero 3 of multiplicity 3. Table 3 clearly reflects the theoretical convergence presented in this paper. The computed asymptotic error

(9)

Table 2. Convergence of the extended leap-frogging Newton’s method for

f (x) =©

x10−√

3x3cos(πx/6) + 1/(x2+ 1)ª

(x − 1)

n xn f (xn) | xn− α | en+1/en2 η

0 0.920000000000000 -0.00501924 0.800000

1 0.991249484161490 -0.0000440460 0.0121355 1.367268100 3.03354251 2 0.999794338683744 −2.31460 × 10−8 0.000360502 2.685871931

3 0.999999872081448 −8.94329 × 10−15 3.35582 × 1−−7 3.024323988 4 0.999999999999950 −1.34667 × 10−27 2.91278 × 10−14 3.033536758 5 1.00000000000000 −3.05348 × 10−53 2.19446 × 10−27 3.033542510 6 1.00000000000000 −1.56986 × 10−104 1.24557 × 10−52 3.033542510 7 1.00000000000000 −4.14947 × 10−207 4.01279 × 10−104 3.033542510 8 1.00000000000000 −2.89905 × 10−412 4.16489 × 10−207 3.033542510 9 1.00000000000000 −2.89905 × 10−799 −2.89905 × 10−400

constants are in good agreement with theoretical asymptotic error con- stants η up to 10 significant digits. The computed root is rounded to be accurate up to the 235 significant digits.

Table 3. Convergence of the extended leap-frogging Newton’s method for

f (x) = (−1 + e−30+7x+x2)(−3 + x)2

n xn f (xn) | xn− α | en+1/en2 η

0 3.50000000000000 213.265 0.500000 2.192307692

1 3.32582570969854 8.05275 0.325826 1.303302839 2 3.17016897270441 0.243364 0.170169 1.602911989 3 3.05596879088136 0.00337242 0.0559688 1.932792228 4 3.00674617976831 4.17384 × 10−6 0.00674618 2.153605047 5 3.00009979932255 1.29304 × 10−11 0.0000997993 2.192864382 6 3.00000002183539 1.35340 × 10−22 2.18354 × 10−8 2.192329399 7 3.00000000000000 1.48461 × 10−44 1.04526 × 10−15 2.192307697 8 3.00000000000000 1.78644 × 10−88 2.39524 × 10−30 2.192307692 9 3.00000000000000 2.58666 × 10−176 1.25776 × 10−59 2.192307692 10 3.00000000000000 5.42299 × 10−356 3.46816 × 10−118 2.192307692 11 3.00000000000000 2.38363 × 10−703 2.63693 × 10−235 2.192307692 12 3.00000000000000 0.0 × 10−1199 0.0 × 10−399

Our analysis has been further confirmed through more test functions that are listed below:

f1(x) = cos x − x

f2(x) = (sin2x − x2+ 1)(cos 2x + 2x2− 3) f3(x) = (sin(πx/2√

2) − x4+ 3)(x2− 2)2(sin(πx/2√

2) − x4+ 3) f4(x) = (x8− 14x4sin(πx/4) − 32)(x2− 4x + 4) log(x − 1)

(10)

f5(x) = (3x7− 37x4+ 208) sin (πx/2) log[x − 1]3 f6(x) = (e(x2+7x−30)− 1)(x − 3) sin4πx/3

f7(x) = (e−xsin x+log[1+(x−π)2])(x−π) sin3x(log[x−π+1])2 f8(x) = (x2sin (πx/8) + e(x−2)2− 1 − 2√

2)(x − 2)3sin4(πx/2) Table 4 shows convergence behavior for the above test functions with the multiplicity m, the initial guess x0, the order of convergence p, the least iteration number ν and the asymptotic error constant η.

Let d denote the number of new function or derivative evaluations per iteration. For our proposed method, d is found to be 3. We remark from [10] that both the computational efficiency EFF

EF F = p d =

½ 3

3, if m = 1

23 ≈ 0.6667, if m ≥ 2, and the efficiency index EF F

EF F = p1/d = (

313 ≈ 1.44225, if m = 1 213 ≈ 1.25992, if m ≥ 2,

display a good measure of computation compared to the classical new- ton’s method with

EF F = p d =

½ 1, if m = 1

1

2, if m ≥ 2, and

EF F = p1/d = (

212 ≈ 1.41421, if m = 1 112 = 1, if m ≥ 2.

Table 4. Convergence of the extended leap-frogging Newton’s method for

f (x) α m x0 en p ν η

f1(x) 0.739085133215161 1 0.490 6.13024 × 10−293 3 5 0.04875502284 f2(x) 1.40449164821534 2 1.290 4.51173 × 10−253 2 8 0.7835709502

f3(x)

2 3 1.080 0. × 10−249 2 10 5.119146433 f4(x) 2.00000000000000 4 2.190 1.18904 × 10−261 2 8 0.5369302217 f5(x) 2.00000000000000 5 2.270 2.41280 × 10−398 2 9 1.11 f6(x) 3.00000000000001 6 2.790 2.52653 × 10−359 2 9 1.096153846 f7(x) π 7 2.590 1.92369 × 10−587 2 10 3.591527519 f8(x) 2.00000000000000 8 1.590 1.90760 × 10−308 2 8 0.08249684013

Various numerical experiments prove the order of convergence and the asymptotic error constant of the extended leap-frogging Newton’s

(11)

method. This proposed development will play a important part in find- ing zeros of the nonlinear equation with highly accuracy. The current investigation will be extended to different methods at a multiple zero.

References

[1] R. G. Bartle, The Elements of Real Analysis, 2nd ed., John Wiley & Sons., New York, 1976.

[2] Ward Cheney and David Kincaid, Numerical Mathematics and Computing, Brooks/Cole Publishing Company, Monterey, California 1980

[3] S. D. Conte and Carl de Boor, Elementary Numerical Analysis, McGraw-Hill Inc., 1980

[4] Qiang Du, Ming Jin, T. Y. Li and Z. Zeng, The Quasi-Laguerre Iteration, Mathematics of Computation, 66 (1997), no. 217, 345-361.

[5] Y. H. Geum, The asymptotic error constant of leap-frogging Newtons method locating a simple real zero, Applied Mathematics of Computation 189 (2007), no. 217, 963-969.

[6] A. Bathi Kasturiarachi, Leap-frogging Newton’s Method, INT. J. MATH.

EDUC. SCI. TECHNOL. 33 (2002), no. 4, 521-527.

[7] L. D. Petkovic, M. S. Petkovic and D. Zivkovic, Hansen-Patrick’s Family Is of Laguerre’s Type, Novi Sad J. Math. 33 (2003), no. 1, 109-115.

[8] Kenneth A. Ross, Elementary Analysis, Springer-Verlag New York Inc., 1980.

[9] J. Stoer and R. Bulirsh, Introduction to Numerical Analysis, 244-313, Springer- Verlag New York Inc., 1980.

[10] J. F. Traub, Iterative Methods for the Solution of Equations, Chelsea Publishing Company, 1982.

[11] Stephen Wolfram, The Mathematica Book, 4th ed., Cambridge University Press, 1999.

*

Department of Pure Mathematics University of Waterloo

Waterloo, Ontario, Canada N2L 3G1 Faculty of Science, University of Malaya 50603, Kuala Lumpur, Malaysia

E-mail: conpana@empal.com

참조

관련 문서

12) Maestu I, Gómez-Aldaraví L, Torregrosa MD, Camps C, Llorca C, Bosch C, Gómez J, Giner V, Oltra A, Albert A. Gemcitabine and low dose carboplatin in the treatment of

최근에는 단순히 Solid Wire만을 사용하지 않고, Filler Metal을 Tube형태로 만들고 그 안에 F l u x를 삽입하여 용하는 Flux Cored Arc Welding, Electro Gas Welding등의 방

Given these quantities, Gordon method implies that the cost of capital of a firm increases with its growth rate.. The second method is based on

Our method is elementary since we only use the R´edei matrix M F + associated to F and this method also works for real quadratic number

However, it is expected that in the case of biotech start-ups facing the Valley- of-Death, the shareholders’ equity value has a function of a growth option in real

We also define period of a Fibonacci sequence modulo an integer, m and derive certain interesting properties related to them.. Afterwards, we derive some new properties of a

- A better method to control the gain uses a JFET as a voltage-controlled resistor in a negative feedback path. - A JFET operating with a small or zero V DS is operating in

The idea of quasi-coincidence of a fuzzy point with a fuzzy set, which is men- tioned in [5], has played a vital role in generating some different types of fuzzy subgroups,