Le Kunstweg de Jost Bürgi — Les-mathematiques.net The most powerful custom community solution in the world

Le Kunstweg de Jost Bürgi

Amis trisecteurs, constructeurs d'ennéagones ou d'heptagones, bonjour !

Voici un algorithme redécouvert récemment (2015 ?) qui permettait à Jost Bürgi (1552-1632) de calculer, pour un entier $n$ donné, des valeurs approchées de tous les sinus des $\frac m n \times 90°$ en même temps (comme on dit de nos jours…).

Nicolas Ursus Reimers appelait cet algorithme le Kunstweg de Bürgi, ce que l'on pourrait traduire par habile démarche, ou chemin heuristique.

Pour $n=9$, par exemple, Bürgi calculait comme suit les sinus de $m\times 10°$ :
Il écrivait sur une colonnes des valeurs grossières de ces sinus exprimées en douzièmes, puis il faisait un calcul de différences inversé remplissant de droite à gauche le tableau ci-dessous:

Toutes les nouvelles colonnes impaires commencent par un $0$ en haut et toutes les nouvelles colonnes paires sont calculées de bas en haut, commençant en bas par la moitié de la denière valeur de la colonne impaire précédente (par exemple $6= \frac {12} 2$).
Les valeurs des colonnes paires successives sont alors de mieux en mieux proportionnelles aux sinus des $m\times 10°$106552

Réponses

  • Bürgi n'a pas apporté la preuve de la convergence de son Kunstweg.
    Cet algorithme a été redécouvert à Wroclaw par Menso Folkerts et il a fait l'objet d'études attentives, notamment par le français Denis Roegel

    Je comprends assez bien la proportionnalité qui est conservée de gauche à droite si l'on prend les valeurs exactes comme valeurs initiales, mais les raisons de la convergence du Kunstweg de Bürgi m'échappent un peu, et je n'ai pas encore compris pourquoi les colonnes paires commencent en-bas par la moitié de la dernière valeur de la colonne précédente….

    Amicalement. jacquot
  • Monologue, suite :

    Voici un schéma qui explique la conservation de la proportionnalité de gauche à droite si l'on prend les valeurs exactes comme valeurs initiales, et les cases rouges montrent pourquoi, en remplissant de droite à gauche, il faut commencer par la moitié de la dernière valeur de la colonne précédente.

    on a bien , en effet $1-\cos d=2\sin^2(\frac d 2 )$.

    j'entrevois la convergence… @ suivre ?106588
  • Voici une idée, éventuellement à affiner.

    Je ne m'occupe que des colonnes paires. Je ne considère pas la case comportant un terme nul. La relation de récurrence est $X_{n+1}=AX_n$ où $A$ est la matrice $n\times n$ dont la $k$-ième ligne est $(1,2,3,\ldots,k-1,k,k,\ldots,k,\frac{k}{2})$.

    Si on arrive à montrer que le vecteur $V=(\sin\frac{k\pi}{2n})_{k=1,\ldots,n}$ est un vecteur propre (*), alors d'après le théorème de Perron-Frobenius la valeur propre correspondante est simple, et c'est le rayon spectral de la matrice $A$. Si on part de n'importe quel vecteur $X_0$ à coordonnées positives, la suite $(X_n)$ devient de plus en plus proportionnelle à $V$ (avec une convergence géométrique).

    (*) Si c'est vrai ça ne devrait pas être insurmontable à démontrer mais je n'ai pas pris la peine de le faire.
  • Merci JLT,

    Je retrouve dans ton ébauche des termes évoqués dans les documents ci-dessous:
    Waldvogel
    Roegel

    Sans doute la démo est-elle trop touffue pour que je puisse la comprendre avec mes maigres moyens. Je pense que je me contenterai d'intuitions.

    Fritz Staudacher, l'enthousiaste biographe de Bürgi, souligne qu'avec son Kunstweg, Jost Bürgi était très en avance sur son temps .
    Je suis en train de développer sa page Wikipédia.

    Amicalement. jacquot
  • Le théorème de Perron-Frobenius trivialise le problème, ce que ne semblent pas avoir remarqué les deux références que tu indiques : plus généralement, si $A$ est une matrice à coefficients strictement positifs et $V$ est un vecteur à coefficients strictement positifs tels que $AV$ est proportionnel à $V$, alors pour tout vecteur non nul $X_0$ à coefficients positifs, la suite $X_n=A^nX_0$ devient de plus en plus proportionnelle à $V$.

    Je termine le calcul de mon message plus haut.

    Soit $\theta=\frac{\pi}{2n}$ et $x_k=\sin k\theta$. Supposons qu'une colonne paire consiste en les termes $(x_1,\ldots,x_n)$ (je ne tiens pas compte du premier terme nul dans la colonne).

    La colonne impaire qui suit est $y_k=x_k+\cdots+x_{n-1}+\frac{x_n}{2}=\frac{1}{2\sin\frac{\theta}{2}}\cos((k-\frac{1}{2})\theta)$.

    La colonne paire qui suit est $z_k=y_1+\cdots+y_k$ et on calcule que $z_k=\frac{1}{4\sin^2\frac{\theta}{2}}x_k$.
  • Bonsoir JLT,
    Je suis heureux d'appendre que le théorème de Perron-Frobenius trivialise le problème ! Je comprends à peu près l'idée , mais serais incapable de donner une démonstration.
    De l'avis de Roegel et de Waldvogel qui ont analysé l'algorithme de Bürgi, lui-même m'a pas apporté la preuve de la convergence de son algorithme, mais il en a eu l'intuition géniale et il était capable ainsi en quelques calculs, de donner en même temps des approximations de plus en plus en plus précises des $\sin(m\times 10°)$ ou encore des $\sin(k\times\frac \pi{14})$, etc.

    Le même Bürgi a développé une forme de calcul logarithmique en utilisant une table de valeurs de la suite $10^9(1,0001)^n$ avant même que Napier n'invente les logarithmes .

    Merci pour tes explications. Amicalement. jacquot
  • Le théorème auquel je fais référence est le théorème 1, page 3, par exemple de ce sujet d'agreg 2012 :

    https://agreg.org/data/uploads/sujets/AP/AP12.pdf (on trouvera un corrigé dans le rapport https://agreg.org/data/uploads/rapports/rapport2012.pdf )

    On suppose trouvé un vecteur propre positif $V=\begin{pmatrix} v_1 \\ \vdots \\v_n \end{pmatrix}$. D'après la question 1.8. du document ci-dessus, la valeur propre correspondante est le rayon spectral $\rho$.

    Soit maintenant $X_0$ un vecteur positif non nul. Soit $X_k=A^kX_0$. On veut montrer que $\rho^{-k}X_k$ tend vers un vecteur non nul proportionnel à $V$. Quitte à diviser $A$ par $\rho$, on peut supposer que $\rho=1$.

    Si $(c_{ij})$ désigne la matrice $A^k$, de l'égalité $A^kV=V$ on déduit $v_i=\sum_j c_{ij}v_j$, donc $c_{ij}\leqslant \frac{v_i}{v_j}$. Ainsi, la suite $(A^k)$ est bornée.

    Pour tout $\lambda\in\C$, notons $F_\lambda$ l'espace caractéristique associé à la valeur propre $\lambda$. La restriction de $A$ à $F_1$ est de la forme $I+N$ où $N$ est nilpotente. Comme $(I+N)^k=I+kN+\frac{k(k-1)}{2}N^2+\cdots+\binom{k}{n-1} N^{n-1}$, du fait que $(I+N)^k$ est bornée on en déduit que $N=0$. Autrement dit, $F_1$ est l'espace propre associé à la valeur propre $1$, c'est-à-dire l'espace engendré par $V$.

    D'autre part, si $\lambda$ est une autre valeur propre, alors $|\lambda|<1$ (cf. théorème I.(iii)). La restriction de $A$ à $F_\lambda$ est de la forme $\lambda I + N$ où $N$ est nilpotente. Comme $(\lambda I +N)^k=\sum_{j=0}^{n-1}\binom{k}{j}\lambda^{k-j}N^j$, on a $\lim_{k\to\infty} (\lambda I + N)^k =0$.

    De ce qui précède on déduit que $(A^k)$ tend vers le projecteur sur $F_1$ parallèlement aux autres espaces caractéristiques. Notons $P$ ce projecteur.

    On a $X_k=A^kX_0$, donc $(X_k)$ tend vers $PX_0$. Comme $PX_0\in F_1$, il est proportionnel à $V$. Il reste à montrer qu'il est non nul.

    Soit $\Phi$ un vecteur propre strictement positif pour la transposée de $A$, c'est-à-dire $A^T\Phi=\Phi$.

    On a pour tout entier $k$ l'égalité des produits scalaires : $\langle \Phi, X_k\rangle = \langle \Phi, A^kX_0\rangle = \langle (A^T)^k\Phi, X_0\rangle = \langle \Phi, X_0\rangle$, donc $\langle \Phi, X_k\rangle$ est une constante strictement positive. On en déduit que la suite $(X_k)$ ne tend pas vers $0$. CQFD.
  • Bonjour,

    Honteusement, je m'aperçois que je n'ai même pas remercié JLT. Que ce soit fait !
    Je voulais rajouter un petit mot pour signaler qu'il y a maintenant un petit article sur Wikipédia à ce sujet.
    Kunstweg de Jost Bürgi
    Un petit coucou amical à tous.
    jacquot
  • Joli travail jacquot !
  • Superbe ! Un régal pour les yeux.

    [small]J'attends la traduction en Alsacien...[/small]

    amicalement,

    e.v.
    À ta naissance, tu pleurais tout le temps et tout le monde souriait autour de toi. Fais en sorte qu'à ta mort, ce soit l'inverse. (Proverbe arabe)
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!