На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Уравнения 3-й степени
    Среди каких чисел искать корни ? Помнится делители первого числа на делители последнего. И как решать их с помощью схем Горнера ?
      Решается всегда (но не всегда хорошо!) с помощью формулы Кардано (кажется).
      Сообщение отредактировано: @Hgpeu -
        среди делителей только рациональные корни.. а иррациональные по формулам кардано все можно найти:)
          пусть имеется уравнение -
          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:
            :o :o :o У меня шок :o :o :o
              Господи, помилуй от такого...
                Цитата kl, 19.04.03, 02:37:19
                Господи, помилуй от такого...

                От тех формул, что выше :o
                  да ладно, у каждого свои причуды ::)
                    Что за формула Кордана такая ?
                    To  8)DEiL: Спасибо за способ   :D Если комп считает, то всё просто. Но мне надо самому, а уравнений штук десять, среди них могут быть уравнения 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 -
                            Я как-то писал прогу, которая решает уравнения 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 -
                              Ну спасибо ребят, помогли. Особенно спасибо DEiL'у за Горнера и Кордана  ;)
                              Только жаль, что после а не до олимпиады прочёл ответы  :) На олимпиаде надо было решить уравнение шестой степени, полученное из тригонометрического уравнения.
                              Я a^2 заменил на b и решил уравнение третьей степени, разложив его на множители.
                              Только при делении углом получил остаток, и плюнул на него (сократил). Так что наверное неправильно сделал номер. Зато как красиво, два листа вычислений  :D  
                                Хе, ни на какой олимпиаде и ни на каких вступительных экзаменах не требуют знание формулы вычислений корней уравнений 3 и 4-й степени. Даже если ты это знаешь и напишеш их, в большинстве случаев тебе не засчитают решение задачи.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0315 ]   [ 15 queries used ]   [ Generated: 21.05.24, 06:31 GMT ]