A modified Newton method for a quadratic vector equation arising in markovian binary trees
We prove the existence of solution for the quadratic vector equation arising in Markovian binary trees. A modified Newton method for finding the minimal solution of the equation is presented. The monotone convergence of the modified Newton method is proved. Numerical experiments show the efficiency...
Gespeichert in:
| Datum: | 2016 |
|---|---|
| Hauptverfasser: | , , , , , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2016
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/1873 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860507753775104000 |
|---|---|
| author | Deng, Liang-Jian He, Jun Huang, Ting-Zhu Денг, Ліанг-Жіян Ге, Юн Хуан, Тінг-Жу |
| author_facet | Deng, Liang-Jian He, Jun Huang, Ting-Zhu Денг, Ліанг-Жіян Ге, Юн Хуан, Тінг-Жу |
| author_sort | Deng, Liang-Jian |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T09:30:15Z |
| description | We prove the existence of solution for the quadratic vector equation arising in Markovian binary trees. A modified Newton method for finding the minimal solution of the equation is presented. The monotone convergence of the modified Newton method is proved. Numerical experiments show the efficiency of our method. |
| first_indexed | 2026-03-24T02:14:20Z |
| format | Article |
| fulltext |
UDC 517.5
Jun He (School Math. and Comput. Sci., China),
Ting-Zhu Huang, Liang-Jian Deng (School Math. Sci., Univ. Electron. Sci. and Technology, Chengdu, China)
A MODIFIED NEWTON METHOD FOR A QUADRATIC VECTOR
EQUATION ARISING IN MARKOVIAN BINARY TREES*
A MODIFIED NEWTON METHOD FOR A QUADRATIC VECTOR
EQUATION ARISING IN MARKOVIAN BINARY TREES
We prove the existence of solution for the quadratic vector equation arising in Markovian binary trees. A modified Newton
method for finding the minimal solution of the equation is presented. The monotone convergence of the modified Newton
method is proved. Numerical experiments show the efficiency of our method.
Доведено iснування розв’язку квадратного векторного рiвняння, що виникає в марковських бiнарних деревах. За-
пропоновано модифiкований метод Ньютона для знаходження мiнiмального розв’язку цього рiвняння. Встановлено
монотонну збiжнiсть модифiкованого методу Ньютона. Числовi експерименти пiдтверджують ефективнiсть цього
методу.
1. Introduction. We consider the following vector equation:
x = a+B(x\otimes x), (1)
where a, x \in \BbbR n, a, x \geq 0, B \in \BbbR n2\times n is a nonnegative matrix, and the vector e = (1, 1, . . . , 1)T is
always a solution of equation (1). The matrix B can be represented by a tensor Bijk, and Bijk \geq 0,
(Bijkx
2)i =
\sum n
j,k=1
Bijkxjxk. Then we can write the vector equation as:
x = a+Bx2.
Equations of this type occur in the analysis of the extinction probability of a particular family of
multitype branching processes which are called Markovian Binary Trees (MBTs). We can refer to
the papers [2, 3] for a detailed description of MBTs. The MBTs is called subcritical, supercritical or
critical if the spectral radius \rho (R) of the matrix
R := b(e, \cdot ) + b(\cdot , e)
is strictly less than one, strictly greater than one, or equal to one, where the map b(u, v) := B(u\otimes v).
In this paper, we just consider the supercritical case, whereas the minimal nonnegative solution
x\ast \leq e.
Bean, Kontoleon and Taylor [2, 13] introduce two linearly convergent algorithms to solve (1).
The first one is named the depth algorithm, which can be seen as the following functional iteration:
xk+1 = a+ b(xk, xk).
The second algorithm named the order algorithm can be written as:
xk+1 = a+ b(xk+1, xk), (2)
* This research is supported by NSFC (61170311), Chinese Universities Specialized Research Fund for the Doctoral
Program (20110185110020), Sichuan Province Sci. & Tech. Research Project (12ZC1802).
c\bigcirc JUN HE, TING-ZHU HUANG, LIANG-JIAN DENG, 2016
712 ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
A MODIFIED NEWTON METHOD FOR A QUADRATIC VECTOR EQUATION ARISING . . . 713
or equivalently as
xk+1 = a+ b(xk, xk+1). (3)
The thicknesses algorithm, still linearly convergent, is proposed in [3] and consists in alternating
iterations of equations (2) and (3). In [1, 14], the authors use another fix point iteration which have
been called the Perron iteration to solve the system (1). In this paper, we do not compare the perron
iteration with our modified Newton method. If we rewrite equation (1) as
F (x) = x - a - b(x, x) = 0, (4)
in [5], the authors apply the Newton method to the equation (4) yields the iteration
xk+1 = (I - b(xk, \cdot ) - b(\cdot , xk)) - 1(a - b(xk, xk)).
the authors show that the resulting sequence is quadratically and globally convergent. A modified
version has been proposed in [6].
In this paper, we apply the modified Newton method for computing the minimal solution of the
quadratic vector equation arising in Markovian binary trees, and we show the monotone convergence
of the modified Newton method.
The paper is organized as follows. In Section 2, some efforts of establishing the solution of
the system (1) are made. The convergence dynamics of the modified Newton method is studied in
Section 3. In Section 4, some numerical experiments are given to show that the algorithm is efficient.
2. Theoretical analysis of the solution. We first introduce the concept of irreducible tensors
which is given in [11, 12].
Definition 1. An m th order n-dimensional tensor A is called reducible if there exists a nonempty
proper index subset I \subset \{ 1, 2, . . . , n\} such that
ai1,i2,...,im = 0 \forall i1 \in I, \forall i2, . . . , im /\in I.
If A is not reducible, then we call A irreducible.
In this paper, we are only interested in the case in which 0 \leq x \leq e. We will show the existence of
the solution of system (1), and we find that, when the solution is not strictly positive, both functional
iterations and Newton-type algorithms may break down [4], if we assume that B is irreducible or B
is reducible for all i \in I, ai > 0, then we can ensure that x be positive.
Theorem 1. If B is a nonnegative tensor, then there exists a nonzero non-negative vector 0 \leq
\leq x \leq e such that x = a + Bx2. In particular, if B is irreducible or B is reducible for all i \in I,
ai > 0, then x must be positive.
Proof. Let
\Omega =
\bigl\{
(x1, x2, . . . , xn)
T \in \BbbR n
\bigm| \bigm| 0 \leq xi \leq 1, 1 \leq i \leq n
\bigr\}
.
It is clear that \Omega is a closed and convex set. We define the following map \Phi :
(\Phi (x))i =
\bigl(
Bx2 + a
\bigr)
i
.
It is clear that \Phi is well-defined and continuous. According to the Brouwer fixed point theorem,
there exists x \in \Phi such that x = a+Bx2.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
714 JUN HE, TING-ZHU HUANG, LIANG-JIAN DENG
Next we would like to show that x is positive when B is irreducible. Assume that x is not
positive, i.e., there exist some entries of x are zero. Let
I = \{ i | xi = 0\} .
It is obvious that I is a proper subset of \{ 1, 2, . . . , n\} . Let \delta = \mathrm{m}\mathrm{i}\mathrm{n} \{ xj | j /\in I \} . We must have
\delta > 0. Since x satisfies x = a+Bx2, we obtain
n\sum
j,k=1
Bijkxjxk + ai = xi = 0 \forall i \in I.
It follows that
\delta 2
n\sum
j,k/\in I
Bijk + ai \leq
n\sum
j,k/\in I
Bijkxjxk + ai = 0.
Then we can get the results easily.
Theorem 1 just show the existence of the solution of the system (1), you can return to the paper
[4] for more about the minimal solution.
3. The modified Newton method. In this part, we first introduce the iterative scheme of the
modified Newton method as following: for a given m \geq 2 and k = 1, 2, . . . ,
\~xk,1 = xk + F
\prime
(xk)
- 1 F (xk) ,
\~xk,p+1 = \~xk,p - F
\prime
(xk)
- 1 F (\~xk,p) , 1 \leq p \leq m - 1, (5)
xk+1 = \~xk,m.
And we can find that, if m = 2, the modified Newton method reduce to the version of Newton method
introduced in [7], see more about the Newton method in [8 – 10]. First, we give some remarks for
the modified Newton method.
Remark 1. If F
\prime
(xk) is nonsingular and x0 is sufficiently near x\ast , the modified Newton method
iterates converge q-superlinearly to x\ast with q-order m + 1. This means that there is Ks > 0, such
that
\| xk+1 - x\ast \| \leq Ks\| xk - x\ast \| m+1. (6)
In fact, from [7], we can get, when p = 1, there is Kc > 0, such that
\| \~xk,2 - x\ast \| \leq Kc\| xk - x\ast \| 3.
From the quadratic convergence for Newton’s method, we can get, there is Kn > 0, such that
\| \~xk,p+1 - x\ast \| \leq Kp - 1
n \| \~xk,2 - x\ast \| p - 1.
If let p = m - 1, Ks = Km - 2
n Kc, we can get (6).
Remark 2. Let us assume that NR operations are required for the construction of the Jacobi
matrix of vector function F (x) , while Nc operations are required for the solution of each system of
linear algebraic equations in (5), we can find that, NR and Nc are the same as the operations in the
Shamanskii method. That is to say, the optimal value of p is also the same as the optimal value in
the Shamanskii method, which have been given in [15] exactly.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
A MODIFIED NEWTON METHOD FOR A QUADRATIC VECTOR EQUATION ARISING . . . 715
In this paper, we assume that, for the minimal solution x\ast , the matrix I - b(x\ast , \cdot ) - b(\cdot , x\ast ) is a
nonsingular irreducible M -matrix. Since the equation (1) is quadratic, the following expansion holds:
F (y) = F (x) + F
\prime
(y - x) +
1
2
F
\prime \prime
(y - x, y - x), (7)
in particular, if y = x\ast , the minimal positive solution of the equation (1), and \Omega (h, h) := F
\prime \prime
(h, h),
we have
0 = F (x) + F
\prime
(x\ast - x) +
1
2
F
\prime \prime
(x\ast - x, x\ast - x).
Then we obtain
F (x) = F
\prime
(x - x\ast ) -
1
2
\Omega (x - x\ast , x - x\ast ), (8)
F
\prime
(x - x\ast ) = F (x) +
1
2
\Omega (x - x\ast , x - x\ast ). (9)
The following lemma provides a useful tool for analyzing the convergence of the modified Newton
method for the the vector equation (1).
Lemma 1. Let x\ast be the minimal positive solution of the vector equation (1). The sequence
of the vector sets \{ xk, \~xk,1, \~xk,2, . . . , \~xk,m\} generated by the modified Newton method (5) with the
initial vector x0 = 0 are well defined. If xk \leq x\ast , F (xk) \leq 0, for all k \geq 0 and 1 \leq p \leq m, we
have
(a) F (xk+1) \leq 0 and F (\~xk,p) \leq 0;
(b) \~xk,1 \leq xk \leq \~xk,2 \leq . . . \leq \~xk,m = xk+1 \leq x\ast .
Proof. Firstly, for p = 1, we have \~xk,1 = xk + F
\prime
(xk)
- 1 F (xk) . Since F (xk) \leq 0 and F
\prime
(x) is
a nonsingular M-matrix, then \~xk,1 \leq xk.
By (7), we have
F (\~xk,1) = F (xk + F
\prime
(xk)
- 1 F (xk)) =
= F (xk) + F
\prime
(xk)F
\prime
(xk)
- 1F (xk) +
1
2
\Omega (F
\prime
(xk)
- 1F (xk), F
\prime
(xk)
- 1F (xk)) =
= 2F (xk) +
1
2
\Omega (F
\prime
(xk)
- 1F (xk), F
\prime
(xk)
- 1F (xk)) \leq 0. (10)
For p = 2, we obtain
\~xk,2 = \~xk,1 - F
\prime
(xk)
- 1 F ( \~xk,1) = xk + F
\prime
(xk)
- 1 (F (xk) - F ( \~xk,1)).
From (10), we can get
F (xk) - F ( \~xk,1) = - F (xk) -
1
2
\Omega (F
\prime
(xk)
- 1F (xk), F
\prime
(xk)
- 1F (xk)) \geq 0,
then we obtain xk \leq \~xk,2.
Let \~ek,1 = \~xk,1 - x\ast , \~ek,2 = \~xk,2 - x\ast , and H(x2 - x1) = F
\prime
(x1) - F
\prime
(x2), then, by (8),
\~ek,2 = \~ek,1 - F
\prime
(xk)
- 1 F ( \~xk,1) =
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
716 JUN HE, TING-ZHU HUANG, LIANG-JIAN DENG
= \~ek,1 - F
\prime
(xk)
- 1 (F
\prime
(\~xk,1) \~ek,1 -
1
2
\Omega (\~ek,1, \~ek,1)) =
= F
\prime
(xk)
- 1 (F
\prime
(xk) - F
\prime
(\~xk,1))\~ek,1 +
1
2
F
\prime
(xk) \Omega (\~ek,1, \~ek,1) =
= F
\prime
(xk)
- 1H(\~xk,2 - \~xk,1)\~ek,1 +
1
2
F
\prime
(xk) \Omega (\~ek,1, \~ek,1) \leq 0.
Thus, \~xk,2 \leq x\ast .
Assume the results are true for 1 \leq p \leq t. Then, for p = t + 1, with the similar process when
p = 2, we can get \~xk,t \leq \~xk,t+1 \leq x\ast and F (\~xk,t+1) \leq 0.
Therefore, we have proved the results by induction.
Theorem 2. Let x\ast be the minimal positive solution of the vector equation (1). The sequence
of the vector sets \{ xk, \~xk,1, \~xk,2, . . . , \~xk,m\} generated by the modified Newton method (5) with the
initial vector x0 = 0 are well defined. For all k \geq 0 and 1 \leq p \leq m, we have
(a) F (xk) \leq 0 and F (\~xk,p) \leq 0;
(b) \~x0,1 \leq x0 \leq \~x0,2 \leq . . . \leq \~x0,m = x1 \leq \~x1,2 \leq . . . \leq \~x1,m = x2 \leq . . . \leq \~xk - 1,m = xk \leq
\leq \~xk,2 \leq . . . \leq \~xk,m = xk+1 \leq . . . \leq x\ast ;
(c) \mathrm{l}\mathrm{i}\mathrm{m}k\rightarrow \infty xk = x\ast .
Proof. We prove the theorem by mathematical induction. Firstly, for k = 0, from [5], we have
F (x0) \leq 0 and F
\prime
(x0) is the identity operator, by Lemma 1, we have
\~x0,1 \leq x0 \leq \~x0,2 \leq . . . \leq \~x0,m = x1 \leq x\ast .
Assume that the statements (a) – (c) are true for 0 \leq k \leq i, again, from Lemma 1, the statements
(a) – (c) holds when k = i+ 1.
Therefore, the statements (a) – (c) are true for k \geq 0. The sequence xk is monotonic and bounded
from above by x\ast , thus it converges. By passing the first equation of (5) to the limit, we see that, the
limit of xk is the minimal positive solution x\ast of (1).
4. Numerical experiments. In this section, we present our numerical experiments of the
modified Newton method to show its efficiency, and let NM and MNM denote the Newton method
and the modified Newton method. All of our tests were conducted in MATLAB 7.0. The machine
we have used is a PC-Intel(R), Core(TM)2 CPU T7200 2.0 GHz, with 1024 MB of RAM. In all of
our runs we used a zero initial guess. The stopping criterion is
\| x - a+ b(x, x)\| \leq n\varepsilon ,
with \varepsilon = 10 - 13.
Example 1. We use a small-size Markovian binary tree with branches of varying length, de-
scribed in [5] (Example 2). The characterizing matrices are
D0 =
\left(
- 10 0 0
0 - 10 0
0 1 - 10
\right) , d =
\left(
1
1
9
\right) ,
R =
\left(
0 0 0 0 9(1 - p) 0 4.5p 0 4.5p
9p 0 0 0 0 0 0 0 9(1 - p)
0 0 0 0 0 0 0 0 0
\right) ,
where a = ( - D0)
- 1d, and B = a = ( - D0)
- 1R.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
A MODIFIED NEWTON METHOD FOR A QUADRATIC VECTOR EQUATION ARISING . . . 717
Example 2. We use a random-generated MBT of larger size (N=100), the system is created by
the following algorithm [14]:
1. Input: the size of the MBT and a parameter lambda> 0
2. e=ones(N, 1)
3. rand(’state’,0)
4. K=max(b\ast kron(e, e))+lambda
5. a = K \ast e - b\ast kron(e, e)
6. a = a/K
7. b = b/K
Table 1
MNM vs NM for Example 1(p = 0.5) and Example 2(\lambda = 4500)
Example m ITs CPU ERR
Example 1 NM 10 0.1063 2.6668e-015
MNM (m = 2) 8 0.1092 1.1102e-016
MNM (m = 3) 7 0.0855 2.4825e-016
MNM (m = 5) 6 0.0980 4.7103e-016
MNM (m = 10) 5 0.0848 8.6711e-016
Example 2 NM 11 2.0022 9.0316e-014
MNM (m = 2) 8 1.5054 5.4054e-014
MNM (m = 3) 7 1.0215 4.0122e-015
MNM (m = 5) 6 1.0061 2.4974e-015
MNM (m = 10) 5 0.9262 4.0122e-015
Table 2
MNM vs SM for Example 2(\lambda = 4950)
Example m ITs CPU ERR
Example 2 NM 13 0.6841 2.8029e-13
MNM (m = 3) 8 0.4726 3.8391e-14
SM (m = 3) 10 0.5793 1.2885e-13
In Table 1, we list the number of iterations(ITs), the CPU time (in seconds) and the relative
errors(ERR) for the Newton method and the modified Newton method. We observe, for different
choice of the m, the modified Newton method may iterate faster than the standard Newton method.
This is very attractive and has consequential effect on applications. we just test the results when
p = 0.6 in Example 1, and \lambda = 4500 in Example 2, then, the vector of quadratic equation is
(0.9960, 0.9938, 0.9994)T in Example 1.
Figures 1 and 2 show a plot of the iteration count of the Newton method and the modified Newton
method with different of the parameter p or \lambda , Figures 3 and 4 show a similar plot, considering the
CPU time instead of the iteration count. We find that, if m \ll n, according to the number of iterations
and the CPU time with suitable value of m, the modified Newton method can work better than the
standard Newton method.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
718 JUN HE, TING-ZHU HUANG, LIANG-JIAN DENG
0 0.2 0.4 0.6 0.8
2
4
6
8
10
12
14
p
Number of iterations
NM
MNM(m=2)
MNM(m=5)
Fig. 1. Number of iterations needed with different p for Example 1.
4000 4200 4400 4600 4800
4
5
6
7
8
9
10
11
12
13
Numeber of iterations
NM
MNM(m=2)
MNM(m=5)
λ
Fig. 2. Number of iterations needed with different \lambda for Example 2.
0 0.2 0.4 0.6 0.8
0.002
0.004
0.006
0.008
0.01
0.012
0.014
0.016
0.018
0.02
0.022
p
CPU time
NM
MNM(m=2)
MNM(m=5)
Fig. 3. CPU time needed with different p for Example 1.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
A MODIFIED NEWTON METHOD FOR A QUADRATIC VECTOR EQUATION ARISING . . . 719
4000 4200 4400 4600 4800
0.8
1
1.2
1.4
1.6
1.8
2
2.2
2.4
2.6
2.8
CPU time
NM
MNM(m=3)
MNM(m=5)
λ
Fig. 4. CPU time needed with different \lambda for Example 2.
4000 4200 4400 4600 4800
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
CPU time
NM
MNM(m=3)
SNM(m=3)
λ
Fig. 5. MNM vs SM for Example 2: CPU time needed with different \lambda for Example 2.
4000 4200 4400 4600 4800
4
5
6
7
8
9
10
11
12
13
14
Number of iterations
NM
MNM(m=3)
SNM(m=3)
λ
Fig. 6. MNM vs SM for Example 2: Number of iteration needed with different \lambda for Example 2.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
720 JUN HE, TING-ZHU HUANG, LIANG-JIAN DENG
In Figures 5 and 6, we show a plot of the iteration count and the CPU time of the Newton method,
the modified Newton method and the Shamanskii method (SM) with different of the parameter p or
\lambda . We observe, when \lambda = 4950 in Example 2, the modified Newton method can work better than
the standard Newton method and the Shamanskii method. We list the number of iterations, the CPU
time and the relative errors for the Newton method, the modified Newton method and the Shamanskii
method in Table 2 when m = 3. But when \lambda = 4900 in Example 2, the Shamanskii method works
better than the standard Newton method and the modified Newton method. Therefore, for different
value of \lambda , we can different methods to solve the quadratic vector equation.
5. Conclusion. In this paper, we apply the modified Newton method for a quadratic vector
equation arising in Markovian binary trees. The modified Newton method shows its computational
advantage, for different choice of the m, the modified Newton method may have a better performance
than the classical Newton method.
References
1. Meini B., Poloni F. A Perron iteration for the solution of a quadratic vector equation arising in Markovian binary
trees // SIAM. J. Matrix Anal. and Appl. – 2011. – 32. – P. 248 – 261.
2. Bean N. G., Kontoleon N., Taylor P. G. Markovian trees: properties and algorithms // Ann. Oper. Res. – 2008. –
160. – P. 31 – 50.
3. Hautphenne S., Latouche G., Remiche M. A. Algorithmic approach to the extinction probability of branching processes
// Meth. and Comput. Appl. Probab. – 2009. – 26. – P. 129 – 149.
4. Poloni F. Quadratic vector equations // Linear Algebra and Appl. – 2013. – 438, Issue 4. – P. 1627 – 1644.
5. Hautphenne S., Latouche G., Remiche M. A. NewtonЎЇs iteration for the extinction probability of a Markovian binary
tree // Linear Algebra and Appl. – 2008. – 428. – P. 2791 – 2804.
6. Hautphenne S., Van Houdt B. On the link between Markovian trees and tree-structured Markov chains // Eur. J. Oper.
Res. – 2010. – 201. – P. 791 – 798.
7. Kou J., Li Y., Wang X. A modification of Newton method with third-order convergence // Appl. Math. and Comput. –
2006. – 181. – P. 1106 – 1111.
8. Shamanskii V. E. A modification of Newtons method // Ukr. Math. J. – 1967. – 19. – P. 133 – 138.
9. Yiqun Lin, Liang B. Convergence analysis of the Newton – Shamanskii method for a nonsymmetric algebraic Riccati
equation // Numer. Linear Alg. and Appl. – 2008. – 15. – P. 535 – 546.
10. Yiqun Lin, Liang B. A modified Newton method for solving non-symmetric algebraic Riccati equations arising in
transport theory // IMA J. Numer. Anal. – 2008. – 28. – P. 215 – 224.
11. Wen Li, Ng M. On the limiting probability distribution of a transition probability tensor. – Preprint. – 2011,
http://www.math.hkbu.edu.hk/mng/tensor-research/highermarkov.pdf
12. Chang K. C., Pearson K., Zhang T. Perron-Frobenius theorem for nonnegative tensors // Commun. Math. Sci. –
2008. – 6. – Issue 2. – P. 507 – 520.
13. Kontoleon N. The Markovian binary tree: a model of the macroevolutionary process: Ph.D. thesis. – Univ. Adelaide,
2005.
14. Bini D. A., Meini B., Poloni F. On the solution of a quadratic vector equation arising in Markovian binary trees //
Numer. Linear Alg. and Appl. – 2011. – 18. – P. 981 – 991.
15. Brent R. P. Some efficient algorithms for solving systems of nonlinear equations // SIAM J. Numer. Anal. – 1973. –
10. – P. 327 – 344.
Received 10.03.13
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 5
|
| id | umjimathkievua-article-1873 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:14:20Z |
| publishDate | 2016 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/bc/07db74094bf3f046d17e30f1fed943bc.pdf |
| spelling | umjimathkievua-article-18732019-12-05T09:30:15Z A modified Newton method for a quadratic vector equation arising in markovian binary trees Модифицированный метод Ньютона для квадратичного векторного уравнения, возникающего в марковизируемых бинарных деревьев Deng, Liang-Jian He, Jun Huang, Ting-Zhu Денг, Ліанг-Жіян Ге, Юн Хуан, Тінг-Жу We prove the existence of solution for the quadratic vector equation arising in Markovian binary trees. A modified Newton method for finding the minimal solution of the equation is presented. The monotone convergence of the modified Newton method is proved. Numerical experiments show the efficiency of our method. Доведено iснування розв’язку квадратного векторного рiвняння, що виникає в марковських бiнарних деревах. За- пропоновано модифiкований метод Ньютона для знаходження мiнiмального розв’язку цього рiвняння. Встановлено монотонну збiжнiсть модифiкованого методу Ньютона. Числовi експерименти пiдтверджують ефективнiсть цього методу. Institute of Mathematics, NAS of Ukraine 2016-05-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/1873 Ukrains’kyi Matematychnyi Zhurnal; Vol. 68 No. 5 (2016); 712-720 Український математичний журнал; Том 68 № 5 (2016); 712-720 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/1873/855 Copyright (c) 2016 Deng Liang-Jian; He Jun; Huang Ting-Zhu |
| spellingShingle | Deng, Liang-Jian He, Jun Huang, Ting-Zhu Денг, Ліанг-Жіян Ге, Юн Хуан, Тінг-Жу A modified Newton method for a quadratic vector equation arising in markovian binary trees |
| title | A modified Newton method for a quadratic vector equation arising in markovian binary trees |
| title_alt | Модифицированный метод Ньютона для квадратичного векторного уравнения, возникающего в марковизируемых бинарных деревьев |
| title_full | A modified Newton method for a quadratic vector equation arising in markovian binary trees |
| title_fullStr | A modified Newton method for a quadratic vector equation arising in markovian binary trees |
| title_full_unstemmed | A modified Newton method for a quadratic vector equation arising in markovian binary trees |
| title_short | A modified Newton method for a quadratic vector equation arising in markovian binary trees |
| title_sort | modified newton method for a quadratic vector equation arising in markovian binary trees |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/1873 |
| work_keys_str_mv | AT dengliangjian amodifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT hejun amodifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT huangtingzhu amodifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT denglíangžíân amodifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT geûn amodifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT huantíngžu amodifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT dengliangjian modificirovannyjmetodnʹûtonadlâkvadratičnogovektornogouravneniâvoznikaûŝegovmarkoviziruemyhbinarnyhderevʹev AT hejun modificirovannyjmetodnʹûtonadlâkvadratičnogovektornogouravneniâvoznikaûŝegovmarkoviziruemyhbinarnyhderevʹev AT huangtingzhu modificirovannyjmetodnʹûtonadlâkvadratičnogovektornogouravneniâvoznikaûŝegovmarkoviziruemyhbinarnyhderevʹev AT denglíangžíân modificirovannyjmetodnʹûtonadlâkvadratičnogovektornogouravneniâvoznikaûŝegovmarkoviziruemyhbinarnyhderevʹev AT geûn modificirovannyjmetodnʹûtonadlâkvadratičnogovektornogouravneniâvoznikaûŝegovmarkoviziruemyhbinarnyhderevʹev AT huantíngžu modificirovannyjmetodnʹûtonadlâkvadratičnogovektornogouravneniâvoznikaûŝegovmarkoviziruemyhbinarnyhderevʹev AT dengliangjian modifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT hejun modifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT huangtingzhu modifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT denglíangžíân modifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT geûn modifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees AT huantíngžu modifiednewtonmethodforaquadraticvectorequationarisinginmarkovianbinarytrees |