An algorithm for solving cubic equations.pdf В настоящее время в справочной литературе для научно-технических работников практически только в [1, с. 29] представлен численный способ решения кубического уравнения. Способ из [1] заключается в последовательном выполнении следующих действий: а) поиск (путём нахождения значений левой части уравнения в отдельных точках числовой оси) того замкнутого промежутка, который содержит во внутренней точке один корень, имеющий кратностью число 1; в) вычисление начального приближения этого корня обратной линейной интерполяцией; у) итерационное вычисление следующих приближений этого корня по формуле метода касательных [2, с. 421]; 5) деление левой части уравнения на разность между неизвестной величиной и последним приближением этого корня; е) вычисление корней квадратного многочлена, полученного предыдущим действием. Этот способ на практике часто требует больших затрат времени. Притом наибольшие затраты приходятся на действия а, в и у, то есть на использование метода касательных. Значительных затрат требует и действие 5 (при воплощении в компьютерные программы). Поэтому целью исследований, представленных в данной работе, было построение такого доступного для научно-технических работников численного способа решения уравнения х3 + k1x2 + k2x + k3 = 0 (1) с действительными коэффициентами, который не использует метод касательных. Задачей исследования служило построение такого алгоритма вычисления корней уравнения (1), который не выполняет действий а, в, Y, 5 и использует дихотомию. Задача исследования была решена в предположении k3^0. Методами исследования были изучение и анализ литературных источников, теоретически обоснованные математические выкладки, математическое моделирование и компьютерный эксперимент. Решение задачи изложено ниже. Применение метода неопределённых коэффициентов к преобразованию левой части уравнения (1) приводит к тождеству х3 + k1x2 + k2x + k3 = (х2 + a*x + b*)(x + c*), (2) * . * * в котором совокупность величин a , b , c является решением системы a + c = k1, (3.1) ac + b = k2, (3.2) bc = k3. (3.3) Решение a , b , c может быть неоднозначным, но для нахождения корней уравнения (1) достаточно найти одно решение системы (3). Ниже этот факт учитывается при построении алгоритма. Алгоритм использует в формулировках шагов 4 и 6 следующие обозначения корней уравнения (1): тот действительный корень, который получается приравниванием к нулю выражения x + c*, имеет обозначение x1; те корни, которые получаются приравниванием к нулю квадратного трехчлена x2 + a*x + b*, имеют обозначения x2 и x3. Согласно принятым обозначениям, справедливо равенство x1 = -c*, которое с помощью зависимости (3.1) преобразуется в соотношение x1 = a* - k1. Это соотношение используется в формулировке шага 4 алгоритма. Тот факт, что x2 и x3 являются корнями трёхчлена x2 + a*x + b*, используется в формулировке шага 6 алгоритма. Система (3) равносильна системе c = k1 - a, (4.1) a(k1 - a) + b = k2, (4.2) b(k1 - a) = k3. (4.3) Так как в уравнениях (4.2) и (4.3) отсутствует величина c, то лишь с помощью этих уравнений можно найти a* и b*. Используем эту возможность, отнеся плоскость к прямоугольным декартовым координатам a,b с центром в точке O. Будем считать, что плоскость изображена на экране монитора (заполняя его полностью), а точка O изображается его центром. Также будем считать, что относительно взгляда пользователя компьютером на экран координатная ось a направлена вправо от центра, а координатная ось b - вверх от центра. Преобразуем соотношения (4.2) и (4.3): b = a2 - k1a + k2, (5.1) b = - k3/( a - k1). (5.2) Из соотношения (5.1) следует, что b* = at (a - k1) + k2. Этот факт используется в формулировке шага 5 алгоритма. Зависимость (5.1) задаёт на плоскости параболу, ветви которой направлены вверх. Ось симметрии параболы в случае k1 = 0 совпадает с координатной осью b, а в случае к1^0 параллельна ей. Абсциссой и ординатой вершины параболы являются соответственно числа 2-1к1 и к2 - 41к12. Зависимость (5.2) определяет на плоскости гиперболу, центром которой служит та точка, абсциссой и ординатой которой являются соответственно числа k1 и 0. Асимптотами гиперболы являются координатная ось a и прямая a = k1. Вертикальная асимптота гиперболы пересекается с параболой в той точке, абсциссой и ординатой которой являются соответственно числа к1 и к2. Исключение величины b из уравнений (4.2) и (4.3) приводит к следующему уравнению для нахождения абсциссы a* точки пересечения гиперболы и параболы: a3 - 2k1a2 + (k12 + k2)a - k1k2 + k3 = 0. (6) Заменим в нём обозначение неизвестной величины символом t, а вместо a* будем использовать обозначение t*. Построим (на основе левой части уравнения (6)) вспомогательный многочлен q, определяемый равенством q(t) = t3 - 2k1t2 + (к12 + k2)t - к1к2 + к3. (7) Рассмотрим на комплексной z-плоскости соответствующее многочлену q уравнение z3 - 2k1z2 + (k12 + k2)z - k1k2 + k3 = 0, (8) в котором z = a + ib. Воспользуемся (с точностью до обозначений) известными свойствами корней алгебраического уравнения с действительными коэффициентами на комплексной плоскости [3, с. 75]. Согласно этим свойствам, корни уравнения (8) на z-плоскости принадлежат замкнутому кольцу или замкнутому кругу. Центром кольца или круга служит начало координат. В случае кольца границей является объединение двух окружностей, имеющих свои радиусы. В случае круга границей служит его окружность. В данной работе в случае кольца меньший радиус имеет обозначение nb, а больший радиус - nc. В случае круга за nb принято число 0, а за nc - радиус круга. Величины nb и nc зависят от величин b3 и c0, определяемых равенствами b3 = max{1, | - 2k1|, |k12 + k2|}; (9) c0 = max{|- 2k1|, | k12 + k2|, |- k1k2 + k3|}. (10) Для величин nb и nc справедливы зависимости nb = |- k1k2 + k3|/(b3 + |-k1k2 + k3|), nc = 1 + c0. (11) Зависимости (9) - (11) учитываются на шаге 1 алгоритма. Величина t*, являясь корнем и многочлена (7), и уравнения (8), располагается на действительной оси комплексной z-плоскости, а именно в объединении замкнутых промежутков [- nc, - nb], [nb, nc]. (12) Из величин nb и nc лишь nb может принимать значение 0. Этот факт учитывается на шаге 2. Если уравнение (8) имеет комплексные корни, а его действительный корень отличен от нуля, то этот корень является внутренней точкой одного из промежутков (12). Поэтому он может быть найден с помощью дихотомии одного из промежутков (12) и присваивания величине t* значения этого корня. Если уравнение (8) не имеет комплексных корней и ни один из его корней не является нулём, то при любом расположении действительных корней уравнения (8) внутри промежутков (12) один из них позволяет найти с помощью дихотомии корень уравнения (8) и присвоить величине t* значения найденного корня. Эти факты являются очевидными и используются на шаге 3 алгоритма. Изложенное выше позволяет сформулировать алгоритм решения уравнения (1). Алгоритм 1. Вычисление значений величин b3, c0, nb, nc по формулам b3 = max{1, | - 2k1|, | k12 + k2|}, c0 = max{ - 2k1|, | k12 + k2|, | - k1k2 + k3|}, nb = | - k1k2 + k3|/(b3 + | - k1k2 + k3|), nc = 1 + c0. 2. Проверка величин nb на корень уравнения Z - 2k1z2 + (k12 + k2)z - k1k2 + + k3 = 0. В случае положительного результата проверки: присваивание величине t* значения nb и переход на шаг 4. 3. Определение знака произведения q(nb)-q(nc). В случае отрицательного знака - дихотомия промежутка [nb,nc] и присваивание величине t* значения найденного корня. В случае положительного знака - дихотомия промежутка [ - nc, - nb] и присваивание величине t* значения найденного корня. 4. Вычисление действительного корня x1 уравнения (1) по формуле x1 = t* - k1. 5. Вычисление значений величин a* и b* по формулам at = t*, b* = at (at - k1) + k2. 6. Вычисление корней уравнения x2 + atx + b* = 0 и присваивание их значений корням x2 и x3 уравнения (1). Пример 1. Требуется решить с помощью алгоритма уравнение x3 - 18,1x -- 34,8 = 0 [1, с. 29]. Перед применением алгоритма находим значения величин к1, к2, к3: к1 = 0; к2 = - 18,1; к3 = - 34,8. Результаты выполнения шагов алгоритма: 1) b3 = 18,1; c0 = 34,8; nb = 0,657844990548204; nc = 35,800000000000000. 2) q(nb) ф 0. 3) q(nb)-q(nc) < 0. t* = 5,005265097281269. 4) x1 = 5,005265097281269. 5) a* = 5,005265097281269; b* = 6,952678694062071. 6) x2 = -2,502632548640635 + i(-0,830366798798310); x3 = -2,502632548640635 + i(0,830366798798310). При решении уравнения из примера 1 посредством алгоритма итерационные шаги были прекращены тогда, когда абсолютная величина значения многочлена q в середине очередного отрезка не превысила числа 10-17. Всего было сделано 65 шагов. Корни, полученные с помощью алгоритма, совпали с корнями, полученными по формулам из [4]. Сопоставление корней, полученных с помощью алгоритма, с корнями из [1] приводит к следующим выводам. При округлении x1 и действительных частей корней x2 и x3, полученных с помощью алгоритма, соответственно до шести и девяти значащих цифр получаются соответствующие величины из [1]. При таком округлении мнимых частей корней x2 и x3, полученных с помощью алгоритма, при котором число значащих цифр совпадает с числом значащих цифр в корнях x2 и x3 из [1], имеет место несовпадение в трёх последних разрядах. Пример 2. Требуется вычислить корни полинома Якоби P3(2,1,x) [5, с. v] с помощью алгоритма. Для вычисления корней предварительно найдём значения коэффициентов к1, к2, к3 по следствию из формулы явного выражения [5, с. v]. В результате получим следующие равенства: к1 = -1,28571428571429; к2 = 4,28571428571429-10 - 1; к3 = -2,85714285714286-10 - 2 Результаты выполнения шагов алгоритма: 1) b3 = 2,57142857142857, c0 = 2,57142857142857, nb = 1,68865435356201-10ч, nc = 3,57142857142857. 2) q(nb) ф 0. 3) q(-nc)-q(-nb) < 0, t* = -1,19712632620158. 4) x1 = 8,85879595127039-10-2. 5) a* = -1,1971263262015, b* = 3,22520450054291-10-1. 6) x2 = 7,87659461760847-10-1, x3 = 4,09466864440735-10-1. При решении уравнения из примера 2 посредством алгоритма итерационные шаги были прекращены тогда, когда абсолютная величина многочлена q в середине очередного отрезка не превысила число 10-17. Всего было сделано 55 шагов. Все корни, полученные с помощью алгоритма, совпали с корнями, полученными по формулам из [4]. Корни x1 и x2, полученные с помощью алгоритма, совпадают с соответствующими известными корнями [5, с. 235] (в [5] приведены корни, полученные методом Ньютона). Притом последняя значащая цифра корня x3, полученного с помощью алгоритма, отличается на единицу от соответствующей цифры корня из [5], а остальные значащие цифры полученного с помощью алгоритма корня x3 совпадают с соответствующими цифрами корня из [5]. Значения величин а* и Ь* в примерах 1 и 2 являются координатами точек, расположенных в верхней полуплоскости той плоскости, которая выше отнесена к системе координат O, а, Ь. В обоих примерах значение величины а* больше значения величины к1, а величина к3 имеет отрицательное значение. Эти факты -проявление следующих закономерностей: если к3 < 0, то в верхней полуплоскости, справа от вертикальной асимптоты гиперболы, парабола и гипербола имеют по крайней мере одну общую точку; если к3 > 0, то в верхней полуплоскости, слева от вертикальной асимптоты гиперболы, парабола и гипербола имеют по крайней мере одну общую точку. Закономерности вытекают из взаимного расположения гиперболы и параболы на плоскости. Алгоритм закономерностей не учитывает, хотя учёт может приводить к уменьшению длины того промежутка, к которому можно применять дихотомию. Учёт закономерностей приводит к изложенной ниже модификации алгоритма. Модификация использует табл. 1, в которой тот промежуток, к которому следует применять дихотомию, имеет обозначение W. Если одной из его границ является к1, то имеет место упоминаемое выше уменьшение длины промежутка, подвергаемого дихотомии. Таблица 1 Границы предназначенного для дихотомии промежутка W Случаи Меньшая и большая г эаницы промежутка W 1 к30; q^O-q^,,)^ к1 п,с 2 к3

Скачать электронную версию публикации