Comment résoudre un polynome de degré n en Java ?

Bonjour,

je viens de débuter en java dans le cadre de mon stage, et je suis amenée à résoudre une équation de degré n.

J'ai créé un objet Polynomial afin de trouver cette équation en calculant le déterminant d'une matrice nxn et donc là il faut que je résolve l'équation.

Voici le programme,

J'ai réfléchi à toute sorte de méthode mais en vain,

si vous avez une idée, s'il vous plait pourriez vous me la faire transmettre???

Merci d'avance,

Margueritian

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import java.util.*;
import java.io.*;
 
 class Polynomial {
    private double[] coef;  // coefficients
    private int deg;     // degree of polynomial (0 for the zero polynomial)
 
    // a * x^b
    public Polynomial(double a, int b) {
        coef = new double[b+1];
        coef[b] = a;
        deg = degree();
    }
 
    // return the degree of this polynomial (0 for the zero polynomial)
    public int degree() {
        int d = 0;
        for (int i = 0; i < coef.length; i++)
            if (coef[i] != 0) d = i;
        return d;
    }
 
    // return c = a + b
    public Polynomial plus(Polynomial b) {
        Polynomial a = this;
        Polynomial c = new Polynomial(0, Math.max(a.deg, b.deg));
        for (int i = 0; i <= a.deg; i++) c.coef[i] += a.coef[i];
        for (int i = 0; i <= b.deg; i++) c.coef[i] += b.coef[i];
        c.deg = c.degree();
        return c;
    }
 
    // return (a - b)
    public static Polynomial minus(Polynomial a,Polynomial b) {
        //Polynomial a = this;
        Polynomial c = new Polynomial(0, Math.max(a.deg, b.deg));
        for (int i = 0; i <= a.deg; i++) c.coef[i] += a.coef[i];
        for (int i = 0; i <= b.deg; i++) c.coef[i] -= b.coef[i];
        c.deg = c.degree();
        return c;
    }
 
    // return (a * b)
    public Polynomial times(Polynomial b) {
        Polynomial a = this;
        Polynomial c = new Polynomial(0, a.deg + b.deg);
        for (int i = 0; i <= a.deg; i++)
            for (int j = 0; j <= b.deg; j++)
                c.coef[i+j] += (a.coef[i] * b.coef[j]);
        c.deg = c.degree();
        return c;
    }
 
    // return a(b(x))  - compute using Horner's method
    public Polynomial compose(Polynomial b) {
        Polynomial a = this;
        Polynomial c = new Polynomial(0, 0);
        for (int i = a.deg; i >= 0; i--) {
            Polynomial term = new Polynomial(a.coef[i], 0);
            c = term.plus(b.times(c));
        }
        return c;
    }
 
 
    // do a and b represent the same polynomial?
    public boolean eq(Polynomial b) {
        Polynomial a = this;
        if (a.deg != b.deg) return false;
        for (int i = a.deg; i >= 0; i--)
            if (a.coef[i] != b.coef[i]) return false;
        return true;
    }
 
 
    // use Horner's method to compute and return the polynomial evaluated at x
    public int evaluate(int x) {
        int p = 0;
        for (int i = deg; i >= 0; i--)
            p =  (int)coef[i] + (x * p);
        return p;
    }
 
    // differentiate this polynomial and return it
    public Polynomial differentiate() {
        if (deg == 0) return new Polynomial(0, 0);
        Polynomial deriv = new Polynomial(0, deg - 1);
        deriv.deg = deg - 1;
        for (int i = 0; i < deg; i++)
            deriv.coef[i] = (i + 1) * coef[i + 1];
        return deriv;
    }
 
    // convert to string representation
    public String toString() {
        if (deg ==  0) return "" + coef[0];
        if (deg ==  1) return coef[1] + "x + " + coef[0];
        String s = coef[deg] + "x^" + deg;
        for (int i = deg-1; i >= 0; i--) {
            if      (coef[i] == 0) continue;
            else if (coef[i]  > 0) s = s + " + " + ( coef[i]);
            else if (coef[i]  < 0) s = s + " - " + (-coef[i]);
            if      (i == 1) s = s + "x";
            else if (i >  1) s = s + "x^" + i;
        }
        return s;
    }
 
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
public class Determinant {
 
private static int m=3;
private static int n=3;
 
public static Polynomial determinant(Polynomial[][]matrix){ //method sig. takes a matrix (two dimensional array), returns determinant.
    Polynomial sum= new Polynomial(0, 0);; 
    Polynomial s;
    Polynomial tmp1;
    if(matrix.length==1){  //bottom case of recursion. size 1 matrix determinant is itself.
      return(matrix[0][0]);
    }
    for(int i=0;i<matrix.length;i++){ //finds determinant using row-by-row expansion
      Polynomial[][]smaller= new Polynomial[matrix.length-1][matrix.length-1]; //creates smaller matrix- values not in same row, column
      for(int a=1;a<matrix.length;a++){
        for(int b=0;b<matrix.length;b++){
          if(b<i){
            smaller[a-1][b]=matrix[a][b];
          }
          else if(b>i){
            smaller[a-1][b-1]=matrix[a][b];
          }
        }
      }
      if(i%2==0){ //sign changes based on i
        s=new Polynomial(1, 0);;
      }
      else{
        s=new Polynomial(-1, 0);;
      }
      tmp1 = s.times(matrix[0][i].times(determinant(smaller) ));
      sum=sum.plus(tmp1); // recursive step: determinant of larger determined by smaller.
    }
    return(sum); //returns determinant value. once stack is finished, returns final determinant.
  }
 
 
// Methode qui permet de soustraire membre a membre les elements de deux tableaux
public static void Sousmat( Polynomial[][]tableau1, int t1, int t2, Polynomial[][]tableau2, Polynomial [][] tabfinal){
	for(int i=0; i<t1; i++){
		for(int j=0; j<t2; j++){
			tabfinal[i][j]= Polynomial.minus(tableau1[i][j],tableau2[i][j]);
		}
	}
}
 
public static void main(String[] args) {
 
double  [][] matrice11 = {{1,2,3},{1,2,3},{1,2,3}}; // cense etre la matrice de variance covariance de type double
Polynomial [][] matrice12 = new Polynomial[m][n]; // Nouveau tableau var cov de type Polynomial
Polynomial [][] matrice2 = new Polynomial[m][n]; // Matrice dont on veux calculer le determinant
Polynomial [][] Lambda = new Polynomial[m][n]; // Tableau que nous allons remplir lambda diagonale
Polynomial det;
double a;
 
// Conversion de la matrice de type double a une matrice de type polynome
for (int i=0; i<m; i++){
	for (int j=0; j<n; j++){
		a=matrice11[i][j];
		matrice12[i][j]= new Polynomial(a,0);
	}
}
 
// La matrice diagonale lambda
for (int i=0; i<m; i++){
	for(int j=0; j<n; j++){
		if (i==j){
			Lambda[i][j]= new Polynomial (1,1);
		}else{
			Lambda[i][j]=new Polynomial (0,0);
		}
	}
}
 
Sousmat(matrice12, m, n, Lambda, matrice2);
	det = determinant(matrice2);
	System.out.print(" le determinant est  "+det+ "\n");
 
/* la matrice est :
 
  |  1    4 |
  | -5   2x |
=> le det = x+20
                    
	matrice[0][0] = new Polynomial(1, 0);  // la valeur 1
	matrice[0][1] = new Polynomial(4, 0);   // la valeur 4
	matrice[1][0] = new Polynomial(-5, 0);    // la valeur -5
	matrice[1][1] = new Polynomial(2, 1);  // la valeur 2x
 
Polynomial det ;
det = determinant(matrice);
System.out.print(" le determinant est  "+det+ "\n");
 
 
 
EquationSolver solver = new EquationSolver(det);
double results= solver.getResult();
System.out.print("resultat="+result);
*/	
	}
}

Il faut partir sur de bonnes bases.
En dehors de tout langage informatique, si tu as un polynôme de degré 1 à résoudre, tu fais comment ?
Puis de degré 2 ? Puis 3 ?
Tu dois d'abord écrire ton algorithme.
Ensuite, tu pourras généraliser ton algorithme au degré N.

Enfin (et seulement enfin) tu vas pouvoir implémenter ton algorithme en Java.

Désolé pour toi mais aucun mathématicien n'a trouvé de solution à partir du degré 6.

Pour source http://fr.wikipedia.org/wiki/Histoir...polyn%C3%B4mes

Bonjour Margueritian,

Effectivement comme le souligne supergeoffrey il n'existe pas de méthode générale de résolution exacte des racines d'un polynôme quelconque.
En revanche il existe des méthodes générales d'évaluation de ces racines tu pourras trouver une bonne implémentation de certaines d'entre elles ici:
http://commons.apache.org/math/userguide/analysis.html
pour bien comprendre regarde aussi par là:
http://commons.apache.org/math/apidocs/index.html