A modified Newton–Raphson method

यह पुस्तक आपको कितनी अच्छी लगी?
फ़ाइल की गुणवत्ता क्या है?
पुस्तक की गुणवत्ता का मूल्यांकन करने के लिए यह पुस्तक डाउनलोड करें
डाउनलोड की गई फ़ाइलों की गुणवत्ता क्या है?
खंड:
20
साल:
2004
भाषा:
english
पृष्ठ:
5
DOI:
10.1002/cnm.664
फ़ाइल:
PDF, 55 KB
Conversion to is in progress
Conversion to is failed
0 comments
 

अपनी समीक्षा पोस्ट करने के लिए साइन इन करें या साइन अप करें
आप पुस्तक समीक्षा लिख सकते हैं और अपना अनुभव साझा कर सकते हैं. पढ़ूी हुई पुस्तकों के बारे में आपकी राय जानने में अन्य पाठकों को दिलचस्पी होगी. भले ही आपको किताब पसंद हो या न हो, अगर आप इसके बारे में ईमानदारी से और विस्तार से बताएँगे, तो लोग अपने लिए नई रुचिकर पुस्तकें खोज पाएँगे.
1

A non-linear triangular curved shell element

साल:
2004
भाषा:
english
फ़ाइल:
PDF, 145 KB
2

‘Interpolation requirements for implicit gradient-enhanced continuum damage models’

साल:
2004
भाषा:
english
फ़ाइल:
PDF, 59 KB
COMMUNICATIONS IN NUMERICAL METHODS IN ENGINEERING
Commun. Numer. Meth. Engng 2004; 20:801–805 (DOI: 10.1002/cnm.664)

A modied Newton–Raphson method
Ji-Huan He∗; †
College of Basic Science; Shanghai Donghua University; 1882 Yan’an Xilu Road; Shanghai 200051; China

SUMMARY
In this paper, we propose the following modied Newton–Raphson iteration formulation:
r
xn+1
= xnr −

rxnr −1 f(xn )
f (xn )

In case r = 1, the obtained formulation reduces to the Newton–Raphson formulation. The present technique circumvent pitfalls of the Newton–Raphson iteration method. Some examples are illustrated.
Copyright ? 2004 John Wiley & Sons, Ltd.
KEY WORDS:

Newton–Raphson iteration method; non-linear equations; Lagrange multiplier

1. INTRODUCTION
The well-known Newton–Raphson method has been extensively used in numerical methods
[1]. Although the method is often very ecient, there are situations where it performs poorly.
Such is the case, e.g. for strongly non-linear equations with poor prediction. This paper
proposes a reliable modication of the method so that the shortcomings of the Newton–
Raphson method can be partly or completely eliminated. The method is denoted as a ‘Modied
Newton–Raphson Method’, the suggested method replace xn by xnr , where n is the iteration
index, and r is a constant dierent from unit.
It is noted that we use the same terminology ‘Modied Newton–Raphson Method’ as that
in some standard books, e.g. Reference [2], with dierent meanings. In the latter case, the
tangent stiness matrix is updated only once per increment, rather than in each iteration as
illustrated in the suggested method.

∗ Correspondence

to: Ji-Huan He, College of Basic Science, Shanghai Donghua University, 1882 Yan’an Xilu Road,
Shanghai 200051, People’s Republic of China.
† E-mail: jhhe@dhu.edu.cn

Published online 10 June 2004
Copyright ? 2004 John Wiley & Sons, Ltd.

Received 9 December 2002
Accepted 1 July 2003

802

J.-H. HE

Table I.
Iteration

x(r = 1)

x(r = 2)

x(r = 3)

x(r = 5)

x(r = 5:5)

x(r = 7); 

1
2
3
4
5
6
7
8
9
10

51.650
46.485
41.836
37.652
33.887
30.498
27.448
24.704
22.233
20.010

7.169
6.412
5.735
5.129
4.588
4.103
3.670
3.283
2.936
2.626

3.376
2.997
2.661
2.363
2.098
1.863
1.655
1.470
1.309
1.174

1.741
1.517
1.324
1.166
1.055
1.007
1.000
1.000
1.000
1.000

1.581
1.371
1.196
1.070
1.010
1.000
1.000
1.000
1.000
1.000

1.279
1.105
1.016
1.000
1.000
1.000
1.000
1.000
1.000
1.000

2. NEWTON–RAPHSON ITERATION FORMULATION
Consider the equation
f(x) = 0

(1)

If xn is the predicted root, f(xn ) = 0, then we can update the prediction by constructing the
following expression [3]:
xn+1 = xn + f(xn )

(2)

where  is a Lagrange multiplier, which can be optimally identied by making the above
expression stationary with respect to xn [3–5], leading to the result
d xn+1
= 1 + f (xn ) = 0
d xn

(3)

from which the multiplier can be identied as
=−

1
f (xn )

(4)

Substituting the determined multiplier into Equation (2), we obtain the well-known Newton–
Raphson formulation:
xn+1 = xn −

f(xn )
f (xn )

(5)

Example 1
We rst consider the example
f(x) = x10 − 1

(6)

with initial estimate x0 = 0:5.
Table I illustrates the iteration procedure (r = 1) [1].
Due to the poor prediction, the technique is converging, after 42 iterations, to the true root
of 1, but at a very slow rate.
Copyright ? 2004 John Wiley & Sons, Ltd.

Commun. Numer. Meth. Engng 2004; 20:801–805

MODIFIED NEWTON–RAPHSON METHOD

803

3. A NEW ALGORITHM
As pointed out in Reference [6] that any iteration formulas
xn+1 = g(xn )

(7)

can be improved by the Lagrange multiplier
xn+1 = g(xn ) + f(xn )

(8)

The multiplier can be identied as
=−

g (xn )
f (xn )

(9)

So we have the following generalized iteration formulation:
xn+1 = g(xn ) −

g (xn )f(xn )
f (xn )

(10)

If g(xn ) = xn − f(xn )=f (xn ), from Equation (10), we have
xn+1 = xn −

f(xn )
f (xn )f2 (xn )
−
f (xn )
f3 (xn )

(11)

which is similar to those obtained by the homotopy perturbation method [7].
Now we slightly modify Equation (2) in the form
r
= xnr + f(xn )
xn+1

(12)

After identication of the multiplier, we have the following new iteration formula:
r
xn+1
= xnr −

rxnr−1 f(xn )
f (xn )

(13)

In case r = 1, it reduces to the original Newton–Raphson method, we denote as linear Newton–
Raphson method. The suggested method can be called as non-linear Newton–Raphson method
or high-order Newton–Raphson method. The modied Newton–Raphson method uses the concept of curvature (a parabola for r = 2) rather than the tangential line.
Table I shows the iteration procedures of Equation (6) in various values of r. We see
the slight modication leads to a dramatic increase of convergence for a wide range of r.
Rationally, the value of r can optimally identied from Equation (6) by setting @xn+1 =@r = 0.
Example 2
Consider the equation
f(x) = sin x

(14)

If we begin with the initial prediction x = 1:6, the Newton–Raphson method is not valid since
f (1:6) = −0:029 is a small value. Therefore, the original-Raphson method diverges. Table II
illustrates the iteration procedure in case r = 10. The nearest solution near x0 = 1:6 is x = .
We see the eectiveness of the present technique.
Copyright ? 2004 John Wiley & Sons, Ltd.

Commun. Numer. Meth. Engng 2004; 20:801–805

804

J.-H. HE

Table II.
x(r = 10)

Iteration
0
1
2
3
4

1.6
2.7375
3.0075
3.1210
3.1410

Table III.
Iteration

x(r = 3)

0
1
2
3
4
5
6
7

0.5
0.6660
0.7951
0.8830
0.9366
0.96683
0.98301
0.99139

Example 3
Consider a problem with multiple roots.
f(x) = x3 − 5x2 + 7x − 3 = (x − 3)(x − 1)2

(15)

As we know, the Newton–Raphson method cannot deal with multiple roots. We choose an
arbitrary value of r, for example, r = 3, then we have
3
= xn3 −
xn+1

3xn2 (xn3 − 5xn2 + 7xn − 3)
3xn2 − 10xn + 7

The iteration procedure is given in Table III.
4. COMPARISON WITH LINE-SEARCH TECHNIQUES
As an improvement of the original Newton–Raphson method, the so-called line-search method
[8] mainly serves as a compensation of a poor initial estimate.
In each iteration n, the line-search algorithm tries to optimize a linear, quadratic, or cubic
approximation of f along a feasible descent search direction sn .
xn+1 = xn + n sn ;

n ¿0

(16)

By computing an approximately optimal scalar n :
f(xn + n sn )¡f(xn )

(17)

In our approach, a suitable choice of r can easily guarantee the inequality: f(xn+1)¡f(xn).
So our method is much more simple than the line-search technique.
Copyright ? 2004 John Wiley & Sons, Ltd.

Commun. Numer. Meth. Engng 2004; 20:801–805

MODIFIED NEWTON–RAPHSON METHOD

805

5. MULTIDIMENSIONAL CASE
The proposed modied Newton–Raphson method is more useful for an n-dimensional problem. For better illustration of the basic procedure, making the underlying idea clear and not
darkened by the unnecessarily complicated form of mathematical expressions, we consider a
simple system:
sin(x + y) = 0;

cos(x − y) = 0

(18)

Applying the Lagrange multipliers to construct the following iteration formulae:
p
= xnp + 1 sin(xn + yn );
xn+1

q
yn+1
= ynq + 2 cos(xn − yn )

(19)

where p and q are constants, 1 and 2 are Lagrange multipliers.
Identifying the multipliers requires that
@ p
(x ) = 0;
@xn n+1

@
(yq ) = 0
@yn n+1

(20)

After identication of the multipliers, we obtain the following iteration formulae:
p
xn+1
= ynp −

pxnp−1 sin(xn + yn )
;
cos(xn + yn )

q
yn+1
= ynq −

qynq−1 cos(xn − yn )
sin(xn − yn )

(21)

6. CONCLUSION
A new modied Newton–Raphson method has been proposed. The most interesting features
of the proposed method are its extreme simplicity and its very good accuracy in a wide
range of non-linear problems. However, no mathematical proof of its convergence is given
here, and a complete study of the accuracy of the method, and the optimal choice of the
parameter r, as well as some of its renements will be given in a forthcoming publication.
REFERENCES
1. Chapra SC, Canale RP. Numerical Methods for Engineers. McGraw-Hill: New York, 2000.
2. Criseld MA. Non-linear Finite Element Analysis of Solids and Structures, vol. 1: Essentials, Wiley:
New York, 1991; vol. 2: Advanced Topics. Wiley: New York, 1997.
3. Inokuti M et al. General use of the Lagrange multiplier in nonlinear mathematical physics. Variational Method
in the Mechanics of Solids. In: Nemat-Nasser S (ed.). Pergamon Press: Oxford, 1978; 156 –162.
4. He JH. Variational iteration method: a kind of nonlinear analytical technique: some examples. International
Journal of Nonlinear Mechanics 1999; 34(4):699 –708.
5. He JH. A review on some new recently developed nonlinear analytical techniques. International Journal of
Nonlinear Sciences and Numerical Simulation 2000; 1(1):51–70.
6. He JH. Improvement of Newton iteration method. International Journal of Nonlinear Sciences and Numerical
Simulation 2000; 1(2):239 –240.
7. He JH. A coupling method of homotopy technique and perturbation technique for nonlinear problems.
International Journal of Nonlinear Mechanics 2000; 35(1):37– 43.
8. Grippo L, Lampariello F, Lucidi S. A nonmonotone line search technique for Newton’s method. SIAM Journal
of Numerical Analysis 1996; 23:707–716.

Copyright ? 2004 John Wiley & Sons, Ltd.

Commun. Numer. Meth. Engng 2004; 20:801–805