Здрасте!
Кто нибудь может подкинуть алгоритм нахождения корней полинома типа:
a0*x^0 + a1*x^1 + a2*x^2 + .... + aN*x^N = 0

Здравствуйте, Аноним, Вы писали:

Ищи итерационный метод Ньютона. Сейчас формулу непомню, а выводить голова пока не соображает. И книжки в pdf по численным дома. Пойщи книгу Самарского.

Здравствуйте, Аноним, Вы писали:

А>Здрасте!
А>Кто нибудь может подкинуть алгоритм нахождения корней полинома типа:
А>a0*x^0 + a1*x^1 + a2*x^2 + .... + aN*x^N = 0


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

Вроде какой-то Borland C++ под Дос

#include <iostream.h>
#include <math.h>
#include <conio.h>
#include <complex.h>

#define NMAX 20

typedef struct SPolinom
{
    complex  mas[NMAX];
    int pow;
}*PPolinom,TPolinom;

typedef struct SRoot
{
   complex  mas[NMAX];
   int num;
}*PRoot,TRoot;

complex FPol(TPolinom &p,complex &x)
{
    int i;
    complex tmp=complex(0,0);

    for(i=0;i<=p.pow;i++)
       tmp=tmp+pow(x,i)*p.mas[i];

    return tmp;
}


void FindAllRoot(TPolinom &pp,TRoot &r)
{
 int i,j;
 complex x1,x0;
 TPolinom defp,p;

 p=pp;
 r.num=p.pow;

 for(i=0;i<r.num;i++)
   {
    defp.pow=p.pow-1;

    for (j=0;j<p.pow;j++)
      defp.mas[j]=p.mas[j+1]*(j+1);

    x1=complex(1,1);

    do
    {
      x0=x1;

      x1=x0-FPol(p,x0)/FPol(defp,x0);
    }
    while (abs(FPol(p,x1))>1e-12);

    r.mas[i]=x1;

    for(j=p.pow-1;j>=0;j--) p.mas[j]=p.mas[j]+p.mas[j+1]*x1;
    for(j=0;j<p.pow;j++) p.mas[j]=p.mas[j+1];
    p.pow--;
   }
}

void main(void)
{
 int i=0;
 TPolinom p;
 TRoot r;

 p.pow=2;
 p.mas[0]=complex(-1,0);
 p.mas[1]=complex(0,0);
 p.mas[2]=complex(4,0);
 p.mas[3]=complex(1,0);
 p.mas[4]=complex(0,0);
 p.mas[5]=complex(0,0);
 p.mas[6]=complex(6,0);

 FindAllRoot(p,r);

 cout<<"\n Найдено"<<r.num<<" корней, у полинома "<<p.pow<<" степени.";

 for(i=0;i<r.num;i++) 
      cout<<"\nX["<<i+1<<"]/корень/ = "<<real(r.mas[i])<<" + i * "<<imag(r.mas[i]);
}

Здравствуйте, OlegO, Вы писали:

OO>Здравствуйте, Аноним, Вы писали:

А>>Здрасте!
А>>Кто нибудь может подкинуть алгоритм нахождения корней полинома типа:
А>>a0*x^0 + a1*x^1 + a2*x^2 + .... + aN*x^N = 0

OO>В детстве баловалася, идея перекинуть метод Ньютона на комплексные числа и находим все корни, даже комплексные:

А неужели только численно? Это же полином! Должны быть точные (хоть и громоздкие для рук) методы. Типа решения системы уравнений по Гауссу. Хотя я что-то не помню...

Здравствуйте, OlegO, Вы писали:

OO>В детстве баловалася, идея перекинуть метод Ньютона на комплексные числа и находим все корни, даже комплексные:

Слушай, а ты не пробовал повыбирать начальное приближение для последующих итераций метода Ньютона в разных точках комплексной плоскости? И раскрасить все точки по тому корню, к которому они "стекают"? Если нет, то я тебе завидую — у тебя впереди много интересного.

Если корня два, то всё чудесно — плоскость делится прямой пополам.
А если 3 — знак мерседеса? — ууупс — если кто не пробовал — проверьте

Здравствуйте, Pushkin, Вы писали:

P>А неужели только численно? Это же полином! Должны быть точные (хоть и громоздкие для рук) методы. Типа решения системы уравнений по Гауссу. Хотя я что-то не помню...

для степеней не выше 4.

Здравствуйте, Pushkin, Вы писали:

P>А неужели только численно? Это же полином! Должны быть точные (хоть и громоздкие для рук) методы. Типа решения системы уравнений по Гауссу. Хотя я что-то не помню...

Насколько я помню, точные методы заканчиваются на степени 5. А дальше возникает вопрос, как разложить многочлен степени N на произведение многочленов.

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

Вобщем надо книжки читать.

Здравствуйте, Pushkin, Вы писали:

P>Слушай, а ты не пробовал повыбирать начальное приближение для последующих итераций метода Ньютона в разных точках комплексной плоскости? И раскрасить все точки по тому корню, к которому они "стекают"? Если нет, то я тебе завидую — у тебя впереди много интересного.

P>Если корня два, то всё чудесно — плоскость делится прямой пополам.
P>А если 3 — знак мерседеса? — ууупс — если кто не пробовал — проверьте

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

Здравствуйте, OlegO, Вы писали:

OO>Насколько я помню, точные методы заканчиваются на степени 5. А дальше возникает вопрос, как разложить многочлен степени N на произведение многочленов.

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

Здравствуйте, OlegO, Вы писали:

OO>А идея у меня такая нашли корень, исключили его, понизив степень, ну и дальше погнали искать уже для нового многочлена, без этого корня.


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

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, OlegO, Вы писали:

OO>>В детстве баловалася, идея перекинуть метод Ньютона на комплексные числа и находим все корни, даже комплексные:

P>Слушай, а ты не пробовал повыбирать начальное приближение для последующих итераций метода Ньютона в разных точках комплексной плоскости? И раскрасить все точки по тому корню, к которому они "стекают"? Если нет, то я тебе завидую — у тебя впереди много интересного.

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

P>Если корня два, то всё чудесно — плоскость делится прямой пополам.
P>А если 3 — знак мерседеса? — ууупс — если кто не пробовал — проверьте

Здравствуйте, Atilla, Вы писали:

A>Только вот не помню, для 5-й степени есть точное решение или уже нет..?

Нет

Здравствуйте, OlegO, Вы писали:

OO>Что-то не пойму , давно это было. А идея у меня такая нашли корень, исключили его, понизив степень, ну и дальше погнали искать уже для нового многочлена, без этого корня.

Я о другом, давай объясню подробней.
Простое уравнение (x-1)(x^2+1)=0, x-комплексное
Корни очевидны — {1,i,-i}
Методом Ньютона хотим найти один любой корень.
Чтобы это сделать, начинаем с произвольного x0 и делаем некую итерационную процедуру, ну не мне тебя учить.
Вопрос — к какому из трёх корней придём?
Ясно, что это зависит как-то от х0.
Раскрасим синим такие x0, откуда упадём в 1,
красным — такие х0, откуда придём к i и
белым — такие х0, откуда придём к -i. (SetPixel)

Картинку нет смысла описывать — это надо видеть

Здравствуйте, Pushkin, Вы писали:

P>Я о другом, давай объясню подробней.
P>Простое уравнение (x-1)(x^2+1)=0, x-комплексное
P>Корни очевидны — {1,i,-i}
P>Методом Ньютона хотим найти один любой корень.
P>Чтобы это сделать, начинаем с произвольного x0 и делаем некую итерационную процедуру, ну не мне тебя учить.
P>Вопрос — к какому из трёх корней придём?
P>Ясно, что это зависит как-то от х0.
P>Раскрасим синим такие x0, откуда упадём в 1,
P>красным — такие х0, откуда придём к i и
P>белым — такие х0, откуда придём к -i. (SetPixel)

P>Картинку нет смысла описывать — это надо видеть

Понимаю, надо будет попробовать. А если еще цвет менять от скорости схождения?

Здравствуйте, OlegO, Вы писали:

OO>Здравствуйте, Pushkin, Вы писали:

OO> Понимаю, надо будет попробовать. А если еще цвет менять от скорости схождения?

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

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

Здравствуйте, Аноним, Вы писали:

А>Здрасте!
А>Кто нибудь может подкинуть алгоритм нахождения корней полинома типа:
А>a0*x^0 + a1*x^1 + a2*x^2 + .... + aN*x^N = 0

Если мнгогочлен над Z(Q), то можно использовать алгоритм Берликемпа для большого p

DOO>Если мнгогочлен над Z(Q), то можно использовать алгоритм Берликемпа для большого p

Скорее уж алгоритмом L3 (Ленстры, Ленстры и еще раз Ленстры ), который включает
в себя вызов Берлекампа. Просто же так исходя из факторизации по модулю p
получить таковую над Z не получится (например, есть неприводимые над Z полиномы, которые
приводимы по всем простым модулям).

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

Здравствуйте, Аноним, Вы писали:

А>Здрасте!
А>Кто нибудь может подкинуть алгоритм нахождения корней полинома типа:
А>a0*x^0 + a1*x^1 + a2*x^2 + .... + aN*x^N = 0

Как, всегда случайно попалось:

здесь есть исходники (FORTRAN + C):

Вычисление корней квадратного уравнения
Вычисление корней уравнения третьей степени
Вычисление корней уравнения четвертой степени
Вычисление всех корней полинома методом Лагерра
Вычисление всех корней полинома методом Дженкинса-Трауба
Вычисление числа вещественных корней полинома вне и внутри заданного интервала методом Штурма
Вычисление корней полинома с комплексными коэффициентами методом наискорейшего спуска
Вычисление рациональных корней полиномов с целыми коэффициентами