cours 2021/2022

Modérateur : xcasadmin

Répondre
parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

cours 2021/2022

Message par parisse » lun. janv. 17, 2022 5:30 pm

Cours 1/12 (17 janvier)
1/ Presentation du module
2/ Rappel suites récurrentes a 1 cran: representation graphique en toile d'araignee
3/ théorème du point fixe.
Définition de fonction contractante f:I=[a,b]->I et |f(y)-f(x)|<=k|y-x| avec k<1 (oups, il faut que je corrige la prochaine fois j'ai mis le k<1 dans le thm du point fixe seulement, pas dans la def de contractante)
Exemples : 1/ f(x)=cos(x), 2/ f(x)=x^3/2, 3/ f(x)=2/x ne convergent pas graphiquement, 4/ f(x)=(x+2)/(x+1) semble converger, 5/ 1/2*(x+2/x) semble converger, et même très rapidement.
Exemple 1 et 4/ avec le TAF
Enoncé du théorème du point fixe et estimations |u_n-l|<=k^n|b-a|, |u_n-l|<=|u_{n+1}-u_n|/(1-k),
exemples, preuve.
Vitesse de convergence linéaire.
Remarques: -> Permet de résoudre certaines équations non résolubles analytiquement (par exemple recherche de V tel que V-e*sin(V)=t).

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. janv. 24, 2022 4:42 pm

Cours 2/12 (24 janvier):
Methode de Newton:
1/ representation graphique de la methode de resolution de f(x)=0, calcul de u_(n+1) en fonction de u_n sous la forme g(u_n), Newton est un cas particulier de point fixe avec g'(r)=0, calcul de g 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''| pres de r. Calcul de m et M pour f(x)=x^2-2, r=sqrt(2). Calcul difficile en général.
Illustration de ce qui peut se passer lorsque u0 n'est pas proche de r avec les bassins d'attraction viewtopic.php?f=34&p=12401#p12401
3/ definition de convexite, critere f''>=0 pour f C^2 sur I
thm de convergence si f C^2 sur [r,b], f(r)=0, f'(r)>0, f''>=0, u_n converge si u_0 appartient a [r,b] en decroissant. De plus 0<= u_n-r <= f(u_n)/f'(r). Variantes selon convexité/concavite et signe de f'(r).
Remarque sur les erreurs d'arrondi qui deviennent importantes lorsque u_n s'approche de r. Calcul avec flottants multiprecision ou avec des rationnels pour x^2-2.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. janv. 31, 2022 11:17 am

Cours 3 sur 12 du 31/1
Prise en main de la calculatrice.

Representation des objets mathématiques sur machine
1/ Entiers:
-> division euclidienne des entiers, ecriture en base b, opération inverse = évaluation du polynome dont les coeffs sont l'écriture en base b en X=b. Exemple en base 10, 2.
-> entiers machines, rapide mais limitation en taille
-> entiers longs (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 + et * en base b=2.
2/ Reels:
-> virgule fixe, peu adapté au calcul scientifique
-> virgule flottante: reel r représenté approximativement par q=m*b^e, ou m est la mantisse (n caractères) et e l'exposant, b la base
-> 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).

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. févr. 07, 2022 12:33 pm

cours 4 sur 12 du 7 fevrier
* Erreur d'arrondi pour les flottants normalises <= 1/2/b^(n-1)
* Produit et somme/difference de 2 flottants.
* erreur relative pour un produit, au 1er ordre <= la somme des erreurs relatives. + un arrondi
* erreur absolue pour une somme/différence, problème de la compensation et perte possible de nombreux chiffres significatifs en une seule opération
* conditionnement pour le calcul de f(x): erreur relative multipliee au 1er ordre par |x*f'(x)/f(x)|, par ex pour exp, si x est de l'ordre de 100, on perd 2 decimales, independamment de l'algorithme utilise
* methodes pour eviter de perdre en precision, reecriture lorsque c'est possible, sommation de termes en commencant par les plus petits, compensation des erreurs d'arrondis (cf. poly en ligne)
* calcul d'erreur trop fastidieux, utilisation de flottants multi-précision, arithmetique d'intervalle ou sensibilité à la variation des paramètres

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » mer. févr. 16, 2022 12:59 pm

cours 5 sur 12 du lundi 14 fevrier:
- correction de Newton pour resoudre tan(x)=x sur ]3*pi/2,5*pi/2[
- formule de Taylor avec reste en fonction de la derivee n+1-ieme
- exemple de la fonction exponentielle, majoration du reste, convergence du reste, calcul pour x=1, x=10, x<0
- problème du n grand pour avoir R_n petit si |x| est grand. Problème des calculs intermédiaires grand avec résultat petit par ex. pour exp(-10). Solution prendre exp(-x)=1/exp(x)
- reduction d'argument via exp(2x)=exp(x)^2,
- discussion sur l'erreur de exp(x) en fonction de celle sur x
- autre reduction possible via x=q*ln(2)+r avec q entier
- traitements analogues possibles pour sin/cos. Mais ne convient pas si on ne sait pas facilement exprimer la derivee n-ieme de f. Exemple tan(x)

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. févr. 28, 2022 12:33 pm

Cours 6 du 28 fevrier
Algorithme de Horner
Serie de Taylor: cas de ln(1+x) la majoration du reste est mauvaise pour x=-1/2 ou <-1/2 -> autre theorie
Def. de serie entiere comme polynome "de degré infini", somme partielle, convergence exemple exp(x), serie geometrique sum_k x^k. Convergence dans un disque de rayon R ou sur C.
Thm de majoration du reste pour |x|<|x_0| lorsque |a_k x_0^k| <= M
Preuve
Corollaire: existence du rayon de convergence
Exemple si |a_k|=1, on peut prendre x_0=1 et M=1
Thm (admis) sur les operations (+,-,*,inv si a0!=0, composition si b0=0, derivation, integration)
Exemple:integration de sum_k x^k -> -ln(1-x), on peut aussi prendre a_k=1 et x_0=1, M=1 -> calcul de ln(2)=-ln(1-1/2).
Calcul de ln(x) en ecrivant x=m*2^e avec m entre 1/2 et 1.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. mars 07, 2022 12:07 pm

Cours 7 sur 7 mars:
* Rappel majoration erreur pour dvpt de Taylor et series entieres
* Attention: f(x) n'est pas toujours egal a son dvpt de Taylor a l'infini meme si il converge (contre-exemple exp(-1/x^2))
* Majoration pour les series alternees, attention bien verifier que le terme general (sans le signe) *decroit* vers 0. Exemple ln(1+x) pour 0<x<1. Les fonctions trigo.
* Reduction d'argument pour eviter les compensations/pertes de precision (par ex. sin(10) ou exp(-10)) et pour accelerer le calcul
* Exemple d'optimisation pour ln(m) avec 1/2<m<1, on pose m=(1+t)/(1-t) avec |t|<1/3 convergence plus rapide et 1 terme sur 2 disparait
* On aurait pu aussi faire la methode de Newton pour resoudre e^x-m=0 a partir de u0 une valeur approchee par exces de ln(m), par ex. a 1e-4, en 2 iterations on devrait etre a 1e-16. L'idee etant que le developpement de exp converge plus vite que celui du log, grace au n!
* Remarque: pour exp, on utilise des fractions rationnelles qui ont le meme developpement de Taylor en 0 et ont de la symetrie (pade(exp(x),x,10,6)), on peut calculer exp avec 15 chiffres en 15 operations elementaires.
* Autre application: calcul de integrate(exp(-t^2),t=0..x)
pour x^2<=1, ca converge bien, au-dela on a les problemes de perte de precision et de nombre de termes a calculer qui augmente sans pouvoir faire de reduction d'argument. La solution consiste a faire un developpement asymptotique pour x grand (par une integration par parties apres changement de variables t^2=u), mais ce developpement diverge, on ne peut pas avoir n'importe quelle precision de cette maniere. Pour les valeurs intermediaires, on utilisera de l'approximation polynomiale.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. mars 21, 2022 11:17 am

cours 8/12 du 21 mars:
Chapitre 4 Polynomes
Rappels: Horner, division euclidienne, algorithme d'Euclide, identite de Bezout (horner, quo, rem, quorem, gcd, egcd)
Factorisation des polynomes:
Distinction entre factorisation exacte sur Q[X] et (rationnel complexe)[X] et approchee sur R[X] et C[X] selon les coefficients du polynome, les facteurs sont de degre 1 ou 2 ou 1 ou de degres quelconques, exemple factor(x^3+x+1), factor(x^3+x+1.0), factor(x^3+x+1.0,i)

Thm: Soit G=gcd(P,P'), alors Q=P/G a les memes racines que P avec multiplicite 1. On peut continuer la factorisation sur les 2 facteurs Q/gcd(Q,G) et gcd(Q,G).

Recherche des racines rationnelles d'un polynome de Q[X] sous la forme +/- num/deno avec num divise le coefficient constant et deno divise le coeff dominant.
Exemple x^3+x+1 (pas de racines rationnelles), 2*x^3-x^2+x+1
Remarque: ce n'est pas efficace (s'il y a beaucoup de diviseurs par exemple)

Factorisation approchee: sur R, dichotomie ou methode 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 meme essayer Newton et s'arreter lorsque P(z) est assez petit. On a alors:
Thm: B(z,degree(P)*abs(P(z)/P'(z)) contient au moins une racine complexe de P.
Demo de P'/P=sum_{z_j racine de P} 1/(x-z_j)
Preuve du thm par l'absurde.
Exemple pour p:=x^3+x+1; q:=p'; R:=3*p(x=34/100-116/100*i)/q(x=34/100-116/100*i); evalf(abs(R)) vaut 6e-3.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » jeu. mars 31, 2022 5:12 pm

Cours 9 sur 12 du 28 mars:
Elimination d'une racine, recherche des autres racines approchees apres elimination, amelioration de precision en faisant une derniere iteration de Newton sur le polynome de depart
factor/cfactor avec argument exact/approche.
Recherche de racines rationnelles d'un polynome a coeffs entiers: numerateur divise coeff dominant, denominateur divise coeff constant.
Application de la factorisation a la decomposition en elements simples
Si N/D est une fraction propre (degre(N)<degre(D)) et si D a des racines simples z_j, alors N/D=sum_j N/D'(z_j)/(X-z_j)
Exemple calcul d'integrale en 2 temps 1/(x^3+x+1)/(x^2-x+1)
factorisation exacte+Bezout -> deux integrales, puis pour le terme en degre 3 on fait une factorisation approchee
Remarque: exemple d'elimination des multiplicites au denominateur avec Bezout 1/(x^4+1)^2 on ecrit 1 en fonction de x^4+1 et sa derivee et on applique integration par parties

Localisation des racines reelles d'un polynome a coefficients reels: def de la suite de Sturm pour P un polynome 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)

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. avr. 04, 2022 10:34 am

Cours 10 sur 12:
Preuve de Sturm.
Majoration des racines complexes d'un polynome par m:=max|coeff(P)|/|coeff_dominant(P)|+1, ce qui permet de compter les racines reelles de P avec Sturm sur [-m,m]
Isolation des racines avec Sturm et dichotomie sur [a,b] (au debut 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.
Theoreme d'existence et unicite de P de degre<=n tel que P(x_i)=y_i pour 0<=i<=n
Preuve par recurrence.
Theoreme 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,2] en -1, -0.5, 0, 0.5, 1, 1.5, 2.0.
Erreur assez bien estimee par le theoreme de majoration (avec majoration de la derivee 7-ieme par 10). Observation: l'erreur est plus grande pres des bords de l'intervalle si on prend des points equidistribues.

Calcul efficace par l'algorithme des differences divisees (debut).

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. avr. 11, 2022 10:25 am

cours 11 sur 12:
Justification des differences divisees.
Methode de calcul "a la Horner" du polynome d'interpolation avec les differences divisees, interet du point de vue erreur d'arrondis par rapport au developpement.
Illustration du fait qu'augmenter le nombre de points d'interpolation de maniere equirepartie peut aggraver l'erreur d'interpolation sur l'intervalle d'interpolation. Cf ci-dessous, essayer avec n>10.
session Xcas
Remarque: la solution c'est de choisir mieux la repartition des points d'interpolation, pour optimiser le facteur product(x-x_i), sur [-1,1] on utilise les abscisses du polynome Tn(cos(t))=cos(n*t)

Chapitre integration numerique.
[a,b] subdivise en N intervalles [alpha,beta] de largeur h=(b-a)/N ou on interpole f par un polynome de degre 0, 1, 2 ou plus.
Degre 0: rectangles gauches/droits, point milieu
Degre 1: trapezes
Degre 2: Simpson
Formules de calcul.
Illustration sur la fonction cos a la machine de la valeur de l'ecart entre formule et valeur de l'integrale lorsque h varie, en h, h^2 et h^4.
Thm majoration de l'erreur en M_1*h/2, M_2*h^2/24, M_2*h^2/12 et M_4*h^4/2880
Preuve sauf pour Simpson.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » lun. avr. 25, 2022 3:38 pm

cours 12 sur 12 du 25 avril:
* methode par interpolation avec N+1 points par subdivision [alpha,beta]: sum_{i=0}^N f(x_i)*omega_i, poids omega_i et poids normalise omega_i/(beta-alpha)
* calcul des poids: exemple pour un des poids de Simpson
* def. de l'ordre n d'une methode: exact pour polynome de degre<=n, non exacte pour degre n+1
* exemples: rectangle, point milieu, trapezes, Simpson
* thm de majoration generique de l'erreur en C_n*M_(n+1)*h^(n+1)*largeur de l'intervalle avec M_(n+1) un majorant de la derivee d'ordre n+1
* interet d'avoir une puissance de h grande
Prolongements (pour la culture generale): choix des abscisses de points d'interpolation pour optimiser l'ordre (quadratures gaussiennes)
methodes adaptatives: on estime l'erreur, si suffisament petite ok, sinon on subdivise en 2 et on recommence la ou l'erreur est la plus grande
Acceleration de Richardson-Romberg avec le developpement de Taylor de la formule des trapezes en h, en eliminant 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.

Répondre