Что значит вещественный корень

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

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

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

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

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

Читайте также:  Что за социальные выплаты 1300

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

Источник

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

Локализация корней полинома

Пример [Уилкинсон]. Вычислить корни полинома

Правило знаков Декарта

Теорема [Декарт]. Число положительных корней полинома

Доказательство ☞ ЗДЕСЬ.

С помощью преобразования корней полинома (см. пункт 1 ☞ ЗДЕСЬ ) можно доказать следствие:

Число отрицательных корней полинома

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

Система полиномов Штурма

Обобщенная система полиномов Штурма

Ганкелевы матрицы в теории локализации корней

Ответ. Три вещественных корня.

Имеет место соотношение

Пример. Определить число вещественных корней полинома

Формула Маркова

Устойчивость

Локализация собственных чисел матрицы

Теорема Гершгорина

Пример. Построить круги Гершгорина для матрицы

gershgorin2

Симметричные матрицы

Доказательство ☞ ЗДЕСЬ.

Совместность

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

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

Условие пункта b) теоремы можно проверить по теореме Эрмита-Сильвестра с использованием формулы Маркова.

Пример. Исследовать на совместность систему

Эту рекомендацию можно обобщить.

scriber

Статья не закончена!

Определение структуры множества решений

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

Задачи

Источники

[4]. Утешев А.Ю., Калинина Е.А. Лекции по высшей алгебре. Часть II. Учеб. пособие. СПб. «СОЛО». 2007. 279 c.

[6]. Markoff A. On the determination of the number of roots of an algebraic equation situated in a given domain. Мат. сборник. 1940. Т. 7(49), N 1, c. 3–6. Текст ☞ ЗДЕСЬ (pdf)

Источник

Извлечение корня из комплексного числа

Третий урок по комплексным числам. В этом уроке вы узнаете:

Читайте также:  Чем помазать присоску на стекло чтобы не отваливалась

Начнём с ключевого определения.

1. Определение комплексного корня

Итого три корня. Как и предполагалось.

Все эти корни считаются по следующей формуле.

2. Формула корней

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

\[z=\left| z \right|\cdot \left( \cos \varphi +i\sin \varphi \right)\]

По сути, эта теорема является обратной к формуле Муавра:

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

Запишем формулу корней в общем виде:

3. Геометрическая интерпретация

\[\begin z & =1\cdot \left( 0+i\cdot 1 \right)= \\ & =1\cdot \left( \cos \frac<\pi ><2>+i\sin \frac<\pi > <2>\right) \end\]

Формула комплексных корней:

\[\sqrt[3]=1\cdot \left( \cos \left( \frac<\pi ><6>+\frac<2\pi k> <3>\right)+i\sin \left( \frac<\pi ><6>+\frac<2\pi k> <3>\right) \right)\]

komplexnie korni 3 stepeni

Рассмотрим более сложный пример:

Сразу запишем формулу корней с выделением начального луча:

\[\sqrt[4]=\sqrt[8]<2>\cdot \left( \cos \left( \frac<\pi ><16>+\frac<\pi k> <2>\right)+i\sin \left( \frac<\pi ><16>+\frac<\pi k> <2>\right) \right)\]

komplexnie korni 4 stepeni

Ну и ещё один пример — вновь без промежуточных вычислений. Только формулировка задачи, формула корней и окончательный чертёж:

Формула корней с выделением начального луча:

\[\sqrt[6]=2\cdot \left( \cos \left( \frac<\pi ><6>+\frac<\pi k> <3>\right)+i\sin \left( \frac<\pi ><6>+\frac<\pi k> <3>\right) \right)\]

komplexnie korni 6 stepeni

4. Почему корней всегда ровно n

5. Выводы

Ключевые факты из урока.

Алгоритм нахождения корней состоит из двух шагов.

Шаг 1. Представить исходное число в тригонометрической форме:

\[z=\left| z \right|\cdot \left( \cos \varphi +i\sin \varphi \right)\]

Шаг 2. Воспользоваться формулой Муавра для вычисления корней:

Геометрическую интерпретацию можно использовать для быстрого «графического» извлечения корней. Но это требует практики и хорошего понимания, что именно и зачем вы делаете. Технология такого извлечения корней описана выше в разделе «Геометрическая интерпретация».

Всё. В следующем уроке начнём решать уравнения в комплексных числах.:)

Источник

Уравнение и его корни: определения, примеры

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

Понятие уравнения

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

Уравнением называется равенство с неизвестным числом, которое нужно найти.

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

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

Уравнение – это равенство, включающее в себя переменную, значение которой нужно вычислить.

В одном уравнении может быть не одна переменная, а две и более. Их называют соответственно уравнениями с двумя, тремя переменными и др. Запишем определение:

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

Корень уравнения

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

Нас больше интересуют именно те значения, с которыми переменная обратится в верное равенство. Они и называются корнями или решениями. Запишем определение.

Читайте также:  Что делать чтобы новорожденный покакал

Корнем уравнения называют такое значение переменной, которое обращает данное уравнение в верное равенство.

Корень также можно назвать решением, или наоборот – оба эти понятия означают одно и то же.

Сколько корней может иметь одно уравнение? Любое ли уравнение имеет корень? Ответим на эти вопросы.

Также бывают уравнения, имеющие несколько корней. У них может быть как конечное, так и бесконечно большое количество корней.

Так, в уравнении x − 2 = 4 есть только один корень – шесть, в x 2 = 9 два корня ­­– три и минус три, в x · ( x − 1 ) · ( x − 2 ) = 0 три корня – нуль, один и два, в уравнении x=x корней бесконечно много.

Когда у уравнения два, три корня или больше, то, как правило, говорят не о корнях, а о решениях уравнения. Сформулируем определение решения уравнения с несколькими переменными.

Решение уравнения с двумя, тремя и более переменными – это два, три и более значения переменных, которые обращают данное уравнение в верное числовое равенство.

Поясним определение на примерах.

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

Источник

Операторы управления

Аналитически функцию, представленную на рис. 3.10, можно записать так:

de3b88accf91a196488d09aebfa7e451

Составим словесный алгоритм решения этой задачи:

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

small3 11

Текст программы на языке Free Pascal будет иметь вид:

Эту программу можно ввести в текстовом редакторе Geany (или в текстовом редакторе Free Pascal) и запустить на выполнение.

Как показано на рис. 3.12, область ограничена линиями 7dc257a7d4c0b3723194bc6b3e864978и c55e251bf5bbbe164f621e9f41e8cb16. Значит, точка с координатами a2186702fd6a70070c9bcc8021454d90будет принадлежать этой области, если будут выполняться следующие условия: 6e5613210bcf882d1e77a4bf1a3cf377и f4ccedb52362396db4a41c3f8160f893. Иначе точка лежит за пределами области.

Блок-схема, описывающая алгоритм решения данной задачи, представлена на рис. 3.13.

small3 12

small3 13

Текст программы к задаче 3.2:

Исходные данные: вещественные числа 51718398f14c2c7248fa166b1c749400и 4a8a08f09d37b73795649038408b5f33— коэффициенты квадратного уравнения.

small3 14

Результаты работы программы: вещественные числа aa687da0086c1ea060a8838e24611319и 8732099f74d777a67257cb2f04ead3d8— корни квадратного уравнения — либо сообщение о том, что корней нет.

Вспомогательные переменные: вещественная переменная 8277e0910d750195b448797616e091ad, в которой будет храниться дискриминант квадратного уравнения.

Составим словесный алгоритм решения этой задачи.

Блок-схема, соответствующая этому описанию, представлена на рис. 3.14.

Текст программы, которая реализует решение квадратного уравнения:

Исходные данные: вещественные числа 51718398f14c2c7248fa166b1c749400и 4a8a08f09d37b73795649038408b5f33— коэффициенты квадратного уравнения.

Результаты работы программы: вещественные числа aa687da0086c1ea060a8838e24611319и 8732099f74d777a67257cb2f04ead3d8— действительные корни квадратного уравнения — либо aa687da0086c1ea060a8838e24611319и 8732099f74d777a67257cb2f04ead3d8— действительная и мнимая части комплексного числа.

Вспомогательные переменные: вещественная переменная 8277e0910d750195b448797616e091ad, в которой будет храниться дискриминант квадратного уравнения.

Можно выделить следующие этапы решения задачи:

feb8501f366eb4c006bf0198ac73786f

и вывод их на экран. При отрицательном дискриминанте выводится сообщение о том, что действительных корней нет, и вычисляются комплексные корни 4 Комплексные числа записываются в виде 3de90564c61daf602b582735803fed9c, где 0cc175b9c0f1b6a831c399e269772661— действительная часть комплексного числа, 92eb5ffee6ae2fec3ad71c777531578f— мнимая часть комплексного числа, 865c0c0b4ab0e063e5caa3387c1a8741— мнимая единица d4c2efeae4a3424da6bb388e41e87557.

small3 15

fb7e948eef447bb10e439a3beabfa128

Текст программы, реализующей поставленную задачу:

Кубическое уравнение имеет вид

41b58583d26df058d47dd31ffc643771 ( 3.1)

После деления на 0cc175b9c0f1b6a831c399e269772661уравнение (3.1) принимает канонический вид:

39fa4dbc9572a15de3d82ed6ec1ec3d5 ( 3.2)

где ed1601fb6b922b9087466372d4d1125c. В уравнении (3.2) сделаем замену e1d63e4f863ecd803e0cf39459ba3c52и получим приведённое уравнение:

f584e4a20dfd59c39d4aa75f28f98c3d ( 3.3)

93e58b8fe1aa0e622692d789b918522d

Число действительных корней приведённого уравнения (3.3) зависит от знака дискриминанта 3c09031beefae4b54002a8c334caaeedприведённого кубического уравнения (табл. 3.1).

Для решения биквадратного уравнения необходимо заменой b4497d4d3ca9c7496c62657779ffc6c9привести его к квадратному уравнению 0ff7fe658a9fb6c5ee28a8c67573e6daи решить это уравнение.

Опишем алгоритм решения этой задачи (рис. 3.17):

small3 17

Текст программы на языке Free Pascal с комментариями:

Источник

Adblock
detector