Suite récurrente d'ordre n
Bonjour à tous,
Je me pose une question sur la méthode de résolution des suites récurrentes d'ordre n. En effet, on remarque vite que l'ensemble des solutions est un espace vectoriel de dimension n, et que toute solution s'exprime donc sous la forme : a1u1(n)+a2u2(n)+...+anu(n). Mais ce qui me gêne c'est qu'une fois arrivés à cette étape on dit : cherchons les suites géométriques de la forme r^n qui vérifient l'équation de récurrence, et là comme par magie on obtient l'équation caractéristique de la relation de récurrence, qu'on résout et on dont les solutions nous donnent exactement les suites u1,u2,u3,..,un , base de notre espace vectoriel de solutions. Par exemple les premiers éléments de cette base sont les solutions à la puissance n, puis n*les solutions à la puissance etc.
Et là vraiment je ne comprends pas : quelle est l'intuition qui nous a poussé à chercher les suites géométriques solutions de l'équation de récurrence ? Nous on sait que c'est la méthode ok , mais comment a-t-on pu penser à inventer cette méthode qui consiste à chercher des solutions particulières de nature géométrique et comme par magie on obtient l'équation caractéristique.
Le deuxième élément de la méthode que je ne comprends pas : c'est la présence de n*les solutions dans la base des solutions. Par exemple dans le cas de récurrence d'ordre 2, on a bien que dans le cas où les deux solutions r1 et r2 de l'équation caractéristique sont identiques, on "vérifie" bien (par récurrence le plus souvent) que toutes les solutions de notre relation de récurrence sont de la forme : ar^n + bnr^n , c'est quoi ce n ? Comment on y pense tout seul ? Quelle est l'intuition qui a justifié de chercher les solutions de cette forme ?
Merci beaucoup pour ces deux questions, désolé si je n'ai pas été suffisamment clair ....
Je me pose une question sur la méthode de résolution des suites récurrentes d'ordre n. En effet, on remarque vite que l'ensemble des solutions est un espace vectoriel de dimension n, et que toute solution s'exprime donc sous la forme : a1u1(n)+a2u2(n)+...+anu(n). Mais ce qui me gêne c'est qu'une fois arrivés à cette étape on dit : cherchons les suites géométriques de la forme r^n qui vérifient l'équation de récurrence, et là comme par magie on obtient l'équation caractéristique de la relation de récurrence, qu'on résout et on dont les solutions nous donnent exactement les suites u1,u2,u3,..,un , base de notre espace vectoriel de solutions. Par exemple les premiers éléments de cette base sont les solutions à la puissance n, puis n*les solutions à la puissance etc.
Et là vraiment je ne comprends pas : quelle est l'intuition qui nous a poussé à chercher les suites géométriques solutions de l'équation de récurrence ? Nous on sait que c'est la méthode ok , mais comment a-t-on pu penser à inventer cette méthode qui consiste à chercher des solutions particulières de nature géométrique et comme par magie on obtient l'équation caractéristique.
Le deuxième élément de la méthode que je ne comprends pas : c'est la présence de n*les solutions dans la base des solutions. Par exemple dans le cas de récurrence d'ordre 2, on a bien que dans le cas où les deux solutions r1 et r2 de l'équation caractéristique sont identiques, on "vérifie" bien (par récurrence le plus souvent) que toutes les solutions de notre relation de récurrence sont de la forme : ar^n + bnr^n , c'est quoi ce n ? Comment on y pense tout seul ? Quelle est l'intuition qui a justifié de chercher les solutions de cette forme ?
Merci beaucoup pour ces deux questions, désolé si je n'ai pas été suffisamment clair ....
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour ton problème néanmoins, le fait de chercher une telle base de solutions est en fait une application directe du lemme des noyaux, voir ici : http://www.les-mathematiques.net/b/c/k/node6.php
Le $n$, on ne peut pas trop y penser tout seul, sauf si on prend de la hauteur. Disons que ta relation de récurrence linéaire d'ordre $2$ soit $u_{n+2} = au_{n+1} + bu_n$ pour tout entier $n$. On peut réécrire cela matriciellement $$U_{n+1} = AU_n,$$ où $$U_n = \begin{pmatrix}u_n\\u_{n+1}\end{pmatrix}$$ et $$A = \begin{pmatrix}0&1\\b&a\end{pmatrix}.$$ On en déduit, comme dans le cas à une dimension, avec une petite récurrence que pour tout entier $n \geq 0$, $$U_n = A^nU_0=A^n\begin{pmatrix}u_0\\u_1\end{pmatrix}.$$ La prochaine étape est donc de calculer les puissances de la matrice $A$. Pour ça, le plus simple est, si on le peut, de la diagonaliser, et au pire, de la trigonaliser. Remarque que le polynôme caractéristique de $A$ est $-X(a-X)-b = X^2-aX-b$, le polynôme caractéristique de l'équation ! Si on suppose que celui-ci admet une racine (complexe) double $r$, alors la matrice $A$ n'est pas diagonalisable (sinon elle serait égale à $r I_2$), mais elle est trigonalisable : on peut trouver une matrice complexe inversible $P$ telle que $A=PDP^{-1},$ où $$D = \begin{pmatrix}r&1\\0&r\end{pmatrix}.$$ On a alors, pour tout entier $n \geq 0$, $$A^n = PD^nP^{-1},$$ et je te laisse vérifier (toujours par récurrence), que $$D^n = \begin{pmatrix}r^n&nr^{n-1}\\0&r^n\end{pmatrix}.$$ Le voilà ton $nr^{n-1}$ ! Je pose maintenant $Y_n = P^{-1}U_n = \begin{pmatrix}y_n\\ y_{n+1}\end{pmatrix},$ de sorte que $Y_n$ vérifie $$Y_n = D^nY_0 = \begin{pmatrix}y_0r^n + nr^{n-1}y_1\\r^ny_1\end{pmatrix}.$$ On retrouve ensuite $U_n = PY_n$, ce qui était notre but initial.
Tout cela se généralise très bien à des récurrences linéaires d'ordre quelconque, on voit que la clé est de savoir calculer les puissances d'une matrice, en général en utilisant la réduction des matrices.
Mais je ne comprends toujours pas d'où vient le terme nr^n (seconde question de mon précédent message) . Avec le lemme des noyaux ok cherche des solutions de type Ker(f-rI)^n , donc f=r^n et on passe à l'équation caractéristique de la relation de récurrence. Mais je ne vois toujours pas comment expliquer la présence de termes en n*r^n dans la base avec cette explication.
Merci beaucoup en tous cas déjà pour la première question c'est impeccable de comprendre les choses comme ça.
$X_{n+1} = MX_n$ et $X' = MX$
Merci beaucoup à tous !
On se place sur l'espace $E$ des suites complexes, disons, et on considère l'endomorphisme $D$ qui envoie une suite $u=(u_n)_{n\in\N}$ sur la suite $Du=v=(v_n)_{n\in\N}$ définie par : $v_n=u_{n+1}$ pour tout $n$. L'espace $F$ des suites satisfaisant à la relation de récurrence linéaire $\sum_{p=0}^da_pu_{n+p}=0$ pour tout $n$ est le noyau de $A=P(D)$ où $P$ est le polynôme $P(X)=\sum_{p=0}^da_pX^p$. On suppose $d$ minimal, c'est-à-dire $a_d\ne0$ ; on divise par $a_d$, c'est-à-dire qu'on suppose $a_d=1$. On factorise $P(X)=\prod_{k=1}^r(X-\lambda_k)^{m_k}$. Alors $F$ est la somme directe des noyaux des $(D-\lambda_k\mathrm{Id})^{m_k}$.
D'évidence, le noyau de $D-\lambda\mathrm{Id}$ est la droite des suites géométriques de rauson $\lambda$ ($u_{n+1}=\lambda u_n$...). Si par exemple tous les $m_k$ valent $1$, les solutions sont les sommes de suites géométriques dont la raison est racine de $P$.
Pour $\lambda=0$, il est facile de voir que le noyau de $D^m$ est l'espace des fonction polynomiales en $n$ de degré $\le m-1$.
Enfin, on fait de la variation de la constante : si deux suites $u$ et $v$ sont reliées par $u_n=\lambda^nv_n$ pour tout $n$, alors $u$ est dans le noyau de $(D-\lambda\mathrm{Id})^m$ si et seulement si $v$ est dans celui de $D^m$. Voilà l'usine à lapin cachée sous le chapeau.
C'est ce que j'avais compris de l'article envoyé par skyffer plus haut dans la discussion. Mais tu rajoutes un point intéressant, le lien entre réciprocité quadratique et lemme des noyaux. Pourrais-tu m'en dire plus ? J'ai fait une vague recherche sur internet je suis arrivé sur des choses très compliquées du genre de "Théorème de Frobenius-Zolotarev" ou une étude des "modules de a-torsion"... bref je ne sais pas trop à quoi tu faisais référence dans ta résonance entre réciprocité quadratique et lemme des noyaux.
Vraiment désolé si je pose une question bête...
Merci pour tout en tous cas.