cours 2022/23

Modérateur : xcasadmin

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

cours 2022/23

Message par parisse » lun. janv. 16, 2023 5:54 pm

Cours 1/12 (16 janvier)
1/ Présentation du module
2/ Suites récurrentes à 1 cran: représentation graphique en toile d'araignée, exemples
3/ théorème du point fixe.
Définition de fonction 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-l|<=|u_{n+1}-u_n|/(1-k) (à postériori),
exemples, preuve.
Exemple : f(x)=cos(x) sur [0,pi/2] non sur [0,1] oui avec k=sin(1)
On a un peu mieux que l'estimation à priori car au bout de quelques itérations on peut améliorer k (proche de |f'(l)|)
4/ Vitesse de convergence linéaire pour le point fixe
5/ Comparaison avec la dichotomie.
Si k>1/2 il vaut mieux utiliser la dichotomie. Si k<1/2 le point fixe. On a intérêt à choisir des points fixes tels que |f'(l)| soit le plus petit possible. Exemple f(x)=1/2*(x+2/x)

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

Re: cours 2022/23

Message par parisse » lun. janv. 23, 2023 4:59 pm

Cours 2/12 (23 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 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.
Calcul des premiers termes avec le tableur de Xcas et 50 digits u0=evalf(2,50)
3/ définition de convexité, critère 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 décroissant. De plus 0<= u_n-r <= f(u_n)/f'(r). Variantes selon convexité/concavité et signe de f'(r).
Remarque sur les erreurs d'arrondi qui deviennent importantes lorsque u_n s'approche de r.
Calcul des premiers termes avec le tableur de Xcas en calcul exact avec u0=2.
Prise en main de Xcas sur les calculatrices.

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

Re: cours 2022/23

Message par parisse » mar. janv. 31, 2023 2:47 pm

Cours 3 sur 12 du 30/1
Calculatrice: écriture d'une fonction pour calculer les itérées d'une suite récurrente

Représentation des objets mathématiques sur machine
1/ Entiers:
-> division euclidienne des entiers, écriture 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 +,*,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
-> 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)

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

Re: cours 2022/23

Message par parisse » lun. févr. 06, 2023 5:05 pm

Cours du 6/2 (4ème cours)
* Produit 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 de 2 flottants, problème de la compensation et perte possible de nombreux chiffres significatifs en une seule opération
* Calcul de f(x): erreur relative 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é
* Calcul approché de f'(x), erreur absolue au moins précision*|f(x)|/h et erreur de Taylor en O(h) ou O(h^2), choix optimal de h
* méthodes pour éviter de perdre en précision, réécriture lorsque c'est possible, sommation de termes en commençant par les plus petits, compensation des erreurs d'arrondis (cf. poly en ligne)
* calcul d'erreur trop fastidieux, utilisation de flottants multi-précision, arithmétique d'intervalle ou sensibilité à la variation des paramètres

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

Re: cours 2022/23

Message par parisse » lun. févr. 20, 2023 5:23 pm

cours 5 sur 12 du lundi 20 fevrier:
Calcul des fonctions usuelles et séries : 1ère partie.
- formule de Taylor avec reste en fonction de la derivee n+1-ieme.
- exemple de la fonction exponentielle, Représentation de exp(x) et de T_n(f)(x) pour n=1,2,3.
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). 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 = floor(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. Exemple tan(x)

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

Re: cours 2022/23

Message par parisse » lun. févr. 27, 2023 5:37 pm

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
Def. de série entière comme polynome "de degré infini". Déf de rayon de convergence.
Thm de 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
Calcul de ln(2)=-ln(1-1/2) à une précision donnée.
Thm (admis) sur les opérations (+,-,*,inv si a0!=0, composition si b0=0, dérivation, intégration).

Autre possibilité de majoration avec les séries alternées.

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

Re: cours 2022/23

Message par parisse » lun. mars 06, 2023 6:15 pm

cours 7 sur 12:
* 3 possibilités pour majorer le reste: dvpt de Taylor, séries entières, séries alternées. Exemple où les 3 s'appliquent: sin(x).
* Vitesse de convergence comme une série géométrique, parfois un peu plus vite (1/n! pour exp) mais reste quand même essentiellement linéaire.
* Réduction d'argument pour accélérer la convergence, éviter les compensations/pertes de précision
* 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. Au lieu d'une cinquantaine de termes, on descend à une vingtaine.
* On aurait pu aussi faire la méthode de Newton pour résoudre e^x-m=0 a partir de u0 une valeur approchée par excès de ln(m), par ex. a 1e-4, en 2 itérations on devrait être a 1e-16. L'idée étant que le calcul de exp est plus efficace.
* Autre application: 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.
* Autre application: solution série entière de certaines équations différentielles, exemple de l'équation de Bessel pour m=0.

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

Re: cours 2022/23

Message par parisse » lun. mars 20, 2023 4:49 pm

cours 8 sur 12 du 20 mars:
Chapitre 4 Polynômes
Rappels: Horner, division euclidienne, algorithme d'Euclide, identité de Bezout (horner, quo, rem, quorem, gcd, egcd, abcuv)
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 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 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: B(z,degree(P)*abs(P(z)/P'(z)) 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^3+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.

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

Re: cours 2022/23

Message par parisse » lun. mars 27, 2023 4:21 pm

Application de la factorisation à la décomposition en éléments 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'intégrale de 1/(x^3-1)
Exemple d'élimination des multiplicités au dénominateur avec Bézout 1/(x^2+1)^2 on écrit 1 en fonction de x^2+1 et sa dérivée (Bezout) et on applique l'intégration par parties
Autre exemple d'application: calcul du développement en série entière d'une fraction rationnelle

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.

Majoration des racines complexes d'un polynôme par m:=max|coeff(P)|/|coeff_dominant(P)|+1,
Application: cela permet de compter les 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.

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

Re: cours 2022/23

Message par parisse » lun. avr. 03, 2023 3:40 pm

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=alpha_0+(x-x0)*(alpha_1+...)
Preuve par récurrence. Exemple avec n=2.
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)

Méthode de calcul "à la Horner" du polynôme d'interpolation donné par la liste des points d'interpolation et des différences divisées alpha_i en 3n opérations.
Calcul efficace des alpha_i par l'algorithme des différences divisées
Justification des différences divisées.

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

Re: cours 2022/23

Message par parisse » lun. avr. 17, 2023 3:54 pm

Chapitre intégration numérique.
[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.
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.
viewtopic.php?f=30&t=2862
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.
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] puis on résoud 72/2880*1/N^4=1e-6, on trouve 13 subdivisions. Vérification.

Généralisation: interpolation par un polynôme en 1 ou plusieurs points de chaque subdivision.

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

Re: cours 2022/23

Message par parisse » lun. avr. 24, 2023 3:55 pm

Dernier cours du 24 avril:
* 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 n d'une méthode: exact pour polynôme de degré<=n, non exact pour degré n+1
* exemples: rectangle, point milieu, trapèzes, Simpson
* thm de majoration générique de l'erreur en C_n*M_(n+1)*h^(n+1)*largeur de l'intervalle avec M_(n+1) un majorant de la dérivee d'ordre n+1, exemples on a une constante un peu meilleure.
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.
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 la subdivision où l'erreur est la plus grande

Répondre