-1 cm 23cm @percent16.5cm 10pt 0pt
UGA 2022 Mat406
Nous utiliserons Xcas,
sur les PC du DLST il se lance à partir de l’icone Xcas du bureau ou directement
depuis un navigateur (par exemple Firefox)
https://www-fourier.univ-grenoble-alpes.fr/~parisse/xcasfr.html
Vous pouvez aussi l’installer si vous disposez de votre propre PC ou Mac,
cf.
www-fourier.ujf-grenoble.fr/~parisse/install_fr
.
Si vous n’avez jamais utilisé Xcas auparavant, commencez par
parcourir le tutoriel, celui-ci est accessible depuis le menu
Aide, Debuter en calcul formel
. Lisez au moins
jusqu’au paragraphe 2.4 (vous pouvez sauter le paragraphe 2.2 sur les
chaines de caractère), puis
faites les exercices du TP de prise en main. Pour trouver
les noms de commandes, regardez d’abord dans le
menu Outils, puis Cmds si vous ne trouvez pas dans le menu Outils, ou dans
le menu Graphe qui fournit des assistants pour les représentations
graphiques.
Pour sauvegarder une session, avec Xcas PC, utilisez le menu Fich, avec Xcas web, vous pouvez vous envoyer un email contenant un lien qui sauvegarde votre session, cliquez sur l’icone d’enveloppe en haut.
Les TP qui suivent ce TP de prise en main
demandent souvent d’écrire des petits programmes, pour
cela utilisez le menu Prg nouveau programme de Xcas PC
ou tapez directement votre programme en ligne de commande
avec Xcas web (taper shift-entrée pour passer à la ligne).
Si vous voulez utiliser la syntaxe compatible avec Python,
dans Xcas PC vérifiez que python
apparait dans la ligne
d’état, sinon cliquez sur cette ligne et modifiez, dans Xcas web
validez en cliquant sur le bouton cyan Cas.
Pour plus de détails sur la programmtion,
vous pouvez consulter le paragraphe 6 du tutoriel.
|
| , |
| , eiπ/6, 4atan( |
| )−atan( |
| ) |
x8−3x7−25x6+99x5+60x4−756x3+1328x2−960x+256 |
x6−2x3+1, (−y+x)z2−xy2+x2y |
∫ |
| dx, | ∫ |
| ln(ln(x)) dx, | ∫ | ex2 dx, | ∫ | xsin(x)ex dx |
∫ |
|
| , | ∫ |
|
| dx |
| k, |
| k2, |
|
|
ln(1+x+x2), |
| , | √ |
| , |
|
⎧ ⎪ ⎨ ⎪ ⎩ |
|
A= | ⎛ ⎜ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎟ ⎠ |
On souhaite étudier des suites récurrentes (un) définies par un+1=f(un) et u0, où f est une fonction de ℝ dans ℝ, par exemple f(x)=√2+x.
Exercice 1
A1
par =sqrt(2+A0)
, puis déplacer la souris vers la partie situé en bas
à droite de la cellule A1
(le curseur souris change de forme), puis
appuyer sur le bouton de la souris et relâcher à la fin de la zone
où vous voulez copier la formule définissant A1
.
La feuille de calcul précédente donne une idée de la convergence de la suite, mais ne donne aucune information quantitative sur la vitesse de convergence. Au lieu de calculer un nombre fixé de termes de la suite, on va écrire un programme avec un test d’arrêt selon la valeur |un+1−un| comparé à un nombre positif (petit) ε fixé à l’avance. Pour éviter que le programme ne boucle indéfiniment lorsque la suite ne converge pas (ou converge trop lentement pour la machine), on fixe aussi un nombre maximal d’itération N.
Exercice 2
Écrire un programme iter
prenant en argument
la fonction f, la valeur de u0, de N et de ε, et
qui s’arrête dès que l’une des conditions suivantes est satisfaite :
Dans le premier cas le programme renverra la valeur de un+1, dans
le second cas une séquence composée de uN et de N.
Tester votre programme avec f(x)=√2+x et f(x)=x2.
On suppose que la fonction f satisfait aux hypothèses du théorème du point fixe. On notera k<1 la constante de contractance. On peut alors trouver un encadrement de la limite l de la suite (un) en fonction de un, un−1 et k.
Exercice 3
Écrire un programme iter_k
prenant en argument
la fonction f, la valeur de u0, la constante k et l’écart toléré ε,
et qui s’arrête dès que | un − l | ≤ ε.
Vérifier les hypothèses du théorème du point fixe pour f(x)=2cos(x/3)
sur [0,2] et expliciter une constante de contractance k.
Déterminer une valeur approchée de la limite de (un)
à 1e-3
près en utilisant la fonction iter_k
.
La convergence de ces suites est en général linéaire, le nombre de décimales exactes augmente de la même valeur à chaque itération. Par contre lorsqu’on est prêt d’une racine, la méthode de Newton permet en gros de multiplier par deux le nombre de décimales à chaque itération.
Exercice 4
f(x)= |
|
evalf(.,40)
sur
les différence entre 2 termes successifs).
iter_k
, trouver un encadrement de
√7 à 1e-6
près pour le point fixe.
Combien d’itérations sont nécessaires ?
Donner aussi un encadrement par la méthode de Newton en utilisant
u4.
Dans les 2 cas, on pourra
prendre une valeur initiale approchée puis entière exacte pour avoir
une valeur numérique approchée puis une fraction.
Dans certains cas, la fonction f n’est pas contractante, mais on peut réécrire l’équation à résoudre sous une autre forme avec une fonction contractante, par exemple en utilisant une fonction réciproque.
Exercice 5
Donner un encadrement à 1e-6
près d’une racine
de l’équation tan(x)=x sur l’intervalle ]3π/2,5π/2[ en
utilisant une méthode de point fixe. On observera qut tan n’est
pas contractante mais que sa fonction réciproque l’est (attention
à y ajuster correctement un multiple entier de π).
On peut aussi appliquer la méthode de Newton sur cet exemple.
(evalf(1,30)+2^(-n))-evalf(1,30)
.
Même question sur votre calculatrice si vous en avez une.evalf(.,30)
,
puis sa partie fractionnaire (frac(.)
). Proposez une commande
permettant de décider si a est un entier.F(x,y)= |
| y6 + x2 (11x2 y2−y6 −121y4−2) + |
| y8 + |
|
F(77617.0,33096.0)
ou F(evalf(77617,30),evalf(33096,30))
) et
l’autre en mode exact. Que pensez-vous de ces résultats?
Combien de chiffres significatifs faut-il pour obtenir un résultat
raisonnable en mode approché?time(a*(a+1))[0]
) du produit
de a × (a+1) pour a=10n avec n=10000,20000,40000. Comment
évolue le temps de calcul lorsque le nombre de décimales double ?powmod
et la méthode “prendre le reste modulo m après avoir
calculé an”
(vous pouvez aussi programmer la méthode rapide et la méthode
lente, cf. par exemple l’article exponentation rapide de wikipedia).P(X) = an Xn + ... + a0 |
P(X)−b0=(X−α )Q(X) |
Q(X) = bn Xn−1 + ... +b2 X + b1 |
horn
effectuant ce calcul:
on donnera en arguments le polynôme sous forme de la
liste de ces coefficients (dans l’exemple [1,0,-2,5]
) et la
valeur de α et le programme renverra P(α ).
(On pourra aussi renvoyer les coefficients de Q).
Exercice 1.
Donner une majoration indépendante de x de l’erreur commise.
(A titre d’illustration, tracer la différence T7(x)−sin(x).)
Exercice 2.
On veut approcher cos(x) à 1e-6
près
en utilisant des développements en séries entières.
T2k(x)= |
| (−1)j |
|
1e-6
de cos(x) sur [−π/2,π/2]
en justifiant et en effectuant les
étapes suivantes:
round
de Xcas) ?
Écrire une fonction qui calcule une valeur approchée à
1e-6
de cos(x) sur [−100,100] en se ramenant au
programme précédent.
Afin de tester votre fonction f et éviter d’éventuelles erreurs grossières,
faites afficher le graphe de f, disons sur l’intervalle [−10,10], puis le graphe
de la différence f−cos où cos est la fonction déjà implémentée dans Xcas.
Exercice 3
α− |
| + |
| − |
| ≤ arctan(α) ≤ α− |
| + |
|
1e-8
près de π/4= arctan(1).
| = 4 arctan( |
| ) − arctan( |
| ) |
Exercice 4
g(x)= |
|
I= | ∫ |
| g(x) dx |
Exercice 5
Cet exercice reprend les calculs de ln(x) et exp(x) discutés en cours
dans l’objectif de les illustrer par vos propres expériences sur ordinateur.
On considère ensuite la série ln2 = ∑k=0∞2/(2k+1) 32k+1. Jusqu’à quel rang faut-il aller afin de garantir une approximation à 10−5 près? Calculer cette approximation de ln2 avec Xcas. Même question pour 10−10. Conclusion?
Jusqu’à quel rang faut-il aller afin de garantir une approximation à 10−20 près? Calculer cette approximation de exp(−32) avec Xcas, d’abord en utilisant la précision standard de 53 bits, soit 16 décimales. Quel problème observez-vous? On pourra augmenter la précision des nombres flottants utilisés: quelle précision est nécessaire, environ, pour raisonnablement effectuer ce calcul?
Est-ce que ces problèmes se posent pour l’approximation de a0 = exp(−1)? Comment en déduire une approximation de exp(−32) avec un minimum d’opérations?
Exercice 6
On reprend des idées des exercices 4 et 5 pour implémenter le
calcul de la fonction
sinus intégral définie par :
Si(x)= | ∫ |
|
| dt |
∫ |
|
| dt = |
|
Exercice 1
Donner le détail des calculs avec Bézout de la décomposition
en éléments simples de :
f(x)= |
|
en déduire :
Exercice 2
Factoriser sur ℚ (factor
) et sur ℚ[i] (cfactor
)
le polynôme
P(x)=x6+x4+x3+x2+x+1. Quels sont les degrés des facteurs ?
Factoriser sur ℝ et sur ℂ le polynôme P en appliquant
factor
et cfactor
à evalf(P)
.
En regroupant les racines (commande proot
) de P, retrouver la factorisation exacte
de P dans ℝ et ℂ.
Exercice 3
Trouver une racine approchée du polynôme P ci-dessus en appliquant
la méthode de Newton avec une valeur initiale complexe aléatoire
(on ne cherchera pas à prouver la convergence sur ℂ pour
laquelle on n’a pas de théorème de niveau licence 2),
éliminer cette racine par division
euclidienne, chercher une autre racine, etc. jusqu’à obtenir
la factorisation complète de P. Comparer la valeur de P
et celle obtenue en développant le produit des X−racine.
Bonus :
Écrire une fonction qui cherche une racine d’un polynôme
en utilisant la méthode de Newton. Ajouter un test pour
être sûr que la racine du polynôme est simple.
Tester avec le polynôme P ci-dessus.
Bonus : modifier la fonction ci-dessus pour trouver toutes
les racines (lorsqu’on trouve une racine, on divise le polynôme
par X−α, et on relance la recherche de racines sur le
polynôme obtenu).
Exercice 4
Écrire une fonction qui détermine les racines rationnelles
d’un polynôme P à coefficients entiers (elles sont
de la forme p/q où q divise le coefficient
dominant de P et ± p divise son coefficient de plus bas degré).
Tester avec le polynôme P=12x5+10x4−6x3+11x2−x−6.
Exercice 5
En utilisant les suites de Sturm, déterminer le nombre
de racines du polynôme P ci-dessus sur l’intervalle
[−3,0] (faites le calcul directement avec sturmab
,
puis en appliquant l’algorithme du cours avec les fonctions
rem
pour les divisions et horner
pour évaluer
un polynôme en un point). Même question sur ℝ tout entier.
Exercice 6
Représenter sur un même graphe cos(x) et
son polynôme interpolateur de Lagrange
en utilisant les 7 points d’abscisses équidistantes {0,π/6,...,π}.
Donner une majoration de l’erreur entre ce polynome et la fonction
cos en un réel x, représenter graphiquement
cette erreur pour x ∈ [0,π]. Où l’erreur est-elle
la plus grande ?
Exercice supplémentaire
Écrire un programme calculant les coefficients du
polynôme d’interpolation de Lagrange par l’algorithme des
différences divisées.
Exercice 7
Éliminer successivement a et b
du système :
⎧ ⎪ ⎨ ⎪ ⎩ |
|
puis trouver les racines du polynôme en c, puis calculer les valeurs de b puis a correspondantes (en cherchant les racines du PGCD des 2 puis 3 équations en b puis a après remplacement de c puis b par leurs valeurs).
Exercice 1 : Calculer une valeur approchée de
∫ |
|
|
par la méthode des rectangles, du point milieu et des trapèzes
en utilisant un pas de 1/10 et de 1/100 (vous pouvez utiliser les fonctions
plotarea
, area
avec la méthode en argument, ou utiliser le
tableur ou écrire un programme effectuant ce calcul avec comme arguments
la fonction, la borne inférieure, la borne supérieure et le nombre
de subdivision). Observez numériquement
la différence entre les valeurs obtenues et la valeur exacte de
l’intégrale.
Exercice 2
Calculer le polynôme interpolateur P de Lagrange de f(x)=1/1+x2
aux points d’abscisse j/4 pour j variant de 0 à 4.
Donner un majorant de la différence entre P et f en un point
x ∈ [0,1]. Représenter graphiquement ce majorant.
Calculer une majoration de l’erreur entre l’intégrale de f
et l’intégrale de P sur [0,1].
En déduire un encadrement de π/4.
Exercice 3
On reprend le calcul de ∫01 dx/1+x mais en utilisant
un polynôme interpolateur de degré 4 sur chacune des
N subdivisions de [0,1] (de pas h=1/N). Le premier
polynôme interpolateur est donc calculé en les points
0, 1/4/N, 2/4/N, 3/4/N,1/N, le deuxième en les points
1/N,1/N+1/4/N, 1/N+2/4/N, 1/N+3/4/N,2/N, etc.
Donner en fonction de N une majoration de l’erreur commise en remplaçant
l’intégrale de 1/(1+x) par le polynôme interpolateur
sur la première subdivision [0,1/N], puis sur les autres
subdivisions, puis une majoration de l’erreur totale sur [0,1].
Déterminer une valeur de N telle que la valeur
approchée de l’intégrale ainsi calculée soit proche à 10−8 près
de ln(2). En déduire une valeur approchée à 10−8 de
ln(2).
Même question pour ∫01 dx/1+x2
et π/4 (pour majorer la dérivée n-ième de 1/1+x2,
on pourra utiliser une décomposition en éléments simples sur ℂ).
D= | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ |
E= | ⎛ ⎜ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎟ ⎠ |
Exercice 1: factorisation numérique
On représente un polynôme par la liste de ses coefficients par
ordre décroissant. Programmer une fonction calculant le polynôme
dérivé d’un polynôme.
Programmer la méthode de Newton pour déterminer une racine d’un
polynôme en utilisant la fonction horner
pour évaluer
le polynôme ou sa dérivée en un point. Programmer ensuite
la recherche de l’ensemble des racines en éliminant les racines
trouvées au fur et à mesure.
Alternative : programmer la méthode de la puissance, pour une matrice à coefficients complexes, si la matrice est à coefficients réels avec un couple de valeurs propres conjuguées empéchant la convergence, on ajoutera une constante complexe aléatoire. Testez avec des matrices de taille assez grandes.
Exercice 2: intégration
On utilise la méthode d’intégration suivante sur une subdivision
[α,β] (par interpolation en 3 points bien choisis) :
I(f)= (β−α) | ⎛ ⎜ ⎜ ⎝ |
| f | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ | + |
| f | ⎛ ⎜ ⎜ ⎝ | α+ |
| (β−α) | ⎞ ⎟ ⎟ ⎠ | + |
| f | ⎛ ⎜ ⎜ ⎝ | α+ |
| (β−α) | ⎞ ⎟ ⎟ ⎠ | ⎞ ⎟ ⎟ ⎠ |
Déterminer l’ordre de cette méthode, en déduire une majoration
de l’erreur. Programmer cette méthode pour calculer
∫ab f(t) dt en découpant l’intervalle [a,b] en N
subdivisions. Déterminer N pour que avoir une valeur approchée
de l’intégrale à 1e-8
prés pour f(x)=1/(1+x2),
a=0 et b=1.
Alternative : programmer la méthode de la puissance pour une matrice réelle symétrique pour avoir la plus grande valeur propre avec une précision moyenne. Utilisez alors la méthode des itérations inverses pour améliorer la précision. Testez avec des matrices de taille assez grandes.
Exercice 3: intégration
On reprend le calcul de ∫01 dx/1+x mais en utilisant
un polynôme interpolateur de degré 3 sur N subdivisions de [0,1]
(de pas h=1/N). Déterminer la formule d’intégration correspondante :
I(f)= (β−α) |
| wj f(xj) |
sur une subdivision [α,β], avec x0=α, x1=(2α+β)/3, x2=(α+2β)/3, x3=β, Indication : utiliser
P:=lagrange([a,(2a+b)/3,(a+2b)/3,b],[y0,y1,y2,y3])
puis intégrer P
pour x=a..b
et factoriser.
Calculer l’ordre de la méthode, puis une majoration de l’erreur.
Déterminer une valeur de N telle que la valeur
approchée de l’intégrale ainsi calculée soit proche à 10−8 près
de ln(2). En déduire une valeur approchée à 10−8 de
ln(2).
Même question pour ∫01 dx/1+x2
et π/4 (pour majorer la dérivée n-ième de 1/1+x2,
on pourra utiliser une décomposition en éléments simples sur ℂ).
Alternative : programmer la méthode de la puissance pour une matrice réelle symétrique pour avoir la plus grande valeur propre. Eliminez la plus grande valeur propre et déterminez toutes les valeurs propres de la matrice. Testez avec des matrices de taille assez grandes.
Exercice 4: intégration
On utilise la méthode d’intégration suivante sur une subdivision
[α,β] (par interpolation en 2 points bien choisis) :
I(f)= (β−α) | ⎛ ⎜ ⎜ ⎝ |
| f | ⎛ ⎜ ⎜ ⎝ |
| α+ |
| β | ⎞ ⎟ ⎟ ⎠ | + |
| f | ⎛ ⎜ ⎜ ⎝ |
| α+ |
| β | ⎞ ⎟ ⎟ ⎠ | ⎞ ⎟ ⎟ ⎠ |
Déterminer l’ordre de cette méthode, en déduire une majoration
de l’erreur. Programmer cette méthode pour calculer
∫ab f(t) dt en découpant l’intervalle [a,b] en N
subdivisions. Déterminer N pour que avoir une valeur approchée
de l’intégrale à 1e-8
prés pour f(x)=1/(1+x2),
a=0 et b=1.
Alternative : Programmer le calcul du polynome caractéristique en recherchant une relation linéaire entre les vecteurs v, ..., Anv pour un vecteur v aléatoire. S’il existe plusieurs relations non proportionnelles, on essaiera de changer de vecteur v. Si c’est encore le cas, on testera si le polynôme correspondant annule la matrice. Testez avec des matrices de taille assez grandes.
Ce document a été traduit de LATEX par HEVEA