Linéarisation locale

Le processus de linéarisation locale approxime une fonction près de l'une de ses entrées avec une fonction plus simple qui a la même valeur à cette entrée et les mêmes valeurs de dérivées partielles.

Keywords: calcul multivariable, optimisation, algèbre linéaire

By Carmen Cincotti  

Je n’arrête pas de me heurter aux murs en ce qui concerne ma simulation du tissu ! En lisant cet article sur la dynamique basée sur la position, je suis tombé sur le concept de linéarisation locale des fonctions non linéaires. L’auteur a mentionné que :

Il est important de noter que PBD linéarise également la fonction de contrainte, mais individuellement pour chaque contrainte. L’équation de contrainte est approchée par :

C(x+x)C(x)+C(x)x>=0. C(x+∆x) ≈ C(x) + ∇C(x)·∆x >= 0.

Le problème, comme toujours, c’est que ce concept m’était inconnu. 🤦‍♂️

Nous avons déjà parlé des fonctions non linéaires lorsque nous avons abordé le sujet des fonctions contraintes dans cet article. Nous poursuivrons cette discussion dans le contexte de simplifier ces fonctions en les linéarisant.

Pourquoi devrais-je m’en soucier ? 🙋 La résolution de fonctions non linéaires peut être une tâche coûteuse, en fonction de sa complexité. Grâce à la linéarisation, il est possible de partitionner des parties linéaires d’une fonction non linéaire pour les résoudre avec des équations linéaires beaucoup plus simples. C’est pour les résoudre plus facilement et à moindre coût en ressources !

⚠️ Bien que j’aie décrit la linéarisation d’une fonction non linéaire comme une sorte de booster de performance magique, assurez-vous qu’il est raisonnable de l’utiliser pour votre application !

Linéarisation avec des plans tangentiels

Pour commencer, définissons rapidement la différence entre une fonction linéaire et une fonction non linéaire :

  • Linéaire - une fonction qui fait une ligne droite lorsqu’elle est tracée. Par exemple, examinons ce graphique pour la fonction y=2x+1y = 2x + 1 :

Graph for the function y=2x+1

Remarquons que ces fonctions prennent la forme :

f(x)=cconstant+vvectorxf(x) = \overbrace{c}^\textrm{constant} + \underbrace{\mathbf{v}}_\textrm{vector} \cdot \mathbf{x}

Par exemple :

y=2x1+3x2+1y=1+[23][x1x2]y = 2x_1 + 3x_2 + 1 \\[6pt] y = 1 + \begin{bmatrix} 2 \\ 3 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}

Vous pouvez aussi remarquer que les dérivées partielles sont constantes. Par exemple - une fonction comme g(x,y)=ax+by+cg(x,y) = ax + by + c aura des dérivées partielles constantes :

fx=afy=b f_x = a \\[6pt] f_y = b

💡 Il est intéressant de noter que les fonctions linéaires qui ne passent pas par l’origine sont techniquement appelées fonctions affines, car les fonctions linéaires doivent passer par l’origine.

  • Non linéaire - il s’agit des fonctions qui ne prennent pas les lignes droites lorsqu’elles sont tracées. Voici la fonction non linéaire y=x21y = x^2 - 1 :

Graph for the function y=x^2-1

Contrairement aux fonctions linéaires, les dérivées partielles d’une fonction non linéaire ne sont pas entièrement constantes. Voici les dérivées partielles d’une fonction g(x,y)=x2+y2+1g(x,y) = x^2 + y^2 + 1 :

fx=2xfy=2y f_x = 2x \\[6pt] f_y = 2y

La linéarisation d’une fonction non linéaire peut être résumée en disant que nous aimerions trouver un plan tangent à un point sur un graphique d’une fonction non linéaire. Cette fonction plane sert de fonction linéaire en ce point donné.

Pour clarifier, voici le graphique pour la fonction non linéaire f(x,y)=x2+y2f(x,y) = x^2+ y^2 (bleu) et un plan tangent représenté par la fonction g(x,y)=2(x1)+2(y1)+2g(x,y)=2(x-1) + 2(y-1) + 2 (violet) :

Plane tangent to a non-linear function

Au point (1,1)(1, 1), les deux fonctions se croisent. Nous pouvons dire qu’au point (1,1)(1,1) la fonction est linéarisée comme g(x,y)g(x,y).

Cependant, cette linéarisation empirera au fur et à mesure que nous nous éloignons du point (1,1)(1,1). C’est pour cela que nous devrions dire que la fonction f(x,y)f(x,y) est linéarisé localement au point (1,1)(1, 1).

Vu que nous sommes désormais plus familiers avec le concept de linéarisation, nous pouvons l’examiner plus en détail. Rappelez-vous que notre objectif est de comprendre cette équation :

C(x+x)C(x)+C(x)x>=0. C(x+∆x) ≈ C(x) + ∇C(x)·∆x >= 0.

Le plan tangent

Dans la section dernière, j’ai utilisé une fonction g(x,y)g(x,y) pour décrire un plan. Cependant, il semble un peu trop magique. 🪄

Comment trouver l’équation d’un plan ? Pour commencer, voici l’équation d’un plan dans son intégralité :

ax+by+cz=d ax + by + cz = d

En utilisant un vecteur normal et deux points qui se trouvent sur le plan, il est possible de trouver son équation.

Calculate the equation of a plane

n=(a,b,c)\vec{n} = (a,b,c) et pq=(xqxp,yqyp,zqzp)\vec{pq} = (x_q - x_p, y_q - y_p, z_q - z_p). pq\vec{pq} se trouve entièrement sur le plan.

Nous savons que le produit scalaire entre deux vecteurs perpendiculaires est 0. Cela nous laisse avec la forme suivante npq=0\vec{n} \cdot \vec{pq} = 0.

(a,b,c)(xqxp,yqyp,zqzp)=0a(xqxp)+b(yqyp)+c(zqzp)=0 (a, b, c) \cdot (x_q - x_p, y_q - y_p, z_q - z_p) = 0 \\[6pt] a(x_q - x_p) + b(y_q - y_p) + c(z_q - z_p) = 0

Enfin, je vais réécrire cette équation sous une forme où le vecteur x0\mathbf{x_0} est la position d’intersection du plan et d’une fonction non linéaire :

a(xx0)+b(yy0)+c(zz0)=0a(x - x_0) + b(y - y_0) + c(z - z_0) = 0

Gardez cette équation à l’esprit parce que nous la verrons dans la prochaine partie !

💡 Cette équation s’écrit souvent où d=ax0+by0+cz0d = ax_0 + by_0 + cz_0 comme suit :

ax+by+cz=dax + by + cz = d

Linéarisation locale

Vu que nous connaissons l’équation d’un plan - nous pouvons ajouter à cette connaissance. Supposons que nous voulions approximer la fonction précédente f(x,y)=x2+y2f(x,y) = x^2+ y^2 en trouvant son approximation linéaire locale.

Pour ce faire, nous voulons trouver une fonction d’un plan qui est tangente à la fonction au point (x,y,z)(x,y,z).

Les entrées de la fonction f(x,y)f(x,y) nous donnent la valeur zz. Nous pouvons donc dire que le plan et la fonction f(x,y)f(x,y) se croisent au point (x,y,f(x,y))(x, y, f(x,y)).

Ensuite, nous pouvons réécrire l’équation d’un plan a(xx0)+b(yy0)+c(zz0)=0a(x - x_0) + b(y - y_0) + c(z - z_0) = 0 pour se débarrasser de la variable cc et pour séparer zz :

ac(xx0)+bc(yy0)+zz0=0A=(a/c)B=(b/c)z=A(xx0)+B(yy0)+z0 \frac{a}{c}(x - x_0) + \frac{b}{c}(y - y_0) + z - z_0 = 0 \\[6pt] A = -(a / c) \\[6pt] B = -(b / c) \\[6pt] z = A(x - x_0) + B(y - y_0) + z_0

Comment allons-nous continuer ? 🤔

Une caractéristique importante d’une courbe tangentielle

Eh bien, la chose la plus importante à retenir lorsqu’on parle des courbes tangentielles est qu’une courbe et sa contrepartie tangentielle doivent avoir la même pente au point d’intersection !

Sinon, elles ne peuvent pas être tangentielles. Regardez ces deux graphiques 2D :

Tangent vs non-tangent graph

  • Le graphique du haut montre deux courbes qui se croisent à peine à un seul point - (1,0)(-1,0), ce qui signifie que la courbe bleue est tangente à la courbe rouge. ✅

  • Le graphique du bas a deux intersections ce qui signifie que la ligne bleue n’est pas tangente à la courbe rouge. ⛔

Vous vous posez peut-être la question :

Comment trouver la pente de f(x,y)f(x,y) ? 🤔

La pente est le gradient f(x,y)\nabla f(x,y) ! Rappelons que le gradient se compose des dérivées partielles d’une fonction de plusieurs variables.

En utilisant les dérivées partielles de f(x,y)f(x,y) - fxf_x et fyf_y - nous pouvons supposer que :

A=fx(x0,y0)B=fy(x0,y0)z=fx(x0,y0)(xx0)+fy(x0,y0)(yy0)+z0 A = f_x(x_0, y_0) \\[6pt] B = f_y(x_0, y_0) \\[6pt] \therefore z = f_x(x_0, y_0)(x - x_0) + f_y(x_0, y_0)(y - y_0) + z_0

Enfin, nous réécrivons cette équation en sachant que les deux points se croisent au point (x,y,f(x,y))(x, y, f(x,y)) et en posant Lf(x,y)=f(x,y)=zL_f(x,y) = f(x,y) = z pour être clair que la fonction Lf(x,y)L_f(x,y) est l’approximation linéaire locale de f(x,y)f(x,y) :

Lf(x,y)=f(x0,y0)+fx(x0,y0)(xx0)+fy(x0,y0)(yy0) L_f(x,y) = f(x_0, y_0) + f_x(x_0, y_0)(x-x_0) + f_y(x_0, y_0)(y-y_0)

Réécriture de la fonction

Rappelons que la fonction linéaire que nous avons utilisée est la suivante :

f(x)=cconstant+vvectorxf(x) = \overbrace{c}^\textrm{constant} + \underbrace{\mathbf{v}}_\textrm{vector} \cdot \mathbf{x}

Nous pouvons réécrire notre fonction Lf(x,y)L_f(x,y) sous cette forme en utilisant x=(x,y)\mathbf{x} = (x, y) et x0=(x0,y0)\mathbf{x}_0 = (x_0, y_0) :

Lf(x)=f(x0)+f(x0)(xx0) L_f(\mathbf{x}) = f(\mathbf{x}_0) + \nabla f(\mathbf{x}_0) \cdot (\mathbf{x} - \mathbf{x}_0) \\[6pt]

…qui est la même forme de la fonction contrainte de l’introduction, mais où x0=x \mathbf{x}_0 = x et x=x+Δx\mathbf{x} = x+\Delta x :

C(x+Δx)C(x)+C(x)Δx>=0 C(x+\Delta x) ≈ C(x) + ∇C(x)·\Delta x >= 0

Des ressources (en français et anglais)


Comments for Linéarisation locale



Written by Carmen Cincotti, computer graphics enthusiast, language learner, and improv actor currently living in San Francisco, CA.  Follow @CarmenCincotti

Contribute

Interested in contributing to Carmen's Graphics Blog? Click here for details!