Уравнения 3-й степени

Среди каких чисел искать корни ? Помнится делители первого числа на делители последнего. И как решать их с помощью схем Горнера ?

Решается всегда (но не всегда хорошо!) с помощью формулы Кардано (кажется).

Сообщение отредактировано: @Hgpeu - 19.04.03, 15:01

среди делителей только рациональные корни.. а иррациональные по формулам кардано все можно найти:)

пусть имеется уравнение -
x^3+a1*x^2+a2*x+a3=0
пусть y=x+a1/3
тогда уравнение примет вид:
y^3+p*y+q=0
пусть y=u+v
тогда:
u^3+v^3+3*u*v*(u+v)+p*(u+v)+q=0
u^3+v^3+(u+v)*(3*u*v-p)+q=0
пусть u*v=-p/3
тогда имеем:
|u^3+v^3=-q
|u*v=-p/3
далее -
|u^3+v^3=-q
|u^3*v^3=-(p^3)/27
рассмотрим уравнение z^2+q*z-(p^3)/27=0
тогда: u^3=-q/2+sqrt((q^2)/4+(p^3)/27)), извлекаем кубический корень и получаем u, но v=-p/(3*u)
вспомним старые обозначения : y=u+v; подставим и получим ровно 3 значения для y..
замечание\запарка - все операции извлечения корня должны проводиться в поле комплексных чисел, т.е. допустим имеется уравнение - a^3=b
a=r*(cosA+i*sinA), b=R*(cosB+i*sinB)
r^3*(cosA+i*sinA)^3=R*(cosB+i*sinB)
по формуле Муавра:
r^3*cos(3A)+i*sin(3A)=R*(cosB+i*sinB)
=>
1) r^3=R
2) 3A=B+2*pi*k, где k=0,1,2
в итоге получаем:
a=корень_третьей_степени_из_R*(cos((B+2*pi*k)/3))+i*sin((B+2*pi*k)/3))), k=0,1,2
т.е. получили ровно 3 комплесных корня
ещё одно замечание:
b=R*(cosB+i*sinB).. R=?
мы знаем, что b=Re(b)+i*Im(b)
R=sqrt(Re(b)^2+Im(b)^2)
cosB=Re(b)/R, sinB=Im(b)/R..

вот :

2DEiL:
У меня шок

Господи, помилуй от такого...

Цитата kl, 19.04.03, 02:37:19

Господи, помилуй от такого...

От тех формул, что выше

да ладно, у каждого свои причуды :

Что за формула Кордана такая ?
To  8)DEiL: Спасибо за способ   Если комп считает, то всё просто. Но мне надо самому, а уравнений штук десять, среди них могут быть уравнения 5-й, 7-й степени, и времени час Есть способ деления углом, но он по-моему не все корни может найти.
Так может кто нить рассказать про схемы Горнера ?

http://vadim-soft.narod.ru/math/theory/kardano_formul.htm
http://algolist.manual.ru/maths/findroot/cubic.php
http://ega-math.narod.ru/Quant/Belaga.htm

2CHIH.net -> как выяснилось, то, что я тебе расписал, и была формула Кордана + её вывод  :D

кстати
если есть уравнение степени выше 4-й (корни 1-й, 2, 3, 4 можно найти по формулам), то:
1. делим на старший коэффициент, чтобы оно стало привидённым
2. выписываем где-нибудь все делители младшего коэффициента (и отрицательные тоже)
3. пользуем схему Горнера либо подставляем "корни" ручками и, если какой-либо из них подходит - делим столбиком на (x-корень)
4. пишем ответ :-)

схема Горнера:
в ряд выписываем все коэффициенты при степенях, начиная с наивысшей.
если в многочлене какой-либо степени нету, то пишем 0
строкой ниже, и чуть левее, выписываем претендента на корень
далее:
под первым коэффициентом из верхней строки пишем этот же коэффициент (должна быть единица, т.к. уравнение привидённое)
далее домножаем корень на этот коэффициент и прибавляем к полученному результату следующий коэф-ент. записываем. полученное число записываем. домножаем на корень и прибавляем следующий коэф-ент. в итоге, если получился 0, то претендент и правда является корнем!
а полученная строка из чисел - коэффициенты (начиная со старшего) уравнения степенью ниже, который получается делением на (x-корень)
пример:
x^3-1=0
делители - +\- 1
коэфф-ты - 1  0  0  -1
схема Горнера:
1)
х=1
     1      0              0                  -1
+1| 1   1*1+0=1    1*1+0=1        1*1-1=0
=> х=1 - корень
получили уравнение:
x^2+x+1 = 0
2)
х=-1
     1      0              0                  -1
-1| 1   1*(-1)+0=-1 -1*-1+0=1  1*(-1)-1=-2
=>x=-1 не корень

Сообщение отредактировано: DEiL - 19.04.03, 17:44

Я как-то писал прогу, которая решает уравнения N-ой степени.
Идея такая:
считаем N-ую производную функции ((c*x^n)' = c*n*x^(n-1))
В конце концов получаем линейное уравнение, которое решить тривиально.
Получаем границу, справо от коророй есть кодин корень уравнения f '(n-1) (x) = 0 ((n-1)-я производная равно 0) и справа тоже.
Находим их (хоть методом деления отрезка пополам). Теперь у нас 2 границы (2 найденных корня) - x1 и x2. Соответсвенно, ищем на трех отрезках корни (от -бесконечности до x1, от x1 до x2 и от x2 до +бесконечности).
Так разворачиваем это дело n раз (т.е. доходим до исходного уравнения). Кстати, это можно делать рекурсивно, тогда проблем меньше будет  ;D

У меня такой метод работал до 15-й степени. Потом вылетал с Arifmetic Owerflow (слишком большие были коэффициенты при x)

Пару слов насчет сложности алгоритма:
вычисление производной функции - O(n)
вычисление n-й производной - O(n^2)
поиск корней производной - nlogn
итого - O(n^3*logn), что для n <= 100 вполне сносное время (меньше секунды при хорошей реализации)

PS: корни находит любые (естественно, действительные) с заданной точностью для метода деления отрезка потолам (или там чего круче)

Сообщение отредактировано: tserega - 20.04.03, 09:39

Ну спасибо ребят, помогли. Особенно спасибо DEiL'у за Горнера и Кордана  ;)
Только жаль, что после а не до олимпиады прочёл ответы  :) На олимпиаде надо было решить уравнение шестой степени, полученное из тригонометрического уравнения.
Я a^2 заменил на b и решил уравнение третьей степени, разложив его на множители.
Только при делении углом получил остаток, и плюнул на него (сократил). Так что наверное неправильно сделал номер. Зато как красиво, два листа вычислений  :D  

Хе, ни на какой олимпиаде и ни на каких вступительных экзаменах не требуют знание формулы вычислений корней уравнений 3 и 4-й степени. Даже если ты это знаешь и напишеш их, в большинстве случаев тебе не засчитают решение задачи.