Discussion :

[j.p.mignot]

Je ne le pense pas car écrire un développement du type
f(x)= f(x0) + (x-x0).f'(x0) + o(x-x0)
n'est justement possible que si f' existe au point considéré.
une fonction du type f(x)=0 si x<0 et =x si x>=0 et calculable de classe C0.

[Tellmarch]

j'ai un peu du mal à imaginer tout ça c'est nouveau pour moi

Peut tu me donner la fonction correspondant à ce calcul?

Si j'ai bien compris elle prend une fonction x en entrée représentant le réel, et doit retourner une fonction y représentant la sortie...

[DrTopos]

une fonction du type f(x)=0 si x<0 et =x si x>=0 et calculable de classe C0.

Effectivement, une fonction linéaire (affine) par morceaux, mais continue (les morceaux de droite se raccordent bien) est tout à fait calculable.

Etant donné une fonction continue f, (avec ton sens de la continuité et des réels), j'ai l'impression que grace à l'a formule de taylor young on peut calculer f' à la précision que l'on veut en tout point. Si f est calculable, f' le serait donc aussi (corrige moi si je me trompe...)
Donc il faut non seulement que la fonction soit continue, mais en fait C-infini, sinon elle n'est pas calculable ?

Non, le fait qu'une fonction soit calculable (avec de vrais réels) a seulement à voir avec la continuité. Dans ton raisonnement, tu supposes d'avance que f est non seulement C-infini, mais même qu'elle est 'analytique', c'est à dire somme de sa série de Taylor. Une telle fonction est a priori calculable ainsi que toutes ses dérivées du moins dans le disque de convergence de cette série entière.

Il faut se méfier. Il existe des fonctions C-infini qui ne sont pas somme de leur série de taylor. par exemple la fonction f définie par:

f(x) = 0 si x = 0
f(x) = e^(-1/x^2) si x != 0

Cette fonction n'est nulle qu'en 0, elle est C-infini (y compris en 0) et pourtant sa série de Taylor est identiquement nulle. C'est une fonction qui n'est pas analytique.

Pour en revenir à ta citation, la fonction de Koch est continue (de R vers R^2), calculable et dérivable en aucun point. Elle est définie comme la limite (uniforme) d'une suite de fonctions affines par morceaux tout à fait explicites et la vitesse de convergence est facilement maîtrisée. Elle est donc tout à fait calculable. Voir une illustration ici.

[Tellmarch]

je crois que je ne comprends pas tout super bien..

je pense que je comprendrais mieux si je voyais un exemple de fonction écrite dans ce formalisme, donc par exemple la fonction
|x -> 0 si x<0
|x -> x si x >=0

Peut-tu me donner le code d'une telle fonction?

en particulier je ne vois pas comment l'on fait en pratique pour tester si un nombre est positif, alors qu'on ne peut le connaitre qu'à une précision finie...


édit : au passage , que représente le parametre de la fonction de Koch définie de R dans R²?

[Tellmarch]

bon j'ai un peu plus réflechi sur ce que je disais, mais je ne comprends toujours pas bien ou est l'erreur...
En faisant simplement l'hypothese que f est continue, C1 par morceaux,
on peut calculer en tout point (f(a+h)-f(a))/h, pour h arbitrairement petit.
si il s'agit d'un point de dérivabilité, cette algorithme nous donnera f'(x) avec une présision arbitraire.
On pourrait ainsi calculer une fonction g, telle que g(x) = f'(x) en tout point ou f est dérivable.
donc f' serait obligatoirement continue???

du coup j'attends avec impatience que vous tu me donnes le contre exemple pour la fonction 0 sur R- puis x->x par exemple, ça me permettra sans doute de voir mon erreur

[DrTopos]

La fonction que tu donnes:

|x -> 0 si x<0
|x -> x si x >=0

est tout à fait calculable. Appelons là 'f'. On a f(x) = 0 pour x négatif ou nul et f(x)=x pour x positif ou nul.

Cette fonction est clairement 1-lipschitzienne, ce qui signifie qu'elle a la propriété suivante pour tous x et y réels:

|f(x) - f(y)| <= |x - y|

(où les barres verticales veulent dire 'valeur absolue'). Pour voir que cette fonction est calculable, il suffit de montrer qu'on est capable de calculer, pour x donné, une approximation rationnelle de f(x) aussi bonne qu'on veut.

Soit donc e (pour 'epsilon') un rationnel positif très petit. x étant un vrai réel qui nous est donné, on peut (par définition) trouver un rationnel r tel que |r - x| < e. Il est facile de calculer f(r), car r est une fraction de deux entiers. On peut donc facilement décider de son signe et donc voir si f(r) est nul ou égal à r.

Par ailleurs, on a |f(x) - f(r)| <= |x - r| < e. On voit donc que le rationnel f(r) répond à la question posée.

Note: être lipschitzienne pour une fonction est plus fort qu'être continue, et même qu'être uniformément continue.

[Tellmarch]

Il y a quelque chose qui me gène dans ton raisonnement.

D'apres ce que j'avais compris de tes définitions, ta fonction prend un réel en entrée, et doit retourner un réel en sortie.
Mais tu dois retourner le réel sans savoir à quelle précision on voudra le regarder ensuite non?

En gros j'ai l'impression que tu fixe e avant de donner la réponse de la fonction, alors que de ce que j'avais compris tu n'as pas le droit...

J'essaie d'expliquer mieux : f est définie de R dans R. je m'attends donc à ça :
je lui donne un réel x en entrée, elle me rend un réel y en sortie.

et ensuite j'ai le droit de calculer y(e) avec e aussi petit que je veux, pour avoir une précision quelconque...
mais e n'est pas fixé au moment du calcul.

Dis moi si j'avais mal compris les définitions...

[Tellmarch]

J'ajoute un exemple de ce que serait pour moi une fonction de R dans R, par exemple la fonction x -> 2x :

f(x) = y, ou y est défini par y(e) = 2 * x(e/2)

La fonction est bien définie indépendament de e...

[DrTopos]

on peut calculer en tout point (f(a+h)-f(a))/h, pour h arbitrairement petit.
si il s'agit d'un point de dérivabilité, cette algorithme nous donnera f'(x) avec une présision arbitraire.
On pourrait ainsi calculer une fonction g, telle que g(x) = f'(x) en tout point ou f est dérivable.
donc f' serait obligatoirement continue???

Très intéressante remarque ! Tu aurais donc démontré ceci:

Si une fonction est calculable et dérivable, alors sa dérivée est calculable.

Ce qui entraine évidemment que cette dérivée est continue, donc que la fonction est C1.

Malheureusement, c'est faux pour la raison suivante. En effet, considérons le taux d'accroissement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
f(a+h) - f(a)
--------------
        h

Comme f est calculable, ce taux d'accroissement est calculable pour toute valeur de h, et comme la fonction est dérivable, en prenant des h de plus en plus petits, on va se rapprocher de la dérivée f'(a). C'est vrai, mais on n'a aucun moyen de savoir à quelle distance de f'(a) on est, et donc on ne sait pas jusqu'où il faut pousser le calcul pour approximer f'(a) à la précision exigée.

D'ailleurs, voici un contre exemple. Considérons la fonction g suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
g(0) = 0
g(x) = x + 2(x^2)sin(1/x)   si x n'est pas nul

On peut facilement vérifier que cette fonction est calculable (malgré le sin(1/x)), car g(x) est toujours compris entre x-2(x^2) et x+2(x^2) et les modules de ces deux expressions sont facilement majorables par des choses petites pour x petit. Donc soit les approximations qu'on obtient de x permettent de le séparer de 0, et alors on se trouve avec de braves fonctions classiques, soit on ne peut pas séparer x de 0, mais alors on peut majorer les modules des deux expressions ci-dessus et donc calculer f(x) avec la précision voulue.

Par ailleurs, cette fonction g est dérivable, même en 0. Sa dérivée en 0 vaut 1. Mais ce qu'on peut aussi facilement constater en calculant (symboliquement) g'(x) pour x non nul, est que g' n'est pas continue en 0:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
g'(x) = 1 + 4x sin(1/x) - 2 cos(1/x)

on voit que le 2 cos(1/x) provoque des oscillations incompatibles avec la continuité de g' en 0 (alors que 1 + 4x sin(1/x) tend gentiment vers 1).

Maintenant, dans le cas de cet exemple, le calcul de la limite du taux d'accroissement ne va pas échouer en 0. Il va échouer pour les points proches de 0, car on va se trouver avec des valeurs proches de 2 cos(1/x) qui sont impossibles à maîtriser avec précision pour x petit, toujours à cause de ces mêmes oscillation sauvages.

[DrTopos]

D'apres ce que j'avais compris de tes définitions, ta fonction prend un réel en entrée, et doit retourner un réel en sortie.
Mais tu dois retourner le réel sans savoir à quelle précision on voudra le regarder ensuite non?

En gros j'ai l'impression que tu fixe e avant de donner la réponse de la fonction, alors que de ce que j'avais compris tu n'as pas le droit...

J'essaie d'expliquer mieux : f est définie de R dans R. je m'attends donc à ça :
je lui donne un réel x en entrée, elle me rend un réel y en sortie.

et ensuite j'ai le droit de calculer y(e) avec e aussi petit que je veux, pour avoir une précision quelconque...
mais e n'est pas fixé au moment du calcul.

C'est tout à fait cela. Mais je n'ai pas fixé e. Il reste arbitraire dans mon raisonnement.

[Tellmarch]

Effectivement je raisonnais mal, merci d'avoir été patient pour m'expliquer
J'ai du le programmer pour me convaincre qu'on pouvait bien le faire

Pour mon "théoreme" précédent, effectivement il me manque des hypothèses
Si je rajoutais l'hypothese que f est C2 par morceaux, et que la dérivée seconde est bornée sur les morceaux, alors par l'inégalité de taylor lagrange à l'ordre 2 on pourrait effectivement calculer f' à une précision arbitraire. Le probleme est qu'il faut etre sûr de rester sur les intervalles ou f est C2 dans le calcul, et rien ne garantit ça...
Donc tout ce que j'ai réussi à montrer (je crois), c'est que si f est C2, de dérivée seconde bornée, et que f est calculable, alors f' est calculable aussi... et ce n'est pas un résultat super interessant ^^

Merci beaucoup d'avoir pris le temps de m'expliquer tout ça

[DrTopos]

Après un peu de réflexion (la nuit porte conseil), je peux répondre aujourd'hui à une question à laquelle je ne savais pas répondre hier, à savoir: existe-t-il des fonctions continues non calculables ? Autrement-dit, la réciproque du théorème de Brouwer-Joyal est-elle fausse ?

La réponse est oui. Voici un exemple très simple de fonction continue non calculable. Commençons par prendre une partie A non récursive de l'ensemble N des entiers naturels. De telles parties existent d'après la théorie des fonctions récursives. Considérons maintenant la fonction f de R vers R, définie par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
f(x) = 0 si x < 0
f(x) = 0 si x >= 0 et E(x):A
f(x) = 1 si x >= 0 et E(x)!:A

où E(x) est la partie entière de x, où : veut dire 'appartient' et où !: veut dire 'n'appartient pas'.

f est une fonction en escalier. Soit F celle de ses primitives qui s'annulle en 0. Alors F est continue (et affine par morceaux). Pourtant F n'est pas calculable.

En effet, si F était calculable, on pourrait pour tout entier n donné, calculer F(n) et F(n+1), avec une précision aussi grande qu'on veut. Or ces deux nombres sont égaux si n:A et diffèrent de 1 si n!:A. On obtiendrait donc un algorithme capable de tester si n est dans A, ce qui est impossible.

[Tellmarch]

je réflechissais au meme genre de choses, sauf que je voulais coder les machines de turing et le probleme de l'arret comme une fonction continue...

ta méthode est plus simple

enfin j'ai comme excuse que je connais pas la théorie des ensembles récursifs ^^