watanabe s. hybrid manipulations for the solution of system of nonlinear equations.pdf

(2194 KB) Pobierz
PubL RIMS, Kyoto Univ.
19 (1983), 367-395
Hybrid Manipulations for the Solution of
of Nonlinear Algebraic Equations
By
Satoshi WATANABE*
§ 1.
fiilrocliiclioii
The solution of systems of nonlinear algebraic equations plays an
important role in the analysis of practical problems arising in mathematics,
physics or engineerings.
Many methods by the numerical manipulation languages such as
FORTRAN have been proposed so far for finding the numerical solution
of a system of nonlinear algebraic equations given by
(1.1)
where
x
and
f(x)
/(-r)=0,
are real ^/-dimensional vectors, and
f(x)
is defined
to be twice continuously differentiable on a bounded region D in R
n
.
However the numerical manipulation languages
calculations of determinants.
can not handle mathe-
matical operations such as formal differentiations, substitutions or symbolic
Only very recently, by practical applications
of the symbolic and algebraic manipulation languages such as REDUCE
2 [7], it is possible for the computers to treat these mathematical opera-
tions.
If we introduce both numerical and symbolic manipulations, termed
here as
hybrid manipulations,
new and efficient algorithms can be devel-
oped which greatly improve the feasibility of solving the system of non-
linear algebraic equations.
oping the package
[14,18,28].
For the purpose the author et al. are devel-
Algebraic
Equation's
Solver}
NAES
(Nonlinear
This paper reports on several implementations which in-
corporate newly developed algorithms into the package.
Communicated by S. Hitotumatu, March 28, 1981.
Department of Mathematics, Tohoku Dental University, Koriyama, Fukushima, Japan.
368
SATOSHI WATANABE
In Section 2, a numerical method termed here as
e-secant method
which is a numerical realization of the Newton-Raphson method and was
treated by Samanskii [20, 23, 24] is discussed first and its quadratic con-
vergence property to a simple root are given [11-13, 17, 27, 29, 30].
Secondly we show that under appropriate conditions the inverse matrix
and determinant of the Jacobian matrix of the system also have quadratic
convergence properties.
The convergence of the Newton-Raphson and present £-secant methods
is proved on the assumption that the inverse of the Jacobian matrix is
nonsingular in the neighborhood of the solution
x*.
However we often
A property in
encounter the appearance of singular Jacobian matrices on some iteration
processes by the Newton-Raphson or s-secant methods.
this section.
In Section 3 we shall consider the question of the realization of the
£-secant process where the rank of the Jacobian matrix in the neighbor-
hood of the solution
x*
is essentially degenerated.
This solution is
deflation
known as the
multiple root.
Several important properties of the multiple
root are presented first. Then an algorithm, termed here as the
accuracy [19, 28].
algorithm,
is proposed for finding the multiple root with a sufficient
Lastly four categories for a computational realization
of the algorithm are distinguished in which both numerical and symbolic
manipulations play important roles respectively.
In the package NAES the system of nonlinear algebraic equations
(1. 1) is given in FORTRAN expressions.
However the expressions of
equations in FORTRAN and REDUCE 2 are different each other, and
hence the equations in the FORTRAN form must be converted into the
REDUCE 2 expressions when some mathematical operations are necessary,
and vice versa.
In Section 4 the outlines of these processes are explained
In addition several procedures in REDUCE 2
To show the effectiveness of
by showing examples.
the neighborhood of such a point (the
singular point)
is also given in
which are used in the NAES are given.
the present methods, an illustrative example of three dimensional non-
linear algebraic equations with a quadruple root which was given in
Samanskii [25] is solved by NAES
[19].
In the following, for an n-dimensional vector
x
and
n
X
n
matrix A,
HYBRID MANIPULATIONS FOR THE SOLUTION
we use the norms defined by
n
3(59
||x||-max|^i, || A ||= max Z ] | a ^ | ,
l^i<.n
l^tfSn .7=1
respectively.
§ 2. £-Seeant Algorithm for Simple Roots
2* 1.
Newton-Raphson
Method
We state first of all the algorithm of Newton-Raphson method.
the system of equations be
(2.1)
/(*)=0,
Substitute the new itera-
Let
and
x
be an approximation for the root
X*.
old iteration
x\
(2.2)
where
tion
x
in (2. 1) and expand it in a truncated Taylor series about the
/(.r)+5(.r)(S-.r)=0,
(
2
. 3)
(2. 1) and
given by
1c
500
Suppose now that
S(x)
is non-
k+1
is the Jacobian matrix of the system.
singular, i.e., det [5
f
(o:)]^0.
Let
Q
x
be the starting value for the system
Then the new approximation
x
is
x
the
k-th
iteration.
(2.4)
*
+13
r = *x-[S(*a:)]-
1
/(*j:),
k = 0
t
l,2, - .
The sufficient conditions for the convergence of the Newton-Raphson
method are given in the following.
Theorem 2* I
(Kantorovich
9
s theorem). Assume that there exist
positive constants B
0
, n
Q
, M and K such that
(i)
for the initial approximation °x in
D,
the Jacobian matrix
S(°x) has an inverse
(2.5)
(ii)
\\°r\\^\\S->(°x)
for °x, the system
(2. 1)
satisfies the folio-wing relation
370
(2.6)
(iii)
satisfied
(2.7)
(iv)
SATOSHI WATANABE
\lf(°^\\<7fo,
for x and y in the region
D
3
the following inequality is
\\S(x-)-S(y)\\<M\\x-y\\,
for the constant M and the tensor f
xx
of the third order
with components d
z
fi (x) /dxjdx
k
,
(2.8)
(v)
inequality
£
(i, j, k = l,2,
• • •,
n)
the constants
B
0i
n
Q
, and K introduced above satisfy
the
(2.
9)
h^KBlu,<\ ,
£
and the cube below is contained in
D,
/T»
(2.
-i
rv\
10)
II
II
^-^"
J-
(I
x ~
0
x
II < -
v-L
"^-Oy
^-=- ^—
15
Q
TC
Q
.
B
—
h
Q
Then the system of equations (2,
1)
has a solution x* in the cube
(2.
10) .
Moreover,
the
successive approximations
*^
l
x defined
by
(2.
3)
exist and converge to x* , and the rate of convergence can be
estimated by the inequality
o~
—X
/OL~ N2&+1-1
"
which shows that the order of convergence for the Newton-Raphson
method is quadratic.
As for the
proof
of Theorem 2. 1, see the next section, Kantorovich
[9], Krasnosel'skii
2o 2.
[10] and Henrici [8].
^-Secant Method
Newton-Raphson method leads to a system of linear equations involv-
ing the Jacobian matrix as the coefficient matrix.
Instead of calculating the Jacobian matrix, we consider a perturbation
technique with parameter £ which is assumed to be small enough, and
some guess
x
for the solution
x*,
and set
HYBRID MANIPULATIONS FOR THE SOLUTION
(2.12)
iy
371
= x+e
ej
,
O'=l,2, -,n),
where
j-y
denotes an ^-dimensional vector and
e$
is the
j-th
unit vector.
Let us define the vector
$f(x)
by
(2. 13)
3
f(x)
=/(,y) =/(*+ e«,)
,
and expanding it into a truncated Taylor expansion about
x,
we have
(2.14)
,/(*)=/(* + e«,)
where
f
Jx
and
(2. 15)
«,
(*)
=/
An 72X?2 matrix f/(x) is constructed from
Uj(x)
as its
j-th
column vector.
Using (2.14), let us define an
n Xn
matrix
S(x;e)
whose
j-th
column
vector 5/(j:;s) is defined by
(2. 16)
5,
(x ;
e) =
(f(x
+ 6«,) - /(x) ) /e = (
y
/(x) - /(x) ) /£
where
Sj(x)
is the
j-th
column vector of
S(x)
given by (2.3).
method.
The
matrix
S(x\
e) is called the
perturbed Jacobian matrix
for the £-secant
Analogous to (2. 4) for the Newton-Raphson method, let us now
consider the following formula as the £-secant
method:
ff)
-I 7\
\£j.
Li)
Qf
k
^'
fc
cA
rk + l
k -]
f(k^,\
O ^
JC,
cj L
•%•—
*£\
— —J \
3C)
?
(~L
A 1 9
\
\K
— ^?
-*->
^?
'")
•
For the perturbed Jacobian matrix *5
r
(
fc
.r;
fc
£), we have the following
theorem.
Theorem 2.2.
Let S(
k
x) and S(
k
x\
k
e)
be the nXn
Then
matrices
defined by
(2. 3)
and (2.
16),
respectively.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin