Найдите все вещественные корни уравнения

Алгоритм расчёта вещественных корней полиномов

Основополагающая идея этого алгоритма очень проста и может быть изложена двумя предложениями. Вещественный корень полинома всегда находится на участке монотонного изменения полинома, т.е. между корнями производной полинома. Но производная полинома — это тоже полином, однако, меньшей степени и, найдя его вещественные корни, надо искать корни исходного полинома между корнями производной методом деления пополам.

А теперь по порядку.

Проблема нахождения корней алгебраических полиномов известна давно, по крайней мере со средневековья. В школе учат решать квадратные уравнения. В википедии можно найти формулы Кардано для решения кубических уравнений и описание метода Феррари для решения в радикалах уравнения четвёртой степени. Там же описан метод Лобачевского для решения алгебраических уравнений произвольной степени. Суть метода Лобачевского вкратце сводится к следующему.

Нетрудно, имея некоторый исходный полином, построить полином2, имеющий те же по модулю корни, что и исходный полином, но с противоположным знаком. Перемножая исходный полином и полином2, получаем полином, корни которого равны квадратам корней исходного полинома.

Это преобразование (квадрирование) полезно повторить несколько раз. В результате, если корни исходного полинома не были равны друг другу, их многократно квадрированные значения оказываются далеко разнесёнными по величине, а их приближенные значения очень просто выражаются через коэффициенты соответствующего квадрированного полинома.

В частности, если коэффициент при старшей степени аргумента полинома равен единице, то следующий по старшинству коэффициент равен (с обратным знаком) сумме корней уравнения, а поскольку значения этих корней сильно разнесены, то приближенно можно считать эту сумму равной наибольшему по модулю корню.

Для конкретности сообщим, что для полинома 4-й степени с корнями 1, 2, 3, 4 метод Лобачевского уже после четвёртого квадрирования даёт правильные до второго знака после запятой значения корней. При этом для представления коэффициентов полиномов достаточно формата long double.

Бесспорно, этот метод является ценным инструментом в руках исследователя, наделённого интеллектом. Однако, его программирование для современной вычислительной техники вызывает серьёзные затруднения при необходимости строгой гарантии достоверности результата при всевозможных особых случаях расположения корней.

Теперь я начну описывать иной метод. В общедоступной печати упоминание о нём начинается с работы [1]. Какие-либо независимые публикации о применении такого метода мне неизвестны. Этот алгоритм сводится к последовательному исследованию интервалов монотонного изменения исходного полинома. Если на границах этого интервала монотонности значения полинома имеют разные знаки, то запускается процедура деления отрезка пополам для расчёта точного значения очередного корня. Границами интервалов монотонности являются точки, в которых значение производной полинома обращается в нуль, т.е. это корни производного полинома. Производный полином имеет степень на единицу меньшую, чем исходный полином, и процесс расчёта коэффициентов производных полиномов следует продолжить до полинома первой степени, корень которого находится непосредственно, без привлечения процедуры деления отрезка пополам. В результате этого шага получим два интервала монотонного изменения для производного полинома второй степени.

Теперь можно найти два вещественных корня производного полинома второй степени (если они существуют) и далее по лестнице из производных полиномов подниматься до корней исходного полинома. Остаётся пояснить, как технически реализуются границы «плюс, минус бесконечность» интервалов монотонности исходного и производных полиномов.

Нормируем полином так, чтобы коэффициент при старшей степени аргумента стал равным единице. Пусть M — наибольшее по модулю значение среди его остальных коэффициентов. Тогда значение полинома больше единицы для всех значений аргумента, больших, чем M+1.

Для доказательства рассмотрим расчёт полинома p(x)=x^n+k[n-1]*x^(n-1)+. +k[1]*x+k[0] по схеме Горнера.

На первом шаге вычисляется p[1]=k[n-1]+x и очевидно, что p[1]>1.
На втором шаге вычисляется p[2]=k[n-2]+x*p[1] и вновь очевидно, что p[2]>1.
Аналогичное имеет место на последующих шагах.
На последнем шаге вычисляется p(x)=k[0]+x*p[n-1] и окончательно получим p(x)>1.

Таким образом, если нужно определить знак полинома при бесконечном значении аргумента, следует взять аргумент равным M+1.

Прилагаемый текст соответствующей программы вполне заменяет занудное изложение отдельных технических подробностей описанного тут алгоритма.

Прокомментирую, наконец, не вполне очевидную особенность реализации алгоритма деления отрезка пополам.

Пробная точка pt, расположенная посередине между текущими концами ng и vg отрезка, вычисляется оператором pt=0.5*(ng+vg); а цикл делений пополам прерывается оператором if(pt =vg)break;.

В силу конечной точности представления вещественных чисел в машине рано или поздно наступает состояние, при котором операция деления пополам вместо нового числа даёт значение одной из исходных границ. Именно в этом состоянии следует прекратить цикл делений пополам. Это состояние соответствует максимально достижимой точности результата.

Недавно мне удалось использовать этот алгоритм для решения задачи вычисления комплексного корня полинома, не имеющего вещественных корней. Но об этом я планирую рассказать на Хабре в следующей статье.

Ниже, как приложение, приведен полный текст файла polynomRealRoots.cpp, реализующего описанныйалгоритм.

Примите также текст заголовочного файла polynomRealRoots.h, позволяющего легко организовать ссылку на приведенный выше программный модуль.

Литература

1. Костин И.К. Семейство алгоритмов расчета интервалов прохождения космического аппарата над круговым наземным объектом с учетом продольной ошибки определения параметров орбиты

Вопросы радиоэлектроники, сер. РЛТ, 2004г., вып. 1

Эту ссылку можно найти в Яндексе поиском по закавыченной фразе «семейство алгоритмов расчета», но текст этой статьи в электронном виде, кажется, недоступен. Поэтому приведу здесь цитату из двух предложений этой статьи:

Вещественный корень полинома всегда находится на участке монотонного изменения полинома, т.е. между корнями производной полинома.

Но производная полинома — это тоже полином, однако, меньшей степени и, найдя его вещественные корни, надо искать корни исходного полинома между корнями производной методом деления пополам.

Решения кубических уравнений с вещественными коэффициентами. Универсальные методы. Дискриминант кубического уравнения. Формула Виета для кубического уравнения.

Решения кубических уравнений с вещественными коэффициентами. Универсальные методы. Дискриминант кубического уравнения. Формула Виета для кубического уравнения.

Кубическим уравнением называется уравнение вида

• ax 3 + bx 2 + cx +d = 0 , (1)
• где a, b,c ,d — постоянные коэффициенты, а х — переменная.

Мы рассмотрим случай, когда коэффициенты являются веществеными числами.

Корни кубического уравнения. Нахождение корней (решение) кубического уравнения.

Число х называется корнем кубического уравнения (1), если при его подстановке уравнение (1) обращается в верное равенство.

Кубическое уравнение имеет не более трех корней (над комплексным полем всегда три корня, с учетом кратности) . И всегда имеет хотя бы 1 (вещественный) корень. Все возможные случаи состава корней легко определить с помощью знака дискриминанта кубического уравнения, т.е.:

Δ= -4b 3 d + b 2 c 2 — 4ac 3 + 18abcd — 27a 2 d 2 (Да, это дискриминант кубического уравнения)

Итак, возможны только 3 следующих случая:

• Δ > 0 — тогда уравнение имеет 3 различных корня. (Для продвинутых — три различных вещественных корня)
• Δ 3 + py + q = 0 (2)

К такому виду можно привести любое кубическое уравнение вида (1) с помощью следующей замены:

• x= y — b/3a (3)
• p= — b 2 /3a 2 + c/a
• q= 2b 3 /27a 3 — bc/3a 2 + d/a

Итак, приступим к вычислению корней. Найдем следующие величины:

Дискриминант уравнения (2) в этом случае равен

Дискриминант исходного уравнения (1) будет иметь тот же знак , что и вышеуказанный дискриминант. Корни уравнения (2) выражаются следующим образом:

Соответственно, если Q>0, то уравнения (2) и (1) будут иметь лишь 1 (вещественный) корень, y₁. Подставим его в (3) и найдем х для уравнения (1). (если вас интересуют также мнимые корни, то просто вычислите еще и y₂, y₃ и подставьте их в (3).

Если Q 3 + ax 2 + bx +c = 0 (4)

Очевидно, любое уравнение вида (1) можно привести к виду (4), просто поделив его на коэффициент а.

Итак, алгоритм применения этой формулы:

3. a) Если S>0, то вычисляем

И наше уравнение имеет 3 корня (вещественных):

Тогда единственный корень (вещественный): x₁= -2sgn(R)*|Q| 1/2 *ch(φ) — a/3

Для тех, кого интересуют также и мнимые корни:

• ch(x)=(e x +e -x )/2
• Arch(x) = ln(x + (x 2 -1) 1/2 )
• sh(x)=(e x -e -x )/2
• sgn(x) — знак х

в) Если S=0,то уравнение имеет меньше трех различных решений:

Консультации и техническая
поддержка сайта: Zavarka Team

Решение кубических уравнений

Кубическое уравнение, содержащее коэффициенты с действительным корнем, остальные два считаются комплексно-сопряженной парой. Будут рассмотрены уравнения с двучленами и возвратные, а также с поиском рациональных корней. Вся информация будет подкреплена примерами.

Решение двучленного кубического уравнения вида A x 3 + B = 0

Кубическое уравнение, содержащее двучлен, имеет вид A x 3 + B = 0 . Его необходимо приводить к x 3 + B A = 0 с помощью деления на А , отличного от нуля. После чего можно применять формулу сокращенного умножения суммы кубов. Получаем, что

x 3 + B A = 0 x + B A 3 x 2 — B A 3 x + B A 2 3 = 0

Результат первой скобки примет вид x = — B A 3 , а квадратный трехчлен — x 2 — B A 3 x + B A 2 3 , причем только с комплексными корнями.

Найти корни кубического уравнения 2 x 3 — 3 = 0 .

Решение

Необходимо найти х из уравнения. Запишем:

2 x 3 — 3 = 0 x 3 — 3 2 = 0

Необходимо применить формулу сокращенного умножения. Тогда получим, что

x 3 — 3 2 = 0 x — 3 3 2 6 x 2 + 3 3 2 6 x + 9 2 3 = 0

Раскроем первую скобку и получим x = 3 3 2 6 . Вторая скобка не имеет действительных корней, потому как дискриминант меньше нуля.

Ответ: x = 3 3 2 6 .

Решение возвратного кубического уравнения вида A x 3 + B x 2 + B x + A = 0

Вид квадратного уравнения — A x 3 + B x 2 + B x + A = 0 , где значения А и В являются коэффициентами. Необходимо произвести группировку. Получим, что

A x 3 + B x 2 + B x + A = A x 3 + 1 + B x 2 + x = = A x + 1 x 2 — x + 1 + B x x + 1 = x + 1 A x 2 + x B — A + A

Корень уравнения равен х = — 1 , тогда для получения корней квадратного трехчлена A x 2 + x B — A + A необходимо задействовать через нахождение дискриминанта.

Решить уравнение вида 5 x 3 — 8 x 2 — 8 x + 5 = 0 .

Решение

Уравнение является возвратным. Необходимо произвести группировку. Получим, что

5 x 3 — 8 x 2 — 8 x + 5 = 5 x 3 + 1 — 8 x 2 + x = = 5 x + 1 x 2 — x + 1 — 8 x x + 1 = x + 1 5 x 2 — 5 x + 5 — 8 x = = x + 1 5 x 2 — 13 x + 5 = 0

Если х = — 1 является корнем уравнения, тогда необходимо найти корни заданного трехчлена 5 x 2 — 13 x + 5 :

5 x 2 — 13 x + 5 = 0 D = ( — 13 ) 2 — 4 · 5 · 5 = 69 x 1 = 13 + 69 2 · 5 = 13 10 + 69 10 x 2 = 13 — 69 2 · 5 = 13 10 — 69 10

Ответ:

x 1 = 13 10 + 69 10 x 2 = 13 10 — 69 10 x 3 = — 1

Решение кубических уравнений с рациональными корнями

Если х = 0 , то он является корнем уравнения вида A x 3 + B x 2 + C x + D = 0 . При свободном члене D = 0 уравнение принимает вид A x 3 + B x 2 + C x = 0 . При вынесении х за скобки получим, что уравнение изменится. При решении через дискриминант или Виета оно примет вид x A x 2 + B x + C = 0 .

Найти корни заданного уравнения 3 x 3 + 4 x 2 + 2 x = 0 .

Решение

3 x 3 + 4 x 2 + 2 x = 0 x 3 x 2 + 4 x + 2 = 0

Х = 0 – это корень уравнения. Следует найти корни квадратного трехчлена вида 3 x 2 + 4 x + 2 . Для этого необходимо приравнять к нулю и продолжить решение при помощи дискриминанта. Получим, что

D = 4 2 — 4 · 3 · 2 = — 8 . Так как его значение отрицательное, то корней трехчлена нет.

Ответ: х = 0 .

Когда коэффициенты уравнения A x 3 + B x 2 + C x + D = 0 целые, то в ответе можно получить иррациональные корни. Если A ≠ 1 , тогда при умножении на A 2 обеих частей уравнения проводится замена переменных, то есть у = А х :

A x 3 + B x 2 + C x + D = 0 A 3 · x 3 + B · A 2 · x 2 + C · A · A · x + D · A 2 = 0 y = A · x ⇒ y 3 + B · y 2 + C · A · y + D · A 2

Приходим к виду кубического уравнения. Корни могут быть целыми или рациональными. Чтобы получить тождественное равенство, необходимо произвести подстановку делителей в полученное уравнение. Тогда полученный y 1 будет являться корнем. Значит и корнем исходного уравнения вида x 1 = y 1 A . Необходимо произвести деление многочлена A x 3 + B x 2 + C x + D на x — x 1 . Тогда сможем найти корни квадратного трехчлена.

Найти корни заданного уравнения 2 x 3 — 11 x 2 + 12 x + 9 = 0 .

Решение

Необходимо произвести преобразование с помощью умножения на 2 2 обеих частей, причем с заменой переменной типа у = 2 х . Получаем, что

2 x 3 — 11 x 2 + 12 x + 9 = 0 2 3 x 3 — 11 · 2 2 x 2 + 24 · 2 x + 36 = 0 y = 2 x ⇒ y 3 — 11 y 2 + 24 y + 36 = 0

Свободный член равняется 36 , тогда необходимо зафиксировать все его делители:

± 1 , ± 2 , ± 3 , ± 4 , ± 6 , ± 9 , ± 12 , ± 36

Необходимо произвести подстановку y 3 — 11 y 2 + 24 y + 36 = 0 , чтобы получить тождество вида

1 3 — 11 · 1 2 + 24 · 1 + 36 = 50 ≠ 0 ( — 1 ) 3 — 11 · ( — 1 ) 2 + 24 · ( — 1 ) + 36 = 0

Отсюда видим, что у = — 1 – это корень. Значит, x = y 2 = — 1 2 .

Далее следует деление 2 x 3 — 11 x 2 + 12 x + 9 на x + 1 2 при помощи схемы Горнера:

2 x 3 — 11 x 2 + 12 x + 9 = x + 1 2 2 x 2 — 12 x + 18 = = 2 x + 1 2 x 2 — 6 x + 9

После чего необходимо найти корни квадратного уравнения вида x 2 — 6 x + 9 . Имеем, что уравнение следует привести к виду x 2 — 6 x + 9 = x — 3 2 , где х = 3 будет его корнем.

Ответ: x 1 = — 1 2 , x 2 , 3 = 3 .

Алгоритм можно применять для возвратных уравнений. Видно, что — 1 – это его корень, значит, левая часть может быть поделена на х + 1 . Только тогда можно будет найти корни квадратного трехчлена. При отсутствии рациональных корней применяются другие способы решения для разложения многочлена на множители.

Решение кубических уравнений по формуле Кардано

Нахождение кубических корней возможно при помощи формулы Кардано. При A 0 x 3 + A 1 x 2 + A 2 x + A 3 = 0 необходимо найти B 1 = A 1 A 0 , B 2 = A 2 A 0 , B 3 = A 3 A 0 .

После чего p = — B 1 2 3 + B 2 и q = 2 B 1 3 27 — B 1 B 2 3 + B 3 .

Полученные p и q в формулу Кардано. Получим, что

y = — q 2 + q 2 4 + p 3 27 3 + — q 2 — q 2 4 + p 3 27 3

Подбор кубических корней должен удовлетворять на выходе значению — p 3 . Тогда корни исходного уравнения x = y — B 1 3 . Рассмотрим решение предыдущего примера, используя формулу Кардано.

Найти корни заданного уравнения 2 x 3 — 11 x 2 + 12 x + 9 = 0 .

Решение

Видно, что A 0 = 2 , A 1 = — 11 , A 2 = 12 , A 3 = 9 .

Необходимо найти B 1 = A 1 A 0 = — 11 2 , B 2 = A 2 A 0 = 12 2 = 6 , B 3 = A 3 A 0 = 9 2 .

Отсюда следует, что

p = — B 1 2 3 + B 2 = — — 11 2 2 3 + 6 = — 121 12 + 6 = — 49 12 q = 2 B 1 3 27 — B 1 B 2 3 + B 3 = 2 · — 11 2 3 27 — — 11 2 · 6 3 + 9 2 = 343 108

Производим подстановку в формулу Кордано и получим

y = — q 2 + q 2 4 + p 3 27 3 + — q 2 — — q 2 4 + p 3 27 3 = = — 343 216 + 343 2 4 · 108 2 — 49 3 27 · 12 3 3 + — 343 216 — 343 2 4 · 108 2 — 49 3 27 · 12 3 3 = = — 343 216 3 + — 343 216 3

— 343 216 3 имеет три значения. Рассмотрим их ниже.

— 343 216 3 = 7 6 cos π + 2 π · k 3 + i · sin π + 2 π · k 3 , k = 0 , 1 , 2

Если k = 0 , тогда — 343 216 3 = 7 6 cos π 3 + i · sin π 3 = 7 6 1 2 + i · 3 2

Если k = 1 , тогда — 343 216 3 = 7 6 cosπ + i · sinπ = — 7 6

Если k = 2 , тогда — 343 216 3 = 7 6 cos 5 π 3 + i · sin 5 π 3 = 7 6 1 2 — i · 3 2

Необходимо произвести разбиение по парам, тогда получим — p 3 = 49 36 .

Тогда получим пары: 7 6 1 2 + i · 3 2 и 7 6 1 2 — i · 3 2 , — 7 6 и — 7 6 , 7 6 1 2 — i · 3 2 и 7 6 1 2 + i · 3 2 .

Преобразуем при помощи формулы Кордано:

y 1 = — 343 216 3 + — 343 216 3 = = 7 6 1 2 + i · 3 2 + 7 6 1 2 — i · 3 2 = 7 6 1 4 + 3 4 = 7 6 y 2 = — 343 216 3 + — 343 216 3 = — 7 6 + — 7 6 = — 14 6 y 3 = — 343 216 3 + — 343 216 3 = = 7 6 1 2 — i · 3 2 + 7 6 1 2 + i · 3 2 = 7 6 1 4 + 3 4 = 7 6

x 1 = y 1 — B 1 3 = 7 6 + 11 6 = 3 x 2 = y 2 — B 1 3 = — 14 6 + 11 6 = — 1 2 x 3 = y 3 — B 1 3 = 7 6 + 11 6 = 3

Ответ: x 1 = — 1 2 , x 2 , 3 = 3

При решении кубических уравнений можно встретить сведение к решению уравнений 4 степени методом Феррари.