Applet polynomes interpolateurs de lagrange (trouver le polynome de degre n-1 qui passe par n points)

Télécharger le projet
Commenter

Description

C'est un algo simple qu'on a vu en td d'algebre, j'avais envie d'en faire un programme, alors voila, on clique un peu partout, et il trace le polynome de degre n-1 qui passe par les n points...

Soit x0, x1 .... xn-1 les abscisses des pts, et idem pour y et l'ordonnee les x sont tous differents

il est simple de trouver un polynome Pl tq pl(xi)=0 pour tout i different de l et pl(xl)=1 : on le deffini comme ceci :
pl0=(X-x0)(X-x1) .... (sans mettre le xl evidement)
pl=pl0 / pl0(xl) xl n'est pas racine donc on peut, et on a construit ce polynome... il s'annulle en tout point choisi sauf un ou il vaut 1... on le multiplie par yl, et on fait la somme des pl l variant de 0 a n, et on obtient le polynome a afficher...

pour demontrer qu'il est unique, on en suppose un autre qui passerait par ces n points, et on montre que la difference des deux s'annulle pour ces n points... la difference a donc n racines, et c'est une difference de polynomes de degre n-1 donc un polynome null (de degre - inf)

Source / Exemple : 


import java.applet.*;
import java.awt.*;
import java.awt.event.*;

/*

ça donne l'ocasion de revoir un TD d'algebre, de s'entrainer en algorithmique,
et de perfectionner ses conaissances du langage java (même si ce dernier point est moins important :))

à partir d'un certain nombre de points, ça chie un peu à cause des limites du type float,
faudrait pour bien faire utiliser des templates pour les deux classes Polynome et
polynomes_interpolateurs_de_lagrange pour remplacer float par un type qui permettrait une
plus grande précision vers + infinit...


  • /


class Polynome{
	private float[] nombres;
	private int deg;
	public float getcoef(int n){
		return nombres[n];
	}
	public void setcoef(int n, float v){
		nombres[n]=v;
	}
	public int getdeg(){
		return deg;
	}
	public float getval(int x){
		float v=0;
		for (int i=0;i<=deg;i++){
			v+=nombres[i]*Math.pow(x, i);
		}
		return v;
	}
	public void Polynome(){}
	public void init(int n){
		nombres=new float[n+1];
		deg=n;
		for (int i=0;i<=deg;i++) nombres[i]=0;
	}
	public void plus(Polynome a){
		for (int i=0;i<=deg;i++)nombres[i]+=a.getcoef(i);
	}
	public void fois(Polynome a){
		float[] n=new float[deg+a.getdeg()+1];
		for (int i=0;i<=deg+a.getdeg();i++){
			n[i]=0;
		}
		for (int i=0;i<=deg;i++){
			for (int j=0;j<=a.getdeg();j++){
				n[i+j]+=a.getcoef(j)*nombres[i];
			}
		}
		nombres=new float[deg+1+a.getdeg()];
		for (int i=0;i<=deg+a.getdeg();i++){
			nombres[i]=n[i];
		}
		deg+=a.getdeg();
	}
	public void fois(int a){
		for (int i=0;i<=deg;i++)nombres[i]*=a;
	}
	public void divise(float f){
		for (int i=0;i<=deg;i++)nombres[i]/=f;
	}
}

public class polynomes_interpolateurs_de_lagrange extends Applet implements MouseMotionListener {
	private Polynome result;
	private int[] lX;
	private int[] lY;
	private int length;
	public void init(){
		//j'ai rien trouvé de mieux... mais faut être un peu con pour faire ça sur 100 points...
		lX=new int[100];		//j'aurais aimé une liste, mais j'ai pas trouvé la syntaxe
		lY=new int[100];		//
		result=new Polynome();
		result.init(0);
		length=0;
		this.addMouseMotionListener(this);
		this.addMouseListener(
			new MouseAdapter() {
				public void mouseClicked(MouseEvent e) {
					polynomes_interpolateurs_de_lagrange.this.mouseClicked(e);
				}
			}
		);
	}
	public void mouseDragged(MouseEvent e) {}
	public void mouseMoved(MouseEvent e) {}
	public void mouseClicked(MouseEvent e){
		int x = e.getX();
		int y = e.getY();
		//lX=new int[length+1];
		//lY=new int[length+1];
		lX[length]=x;
		lY[length]=y;
		length++;
		if (length>2){
			genere_polynome();
		}
		repaint();
	}
	private void genere_polynome(){
		result.init(length-1);
		for (int i=0;i<length;i++){
			Polynome temp1=new Polynome();
			temp1.init(length-1);
			temp1.setcoef(0, 1);		//p(x)=1*X^0
			for (int j=0;j<length;j++){
				if (i!=j){
					Polynome temp2=new Polynome();
					temp2.init(1);
					temp2.setcoef(0, -lX[j]);
					temp2.setcoef(1, 1);
					temp1.fois(temp2);
				}
			}
			//c'est !=0 car le polynome est de degré length-1 et a déjà length-1 racines. length>=3...
			temp1.divise(temp1.getval(lX[i]));
			temp1.fois(lY[i]);
			result.plus(temp1);
		}
	}
	public void paint( Graphics g ) {
		int sizeX=getSize().width;
		int sizeY=getSize().height;
		g.setColor(Color.white);
		g.fillRect(0, 0, sizeX, sizeY);
		g.setColor( Color.gray );
		for (int i=0;i<sizeX;i+=30){
			g.drawLine(i, 0, i, sizeY);
		}
		for (int i=0;i<sizeY;i+=30){
			g.drawLine(0, i, sizeX, i);
		}
		g.setColor( Color.blue );
		int y1, y2;
		if (length>2){
			for (int i=0;i<sizeX;i++){
				y1=(int)result.getval(i);
				y2=(int)result.getval(i+1);
				g.drawLine(i, y1, i+1, y2);
			}
		}
		g.setColor( Color.red );
		for (int i=0;i<length;i++){
			g.drawOval(lX[i]-5, lY[i]-5, 10, 10);
		}
	}
}
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (coucou747)