15/1: cours 1
1/ Présentation du module
2/ Suites récurrentes à 1 cran: représentation graphique en toile d'araignée, solutions de l=f(l) exemples
f(x)=cos(x) (pas de formule pour l), f(x)=x^3/2 (0 et +/-sqrt(2)), f(x)=(x+2)/(x+1) (sqrt(2)), 1/2*(x+2/x) (+/-sqrt(2))
3/ théorème du point fixe.
Définition de fonction lipschitzienne puis contractante f:I=[a,b]->[a,b] et |f(y)-f(x)|<=k|y-x| avec k<1
Enoncé du théorème du point fixe et estimations |u_n-l|<=k^n|b-a| (à priori), |u_{n+1}-l|<=|u_{n+1}-u_n|*k/(1-k) (à postériori),
Preuve.
Exemple : f(x)=cos(x) sur [0,pi/2] ne va pas, mais sur [0,1] oui avec k=sin(1), illustration à la machine, il faut environ 6 itérations pour gagner une décimale. Par contre on observe que pour 1/2*(x+2/x) on double approximativement le nombre de décimales à chaque itération!
4/ la valeur de n à partir de laquelle on peut certifier qu'on a une approximation en utilisant l'estimation à priori dépend linéairement du ln de la précision, donc du nombre de chiffres. On a intérêt à avoir 1/(-ln(k)) petit, donc k proche de 0.
5/ Si k>1/2 il vaut mieux utiliser la dichotomie que le point fixe.
cours 2023/24
Modérateur : xcasadmin
Re: cours 2023/24
Cours 2/12 (22 janvier):
Méthode de Newton:
1/ représentation graphique de la méthode de résolution de f(x)=0, calcul de u_(n+1) en fonction de u_n, exemple pour f(x)=x^2-2
2/ thm de convergence si f est C^2 sur I contenant strictement r tel que f(r)=0 et f'(r)!=0, il existe eta>0 tel que u_n converge si u_0 appartient a [r-eta,r+eta], estimation sur eta avec 1/(2*m*M), où m=max|1/f'| et M=max|f''| près de r. Calcul de m et M pour f(x)=x^2-2, r=sqrt(2). Calcul difficile en général.
3/ définition de convexité, critère f''>=0 pour f C^2 sur I
thm de convergence si f convexe sur [r,b], f(r)=0, f'(r)>0, u_n converge si u_0 appartient a [r,b] en décroissant. De plus 0<= u_n-r <= f(u_n)/f'(r). Variantes selon convexité/concavité et signe de f'(r). Preuve dans le cas C^2
Remarque sur les erreurs d'arrondi qui deviennent importantes lorsque u_n s'approche de r.
Calcul des premiers termes avec Xcas en calcul exact avec u0=2, approché avec u0=2.0, multiprécision avec u0=evalf(2,50). Erreur d'arrondi pouvant conduire à des absurdités comme f(u_n)<0 en calcul approché.
Prise en main calculatrices.
Méthode de Newton:
1/ représentation graphique de la méthode de résolution de f(x)=0, calcul de u_(n+1) en fonction de u_n, exemple pour f(x)=x^2-2
2/ thm de convergence si f est C^2 sur I contenant strictement r tel que f(r)=0 et f'(r)!=0, il existe eta>0 tel que u_n converge si u_0 appartient a [r-eta,r+eta], estimation sur eta avec 1/(2*m*M), où m=max|1/f'| et M=max|f''| près de r. Calcul de m et M pour f(x)=x^2-2, r=sqrt(2). Calcul difficile en général.
3/ définition de convexité, critère f''>=0 pour f C^2 sur I
thm de convergence si f convexe sur [r,b], f(r)=0, f'(r)>0, u_n converge si u_0 appartient a [r,b] en décroissant. De plus 0<= u_n-r <= f(u_n)/f'(r). Variantes selon convexité/concavité et signe de f'(r). Preuve dans le cas C^2
Remarque sur les erreurs d'arrondi qui deviennent importantes lorsque u_n s'approche de r.
Calcul des premiers termes avec Xcas en calcul exact avec u0=2, approché avec u0=2.0, multiprécision avec u0=evalf(2,50). Erreur d'arrondi pouvant conduire à des absurdités comme f(u_n)<0 en calcul approché.
Prise en main calculatrices.
Re: cours 2023/24
Cours 3 sur 12 du 29/1
Calculatrice: écriture d'une fonction pour calculer les itérées d'une suite récurrente, exécution en mode pas à pas.
Représentation des objets mathématiques sur machine
1/ Entiers:
-> division euclidienne des entiers, écriture en base b, opération inverse = évaluation du polynôme dont les coeffs sont l'écriture en base b en X=b. Exemple en base 2.
-> entiers machines : limitation en taille
-> entiers longs (représenté par exemple en base 2^32 ou 2^64), plus de limitation en taille, mais plus lents : opérations comme pour les polynomes mais avec retenues. Exemple +,*,division euclidienne en base b=2.
2/ Réels:
-> virgule fixe, peu adapté au calcul scientifique
-> virgule flottante: réel r représenté approximativement par q=m*b^e, ou m est la mantisse (n caractères) et e l'exposant, b la base. Exemple avec pi, b=10, n=3 on a intérêt à prendre e=-2 et m=314
-> Flottant normalisé b^(n-1)<= m <= b^n-1. Exemple: flottants machine (double), n=53 codé sur 52 bits (non écriture du 1 initial redondant)
-> Erreur relative avec le représentant flottant le plus proche) 1/2/b^(n-1)
Calculatrice: écriture d'une fonction pour calculer les itérées d'une suite récurrente, exécution en mode pas à pas.
Représentation des objets mathématiques sur machine
1/ Entiers:
-> division euclidienne des entiers, écriture en base b, opération inverse = évaluation du polynôme dont les coeffs sont l'écriture en base b en X=b. Exemple en base 2.
-> entiers machines : limitation en taille
-> entiers longs (représenté par exemple en base 2^32 ou 2^64), plus de limitation en taille, mais plus lents : opérations comme pour les polynomes mais avec retenues. Exemple +,*,division euclidienne en base b=2.
2/ Réels:
-> virgule fixe, peu adapté au calcul scientifique
-> virgule flottante: réel r représenté approximativement par q=m*b^e, ou m est la mantisse (n caractères) et e l'exposant, b la base. Exemple avec pi, b=10, n=3 on a intérêt à prendre e=-2 et m=314
-> Flottant normalisé b^(n-1)<= m <= b^n-1. Exemple: flottants machine (double), n=53 codé sur 52 bits (non écriture du 1 initial redondant)
-> Erreur relative avec le représentant flottant le plus proche) 1/2/b^(n-1)
Re: cours 2023/24
Cours du 5/2 (4ème cours)
* Réels représentables exactement en base 2 et 10, 5*0.6 ne fait pas forcément 3 en base 2, comme 3*1/3.0 en base 10
* Produit de 2 flottants.
* Erreur absolue pour une somme/différence de 2 flottants, problème de la compensation et perte possible de nombreux chiffres significatifs en une seule opération
* Erreur relative pour un produit, au 1er ordre <= la somme des erreurs relatives.
* En toute rigueur, il faut rajouter une erreur relative d'arrondi au plus proche (1/2/b^(n-1))
* Calcul de f(x): l'erreur relative est multipliée au 1er ordre par |x*f'(x)/f(x)|, par ex pour exp, si x est de l'ordre de 100, on perd 2 décimales, indépendamment de l'algorithme utilisé, illustration machine
* Calcul approché de f'(x) par (f(x+h)-f(x))/h pour h petit, on ne peut pas prendre h trop petit, sinon f(x+h)-f(x) perd trop de précision, mais il faut un h pas trop grand pour approcher f'(x), il y a un h optimal, illustration machine. La formule (f(x+h)-f(x-h))/h est plus précise (exercice)
* astuces classique pour éviter de perdre en précision, réécriture lorsque c'est possible (par ex. multiplier par le conjugué, calcul précis des racines d'une équation du second degré, 1-cos^2=sin^2...), sommation de termes en commençant par les plus petits, compensation des erreurs d'arrondis (cf. poly en ligne), illustration machine
* calcul d'erreur trop fastidieux/difficiles, en pratique on peut utiliser de flottants multi-précision, de l'arithmétique d'intervalle (permet de certifier un calcul approché) ou tout simplement faire un peu varier les paramètres pour voir l'effet
* Réels représentables exactement en base 2 et 10, 5*0.6 ne fait pas forcément 3 en base 2, comme 3*1/3.0 en base 10
* Produit de 2 flottants.
* Erreur absolue pour une somme/différence de 2 flottants, problème de la compensation et perte possible de nombreux chiffres significatifs en une seule opération
* Erreur relative pour un produit, au 1er ordre <= la somme des erreurs relatives.
* En toute rigueur, il faut rajouter une erreur relative d'arrondi au plus proche (1/2/b^(n-1))
* Calcul de f(x): l'erreur relative est multipliée au 1er ordre par |x*f'(x)/f(x)|, par ex pour exp, si x est de l'ordre de 100, on perd 2 décimales, indépendamment de l'algorithme utilisé, illustration machine
* Calcul approché de f'(x) par (f(x+h)-f(x))/h pour h petit, on ne peut pas prendre h trop petit, sinon f(x+h)-f(x) perd trop de précision, mais il faut un h pas trop grand pour approcher f'(x), il y a un h optimal, illustration machine. La formule (f(x+h)-f(x-h))/h est plus précise (exercice)
* astuces classique pour éviter de perdre en précision, réécriture lorsque c'est possible (par ex. multiplier par le conjugué, calcul précis des racines d'une équation du second degré, 1-cos^2=sin^2...), sommation de termes en commençant par les plus petits, compensation des erreurs d'arrondis (cf. poly en ligne), illustration machine
* calcul d'erreur trop fastidieux/difficiles, en pratique on peut utiliser de flottants multi-précision, de l'arithmétique d'intervalle (permet de certifier un calcul approché) ou tout simplement faire un peu varier les paramètres pour voir l'effet
Re: cours 2023/24
cours 5 sur 12 du lundi 12 février:
Utilisation de la calculatrice: exercice 4 de TP (compte-rendu avec note indicative)
Calcul des fonctions usuelles et séries de Taylor : 1ère partie.
- formule de Taylor avec reste en fonction de la dérivée n+1-ieme.
- exemple de la fonction exponentielle, Représentation de exp(x) et de T_n(f)(x) pour n=2,3,4.
Majoration du reste, convergence du majorant, calcul pour x=1, x=10, x<0
- problème du n grand pour avoir R_n petit lorsque |x| est grand. Problème des calculs intermédiaires grands avec résultat petit par ex. pour exp(-10) perte d'environ 8 décimales.
Pour les fonctions usuelles on peut faire plus efficace ou/et plus précis en utilisant leurs propriétés.
- Réduction d'argument pour exp via exp(2x)=exp(x)^2. Estimation de l'erreur relative induite, multipliée par un facteur |x| ce qui est optimal
- autre réduction possible via x=q*ln(2)+r avec q entier = round(x/ln(2)) (si on connait ln(2))
- traitements analogues possibles pour sin/cos. Mais ne convient pas si on ne sait pas facilement exprimer la dérivée n-ième de f, par exemple tan(x), on calcule sin(x)/cos(x)
Fonction inverses:
Dérivée n+1-ième de ln(1+x), majoration du reste pour x>0 par 1/(n+1)*x^(n+1), ok si x<1, mais pour x<0 c'est mauvais en particulier si x<-1/2.
Utilisation de la calculatrice: exercice 4 de TP (compte-rendu avec note indicative)
Calcul des fonctions usuelles et séries de Taylor : 1ère partie.
- formule de Taylor avec reste en fonction de la dérivée n+1-ieme.
- exemple de la fonction exponentielle, Représentation de exp(x) et de T_n(f)(x) pour n=2,3,4.
Majoration du reste, convergence du majorant, calcul pour x=1, x=10, x<0
- problème du n grand pour avoir R_n petit lorsque |x| est grand. Problème des calculs intermédiaires grands avec résultat petit par ex. pour exp(-10) perte d'environ 8 décimales.
Pour les fonctions usuelles on peut faire plus efficace ou/et plus précis en utilisant leurs propriétés.
- Réduction d'argument pour exp via exp(2x)=exp(x)^2. Estimation de l'erreur relative induite, multipliée par un facteur |x| ce qui est optimal
- autre réduction possible via x=q*ln(2)+r avec q entier = round(x/ln(2)) (si on connait ln(2))
- traitements analogues possibles pour sin/cos. Mais ne convient pas si on ne sait pas facilement exprimer la dérivée n-ième de f, par exemple tan(x), on calcule sin(x)/cos(x)
Fonction inverses:
Dérivée n+1-ième de ln(1+x), majoration du reste pour x>0 par 1/(n+1)*x^(n+1), ok si x<1, mais pour x<0 c'est mauvais en particulier si x<-1/2.
Re: cours 2023/24
cours 6 du 19/02:
Rappel majoration du reste de la série de Taylor: cas de ln(1+x) la majoration est mauvaise pour x=-1/2 ou <-1/2 -> autre théorie
Série entière comme polynome "de degré infini". Déf de rayon de convergence et majoration du reste pour |x|<|x_0| lorsque |a_k x_0^k| <= M
Preuve.
Exemple si |a_k|=1 ou 1/k, on peut prendre x_0=1 et M=1
Définition de fonction développable en série entière en x=0, = dvpt Taylor à l'infini et rayon de convergence>0.
Exemple: exp, R=+infini
Thm (admis) sur les opérations de fonctions développables en séries entières (+,-,*,inv si f(0)!=0, composition g@f si si f(0)=0, dérivation, intégration).
Exemple: ln(1+x)=primitive de 1/(1+x)
Calcul de ln(2)=-ln(1-1/2) à une précision donnée.
Autre possibilité de majoration du reste avec les séries alternées. Attention à bien vérifier la décroissance en valeur absolue du terme général.
Exemples: ln(1+x) pour x entre 0 et 1, même résultat que la majoration séries alternées
sin, attention alternée à partir du rang |x|/2
Réduction d'argument pour accélérer la convergence, calcul de ln(x) en écrivant x=2^e*M -> ln(m)+(e+n)*ln(2) avec m=M/2^n entre 1/2 et 1, on peut appliquer m=1+x avec x entre -1/2 et 0, ou mieux (astuce) en posant m=(1+t)/(1-t) avec t entre 0 et 1/3.
Culture générale: Ces méthodes sont à convergence linéaire ou à peine mieux (quand on a un facteur 1/n!), comme le point fixe. On aimerait avoir du quadratique (comme Newton) si on veut beaucoup de précision (par ex. un million de décimales). Il existe un algorithme à convergence quadratique pour le ln, basé sur la moyenne arithmético-géométrique. Qui permet ensuite de faire pareil pour exp avec la méthode de Newton.
Rappel majoration du reste de la série de Taylor: cas de ln(1+x) la majoration est mauvaise pour x=-1/2 ou <-1/2 -> autre théorie
Série entière comme polynome "de degré infini". Déf de rayon de convergence et majoration du reste pour |x|<|x_0| lorsque |a_k x_0^k| <= M
Preuve.
Exemple si |a_k|=1 ou 1/k, on peut prendre x_0=1 et M=1
Définition de fonction développable en série entière en x=0, = dvpt Taylor à l'infini et rayon de convergence>0.
Exemple: exp, R=+infini
Thm (admis) sur les opérations de fonctions développables en séries entières (+,-,*,inv si f(0)!=0, composition g@f si si f(0)=0, dérivation, intégration).
Exemple: ln(1+x)=primitive de 1/(1+x)
Calcul de ln(2)=-ln(1-1/2) à une précision donnée.
Autre possibilité de majoration du reste avec les séries alternées. Attention à bien vérifier la décroissance en valeur absolue du terme général.
Exemples: ln(1+x) pour x entre 0 et 1, même résultat que la majoration séries alternées
sin, attention alternée à partir du rang |x|/2
Réduction d'argument pour accélérer la convergence, calcul de ln(x) en écrivant x=2^e*M -> ln(m)+(e+n)*ln(2) avec m=M/2^n entre 1/2 et 1, on peut appliquer m=1+x avec x entre -1/2 et 0, ou mieux (astuce) en posant m=(1+t)/(1-t) avec t entre 0 et 1/3.
Culture générale: Ces méthodes sont à convergence linéaire ou à peine mieux (quand on a un facteur 1/n!), comme le point fixe. On aimerait avoir du quadratique (comme Newton) si on veut beaucoup de précision (par ex. un million de décimales). Il existe un algorithme à convergence quadratique pour le ln, basé sur la moyenne arithmético-géométrique. Qui permet ensuite de faire pareil pour exp avec la méthode de Newton.
Re: cours 2023/24
Cours du lundi 4 mars:
Application des séries entières au calcul de fonctions spéciales: calcul de integrate(exp(-t^2),t=0..x)
pour x^2<=1, ça converge bien, au-delà on a les problèmes de perte de précision et de nombre de termes à calculer qui augmente sans pouvoir faire de réduction d'argument. Ce qui nécessite de la multi-précision et est donc couteux. (en pratique, pour x grand, on utilise plutôt un développement asymptotique). Pour les valeurs intermédiaires, on utilisera de l'approximation polynomiale.
Recherche de solution série entière de certaines équations différentielles linéaires non résolubles analytiquement : exemple de l'équation de Bessel pour m=0.
Chapitre 4 Polynômes
Arithmétique de base: + - * division euclidienne, algorithme d'Euclide, identité de Bezout avec l'algorithme d'Euclide étendu (exemple sur Z puis sur Q[X])
Applications de Bezout: décomposition en éléments simples, calcul de primitive, dérivée n-ième et dvpt en série entière. Euclide étendu partiel permet même d'améliorer l'approximation de exp(x) (approximant de Padé, illustration machine à l'ordre 10 avec numérateur et dénominateur de degré <=5).
Application des séries entières au calcul de fonctions spéciales: calcul de integrate(exp(-t^2),t=0..x)
pour x^2<=1, ça converge bien, au-delà on a les problèmes de perte de précision et de nombre de termes à calculer qui augmente sans pouvoir faire de réduction d'argument. Ce qui nécessite de la multi-précision et est donc couteux. (en pratique, pour x grand, on utilise plutôt un développement asymptotique). Pour les valeurs intermédiaires, on utilisera de l'approximation polynomiale.
Recherche de solution série entière de certaines équations différentielles linéaires non résolubles analytiquement : exemple de l'équation de Bessel pour m=0.
Chapitre 4 Polynômes
Arithmétique de base: + - * division euclidienne, algorithme d'Euclide, identité de Bezout avec l'algorithme d'Euclide étendu (exemple sur Z puis sur Q[X])
Applications de Bezout: décomposition en éléments simples, calcul de primitive, dérivée n-ième et dvpt en série entière. Euclide étendu partiel permet même d'améliorer l'approximation de exp(x) (approximant de Padé, illustration machine à l'ordre 10 avec numérateur et dénominateur de degré <=5).
Re: cours 2023/24
cours 8 sur 12 du 18 mars:
Factorisation des polynômes:
Distinction entre factorisation exacte sur Q[X] et (rationnel complexe)[X] et approchée sur R[X] et C[X] selon les coefficients du polynôme, les facteurs sont de degré 1 ou 2 ou 1 ou de degrés quelconques, exemple factor(x^3+x+1), factor(x^3+x+1.0), cfactor(x^3+x+1.0)
Thm: Soit G=gcd(P,P'), alors Q=P/G a les mêmes racines que P avec multiplicité 1.
On suppose dans la suite que le polynôme n'a que des racines simples.
Recherche des racines rationnelles d'un polynôme de Q[X] sous la forme +/- num/deno avec num divise le coefficient constant et deno divise le coeff dominant.
Exemple 2*x^3-x^2+x+1
Remarque: ce n'est pas efficace (s'il y a beaucoup de diviseurs par exemple)
Factorisation approchée: sur R, dichotomie ou méthode de Newton, par ex. pour x^3+x+1, concave croissant sur [-1,0], u0=-1 la suite de Newton converge
Sur C, pas de signe, donc pas de dichotomie, et pas d'analogue de convexe/concave croissant.
On peut quand même essayer Newton et s'arrêter lorsque P(z) est assez petit. On a alors:
Thm: la boule de centre u_n et de rayon degree(P)*abs(P(u_n)/P'(u_n)) contient au moins une racine complexe de P.
Démo de P'/P=sum_{z_j racine de P} 1/(x-z_j)
Preuve du thm par l'absurde.
Exemple pour p:=x^4+x+1; q:=p'; on part d'un u0 complexe au hasard et on itère puis quand cela se stabilise on fait exact(un) et on calcule degree(P)*abs(P(un)/P'(un)) pour pouvoir certifier l'existence d'une racine dans un disque du plan complexe de ce rayon.
Application: décomposition en éléments simples de N/D avec degre(N)<degre(D) et D a racines simples, calcul de primitive dans ce cas, exemple 1/(x^2-4)
Factorisation des polynômes:
Distinction entre factorisation exacte sur Q[X] et (rationnel complexe)[X] et approchée sur R[X] et C[X] selon les coefficients du polynôme, les facteurs sont de degré 1 ou 2 ou 1 ou de degrés quelconques, exemple factor(x^3+x+1), factor(x^3+x+1.0), cfactor(x^3+x+1.0)
Thm: Soit G=gcd(P,P'), alors Q=P/G a les mêmes racines que P avec multiplicité 1.
On suppose dans la suite que le polynôme n'a que des racines simples.
Recherche des racines rationnelles d'un polynôme de Q[X] sous la forme +/- num/deno avec num divise le coefficient constant et deno divise le coeff dominant.
Exemple 2*x^3-x^2+x+1
Remarque: ce n'est pas efficace (s'il y a beaucoup de diviseurs par exemple)
Factorisation approchée: sur R, dichotomie ou méthode de Newton, par ex. pour x^3+x+1, concave croissant sur [-1,0], u0=-1 la suite de Newton converge
Sur C, pas de signe, donc pas de dichotomie, et pas d'analogue de convexe/concave croissant.
On peut quand même essayer Newton et s'arrêter lorsque P(z) est assez petit. On a alors:
Thm: la boule de centre u_n et de rayon degree(P)*abs(P(u_n)/P'(u_n)) contient au moins une racine complexe de P.
Démo de P'/P=sum_{z_j racine de P} 1/(x-z_j)
Preuve du thm par l'absurde.
Exemple pour p:=x^4+x+1; q:=p'; on part d'un u0 complexe au hasard et on itère puis quand cela se stabilise on fait exact(un) et on calcule degree(P)*abs(P(un)/P'(un)) pour pouvoir certifier l'existence d'une racine dans un disque du plan complexe de ce rayon.
Application: décomposition en éléments simples de N/D avec degre(N)<degre(D) et D a racines simples, calcul de primitive dans ce cas, exemple 1/(x^2-4)
Re: cours 2023/24
cours 9 sur 12:
Majoration des racines complexes d'un polynôme par m:=max|coeff(P)|/|coeff_dominant(P)|+1,
Localisation des racines réelles d'un polynôme à coefficients réels: def de la suite de Sturm pour P un polynôme sans racine multiple donc pgcd(P,P')=1, on prend la suite de l'algo d'Euclide en changeant le signe du reste
R_0=P, R_1=P', R_{n+2}=-rem(R_n,R_{n+1})
sigma(a)=nombre de changements de signe de la suite R_0,...,R_N(a) avec R_N=dernier reste non nul.
Thm: nombre de racines dans l'intervalle a b = sigma(a)-sigma(b)
Exemple: x^3+x+1 sur [-1,0]
Preuve de Sturm.
Nombre de racines réelles de P avec Sturm sur [-m,m]
Isolation des racines avec Sturm et dichotomie sur [a,b] (au début a=-m, b=m)
si 0 racine on s'arrete, si 1 racine on passe en dichotomie classique, si >=2 racines on coupe l'intervalle en 2 et on refait Sturm.
Chapitre 5: interpolation polynomiale
Théoreme d'existence et unicité de P de degré<=n tel que P(x_i)=y_i pour 0<=i<=n sous la forme
P=q_0+(x-x0)*(q_1+...)
Preuve par récurrence. Exemple avec n=2.
Calcul de P avec la liste des x_i et des q_i en 3n opérations.
Algorithme de calcul des q_i par les différences divisées. Preuve.
Exemple avec n=3
Majoration des racines complexes d'un polynôme par m:=max|coeff(P)|/|coeff_dominant(P)|+1,
Localisation des racines réelles d'un polynôme à coefficients réels: def de la suite de Sturm pour P un polynôme sans racine multiple donc pgcd(P,P')=1, on prend la suite de l'algo d'Euclide en changeant le signe du reste
R_0=P, R_1=P', R_{n+2}=-rem(R_n,R_{n+1})
sigma(a)=nombre de changements de signe de la suite R_0,...,R_N(a) avec R_N=dernier reste non nul.
Thm: nombre de racines dans l'intervalle a b = sigma(a)-sigma(b)
Exemple: x^3+x+1 sur [-1,0]
Preuve de Sturm.
Nombre de racines réelles de P avec Sturm sur [-m,m]
Isolation des racines avec Sturm et dichotomie sur [a,b] (au début a=-m, b=m)
si 0 racine on s'arrete, si 1 racine on passe en dichotomie classique, si >=2 racines on coupe l'intervalle en 2 et on refait Sturm.
Chapitre 5: interpolation polynomiale
Théoreme d'existence et unicité de P de degré<=n tel que P(x_i)=y_i pour 0<=i<=n sous la forme
P=q_0+(x-x0)*(q_1+...)
Preuve par récurrence. Exemple avec n=2.
Calcul de P avec la liste des x_i et des q_i en 3n opérations.
Algorithme de calcul des q_i par les différences divisées. Preuve.
Exemple avec n=3
Re: cours 2023/24
Théorème de majoration de l'erreur f(x)-P(x) et preuve.
Illustration de l'erreur pour f(x):=x*sin(x)-cos(x) interpole sur [-1,1] en -1, -0.5, 0, 0.5, 1.
Ordre de grandeur de l'erreur assez bien estimée par le théorème de majoration (avec majoration de la dérivée 5-ième par 7). Observation: l'erreur est plus grande près des bords de l'intervalle si on prend des points équidistribués.
Illustration du fait qu'augmenter le nombre de points d'interpolation de manière équirépartie peut aggraver l'erreur d'interpolation sur l'intervalle d'interpolation. Cf ci-dessous, essayer avec n>10.
session Xcas
Remarque hors programme: la solution c'est de choisir mieux la répartition des points d'interpolation, pour optimiser le facteur product(x-x_i), sur [-1,1] on utilise pour x_i les racines du polynôme Tn(cos(t))=cos(n*t)
Chapitre intégration approchée.
[a,b] subdivisé en N intervalles [alpha,beta] de largeur h=(b-a)/N
Méthodes classiques:
rectangles gauches/droits, point milieu (utilise un point, remplace f par une constante)
trapèzes (utilise 2 points, remplace f par un segment)
Simpson (utilise 3 points, remplace f par un arc de parabole)
Formules de calcul.
Majoration de l'erreur, preuve sauf dans le cas Simpson.
Illustration sur la fonction cos a la machine de la valeur de l'écart entre formule et valeur de l'integrale lorsque h varie, en h, h^2 et h^4.
Illustration de l'erreur pour f(x):=x*sin(x)-cos(x) interpole sur [-1,1] en -1, -0.5, 0, 0.5, 1.
Ordre de grandeur de l'erreur assez bien estimée par le théorème de majoration (avec majoration de la dérivée 5-ième par 7). Observation: l'erreur est plus grande près des bords de l'intervalle si on prend des points équidistribués.
Illustration du fait qu'augmenter le nombre de points d'interpolation de manière équirépartie peut aggraver l'erreur d'interpolation sur l'intervalle d'interpolation. Cf ci-dessous, essayer avec n>10.
session Xcas
Remarque hors programme: la solution c'est de choisir mieux la répartition des points d'interpolation, pour optimiser le facteur product(x-x_i), sur [-1,1] on utilise pour x_i les racines du polynôme Tn(cos(t))=cos(n*t)
Chapitre intégration approchée.
[a,b] subdivisé en N intervalles [alpha,beta] de largeur h=(b-a)/N
Méthodes classiques:
rectangles gauches/droits, point milieu (utilise un point, remplace f par une constante)
trapèzes (utilise 2 points, remplace f par un segment)
Simpson (utilise 3 points, remplace f par un arc de parabole)
Formules de calcul.
Majoration de l'erreur, preuve sauf dans le cas Simpson.
Illustration sur la fonction cos a la machine de la valeur de l'écart entre formule et valeur de l'integrale lorsque h varie, en h, h^2 et h^4.
Re: cours 2023/24
Exemple: pour avoir l'intégrale de exp(-x^2) entre 0 et 1 avec une précision de 1e-6, on calcule la dérivée 4-ième, on la majore (assez grossièrement) par 72 sur [0,1], ou plus finement en étudiant la dérivée 5ème, puis on résoud 72/2880*1/N^4=1e-6, on trouve 13 subdivisions. Vérification.
Généralisation : méthode de Newton-Cotes par interpolation avec n+1 points par subdivision [alpha,beta]: sum_{i=0}^n f(x_i)*omega_i, poids normalisé omega_i/(beta-alpha)
Calcul des poids, exemple pour les poids de Simpson
Def. de l'ordre o d'une méthode: exact pour polynôme de degré<=o, non exact pour degré o+1. Exemples: rectangle, Simpson
Thm de majoration générique de l'erreur en C_o*M_(o+1)*h^(o+1)*largeur de l'intervalle avec M_(o+1) un majorant de la dérivee d'ordre o+1, exemple pour ordre 3, on a une constante un peu meilleure pour Simpson.
Prolongements (pour la culture generale): on peut choisir les abscisses de points d'interpolation pour optimiser l'ordre (quadratures gaussiennes)
Accélération de Richardson-Romberg avec le développement de Taylor de la formule des trapèzes en puissances paires de h (formule d'Euler-Mac Laurin), en éliminant le terme en h^2 T_1(h):=(4*T(h/2)-T(h))/(4-1) puis en h^4 T_2(h):=(16*T1(h/2)-T1(h))/(16-1), etc. Remarque: T_1 est la méthode de Simpson
Méthodes adaptatives: au lieu d'utiliser un même pas pour toutes les subdivisions, on estime l'erreur sur une subdivision avec une méthode précise et une moins précise, si suffisamment petite ok, sinon on subdivise en 2 etc.
Généralisation : méthode de Newton-Cotes par interpolation avec n+1 points par subdivision [alpha,beta]: sum_{i=0}^n f(x_i)*omega_i, poids normalisé omega_i/(beta-alpha)
Calcul des poids, exemple pour les poids de Simpson
Def. de l'ordre o d'une méthode: exact pour polynôme de degré<=o, non exact pour degré o+1. Exemples: rectangle, Simpson
Thm de majoration générique de l'erreur en C_o*M_(o+1)*h^(o+1)*largeur de l'intervalle avec M_(o+1) un majorant de la dérivee d'ordre o+1, exemple pour ordre 3, on a une constante un peu meilleure pour Simpson.
Prolongements (pour la culture generale): on peut choisir les abscisses de points d'interpolation pour optimiser l'ordre (quadratures gaussiennes)
Accélération de Richardson-Romberg avec le développement de Taylor de la formule des trapèzes en puissances paires de h (formule d'Euler-Mac Laurin), en éliminant le terme en h^2 T_1(h):=(4*T(h/2)-T(h))/(4-1) puis en h^4 T_2(h):=(16*T1(h/2)-T1(h))/(16-1), etc. Remarque: T_1 est la méthode de Simpson
Méthodes adaptatives: au lieu d'utiliser un même pas pour toutes les subdivisions, on estime l'erreur sur une subdivision avec une méthode précise et une moins précise, si suffisamment petite ok, sinon on subdivise en 2 etc.