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

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

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

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

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

Нетрудно, имея некоторый исходный полином, построить полином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

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

* Entering and Manipulating Equations: The lhs and rhs commands *

Напомним, что уравнению, точно так же как и выражению, можно присвоить имя. В следующей командной строке мы введём уравнение и присвоим ему имя » eq1 » :

Мы можем вывести на экран левую и правую части уравнения по-отдельности при помощи команд lhs и rhs :

Воспользуемся командами lhs и rhs для того, чтобы привести уравнение к стандартному виду, в котором все члены собраны слева, а справа остался только 0:

04. 02 Нахождение точных корней. Команда solve

* Finding Exact Solutions: The solve command *

Рассмотрим вначале рациональные уравнения. Известно, что существуют алгоритмы определения точных корней рациональных корней вплоть до 4-го порядка включительно. В Maple-команду solve и заложены эти алгоритмы.

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

Обратите внимание: в команде мы указываем, относительно какой переменной следует решать уравнение. Хотя в нашем конкретном случае это и не обязательно:

Maple нашел все 3 действительных корня и вывел их ( в неупорядоченном виде ).

Иногда очень важно выбрать конкретный корень, чтобы потом использовать в дальнейших преобразованиях именно его. Для этого заранее следует присвоить имя результату исполнения команды solve . Назовём его X . Тогда конструкция X[1] будет соответствовать первому корню из списка (подчеркнем: это не обязательно меньший корень! ), X[2] — второму корню, и т.д. ( Скобки — квадратные! ):

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

Ещё раз подчеркнём: практика показывает, что уравнению целесообразно присвоить имя. Традиционно в Maple такое имя начинается с букв eq :

(Не путать оператор присваивания » := » со знаком равенства » = » !)

Теперь решим уравнение при помощи команды solve . Множеству корней присвоим имя X :

Для убедительности проверим, нет ли среди найденных корней посторонних. Проверку выполним непосредственной подстановкой

Разумеется, частенько «точные» решения довольно громоздки, если не сказать иначе. Например, это касается уравнения :

Теперь Вам понятно, о чем речь? Для себя заметьте, что мнимая единица в Maple обозначается посредством прописной буквы I . Разумеется, в таких случаях не грех найти приближенные значения корней. Имея на руках точное решение, Вы и сами сообразите, как это сделать:

В подобных ситуациях хорошей альтернативой команде solve является fsolve , особенности которой будут рассмотрены в следующем параграфе.

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

Решим уравнение :

Иногда (а в тригонометрии — всегда ) Maple, по умолчанию , не выводит всё множество корней:

Но безвыходных ситуаций не бывает! Взяв за основу полученный результат, воспользуйтесь своими знаниями тригонометрических уравнений и запишите полное решение ( как ? ).

Упражнение 4.1

Решить уравнение Разберитесь, сколько различных корней имеет уравнение. Как Maple поступает при наличии равных корней?

Совет : разложите на множители левую часть уравнения.

Корень х = 7 является двукратным, а потому у кубического уравнения только два различных корня. Разложение на множители левой части уравнения — тому подтверждение.

04. 03 Поиск приближенных корней. Команда fsolve

* Finding Approximate Solutions: The fsolve command *

Для приближенного решения уравнений используется Maple-команда fsolve . В случае рационального уравнения, fsolve выводит весь список действительных корней (см. Пример 01). Для трансцендентных уравнений эта команда, по умолчанию, выводит только один корень (см. Примеры 02 и 03).

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

Эти четыре корня и составляют исчерпывающее решение исходного рационального уравнения ( хотя и приближенное ).

Используя команду fsolve , найти хотя бы один действительный корень уравнения :

Maple и вывел только один корень. На этот раз Maple не стал «живописать». Как теперь убедиться в том, что других действительных корней нет? Следующий пример даёт такой инструментарий.

Получить все действительные корни уравнения и убедиться в этом.

Шаг первый ( Основная идея ) : найдём графическое решение уравнения. Для этого построим график функции, стоящей в левой части уравнения. Абсциссы точек пересечения этого графика с осью Ох и будут искомыми корнями.

Т.к. мы умело подобрали диапазоны изменений абсцисс и ординат точек графика, то легко обнаружим 4 точки пересечения линии с осью Ох. Одна из них соответствует корню, найденному в Примере 02 ( какая именно? ).

Второй корень очевиден: х = 0. А как поточнее найти остальные?

Шаг второй ( Уточнение ) : применим команду fsolve более «зряче». В Maple предусмотрена возможность указания промежутка, на котором отыскиваются корни. В частности, для определения отрицательного корня нашего уравнения, укажем, что поиски следует вести в «районе» [-1;-0.2]. Об этом красноречиво свидетельствует графическое решение.

Оставшиеся корни явно принадлежат промежуткам [1;2] и [4;5] . Расскажем об этом команде fsolve :

Ну а что произойдёт, если мы подсунем Maple «пустой участок»? Например, отрезок [2;4] для нашего уравнения. Там графического решения явно нет:

Maple выдаёт название команды, само уравнение, имя аргумента и отрезок. Т.е. ничего нового. Мол: «Ищите корни сами, а я не нашел».

Шаг третий ( Дополнительный анализ ) : Как теперь удостовериться в том, что найдены все корни , а не только в видимой области графического решения? Для этого следует расширить интервал поисков:

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

Попробуем в других местах: справа и слева от области найденных корней.

И здесь ни одного дополнительного корня! Поняв, что с влиянием показательной части уравнения всё ясно, делаем окончательные выводы.

Исчерпывающее решение уравнения состоит из четырёх корней: -.8251554597 , 0 , 1.545007279 , 4.567036837 .

Применим команду fsolve для приближенного решения трансцендентного уравнения .

Как и в предыдущем случае, найдём вначале качественное графическое решение. Для этого ещё нужно угадать, как разбросать по обеим частям уравнения его члены. Но графические возможности Maple настолько великолепны, что почти всегда можно собирать все члены уравнения с одной стороны.

Рассмотрим уравнение, равносильное данному: . Абсциссы точек пересечения графика функции, стоящей в левой части уравнения, с осью Ох и будут искомыми корнями.

График указывает область поисков корней: промежуток [1;2]. Настаёт черёд команды fsolve :

Корень найден. Но, очевидно, он — не единственный. Расширьте область поисков и ещё раз примените команду fsolve для отыскания второго корня.

Упражнение 4.2

Найти все действительные корни уравнения , начав с графического решения.

Построим график левой части уравнения:

В результате находим корни уравнения в первом приближении: -2 ; -1.5 ; 0 . Применим теперь команду fsolve без указания диапазона поиска ( оценим возможности Maple ):

С удовлетворением отмечаем, что Maple выводит все три корня (Не будем забывать, что решали рациональное уравнение.)

Упражнение 4.3

Найти все корни уравнения . Воспользуйтесь графическим решением. Проверьте каждый корень непосредственной подстановкой.

Приведём уравнение к стандартному (для этого раздела) виду:

Теперь построим график левой части уравнения:

По всей видимости, существует два корня. Один примерно равен -2, а другой, похоже, 2.

Применим команду fsolve , ограничив диапазон поиска:

Непосредственной подстановкой проверим корни:

Обратите внимание: в обоих случаях истинного равенства нет . С учётом ошибок при округлении, разумное расхождение вполне допустимо .

Убедитесь в отсутствии других корней. Ответ обоснуйте.

Упражнение 4.4

Графики функций и дважды пересекаются на отрезке [-5;5].

а). Постройте в одной системе координат графики обеих функций и при помощи мыши найдите координаты точек пересечения.

b). Составьте уравнение, корнями которого являются абсциссы точек пересечения графиков.

c). Используйте команду fsolve для решения этого уравнения.

d). Используйте результаты из пункта с) для оценки ординат точек пересечения графиков.

e). У Вас не создалось впечатление, что линии могут пересекаться и в третьей точке с координатами (1;9)? Используйте fsolve и графические возможности Maple, чтобы убедиться в противном.