Determination of All Roots of a Polynomial of nth Degree with Complex Coefficients on the Minsk-1 Computer
Abstract Generated abstract
This paper presents a computational procedure for finding all roots of a polynomial of degree up to 20 with complex coefficients on the Minsk-1 computer. It formulates root finding as minimization of the modulus of the polynomial and applies a steepest descent iteration, supplemented by a circular search step when the derivative is small or the descent parameter is inefficient. The program uses complex arithmetic subroutines, Horner evaluation of derivatives, an automatically chosen initial approximation based on the mean of the roots, and deflation after each root is obtained. The authors describe the memory organization and control flow of the implementation, emphasizing that the method does not require prior approximate root values and is intended to provide accurate roots with rapid, quadratically convergent computation.
Full Text
Proceedings of the Tomsk Polytechnic Institute named after S. M. Kirov
Tom 243, 1972
Determination of All Roots of a Polynomial of the \(n\)-th Degree with Complex Coefficients on the “Minsk-1” Computer
G. L. Kalinichenko, G. N. Dronova
(Presented by the Computer Engineering Department of the Scientific Research Institute of Nuclear Electric Power Plants)
The solution of equations, algebraic or transcendental, is one of the essential problems of applied analysis, the need for which arises in numerous and highly varied branches of physics and mechanics, engineering and natural science in the broadest sense of the word.
In computing practice, the need most often arises to determine the roots of a polynomial without knowing their approximate values. This problem can be solved by the method of steepest descent. The method of steepest descent makes it possible to determine all roots of a polynomial of the \(n\)-th degree with complex coefficients without specifying approximate values. The method of steepest descent is implemented on a computer, ensures a high operating speed, and makes it possible to determine the roots with a high degree of accuracy; moreover, it has quadratic convergence.
The problem of determining all roots of a polynomial is equivalent to the problem of determining all points of absolute minimum of a function of two variables \(\varphi[u(x,y), v(x,y)]\), where \(F=\varphi(u,v)\) is taken as
\[ \sqrt{u^2+v^2}\quad \text{or}\quad |u|+|v|. \]
Successive approximations to the points of minimum may be carried out by the formulas
\[ z_{k+1}=z_k-\mu\,\frac{P_n(z_k)}{P'_n(z_k)}, \]
where \(\mu\) is determined from the inequality
\[ (*)\qquad |P_n(z_{k+1})|<|P_n(z_k)|. \tag{1} \]
The number for which this inequality is determined is called a suitable parameter \(|0|<\mu<1\). If \(P'(z_k)\) is small, then for descent along the surface \(F(x,y)\) it is inadvisable to apply formula \((*)\), since the suitable parameter is determined after a large number of trials. If a circle of radius \(r_k\) is described around any point \(z_k\), then on the boundary of this circle there will necessarily be found points at which inequality (1) is satisfied. These points may be taken as the next approximations to the root. The radius of the circle is determined by the formula
\[ r_k=\left[\max\left\{\left|\frac{n c_n-j}{c_n}\right|^{\frac{1}{j}}\right\}_{j=1}^{j=n}\right]^{-1}. \tag{**} \]
Here \(c_j\) are the coefficients of the expansion of the polynomial \(P_n(z)\) in powers of \((z-z_k)\).
The search for a point on the circumference is carried out in the following way. We compute the sequence of numbers
\[ z^{(0)}_{lk}=z_k\ldots z_k l^{i l h_0}, \quad \text{where } h_0=\frac{\pi}{4};\quad l=0,1\ldots 7 \]
\[ z^{(j)}_{lk}=z_k+z_k l^{i(2l+1)h_j};\quad h_j=\frac{h_j-1}{2} \tag{***} \]
\[ l=0,1,\ldots 2^{2+j}-1;\quad j=1,2\ldots \]
And as \(z_{k+1}\) one takes that one of them for which inequality (1) is satisfied for the first time.
Thus, the computation is performed either according to \((*)\) or according to \((***)\). The criterion for passing from one formula to the other is the inequality
\[ |P_n(z_k)|\geq \mu R_k |P'_n(z_k)|, \]
\[ \text{where}\qquad R_k=\sqrt[n]{|P_n(z_k)|\frac{1}{|a_0|}},\qquad \mu=(4\div 6). \tag{2} \]
If this inequality is satisfied, the computations are performed according to formula \((***)\); if it is not satisfied, then according to \((*)\). The method of steepest descent makes it possible to determine the roots of a polynomial starting from an arbitrary initial approximation \(z_0\). However, in order to save computation time, as the initial approximation one may take
\[ z_0=\nu+i\sqrt[n]{|P_n(\nu)|\frac{1}{|a_0|}}, \]
where \(\nu=-\dfrac{a_1}{n a_0}\). The quantity \(\nu\) is the arithmetic mean of all the roots of the polynomial.
Description of the program
The program is written in the interpreting system and is designed for a polynomial with complex coefficients of degree not greater than 20. For each coefficient two cells are allotted—one for the real part, the other for the imaginary part. The program contains standard subroutines for multiplication and division of complex numbers, as well as for finding the derivative of a polynomial at a complex number by Horner’s scheme, and the modulus of a complex number, which have to be accessed frequently.
The memory of the machine is divided as follows:
- The standard subroutines, together with the IS, occupy cells 1 through 750.
- The data are entered beginning with cell 1572.
- The working cells are located in cells 1500–1515. The program is started from cell 767.
The initial approximation is found by formula (3). Depending on whether conditions (1) and (2) are satisfied, the subsequent approximations are sought by formulas \((*)\), \((***)\). After an approximation satisfies the prescribed accuracy, we identify this approximation as a root of the polynomial. Then we reduce the degree of the polynomial and compute the next root of the polynomial of degree \(n-1\), if the root is real, and of degree \(n-2\), if the root is complex, and so on until all roots of the polynomial have been found.
Fig. 1. Program flowchart
Visible labels in the flowchart:
- Preparation for work
- Conversion of numbers from base 10 to base 2
- Finding \(z_n\) by formula (3)
- Finding \(|P(z_n)|/P'(z_n)\)
- Checking condition (2) [[unclear: formula inside decision block]]
- Finding \(z_{n+1}\) by formula (*)
- Checking the condition [[unclear: formula inside decision block]]
- Accuracy check
- Real or complex root
- Decreasing the degree of the polynomial by 1
- Decreasing the degree of the polynomial by 1
- Preparation for the next number
- Is an equation of the first degree left?
- Check for completion
- Solution of a linear equation
- Stop
- Finding \(|C_k|\)
- Search for \(\max |C_k|\)
- Finding \(z_k\) by formula (*)
- Finding \((j)\) by \(k\) [[unclear: formula text]]
- Checking condition (1) [[unclear: formula inside decision block]]
Arrow labels: yes; no; to 8; to 3.
REFERENCES
B. I. Demidovich and I. A. Maron. Fundamentals of Computational Mathematics. ShFM&L, Moscow, 1963.
V. V. Voevodin. Numerical Methods of Algebra. FML, Moscow, 1966.
V. L. Zaguskin. Handbook of Numerical Methods for Solving Algebraic and Transcendental Equations. FML, Moscow, 1960.
V. D. Del, G. L. Kalinichenko, V. A. Maltsev. Automation of Programming for the Minsk-1 Digital Computer by the Method of Interpreting Systems. Tomsk, 1969.