Convergence de suites - Matlab

Le problème exposé dans ce sujet a été résolu.

Bonjour à tous,

Je dois faire un algorithme/script sur Matlab pour tester la convergence de ces deux suites: % ${x_n} = a{x_{n - 1}} + b{x_{n - 2}}$ et ${y_n} = \frac{{a{y_{n - 1}} + b{y_{n - 2}}}}{{{y_{n - 1}}}}$ avec différents paramètres $a$ et $b$ et $x_{n-1}$ $x_{n-2}$ les deux premiers éléments de $x_n$ (idem pour y). On choisit de rentrer les coefficient $a$ et $b$ sous forme de vecteur coeff = [a, b] et les deux premières valeurs x = [ ${x_{n - 1}}$, ${x_{n - 2}}$ ]

Dans ma fonction testBoundaries, je regarde la convergence des suites (suivant la suite appelée). isBound =3 si j'ai un Sup et un Inf. isBound = 0 si elle diverge.

J'ai un problème avec une des suites que je teste, c'est la suiteY (cf. seriesFunY) avec les paramètres coeff=[0.5,-0.2] et x0=[1,0]. Elle me dit qu'elle converge alors qu'elle diverge grossièrement (clair suivant le plot effectué). Pour X ça fonctionne bien.

Voici les codes importants pour comprendre ce que je dis:

seriesFunY:

1
2
3
4
5
6
7
function yn = seriesFunY(y2, y1, a, b) 
switch nargin
    case 4
        yn = (a*y2 + b*y1)/y2; %scalar
    case 2
        yn = (y1(1)*y2(1)+y1(2)*y2(2))/y2(1);%vector
end

CalcSeries

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function x = calcSeries(seriesFun, coeff, x0, N)
x=zeros(1,N);
x(1)=x0(2);
x(2)=x0(1);
for i=3:N
    x0=[x(i-1),x(i-2)];
    x(i) = seriesFun(x0, coeff);
end
plot(x,'--')
end

-> Sert à calculer les N premiers termes de la suite.

callCalcSeries:

1
2
3
4
5
x0=[1,0];
coeff=[0.5,-0.2];
N=100000;
seriesFun=@seriesFunY;
x=calcSeries(seriesFun,coeff,x0,N);

(J'appelle la suite Y avec les paramètres comme dit avant)

TestBoudaries:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
function [isBound,lowerbound,upperbound]= testBoundaries(seriesFun,p,errorThreshold,maxsteps)%hm2c
x(2)=p.a; %initialise x(1) et x(2)
x(1)=p.b;
i=2;

while i<maxsteps && abs(x(i)-x(i-1))>errorThreshold
    x(i+1)=seriesFun(x(i),x(i-1),p.c,p.d);%call the function seriesFunX or Y

    i=i+1;
end

switch nargout
    case 1

        if abs(x(i)-x(i-1))<errorThreshold && x(i)~=Inf && x(i)~=-Inf %Inf-Inf=0 and is < errorThreshold
        isBound=3;

    else if abs(x(i)-x(i-1))>errorThreshold%if it diverges not to +/- Inf the difference is > errorThreshold and it has no bound
        isBound=0;

        else if x(i)==Inf
                isBound=1;%the case with no bound is already done so we verify only this condition to see if it has a lowerbound
            else if x(i)==-Inf
                isBound=2;%also only this condition has to be verified
                end
            end
        end
        end

    case 3

        if abs(x(i)-x(i-1))<errorThreshold && x(i)~=Inf && x(i)~=-Inf %Inf-Inf=0 and is < errorThreshold
        isBound=3;
        upperbound=max(x);
        lowerbound=min(x);


    else if abs(x(i)-x(i-1))>errorThreshold%if it diverges not to +/- Inf the difference is > errorThreshold and it has no bound
        isBound=0;
        upperbound=NaN;
        lowerbound=NaN;


        else if x(i)==Inf
                isBound=1;%the case with no bound is already done so we verify only this condition to see if it has a lowerbound
                upperbound=NaN;
                lowerbound=min(x);

            else if x(i)==-Inf
                isBound=2;%also only this condition has to be verified
                upperbound=max(x);
                lowerbound=NaN;
                end
            end
        end
        end
end

Qui teste si elle est bornée. Le problème doit sûrement venir d'ici.

CallTestBoundaries: (pour appeler la fonction testBoundaries)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
x0=[1,0];
coeff=[0.5,-0.2];
p.a=x0(1);%initialize x(1),x(2) and the coeff in a structure p to have only one input
p.b=x0(2);
p.c=coeff(1);
p.d=coeff(2);
seriesFun=@seriesFunY;
errorThreshold=10^-6;
maxsteps=10^6;
[isBound,lowerbound,upperbound]=testBoundaries(seriesFun,p,errorThreshold,maxsteps)

J'aimerais aussi essayer de faire un cas pour des suites plus exotiques avec des cas isBound = 2 si la suite possède juste une borne supérieure mais pas inférieure (diverge en - infini et converge vers une certaine valeur en +infini par exemple). Je sais pas si c'est vraiment possible. Ca doit être beaucoup plus compliqué ?

Merci d'avance!

+0 -0

J'ai du mal à suivre ce que tu veux faire. Ton code est chaotique.

$y$ semble être un genre de suite oscillante, elle ne converge donc probablement pas. Je n'ai pas réussi à le montrer cependant.

Es-tu sûr que les deux derniers termes calculés ne sont pas très proches sans pour autant que la suite converge ?

Merci pour ta réponse. Mon code est sûrement très chaotique étant assez mauvais en programmation!

$y$ semble être un genre de suite oscillante, elle ne converge donc probablement pas. Je n'ai pas réussi à le montrer cependant.

Es-tu sûr que les deux derniers termes calculés ne sont pas très proches sans pour autant que la suite converge ?

Aabu

Elle diverge. C'est sûr. C'est sûrement parce que ces deux termes sont très proches qu'elle me dit qu'elle est bornée (et convergente) mais je vois pas pourquoi car le "pas d'erreur" est fixé à 10-6 ce qui est petit et c'est censé marcher d'après l'énoncé.

PS: Comment rendre ce code plus propre ?

+0 -0

Hello,

Je suis comme Aabu, j'ai un peu de mal à suivre ton code… Cela dit, par curiosité, j'ai généré les premiers termes de la suite, et la représentation graphique permet de comprendre ce qui peut coincer pour déterminer numériquement qu'elle est divergente.

Vu de loin, la suite ne semble en effet pas converger parce qu'il y a toujours des points isolés bien au-dessus des autres :

Premiers termes de la suite y(n)

Et si on zoome un peu (beaucoup) :

Zoom sur le plot de y(n)

Il y a donc deux choses qui rendent difficile l'évaluation du caractère divergent de $y(n)$ par méthode numérique :

  • les valeurs maximales sont très isolées et grandissent lentement, donnant l'impression que la suite est effectivement bornée si on échantillonne sur un intervalle trop petit ;
  • la majorité des valeurs oscillent en gros entre -1 et 1, avec des valeurs successives parfois très proches, rendant impuissant l'utilisation d'un seuil de différence entre les valeurs successives de la suite.

Pour référence, j'ai généré les points avec le code Haskell suivant puis plotté avec gnuplot :

1
2
3
4
5
6
7
ySequence :: Double -> Double -> (Double, Double) -> [Double]
ySequence a b seed@(y0,_) = y0:(map snd $ iterate go seed)
    where go (yn2, yn1) = (yn1, (a*yn1 + b*yn2)/yn1)

yn = ySequence 0.5 (-0.2) (0, 1)

main = writeFile "y_seq" $ unlines $ map show $ take 10000 yn
+1 -0

Merci adri1. Qu'est-ce que vous ne trouvez pas clair et que je peux expliquer pour que vous puissiez mieux m'aider ? :) Je suppose testBoudaries… Je pensais mettre quelque chose comme ceci:

1
2
delta_n = abs(x(i)-x(i-1)); %delta n 
delta_n1 = abs(x(i-1)-x(i-2));%delta (n-1)

pour plus de précision (?) pour faire $\Delta n = \left| {{x_n} - {x_{n - 1}}} \right|$ puis ${\Delta _{n - 1}} - {\Delta _n} < errorTreshold$ . Ceci donnerait au final dans testBondaries:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function [isBound,lowerbound,upperbound]= testBoundaries(seriesFun,p,errorThreshold,maxsteps)%hm2c
x(2)=p.a; %initialise x(1) et x(2)
x(1)=p.b;
i=3;

while i<maxsteps && abs(x(i)-x(i-1))>errorThreshold
    x(i+1)=seriesFun(x(i),x(i-1),p.c,p.d);%call the function seriesFunX or Y
    delta_n = abs(x(i)-x(i-1)); %delta n 
    delta_n1 = abs(x(i-1)-x(i-2));%delta (n-1)

    i = i +1;
end

switch nargout
    case 1
      if abs(delta_n1 - delta_n)<errorThreshold && x(i)~=Inf && x(i)~=-Inf %Inf-Inf=0 and is < errorThreshold
        isBound=3;

      else if abs(delta_n1 - delta_n)>errorThreshold%if it diverges not to +/- Inf the difference is > errorThreshold and it has no bound
        isBound=0;

      else if x(i)==Inf
                isBound=1;%the case with no bound is already done so we verify only this condition to see if it has a lowerbound
      else if x(i)==-Inf
                isBound=2;%also only this condition has to be verified
      end
      end
      end 
      end
    case 3
      if abs(delta_n1 - delta_n)<errorThreshold && x(i)~=Inf && x(i)~=-Inf %Inf-Inf=0 and is < errorThreshold
        isBound=3;
        upperbound=max(x);
        lowerbound=min(x);
      else if abs(x(i)-x(i-1))>errorThreshold%if it diverges not to +/- Inf the difference is > errorThreshold and it has no bound
        isBound=0;
        upperbound=NaN;
        lowerbound=NaN;
      else if x(i)==Inf
         isBound=1;%the case with no bound is already done so we verify only this condition to see if it has a lowerbound
         upperbound=NaN;
         lowerbound=min(x);
      else if x(i)==-Inf
         isBound=2;%also only this condition has to be verified
         upperbound=max(x);
         lowerbound=NaN;
      end
      end
      end
      end
end

Cette fois ça ne compile plus. Erreurs dans la première while (l.7) apparemment mais de toute façon je ne sais pas si c'est une solution possible.

+0 -0

Salut,

Pour rendre ton code plus clair, tu peux déjà éviter de dupliquer des portions de code : ton calcSeries ne sert à rien, ou alors il faut l'étendre pour remplacer le début de testBoundaries.

Ensuite, tu peux aussi éviter de créer des complications artificielles : seriesFunY utilise un switch nargin assez maladroit. On dirait que tu n'as pas réussi à choisir l'interface de ta fonction ; il vaut mieux choisir une des deux. Ma préférence va à celle avec quatre arguments. Réserve les arguments en nombre variable pour les fonctions avec des valeurs d'argument par défaut (regarde la doc à ce niveau-là, elle regorge de tels exemples).

Le switch nargout ne sert à rien non plus. Renvoie tous les arguments, et il me semble que l'utilisateur pourra faire le tri (de toute façon, c'est toi…). Il y a d'ailleurs des morceaux de code dupliqués dans ce switch.

+0 -0

Salut,

Pour rendre ton code plus clair, tu peux déjà éviter de dupliquer des portions de code : ton calcSeries ne sert à rien, ou alors il faut l'étendre pour remplacer le début de testBoundaries.

Ensuite, tu peux aussi éviter de créer des complications artificielles : seriesFunY utilise un switch nargin assez maladroit. On dirait que tu n'as pas réussi à choisir l'interface de ta fonction ; il vaut mieux choisir une des deux. Ma préférence va à celle avec quatre arguments. Réserve les arguments en nombre variable pour les fonctions avec des valeurs d'argument par défaut (regarde la doc à ce niveau-là, elle regorge de tels exemples).

Le switch nargout ne sert à rien non plus. Renvoie tous les arguments, et il me semble que l'utilisateur pourra faire le tri (de toute façon, c'est toi…). Il y a d'ailleurs des morceaux de code dupliqués dans ce switch.

Aabu

Ok, merci des conseils je vois ce que tu veux dire maintenant. Ce code a été écrit dans le cadre d'un exercice guidé qu'on nous a donné (toujours pas de correction…) et toutes les fonctions que j'ai écrit ont été demandées en fait. C'est sûrement pas le plus optimal et facile mais on nous a demandé a) créer seriesFunY b) calcSeries c) TestBoundaries + celles pour appeler les fonctions. C'est surtout pour nous faire comprendre comment appliquer l'utilisation de nargin et nargout par exemple qu'on nous demande de les mettre explicitement :) (Je trouve aussi que la notation en vecteurs est débile)

Edit: Mais du coup vous voyez pas vraiment d'où ça peut venir ? Cette idée de delta pourrait pas améliorer la chose (voir post précédent)

+0 -0

Mais du coup vous voyez pas vraiment d'où ça peut venir ?

Il me semble que mon post est assez clair là-dessus, la convergence de la suite que tu étudies est intrinsèquement difficile à déterminer numériquement à cause des valeurs proches et du fait que les maxima locaux sont éloignés les uns des autres.

Cette idée de delta pourrait pas améliorer la chose (voir post précédent)

$|\Delta_{n-1}-\Delta_n|$ va juste valoir $|2x_{n-1}-x_{n-2}-x_n|$ ou $|x_n-x_{n-2}|$ selon si la suite est strictement croissante/décroissante ou non sur les trois points. Il n'y a pas de raison particulière pour que ce critère soit pertinent…

Ok, merci des conseils je vois ce que tu veux dire maintenant. Ce code a été écrit dans le cadre d'un exercice guidé qu'on nous a donné (toujours pas de correction…) et toutes les fonctions que j'ai écrit ont été demandées en fait. C'est sûrement pas le plus optimal et facile mais on nous a demandé a) créer seriesFunY b) calcSeries c) TestBoundaries + celles pour appeler les fonctions. C'est surtout pour nous faire comprendre comment appliquer l'utilisation de nargin et nargout par exemple qu'on nous demande de les mettre explicitement :)

sotibio

Je vois l'idée. Autant manipuler les fonctions est intéressant (en particulier le passage par argument à des fonctions génériques), autant l'utilisation de nargin et nargout est vraiment secondaire. Il y a sûrement d'autres choses plus utiles à apprendre avant. :-D

Merci à vous deux. Peut-être que c'est un coup de bol mais en mettant

1
2
3
delta_n = abs(x(i)-x(i-1)); %delta n 
delta_n1 = abs(x(i-1)-x(i-2));%delta (n-1)
deltaD = abs(delta_n1 - delta_n);

Le programme me sort enfin que la suite diverge. Aussi, dans mon code j'ai plein de end à la fin mes else if et je comprends pas vraiment pourquoi c'est nécessaire de les mettre (sans ça ne va pas). C'est moche comme ça… Cependant, un ami m'a envoyé ce qu'il avait fait et ça semble plus propre (et optimal). Je sais pas ce que vous en pensez ?

Je ne met que testBoundaries le reste étant presque pareil.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
% Fonction TestBoundaries pour savoir si une série est bornée ou non, et connaître ses bornes

function [isBound, lowerbound, upperbound]= TestBoundaries(seriesFun,p ,errorThreshold, maxsteps)

k = 3;
[xn] = calcSeries(seriesFun, p.coeff, p.start, maxsteps); %calcul de xn avec la fonction calcSeries
convergence = 0; % variable convergence initialisée à 0

while k <= maxsteps && xn(1,k)~= +inf % boucle while allant de k à maxsteps pour des éléments de xn(1,k) différents de l'infini
        diff1 = abs (xn(1,k)-xn(1,(k-1))); %calcul de delta n
        diff2 = abs (xn(1,(k-1))-xn(1,(k-2))); %calcul de detla n-1
        delta = abs(diff2 - diff1); % calcul de delta, la différence entre delta n-1 et delta n
   if k == maxsteps; % si k= maxsteps, on compare delta à l'errorThreshold pour déterminer s'il y a ou non convergence
            if delta > errorThreshold
                convergence = 0; 
            else
                convergence = 1; % delta est plus petit que errorThreshold au dernier step
            end
            k = k + 1; %incrémentation de k
    elseif delta > errorThreshold % dans le cas ou delta est plus grand que errorThreshold, on incrémente k et on continue dans la boucle
            k = k + 1;
            continue
    else % si delta est plus petit que errorThreshold, convergence
            convergence = 1; 
            k = maxsteps + 1; % pour sortir de la boucle k prend la valeur de maxsteps + 1
   end
end

Lbound = min(xn,[],2); % calcul du minimum de xn
Ubound = max(xn,[],2); % calcul du maximum de xn

if convergence == 1 % si la série est bornée (borne supérieure et inférieure)
    isBound = 3;
else % si la série n'est pas bornée
    isBound = 0;
end

if nargout > 1 %Utilisation de nargout pour que la fonction fonctionne avec plus 1 ou 3 output
    switch isBound 
        case 0 %si isBound vaut 0, la série n'a ni borne supérieure ni borne inférieure
             lowerbound = NaN;
             upperbound = NaN;
        case 3
             lowerbound = Lbound;
             upperbound = Ubound;
     end 
end              

end
+0 -0

Peut-être que c'est un coup de bol

C'en est certainement un. Pour les critères que tu appliques, tu peux toujours trouver une suite qui ne converge pas et qui respectera le critère.

Le code de ton camarade est plus clair, c'est sûr. Il contient cependant de nombreuses petites lourdeurs liées à une méconnaissance de Matlab et quelques maladresses. Entre autres, il indiquera que n'importe quelle suite qui respecte le critère pour un rang donné converge.

En fait, comme le disait @dr1, il est très difficile de tester la convergence des suites similaires à $y$, qui ont une évolution quelque peu cahoteuse. La méthode marchera bien seulement pour des suites assez régulières (de norme monotone par exemple).

Merci. C'est donc limite un cas impossible à traiter de manière numérique si je comprends bien.

Par contre, je vois pas en quoi le second code (de mon ami, dernier publié) est lourd (hormis les commentaires) car pour moi c'est la version la plus simple. Je connais mal Matlab mais en C je l'aurais fais de cette manière je pense.

C'est donc limite un cas impossible à traiter de manière numérique si je comprends bien.

La convergence de toute suite est impossible à traiter de manière numérique. Comme le disait Aabu, tu as besoin d'hypothèses sur la monotonie de la norme de la suite (ou au moins de ses sous-suites) pour pouvoir déduire quoique ce soit sur la convergence d'une suite à partir d'un nombre fini de termes.

$y(n)$ ajoute en plus la difficulté que trouver une sous-suite strictement croissante nécessite un large échantillon et qu'au contraire les termes proches induisent rapidement en erreur un programme basé sur des seuils.

Peut-être que c'est un coup de bol mais en mettant…

Comme explicitement indiqué dans mon précédent message, c'est un coup de bol. Prends $u_n=n$, qui est évidemment divergente, et tu as $\Delta_n=1$ et donc $\Delta_{n-1}-\Delta_{n}=0$. Ce "critère" n'a aucune valeur particulière pour déterminer le caractère convergent d'une suite.

+1 -0

Je reposte une question car j'ai testé une autre suite qui converge mais le code que j'ai écris plus haut me dit qu'elle diverge ce qui confirme que c'est très mauvais comme code. Je le remet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function [isBound,lowerbound,upperbound]= testBoundaries(seriesFun,p,errorThreshold,maxsteps)%hm2c
x(2)=p.a; %initialise x(1) et x(2)
x(1)=p.b;
i=2;

while i<=maxsteps && abs(x(i)-x(i-1))>errorThreshold
    x(i+1)=seriesFun(x(i),x(i-1),p.c,p.d);%call the function seriesFunX or Y
    i = i +1; %incrementing i
    delta_n = abs(x(i)-x(i-1)); %delta n 
    delta_n1 = abs(x(i-1)-x(i-2));%delta (n-1)
    deltaD = abs(delta_n1 - delta_n); %the difference between both delta's
end

switch nargout
    case 1
      if abs(deltaD)<errorThreshold && x(i)~=Inf && x(i)~=-Inf %is < errorThreshold and both different from infinitys
        isBound=3;
      elseif abs(deltaD)>errorThreshold%if it diverges not to +/- Inf the difference is > errorThreshold and it has no bound
        isBound=0;
      elseif x(i)==Inf
        isBound=1;%the case with no bound is already done so we verify only this condition to see if it has a lowerbound
      elseif x(i)==-Inf
        isBound=2;%also only this condition has to be verified
      end 
    case 3
      if abs(deltaD)<errorThreshold && x(i)~=Inf && x(i)~=-Inf %Inf-Inf=0 and is < errorThreshold
        isBound=3;
        upperbound=max(x);
        lowerbound=min(x);
      elseif deltaD>errorThreshold%if it diverges not to +/- Inf the difference is > errorThreshold and it has no bound
        isBound=0; %If isBound == 0, the sequence has no upperBound neither lowerBound.
        upperbound=NaN;
        lowerbound=NaN;
      elseif x(i)==Inf
         isBound=1;%The case with no bound is already done so we verify only this condition to see if it has a lowerbound
         upperbound=NaN;
         lowerbound=min(x);
      elseif x(i)==-Inf
         isBound=2;
         upperbound=max(x);
         lowerbound=NaN;
      end
end

La suite que je teste est ${x_n} = a{x_{n - 1}} + b{x_{n - 2}}$ avec $[a,b] = [0.5; -0.5]$ et on prend comme avant $[1;0] pour les deux premiers termes. Elle me dit qu'elle diverge mais elle converge clairement vers 0… Je pense que le soucis vient de la boucle while car elle converge super vite.. Je vois pas comment y remédier.

Salut,

J'arrive un peu tard mais concernant ta dernière suite, il n'y a effectivement aucune raison que ton programme t'affiche une divergence. Je te conseille de sortir les "delta" pour voir ce qui cloche. C'est ce que j'ai fais avec ton programme et en changeant quelques petites choses ça fonctionne correctement. Tout d'abord comme la suite converge très rapidement vers la valeur de 0, va piocher ton troisième élément $x(3)$ (ce qui fait que tu commences à $i=3$). Modifie une petite chose dans ton $while$ et ça ira parfaitement.

1
2
3
4
while i<maxsteps && deltaD>errorThreshold
    x(i+1)=seriesFun(x(i),x(i-1),p.c,p.d);
    i = i +1;
end

(où deltaD est ce que tu avais défini avant…)

Je n'ai aucune idée de "comment rendre ce programme plus optimal pour Matlab mais ça fonctionne donc ma foi, c'est bien pour un exercice de ce genre.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte