RAIZES DE POLINOMIOS

tjurkfitz
(usa Outra)

Enviado em 05/12/2015 - 11:04h

Preciso desenvolver um software em C que rode no DEV C, para a determinação de todas as raízes reais de um polinômio até ordem 10, ou seja, escolher o grau do polinômio e dependendo do grau mostrar suas raízes Se possível que me expliquem como foi realizado pois sou iniciante em programação. Agradeço pela ajuda desde já e fico na esperança de uma alma caridosa. Hehehehe

Thihup
(usa Manjaro Linux)

Enviado em 05/12/2015 - 11:10h

Olá amigo!

Primeiramente gostaria de lhe dizer que o Dev C++ já está desatualizado faz bastante Tempo.

Bom, poste o código que você já possui, pois aqui no VOL não é interessante postar a resolução "de bandeja".

Aqui, temos o intuito de ensinar a fazer, sem entregar o código.

Enfim, qual seria sua dúvida?

Espero poder ajudar

[]'s

T+

--

Att,

Thiago Henrique Hüpner

(Mensagem scaneada pelo antivírus........ops! não precisa, afinal eu uso Linux!)

removido
(usa Nenhuma)

Enviado em 05/12/2015 - 18:35h

Isso envolve mais matemática do que programação em si (já que esta parte é fácil);
Sabendo efetuar divisões e testes com restos (pra ver se um número é ou não divisível por outro) no C você resolve este problema;

O que você tem que fazer é usar o Teorema das raízes racionais;

Vou dar uma resumida: todo polinômio (TODO, desde que não seja nulo) tem a "cara" ax^n + bx^n-1 + cx^n-2 + ... + dx + e, onde a é o coeficiente dominante (com o x de maior grau - logo, o grau do polinômio) e e o coeficiente constante (sem o x);
O que o teorema diz é que as raízes de um polinômio de grau N é(são) aqueles na forma p/q, onde p é divisível por e (o coeficiente constante) e q é divisível por a (o coeficiente dominante), de modo que todos os valores possíveis entre p e q formem "pares" entre si e que o MDC entre eles seja igual a 1;

Depois de determinar as raízes (são várias), é só jogar no X do polinômio e resolver; se a resposta for 0 é que o valor é, de fato, a raiz do polinômio, se não der 0, não é raiz. Nota: o número de raízes de um polinômio é sempre igual ao valor do seu grau (mas pode existir raiz dupla, tripla e por aí vai)


Não sei se você sabe disso ou não, mas falei porque é assim que eu faria este programa; não sei também se o header <math.h> inclui funções próprias para trabalhar com polinômios, mas se tiver, simplificaria muito. Por fim, qualquer dúvida é só postar (inclusive não sei se o que eu respondi é o que você realmente precisa)

paulo1205
(usa Ubuntu)

Enviado em 05/12/2015 - 19:19h

Um polinômio de grau par com todos os coeficientes reais pode não ter nenhuma raiz real, e um de grau ímpar pode ter apenas uma raiz real (as não-reais formam pares complexos conjugados).

Para polinômios não-triviais com grau maior do que 2, a solução do seu problema não é algébrica, mas numérica. Logo, seus resultados estarão sujeitos a todos os problemas da disciplina de Cálculo Numérico, tais como a não representação exata dos valores dos números, convergência, arredondamento, propagação (acumulativa) de erros, margens de erro etc.

A solução do seu problema é a seguinte. A partir de um determinado ponto, você tem de varrer o plano complexo -- e não apenas para o eixo real -- e procurar um valor que zere o polinômio (ou que, na verdade, se aproxime, dentro da margem esperada de tolerância, de zerá-lo). Se você achar uma raiz real r, você divide o polinômio original por x-r e prossegue procurando as demais raízes. Se a raiz encontrada for um número complexo na forma a+ib, então seu conjugado a-ib também será uma raiz, e você poderá dividir o polinômio original por x²-2a·x+a²+b², e prosseguir procurando as demais raízes. Você prossegue nessa diminuição gradativa de graus do polinômio até chegar a um polinômio de grau 1 ou dois, que têm soluções algébricas.

MattF
(usa Slackware)

Enviado em 05/12/2015 - 19:50h

Gostaria de fazer uma pequena correção. O teorema correto seria: dado um polinômio da forma ax^n + bx^(n-1) + .....cx+q=0; caso existam raízes inteiras ou fracionárias(racionais) elas serão da forma Dq/Dn onde Dq são divisores de q e Dn são divisores de n. Ou seja, não há obrigatoriedade das raízes serem dessa forma, e se alguma for, as outras raízes não precisam ser porque elas podem ser irracionais, mesmo que a, b, c, ....q sejam inteiros(a exigência é que eles sejam reais). Desta forma seu programa estaria incompletíssimo se usasse somente esse teorema, mas nada te impede de implementá-lo com isso.

Já fiz exatamente isso que você quer usando python, mas não usei nenhuma biblioteca ou coisa do tipo, tentei construir minha lógica. A melhor solução que achei foi mais ou menos assim:

Limite o usuário para encontrar as soluções em um intervalo e com uma determinada precisão. Use a precisão como um intervalo de saltos dx pelo qual você vai percorrendo e computando valores de y correspondente. Se, durante esse loop, y=0 eis uma solução(não se esqueça de fazer tudo float). Se y muda de sinal use a média aritmética dos valores antes e depois da mudança de sinal como sendo a raiz, ou você pode usar outro critério. Vá armazenando as raízes nos arrays.

Claro que o programa ainda tem duas limitações: 1º não encontra os valores exatos da raiz 2º necessita de um intervalo de varredura(está limitado).

Para o primeiro problema se o resultado for irracional não existe melhor solução do que aproximar mesmo, mas e se for uma fração ou um inteiro aproximado? Ai sim você usa aquele teorema. Uma dica é criar um vetor com todos as combinações possíveis de divisores e depois comparar com os valores das aproximações.

Para o segundo problema é mais complicado. Você teria que analisar se a função é crescente ou decrescente, por exemplo, se o polinômio é de terceiro grau e você encontrou 3 raízes diferentes então resolvido. Agora, se você encontrou 2, então o polinômio pode ser sido ou não resolvido, pode ser que haja uma raíz dupla. Como verificar isso? Veja se no intervalo após a maior das raízes o polinômio representa uma função crescente e antes da menor é decrescente ou vice versa, já que se trata de uma função "ímpar". As aspas são porque ela não é ímpar, mas se comporta como uma, ao contrário do que seriam polinômios de grau dez. A coisa complicaria se você encontrasse uma solução.

Há no que se pensar. A vantagem de usar isso é que resolveria raízes não só de polinômios, mas também de funções em geral, teoricamente. A grande desvantagem é o quão pesada é essa varredura, mas por sorte estamos falando de C.

Se você pudesse aproveitar uma biblioteca que permitisse manipulação de variáveis e cálculo diferencial poderia utilizar o recurso do método de newton-raphson, se tiver alguma prática com cálculo. Bem, você também pode simplesmente identificar de qual grau é a função e aplicar o algoritmo de raphson-newton já pronto e depois de algumas permutações teria um resultado aproximado: https://pt.wikipedia.org/wiki/M%C3%A9todo_de_Newton-Rhapson


Para fazer isso você precisaria de ter uma função para cada caso que tem como argumentos cada coeficiente e computassem a fórmula para cada caso. A fórmula para décimo grau fica difícil ein!

Espero que consiga fazer um bom programa com isso. Esse é realmente um problema mais matemático que de programação, mas acho que aí é que esteja o erro. Programação é puramente matemática, com uma pitada de sintaxe. Se tiver mais alguma dúvida quanto ao problema não hesite em perguntar.

removido
(usa Nenhuma)

Enviado em 05/12/2015 - 20:32h

Tem toda razão, eu havia apenas considerado o caso de os coeficientes serem apenas inteiros;
Então o melhor e mais prático a se fazer é algo mais ou menos como você sugeriu: jogar o polinômio num loop infinito e ficar testando; quanto à precisão, creio que 15 casas decimais são mais do que o suficiente (i=i+0,000000000000001);

Quanto ao "limite" do intervalo, dá pra deixar o loop rodar até a limitação da variável float, que é de 3,4*10^38; caso a raiz esteja ainda acima deste valor, tente com double ou long double; se estiver ainda acima disso, tente arrumar um computador da NASA, rsrsrsrsrs

tjurkfitz
(usa Outra)

Enviado em 09/12/2015 - 09:55h

Obrigado pela colaboração pessoal,

Tentei de muitas formas, mas como eu disse sou muito inciante. hehehe. Consegui desenvolver um código pra fazer uma raíz de um polinomio até grau 10, porém não sei como implementar para varrer e encontrar as outras raízes. Se alguém conseguir complementar eu agradeço. Estará me passando em uma cadeira na faculdade hehehe. Abraço e agradeço desde já.

#include <stdio.h>
#include <math.h>

double calculafx(double coef[10], double p0){
double fx;
int i;
fx = coef[10];
for(i= 9;i>=0;i--){
fx = (p0*fx) + coef[i];}
return fx;}

double calculadfx(double coef[10], double p0){
double fx, dfx;
int i;
fx = coef[10];
dfx = coef[10];
for(i= 9;i>=1;i--){
fx = (p0*fx) + coef[i];
dfx = (p0*dfx) + fx;}
return dfx;}

double calculaddfx(double coef[10], double p0){
double fx, dfx, ddfx;
int i;
fx = coef[10];
dfx = coef[10];
ddfx = coef[10];
for(i= 9;i>=2;i--){
fx = (p0*fx) + coef[i];
dfx = (p0*dfx) + fx;
ddfx = (p0*ddfx) + 2*dfx;}
return ddfx;}

double modulo(double x){
if (x>=0.0){
return (x);}
else{
return (-1.0*x);}}

void main(void)
{
int n, op, grau, i;
double e, p0, p, fx, dfx, ddfx, tol, coef[10];
tol = 0.000001;
printf("Entre com o grau do polinomio: ");
scanf("%i", &grau);
for(i = 0 ; i <= 9 ; i++){
coef[i] = 0;
}
for(i = 0 ; i <= grau ; i++){
printf("\nEntre com o coeficiente a%i: ", i);
scanf("%lf",&coef[i]);
}
printf("\nEntre com o ponto inicial: ");
scanf("%lf", &p0);
n = 1;
fx = calculafx (coef,p0);
dfx = calculadfx (coef,p0);
ddfx = calculaddfx (coef,p0);
p = p0 - (fx*dfx)/((dfx*dfx)-(fx*ddfx));
printf("\nP%i %lf\n", (n-1), p0);
e = modulo(p-p0);
while (n<20 && e>=tol) {
p0 = p;
fx = calculafx (coef,p0);
dfx = calculadfx (coef,p0);
ddfx = calculaddfx (coef,p0);
p = p0 - (fx*dfx)/((dfx*dfx)-(fx*ddfx));
n++;
e = modulo(p-p0);
printf("P%i %lf\n", (n-1), p0);
}
printf("\nAproximacao p/ raiz e %e\n", p);
printf("\nAproximacao da f(x) no ponto e %e\n", fx);
printf("Com %i iteracoes\n\n", n);
}

paulo1205
(usa Ubuntu)

Enviado em 09/12/2015 - 13:47h

Como não sabe? Acima eu disse uma coisa que você poderia fazer.

"Varrer o plano complexo" é escolher um valor z=x+iy inicial (um chute razoável seria a raiz índice n do termo independente, sendo n o grau do polinômio) e calcular o valor do polinômio com esse valor de z. Você então poderia verificar outros valores na vizinhança de z ou aplicar o método de Newton-Raphson para recalcular sucessivos valores de z, até achar algum que se aproxime suficientemente de zerar o polinômio.

Caso opte por Newton-Raphson e dê azar de cair num ponto onde a derivada do polinômio é nula para z (por exemplo, um ponto equidistante de cada par de raízes complexas conjugadas de um polinômio de grau par e sem raízes reais), você pode introduzir uma perturbação aleatória em z (tanto na parte real quanto imaginária), para tentar ajudá-la a convergir.

Para valores reais, o método de Newton-Raphson nem sempre converge. Então um número máximo de tentativas costuma ser usado como limite do tempo de execução. Pelo que li, com variáveis complexas, as chances de convergência são bem maiores (porque um dos casos em que a convergência real não acontece é justamente quando o algoritmo fica oscilando em torno de inflexões causadas pela presença de raízes complexas conjugadas). Mesmo assim, ter um limite máximo do número de iterações ou tempo de execução, ou ainda uma avaliação de se os valores de z estão efetivamente convergindo para algum ponto ainda pode ser uma boa medida de segurança.

saitam
(usa Slackware)

Enviado em 09/12/2015 - 15:04h

Regra de Horner também pode ser utilizado para cálculo de polinômios de grau n.

http://www.vivaolinux.com.br/script/Regra-de-Horner-para-calculo-do-polinomio/


http://mundodacomputacaointegral.blogspot.com.br/
Twitter: http://twitter.com/@blogcomputacao
Facebook: http://www.facebook.com/BlogComputacao

tjurkfitz
(usa Outra)

Enviado em 09/12/2015 - 15:16h

O método de Horner, também tinha feito algo bem parecido com esse. Meu problema é encontrar uma forma que ao digitar o polinomio e um ponto ele me de todas raízes reais a partir do ponto indicado. Não sei como complementar o código. Não sei se deu pra entender.

paulo1205
(usa Ubuntu)

Enviado em 09/12/2015 - 15:40h

Alguém está lendo minhas postagens neste tópico?

removido
(usa Nenhuma)

Enviado em 09/12/2015 - 16:02h

Sim.

Eu não tenho prática em usar a implementação de números complexos em C, mas sei que ela existe e que tem header para isto.
Talvez o problema seja ninguém pensar em usar a implementação.
Deve ser melhor do que implementar complexos na unha com structs etc.

----------------------------------------------------------------------------------------------------------------
# apt-get purge ubuntu