Решение кубического уравнения / Методы решения нелинейных уравнений и их систем / Алгоритмы
Решение кубического уравненияНа этой странице представлен алгоритм для решения кубического уравнения методом Виета-Кардано. Программа написана для случая действительных коэффициентов (корни могут быть комплексными). Кубическое уравнение записывается в виде: x 3 +a*x 2 +b*x+c=0. Для нахождения его корней, в случае действительных коэффициентов, вначале вычисляются: Q=(a 2 -3b)/9, R=(2a 3 -9ab+27c)/54. Далее, если R 2 3 , то уравнение имеет три действительных корня, вычисляющихся по формулам (Виета): t=acos(R/sqrt(Q 3 ))/3, В том случае, когда R 2 >=Q 3 , то действительных корней один (общий случай) или два (вырожденные случаи). Кроме действительного корня, имеется два комплексно-сопряженных. Для их нахождения вычисляются (формула Кардано): Формулы Кардано и Виета требуют применения специальных функций, и в том случае, когда требуется провести большую серию вычислений корней кубического уравнения с не слишком сильно меняющимися коэффициентами, более быстрым алгоритмом является использование метода Ньютона или других итерационных методов (с нахождением начального приближения по формулам Кардано-Виета). Решение кубических уравнений на сиМодуль состоит из двух файлов, poly34.h, poly34.cpp. poly34.h — заголовочный файл Уравнения степени 3Линейные и квадратные уравнения с действительными коэффициентами решаются просто. Для решения кубических уравнений можно взять триногометрическую формулу Виета, код программы занимает около двух десятков строк. Корни уравнения x 3 + ax 2 + bx + c = 0 находятся с помощью функции Здесь x должен быть маccивом длины 3. В случае трех действительных корней функция возвращает число 3, сами корни возвращаются в x[0],x[1],x[2]. Замечание 1. Корни не обязательно упорядочены! Если функция возвращает 1, то x[0] — действительный корень и x[1]±i*x[2] — пара комплексно сопряженных. Замечание 2. Из-за погрешностей округления пара комплексно сопряженных корней с очень малой мнимой частью иногда может оказаться действительным корнем кратности 2. Например, для уравнения x 3 — 5x 2 + 8x — 4 = 0 с корнями 1,2,2 получаются корни 1.0, 2.0±i*9.6e-17. Если мнимая часть корня по модулю не превышает 1e-14, то функция SolveP3 сама заменяет такую пару на один действительный двукратный корень, но пользователь должен все равно иметь в виду возможность такой ситуации. Уравнения степени 4Для решения уравнений 4-й степени лучше взять решение Декарта — Эйлера. Корни уравнения x 4 + ax 3 + bx 2 + cx + d = 0 находятся с помощью функции Здесь x должен быть маccивом длины 4. В случае 4-х действительных корней функция возвращает число 4, сами корни возвращаются в x[0],x[1],x[2],x[3]. В случае 2-х действительных и пары комплексно сопряженных корней функция возвращает число 2, x[0],x[1] — действительные корни и x[2]±i*x[3] — пара комплексно сопряженных. Если уравнение имеет две пары пары комплексно сопряженных корней, то функция возвращает 0, x[0]±i*x[1] и x[2]±i*x[3] — сами корни. Уравнения степени 5Все корни уравнения 5-й степени f(x) = x 5 + ax 4 + bx 3 + cx 2 + dx + e = 0 не превосходят по модулю величины brd = 1 + max( |a|, |b|, |c|, |d|, |e| ). Уравнение 5-й степени всегда имеет по крайней мере один действительный корень. Для его нахождения, начиная с интервала [-brd,brd] сделаем 6 «делений отрезка пополам». После этого уточним корень методом Ньютона. Найдя один действительный корень x0, поделим на него исходный многочлен f(x) и найдем корни полученного многочлена 4-й степени. Корни многочлена f(x) находятся с помощью функции Здесь x должен быть маccивом длины 5. В случае 5 действительных корней функция возвращает число 5, сами корни возвращаются в x[0],x[1],x[2],x[3],x[4]. В случае 3-х действительных и пары комплексно сопряженных корней функция возвращает число 3, x[0],x[1],x[2] — действительные корни и x[3]±i*x[4] — пара комплексно сопряженных. Если уравнение имеет две пары пары комплексно сопряженных корней, то функция возвращает 1, x[0] — действительный корень и x[1]±i*x[2] , x[3]±i*x[4] — комплексные корни. Вспомогательные функцииРешение кубических уравнений производится в одной-единственной функции SolveP3. Для решения уравнений 4-й степени используются три вспомогательных функции: Первая служит для извлечения квадратного корня из комплексного числа: a+i*s = sqrt(x+i*y). Вторая — для решения биквадратного уравнения, третья — для решения неполного уравнения. Для решения уравнений 5-й степени используются функции: Полное решение кубического уравнения (формула Кардано)Необходимо решить кубическое уравнение с действительными коэффициентами: ax 3 + bx 2 + cx + d = 0 . По основной теореме алгебры оно имеет три корня (4 различных типа). Формула была украдена у Тартальи и опубликована Джероламо Кардано (тем самым изобретателем карданного вала) в книге «Великое искусство» в 1545 году. Описание алгоритма доступно в Интернете, однако программная реализация имеет некоторые нюансы, связанные с необходимостью анализа исходных данных. Вот что получилось: Входными параметрами метода являются коэффициенты a, b, c, d; по ссылке возвращается тип корней (tip=1,2,3,4) и их значения (p1,p2,p3): Для типа 1 (tip=1) имеется один действительный и два комплексных корня: x1=p1; x2=p2+i*p3; x3=p2-i*p3, где i — мнимая единица. Для тестирования метода используйте следующую программу: Минимальный набор тестов: источники: http://math.ivanovo.ac.ru/dalgebra/Khashin/cutil/poly34.html http://c-sharp.pro/%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D0%B5-%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5-%D0%BA%D1%83%D0%B1%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8/ |