Abstract Generated abstract
This note extends a modification of the Lobachevsky-Graeffe method for numerical solution of algebraic equations to cases in which roots have equal moduli and may be multiple, avoiding a preliminary separation of multiple roots. It derives how repeated Graeffe transformations and a small shift of the variable can distinguish groups of equal modulus through the regular or irregular behavior of transformed coefficients. The method gives formulas for computing root moduli, forming quadratic equations to recover the roots, and determining multiplicities within real and complex conjugate groups. Practical qualifications are discussed for nearly equal moduli and roots near the unit circle, and the procedure is illustrated by a sixth degree example.
Full Text
Mathematics
A. N. Kostovskii
On a Method for the Numerical Solution of Algebraic Equations in the Case of Roots Equal in Modulus
(Presented by Academician S. L. Sobolev on 23 XI 1959)
V. Horak, developing Graeffe’s ideas, gives in paper \((^1)\) a modification of the well-known Lobachevsky—Graeffe method for the numerical solution of algebraic equations. In the equation under study, V. Horak first frees it from multiple roots. In practice such a freeing causes considerable difficulties if the coefficients of the given equation have not exact, but approximate, values.
The purpose of the present note is to extend the results of the cited paper to equations having multiple roots and to indicate an algorithm for determining their multiplicities.
Let an equation with real coefficients be given
\[ f(x)=a_0+a_1x+\ldots+a_nx^n=0,\quad a_0\ne0, \tag{1} \]
the moduli of whose roots satisfy the inequalities
\[ 0<|x_1|\leqslant |x_2|\leqslant\ldots\leqslant |x_n|. \tag{2} \]
Then
\[ (-1)^k\frac{a_k}{a_0}=S(\alpha_1\alpha_2\ldots\alpha_k) =\alpha_1\alpha_2\ldots\alpha_k+\alpha_1\ldots\alpha_{k-1}\alpha_{k+1}+\ldots, \tag{3} \]
where
\[ \alpha_k=x_k^{-1},\quad k=1,2,\ldots,n. \]
Consider a group of roots equal in modulus
\[ \leqslant |x_l|<|x_{l+1}|=|x_{l+2}|=\ldots=|x_{l+q}|=\rho<|x_{l+q+1}|\leqslant, \tag{4} \]
with
\[ x_{l+1}=x_{l+2}=\ldots=x_{l+r_0}=\rho,\quad l_0=r_0. \]
\[ x_{l+l_0+1}=x_{l+l_0+2}=\ldots=x_{l+l_0+r_1} =\overline{x}_{l+l_0+r_1+1}=\ldots=\overline{x}_{l+l_0+2r_1} =\rho e^{i\varphi_1}, \]
\[ l_1=l_0+2r_1. \]
\[ x_{l+l_1+1}=x_{l+l_1+2}=\ldots=x_{l+l_1+r_2} =\overline{x}_{l+l_1+r_2+1}=\ldots=\overline{x}_{l+l_1+2r_2} =\rho e^{i\varphi_2}, \]
\[ l_2=l_1+2r_2, \]
\[ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \tag{5} \]
\[ x_{l+l_{s-1}+1}=x_{l+l_{s-1}+2}=\ldots=x_{l+l_{s-1}+r_s} =\overline{x}_{l+l_{s-1}+r_s+1}=\ldots \]
\[ \ldots=\overline{x}_{l+l_{s-1}+2r_s}=\rho e^{i\varphi_s},\quad l_s=l_{s-1}+2r_s, \]
\[ x_{l+l_s+1}=x_{l+l_s+2}=\ldots=x_{l+q}=-\rho,\quad l_{s+1}=q=l_s+r_{s+1}, \]
where
\[ 2r_1+2r_2+\ldots+2r_s=l_s-l_0=2r,\quad r_k=\tfrac12(l_k-l_{k-1}),\quad k=1,2,\ldots,s; \]
\[ 0\leqslant r_k\leqslant [\tfrac12 q],\quad 0\leqslant r_0\leqslant q,\quad 0\leqslant r_{s+1}\leqslant q,\quad 0<\varphi_1<\varphi_2<\ldots<\varphi_s<\pi. \tag{6} \]
Transform (1) \(\nu\) times by the Lobachevsky–Graeffe method
\[ f_\nu(x)=a_0^{(\nu)}+a_1^{(\nu)}x+\cdots+a_n^{(\nu)}x^n=0, \tag{7} \]
\[ a_k^{(\eta)}=\left(a_k^{(\eta-1)}\right)^2+2\sum_{i=1}^{p}(-1)^i a_{k-i}^{(\eta-1)}a_{k+i}^{(\eta-1)},\qquad p=\min(k,n-k), \tag{8} \]
where \(k=0,1,2,\ldots,n;\ \eta=1,2,\ldots,\nu\), and \((^{2})\)
\[ a_{l+k}^{(\nu)} =(\alpha_1\cdots \alpha_l \rho^{-k})^{2^\nu} \left\{ \sum_{j=0}^{k}\left[ C_{q-2r}^{\,j} \sum_{1\le i_1<\cdots<i_{k-j}\le 2r} \cos 2^\nu(\varphi_{i_1}+\cdots+\varphi_{i_{k-j}}) \right]+\varepsilon_{l+k} \right\}, \]
\[ k=1,2,\ldots,q-1, \tag{9} \]
where \(\sum \cos 2^\nu(\varphi_{i_1}+\cdots+\varphi_{i_m})=0\), if \(m>2r\), and \(C_{q-2r}^{\,m}=0\), if \(m>q-2r\).
Using the formula \(\rho=(a_l^{(\nu)}:a_{l+q}^{(\nu)})^{1/q2^\nu}\), determine the moduli of the roots of (1)
\[ \rho_1<\rho_2<\cdots<\rho_m,\qquad 1\le m\le n, \tag{10} \]
where \(|x_{l_i}|<|x_{l_i+1}|=\cdots=|x_{l_i+q_i}|=\rho_i<|x_{l_i+q_i+1}|\), \(q_1+q_2+\cdots+q_m=n\).
Make in (1) the change of variable \(x=y+h\)
\[ f(y+h)=a_0+a_1(y+h)+\cdots+a_n(y+h)^n=A_0+A_1y+\cdots+A_ny^n=0, \tag{11} \]
where*
\[ |h|<\frac12\min_{1\le i<m}(\rho_{i+1}-\rho_i). \tag{12} \]
By virtue of inequality (12), for the roots of (11) \(y_i=x_i-h\) the inequalities (2) will remain valid**
\[ 0\le |y_1|\le |y_2|\le\cdots\le |y_n|; \tag{13} \]
\[ \rho'_1<\rho'_2<\cdots<\rho'_{m'}, \tag{13'} \]
where \(|y'_{i_i}|<|y'_{i_i+1}|=\cdots=|y'_{i_i+q'_i}|=\rho'_i<|y'_{i_i+q'_i+1}|\), \(q'_1+q'_2+\cdots+q'_{m'}=n\).
By virtue of inequalities (6) and (12), relations (4) will be written as follows:
\[ |y_j|<\rho'_j<\rho'_{j+1}<\cdots<\rho'_{j+s+1}<|y_{l+q+1}|,\qquad q'_0+q'_1+\cdots+q'_{j+s+1}=q. \tag{14} \]
With the aid of formulas (8), transform equation (11) \(\mu\) times
\[ f_\mu(y+h)=A_0^{(\mu)}+A_1^{(\mu)}y+\cdots+A_n^{(\mu)}y^n=0. \tag{15} \]
Consider in (10) a group of roots equal in modulus (4), where by \(\rho\) is denoted a group of roots \(\rho_i\) equal in modulus, and \(q=q_i,\ i=1,2,\ldots,m\).
For a sufficiently large number of transformations \(\nu\) and \(\mu\), in equations (7) and (15) the coefficients \(a_l^{(\nu)}, a_{l+q}^{(\nu)}\) and \(A_l^{(\mu)}, A_{l+l_0}^{(\mu)}, A_{l+l_1}^{(\mu)},\ldots,A_{l+l_s}^{(\mu)}, A_{l+q}^{(\mu)}\) will change “regularly” \((^{3})\). The coefficients \(a_{l+1}^{(\nu)}, a_{l+2}^{(\nu)},\ldots,a_{l+q-1}^{(\nu)}\) and \(A_{l+1}^{(\mu)}, A_{l+2}^{(\mu)},\ldots,A_{l+l_0-1}^{(\mu)}, A_{l+l_0+1}^{(\mu)}, A_{l+l_0+2}^{(\mu)},\ldots,A_{l+l_1-1}^{(\mu)}, A_{l+l_1+1}^{(\mu)},\ldots,A_{l+l_s-1}^{(\mu)}, A_{l+l_s+1}^{(\mu)},\ldots,A_{l+q-1}^{(\mu)}\) will change “irregularly.”
The moduli \(\rho'_0,\rho'_1,\ldots,\rho'_{s+1}\) of the roots \(y_{l+1},y_{l+2},\ldots,y_{l+q}\), corresponding
* If \(m=1\), then we take \(h\) arbitrarily.
** If we also set \(h<\frac12\rho_1\), then \(A_0\ne0\) and \(0<|y_1|\le |y_2|\le\cdots\)
in the group of roots equal in modulus, \(x_{l+1}, x_{l+2}, \ldots, x_{l+q}\), are computed by the formulas
\[ \rho'_k = \left(A_{l+l_{k-1}}^{(\mu)} : A_{l+l_k}^{\nu}\right)^{1/q'_k 2^\nu}, \qquad k=0,1,\ldots,s+1,\quad q'_0=0,\quad q'_k=l_k-l_{k-1}. \]
To determine the roots \(x_{l+1}, x_{l+2}, \ldots, x_{l+q}\), we form \(s+2\) quadratic equations
\[ x^2+\frac{(\rho'_k)^2-\rho^2-h^2}{h}\,x+\rho^2=0, \qquad k=0,1,\ldots,s+1. \tag{16} \]
Indeed, \(x_k \bar{x}_k=\rho^2,\;(\rho'_k)^2=(x_k-h)(\bar{x}_k-h)\).
The multiplicities of the roots of modulus \(\rho_i\) of equation (1) are determined from the sequence of “regularly” changing coefficients of equation (15) by the formulas
\[ r_0=q'_0=l_0,\qquad r_{s+1}=q_{s+1}=q-l_s,\qquad r_k=\frac{1}{2}q'_k=\frac{l_k-l_{k-1}}{2},\quad k=1,2,\ldots,s. \]
If the equation contains other groups of roots equal in modulus, then they are determined analogously to what was set forth above for group (4).
Suppose that in inequalities (10) there occur differences \(\rho_{i+1}-\rho_i\) that are considerably less than one. In this case, by virtue of inequality (12), in order to compute the roots of equation (1) with the required accuracy, the coefficients in equation (11) must be taken with a larger number of significant figures. Therefore, when determining \(h\), small differences \(\rho_{i+1}-\rho_i\) may be disregarded; then, if
\[ (\rho_i)^{-1}-(\rho_{i+1})^{-1}>2h, \]
the reciprocals of the roots whose moduli were equal to \(\rho_i\) and \(\rho_{i+1}\) can be determined from \(q'_i+q'_{i+1}\) quadratic equations
\[ \alpha^2+\frac{(\rho'_k)^2-\rho^2-h^2}{\rho^2 h}\,\alpha+\frac{1}{\rho^2}=0, \tag{17} \]
taking \(q'_i\) times \(\rho\) equal to \(\rho_i\), and \(q'_{i+1}\) times equal to \(\rho_{i+1}\); if, however, \(\rho_{i+1}-\rho_i<2h\) and \((\rho_i)^{-1}-(\rho_{i+1})^{-1}<2h\), then for each root whose modulus is equal to \(\rho_i\) or \(\rho_{i+1}\), one must form two quadratic equations (16), taking \(\rho=\rho_i\) and \(\rho=\rho_{i+1}\), and for the root choose the required one from the two values obtained.
When determining \(h\) in (12), the differences \(\rho_{i+2}-\rho_{i+1},\ldots,\rho_{i+k}-\rho_{i+k-1}\) may be disregarded. In this case, for each root with modulus \(\rho_j\) \((i+1\le j\le i+k)\), one should form \(k\) quadratic equations, taking \(\rho\) equal to \(\rho_{i+1},\ldots,\rho_{i+k}\), and for the root choose the required one from the \(k\) values obtained.
If equation (1) has roots whose ratios of moduli differ only slightly from one, then such roots will be computed by the method described above with reduced accuracy. The accuracy of the computations can be increased by separating such roots, increasing the number of transformations \(\nu\) and \(\mu\) of equations (7) and (15).
Suppose that in (10) \(\rho_k<1\), and \(\rho_{k+1}\ge 1\). To avoid small differences \(\rho_{i+1}-\rho_i\), \(h\) should be determined in two ways:
a) \(|h_1|<\frac{1}{2}\min_{k\le i<m}(\rho_{i+1}-\rho_i)\); the roots of equation (1) with moduli not less than one are determined from equations (16);
b) \(|h_2|<\frac{1}{2}\min_{1\le j<k}(\rho_j^{-1}-\rho_{j+1}^{-1})\); the reciprocal values of the roots of equation
(1) with moduli less than one are determined from equations (17).
In cases a) and b), small values of \(h\) can be obtained only for roots whose ratios of moduli differ only slightly from unity. In this case the value of \(h\) can be increased if, as the initial equation, one takes an equation obtained from the given one by one or two transformations, i.e., takes (7) for \(0<\nu\leq 2\).
Example.
\[ f(x)=1+x-0.75x^{2}-2.5x^{3}-0.75x^{4}+x^{5}+x^{6}=0. \]
We record the transformations of the equation in Table 1.
Table 1
| \(a_0=1\) | \(a_1=1\) | \(a_2=-0.75\) | \(a_3=-2.5\) | \(a_4=-0.75\) | \(a_5=1\) | \(a_6=1\) | \(\nu\) |
|---|---|---|---|---|---|---|---|
| 1 | 2.5 | 4.0625 | 5.1250 | 4.0625 | 2.5 | 1 | 1 |
| 1 | \(-1.875\) | \(-0.99609375\) | \(-3.7578125\) | \(-0.99609375\) | \(-1.875\) | 1 | 2 |
| 1 | 5.5078125 | 13.091812 | 17.167999 | 13.091812 | 5.5078125 | 1 | 3 |
| \(a_0^{(4)}=1\) | \(a_1^{(4)}=4.1523743\) | \(a_2^{(4)}=8.46292\) | \(a_3^{(4)}=1.06211\) | \(a_4^{(4)}=8.46292\) | \(a_5^{(4)}=4.152374\) | \(a_6^{(4)}=1\) | 4 |
The coefficients \(a_1^{(\nu)}, a_2^{(\nu)}, a_3^{(\nu)}, a_4^{(\nu)}, a_5^{(\nu)}\) change “irregularly,” therefore
\[ |x_1|=|x_2|=|x_3|=|x_4|=|x_5|=|x_6|=\rho. \]
Here \(\nu=4,\ l=0,\ q=6,\ m=1,\)
\[ \rho=\left(a_0^{(\nu)}:a_6^{(\nu)}\right)^{\frac{1}{6\cdot 16}}=1. \]
For \(h\) we take an arbitrary value, for example \(h=1.5\), and form the equation
\[ f(y+1.5)=7.5625+42.625y+87.5625y^{2}+83y^{3}+40.5y^{4}+10y^{5}+y^{6}=0. \]
We record the coefficients of the transformation of this equation in Table 2.
Table 2
| \(A_0=7.5625\) | \(A_1=42.625\) | \(A_2=87.5625\) | \(A_3=83\) | \(A_4=40.5\) | \(A_5=10\) | \(A_6=1\) | \(\mu\) |
|---|---|---|---|---|---|---|---|
| 57.19141 | 492.5078 | 1204.004 | 633.8125 | 155.3750 | 19 | 1 | 1 |
| \(3.27085\cdot 10^{3}\) | \(1.04847\cdot 10^{5}\) | \(8.43082\cdot 10^{5}\) | \(4.61750\cdot 10^{4}\) | \(2.46452\cdot 10^{3}\) | \(5.025\cdot 10^{1}\) | 1 | 2 |
| \(1.06985\cdot 10^{7}\) | \(5.4776\cdot 10^{9}\) | \(7.01121\cdot 10^{11}\) | \(-2.01292\cdot 10^{9}\) | \(3.11944\cdot 10^{6}\) | \(-2.40398\cdot 10^{3}\) | 1 | 3 |
| \(A_0^{(4)}=\) \(=1.14458\cdot 10^{14}\) | \(A_1^{(4)}=\) \(=1.50015\cdot 10^{19}\) | \(A_2^{(4)}=\) \(=4.91591\cdot 10^{23}\) | \(A_3^{(4)}=\) \(=-3.218\cdot 10^{17}\) | \(A_4^{(4)}=\) \(=1.45511\cdot 10^{12}\) | \(A_5^{(4)}=\) \(=-4.5976\cdot 10^{5}\) | \(A_6^{(4)}=1\) | 4 |
The coefficients \(A_0^{(\mu)}, A_2^{(\mu)}, A_6^{(\mu)}\) change “regularly”; consequently,
\[ |y_1|=|y_2|=\rho_0',\quad |y_3|=|y_4|=|y_5|=|y_6|=\rho_1', \]
\[ \mu=4,\quad l_0=q_0'=2,\quad s=1,\quad l_1=6,\quad q_1'=q-l_0=4,\quad (\rho_0')^{2}=0.2500,\quad (\rho_1')^{2}=5.500. \]
Equations (16) are written as follows:
\[ x^{2}-2x+1=0,\qquad r_0=q_0'=2, \]
\[ x^{2}+1.5x+1=0,\qquad r_1=\frac{1}{2}q_1'=2, \]
therefore,
\[ x_1=x_2=1,\quad x_3=x_4=x_5=x_6=-0.75+i\sqrt{0.4375}. \]
Received
16 XI 1959
REFERENCES CITED
\(^{1}\) V. Horak, Časohis pro pěstování matematiky, 82, 4 (1957).
\(^{2}\) A. N. Kostovskii, Scientific Notes of Lvov University, 38, issue 7, 48 (1956).
\(^{3}\) A. N. Krylov, Lectures on Approximate Calculations, 1950.