Méthode de Newton

1) Méthode de Newton pour une fonction de `RR"→"RR`

Nous avons une procédure calculant une fonction numérique `f` de `RR"→"RR`. Et on souhaite trouver de façon approchée une racine, c'est à dire une valeur de `x` pour laquelle la fonction s'annule, `f(x)"="0`.

On adopte la notation des physiciens. On considère un système physique possédant deux variables d'état `f` et `x` liées par le neurone `f"←"(x)`. Ce neurone indique que la variable d'état `f` est déterminée par la variable d'état `x`, que l'appel de la fonction `f` qui matérialise ce lien se fait en utilisant les parenthèses telles qu'utilisées dans le neurone, `f(x)`, et que la variable d'état `f` possède un système de coordonnée par défaut qui est `(x)`. De tel sorte que nous avons toujours `f"="f(x)`.

On cherche des états de ce système tels que `f"="0`.

On suppose que la variable `f` est dérivable par rapport à `x`, une dérivée totale puisqu'elle ne dépend que de `x`. Dés lors la dérivée selon `x` constitue une nouvelle variable d'état bien définie notée `f’` et est liée à `x` par un neurone et par la formule explicite suivante :

`f’"←"(x)`
`f’ = lim_(epsilon->0) (f(x"+"epsilon)-f)/epsilon`

La fonction `f` admet un développement de Taylor. On considère une variation infiniment petite `dx`. Selon l'ordre à laquelle on coupe le développement, on obtient une fonction de `dx` qui est soit constante, soit linéaire (à condition bien entendue que `f` soit dérivable), soit du second degrès (à condition que `f` soit deux fois dérivable), etc..

`f(x"+"dx) = f + O(dx)`

`f(x"+"dx) = f + f’dx + O(dx^2)`

`f(x"+"dx) = f + f’dx + (f’’)/2dx^ 2+O(dx^3)`

Puis, nous allons utiliser à la place de l'élément différentiel `dx` qui représente un infiniment petit, une valeur très petite `v`. La notation du grand `O` permet d'évoquer l'ordre de grandeur :

`O(1)` désigne notre échelle,

`O(v)` désigne l'échelle où évolue la variable `v`,

`O(v^2)` désigne l'échelle des carrés de ces valeurs,

`...`

`O(v^n)` désigne l'échelle des puissances `n` de ces valeurs.

On n'utilise que les deux premiers termes du développement de Taylor c'est à dire son approximation linéaire. On pose une valeur `x` initiale et une variation `v`

`f(x"+"v) = f + f’v + O(v^2)`

Et on cherche la variation `v` telle que `x"+"v` soit une racine de `f`, c'est à dire telle que `f(x"+"v)=0`. Le calcul se fait à `O(v^2)` près.

`f(x"+"v) = 0`

`f + f’v = 0`

`f’v = -f`

`v = -f/(f’)`

Et on calcul empiriquement à une échelle `epsilon` la dérivée de `f` en `x` :

`f’(x) = (f(x+epsilon)-f)/epsilon`

`v = - f/(f’)`

`v = - (epsilon f)/(f(x"+"epsilon)-f)`

Dans le principe, l'échelle de `v` doit être la même que celle d'`epsilon`. On remarque de façon empirique que le choix le plus simple est un bon choix :

`epsilon=v`

2) Algorithme

On adopte la notation informatique. Le symbole `x:=y` désigne une instruction impérative d'un programme qui va changer la valeur de `x` en celle de `y`. Mais attention, si on change la valeur de `x`, on change l'état du système déterminé par `x`, on change les valeurs des autres variables d'état qui dépendent de `x` que sont `f` et `f’` et qu'il faut donc recalculer, puisque par définition `f"="f(x)` et `f’"="f’(x)`.

L'algorithme de recherche d'une racine de `f` consiste à répéter les deux instructions suivantes, en partant par défaut de `epsilon"="1` et `x"="0`. Et si on est proche d'une racine, 3 itérations suffisent. C'est la méthode de Newton :

`epsilon := - f(x)epsilon/(f(x"+"epsilon)-f(x))`
`x := x + epsilon`

On divise par deux le nombre d'appels de la fonction `f` en calculant empiriquement la dérivée `f'` à partir de la valeur de `f` actuelle et de la valeur de `f` calculée dans l'itération précédente :

`x` : Position actuelle.
`y` : Position dans l'itération précédente.
`f(x)` : Valeur actuelle de `f`.
`f(y)` : Valeur de `f` dans l'itération précédente..

`f’ = (f(x)-f(y))/(x-y)`
`v = - f/(f’)`
`v = -f(x)(x-y)/(f(x)-f(y))`

L'algorithme de recherche d'une racine de `f` consiste à répéter les deux instructions suivantes, en partant par défaut de `y"="1` et `x"="0`. Et si on est proche d'une racine, 3 itérations suffisent. C'est la méthode de Newton approchée qui correspond à la méthode de la sécante.

`z := x - f(x)(x-y)/(f(x)-f(y))`
`y := x`
`x := z`

3) Système formel

L'algorithme décrit le calcul, mais ne s'occupe pas de la communication avec l'extérieur. On souhaite faire une procédure qui puisse être utilisé partout, c'est à dire une procédure formelle qui comprend la communication avec l'extérieur. On y définit les conditions d'appel, les conditions d'arrêt, et ce qu'elle retourne. On formalise ces conditions et ce qu'elle retourne dans un système formel parent qu'il convient également de définir.

Dans quelle ensemble travaillons-nous ? Un ensemble de nombres flottants. Et qu'est ce qu'un ensemble de nombres flottants de façon formelle ?. C'est le corps des réels `RR` mais altéré à une précision de `n` bits de mantisse que l'on note `RR"§"n`.

L'algorithme peut fonctionner pour tout ensemble munie d'une addition interne, d'une soustraction interne, d'une multiplication interne et d'une division interne (à l'exception de la division par zéro). Mais il ne sera pertinant que pour les ensembles approximant un corps différentiable telle que `RR, CC` ou `bbbH`. Soit deux conditions, l'une d'ordre technique, l'autre d'ordre logique.

La communication de la procédure avec l'extérieur peut s'inspirer du fonctionnement des réseaux Ethernets, empilant une succession de protocoles, le type de structure, le type d'altération, le type d'implémentation, dans une hierarchie de protocoles. Et ces protocoles, pour ce qui est des premiers, ceux de haut niveau, ont toutes raisons de se constituer en grand nombre au niveau international et donc reconnus universellement, les protocoles particuliers ou singuliers qui dénotent le choix d'arbitraires non consensuels, arrivant dans les bas niveaux.

---- 27 juillet 2021 ----