An algorithm for solving cubic equations

Yu. A. Nesmeev

Vestnik Tomskogo gosudarstvennogo universiteta. Matematika i mehanika, no. 5 (2014), pp. 30-39

Résumé

An algorithm for finding the roots of a cubic equation is proposed. It uses the dichotomy and the method of undetermined coefficients. It takes into account the relative position of the parabola and the hyperbola in the plane and the location of roots of algebraic equations in the complex plane. A modification of the algorithm is proposed. Using the algorithm, three examples are solved. One of them is looking for roots of the Jacobi polynomial. The well-known numerical method for solving cubic equations is estimated (from the viewpoint of the scientific and technical personnel). Its following stages are estimated. $\alpha$) Searching for an interval that contains one root. $\beta$) Calculation of the initial approximation of the root. $\gamma$) Calculation of next approximations. $\delta$) Dividing the left side of the cubic equation by a binomial. $\varepsilon$) Calculation of roots of a quadratic polynomial. The author reported the aim of researches presented in this article. The aim was to build such a numerical method of solving the equation $x^3+k_1x^2+k_2x+k_3=0$, (1) that is available to technologists and does not use the method of tangents. The author reported the problem of the research: to construct such an algorithm that computes roots of equation (1) without performing actions $\alpha,\beta,\gamma$, and $\delta$ and uses the dichotomy. The problem of the research was solved under the assumption that $k_3\ne0$. The used methods are as follows: studying and analyzing the literature, mathematical calculations, mathematical modeling, and computer experiment. The following algorithm is presented. 1. Calculating values of the quantities $b_3,c_0,n_b$, and $n_c$ by formulas $b_3=\max\{1,|-2k_1|,|k_1^2+k_2|\}$, $c_0=\max\{|-2k_1|,|k_1^2+k_2|,|-k_1k_2+k_3|\}$, $n_b=|-k_1k_2+k_3|/(b_3+|-k_1k_2+k_3|)$, and $n_c=1+c_0$. 2. Checking quantities $n_b$ for being a root of the equation $q(z)\equiv z^3-2k_1z^2+(k_1^2+k_2)z-k_1k^2+k_3=0$. In the case of a positive test result, assigning the value $n_b$ to the quantity $t^*$ and going to step 4. 3. Determination of the sign of the product $q(n_b)\cdot q(n_c)$. In the case of a negative sign, the dichotomy is applied to the interval $[n_b,n_c]$ and the quantity $t^*$ is assigned the value of the found root. In the case of a positive sign, the dichotomy is applied to the interval $[-n_c,-n_b]$ and the quantity $t^*$ is assigned the value of the found root. 4. Calculating the real root $x_1$ of equation (1) by the formula $x_1=t^*-k_1$. 5. Evaluation of the quantities $a^*$ and $b^*$ by the formulas $a^*=t^*$ and $b^*=a^*(a^*-k_1)+k_2$. 6. Calculation of roots of the equation $x_2+a^*x+b^*=0$ and assigning their values to the roots $x_2$ and $x_3$ of equation (1). In two examples, the author used a specially designed computer programs written in Turbo Pascal. Arithmetic operations on numbers and square rooting generation for non-negative numbers were performed by arithmetic expressions and $sqrt$ function, respectively, from the programming language standard. In one example, operations on numbers were replaced by operations on strings.

Détail

Keywords: dichotomy, complex plane, root of an equation.

Bibliographie

[1] Spravochnik po spetsial'nym funktsiyam s formulami, grafikami i tablitsami, Nauka Publ., Moscow, 1979, 832 pp. (in Russian) | MR

[2] Matematicheskiy entsiklopedicheskiy slovar', Sov. entsiklopediya Publ., Moscow, 1988, 847 pp. (in Russian) | MR

[3] Monastyrskiy P. I. (ed.), Sbornik zadach po metodam vychisleniy, Izd-vo BGU im. V. I. Lenina, Minsk, 1983, 288 pp. (in Russian) | MR

[4] Nesmeev Yu. A., “Ob odnom podkhode k resheniyu algebraicheskikh uravneniy 3-y i 4-y stepeney”, Vestnik Tomskogo gosudarstvennogo universiteta. Matematika i mekhanika, 2011, no. 1(13), 26–30 (in Russian)

[5] Glonti E. N., Tablitsy korney i kvadraturnykh koeffitsientov polinomov Yakobi, Vychislitel'nyy tsentr AN SSSR Publ., Moscow, 1971, 238 pp. (in Russian) | MR

[6] Rukovodstvo po programmirovaniyu pod upravleniem MS DOS, Radio i svyaz' Publ., Moscow, 1995, 544 pp. (in Russian)