Méthode des carrés. Où est utilisée la méthode des moindres carrés ?
- Tutoriel
Introduction
Je suis mathématicien et programmeur. Le plus grand pas que j'ai fait dans ma carrière a été lorsque j'ai appris à dire : "Je ne comprends rien !" Maintenant, je n'ai pas honte de dire au sommité de la science qu'il me donne une conférence, que je ne comprends pas ce que lui, le sommité, me dit. Et c'est très difficile. Oui, admettre son ignorance est difficile et embarrassant. Qui aime admettre qu’il ne connaît pas les bases de quelque chose ? En raison de ma profession, je dois assister grandes quantités des présentations et des conférences, où, je l'avoue, dans la grande majorité des cas j'ai envie de dormir parce que je ne comprends rien. Mais je ne comprends pas, car l’énorme problème de la situation actuelle de la science réside dans les mathématiques. Cela suppose que tous les auditeurs connaissent absolument tous les domaines des mathématiques (ce qui est absurde). Admettre qu’on ne sait pas ce qu’est un dérivé (nous parlerons de ce que c’est un peu plus tard) est honteux.
Mais j'ai appris à dire que je ne sais pas ce qu'est la multiplication. Oui, je ne sais pas ce qu'est une sous-algèbre sur une algèbre de Lie. Oui, je ne sais pas pourquoi ils sont nécessaires dans la vie équations quadratiques. Au fait, si vous êtes sûr de le savoir, alors nous avons de quoi parler ! Les mathématiques sont une série d'astuces. Les mathématiciens tentent de semer la confusion et d'intimider le public ; là où il n’y a pas de confusion, il n’y a pas de réputation, pas d’autorité. Oui, il est prestigieux de parler dans un langage aussi abstrait que possible, ce qui est un non-sens complet.
Savez-vous ce qu'est un dérivé ? Très probablement, vous me parlerez de la limite du rapport de différence. En première année de mathématiques et de mécanique à l'Université d'État de Saint-Pétersbourg, Viktor Petrovich Khavin m'a dit déterminé dérivée comme coefficient du premier terme de la série de Taylor de la fonction en un point (c'était une gymnastique distincte pour déterminer la série de Taylor sans dérivées). J'ai longtemps ri de cette définition jusqu'à ce que je comprenne enfin de quoi il s'agissait. La dérivée n'est rien de plus qu'une simple mesure de la similitude de la fonction que nous différencions avec la fonction y=x, y=x^2, y=x^3.
J'ai maintenant l'honneur de donner des conférences à des étudiants qui effrayé mathématiques. Si vous avez peur des mathématiques, nous sommes sur le même chemin. Dès que vous essayez de lire un texte et qu’il vous semble que c’est trop compliqué, sachez qu’il est mal écrit. J'affirme qu'il n'y a pas un seul domaine des mathématiques qui ne puisse être discuté « sur les doigts » sans perdre en précision.
Devoir pour le futur proche : J'ai demandé à mes étudiants de comprendre ce qu'est un régulateur quadratique linéaire. Ne soyez pas timide, passez trois minutes de votre vie et suivez le lien. Si vous ne comprenez rien, alors nous sommes sur le même chemin. Moi (un mathématicien-programmeur professionnel) je n’ai rien compris non plus. Et je vous assure que vous pouvez le comprendre « sur vos doigts ». Sur à l'heure actuelle Je ne sais pas ce que c'est, mais je vous assure que nous pouvons le découvrir.
Donc, la première conférence que je vais donner à mes étudiants après qu'ils soient venus me voir avec horreur et m'aient dit qu'un régulateur linéaire-quadratique est une chose terrible que vous ne maîtriserez jamais de votre vie est méthodes moindres carrés . Pouvez-vous décider équations linéaires? Si vous lisez ce texte, ce n’est probablement pas le cas.
Ainsi, étant donné deux points (x0, y0), (x1, y1), par exemple (1,1) et (3,2), la tâche est de trouver l'équation de la droite passant par ces deux points :
illustration
Cette ligne devrait avoir une équation comme la suivante :
Ici alpha et bêta nous sont inconnus, mais deux points de cette droite sont connus :
On peut écrire cette équation sous forme matricielle :
Que faut-il faire ici digression: Qu'est-ce qu'une matrice ? Une matrice n'est rien de plus qu'un tableau à deux dimensions. Il s’agit d’une manière de stocker des données ; aucune autre signification ne doit y être attachée. Cela dépend de nous exactement comment interpréter une certaine matrice. Périodiquement, je l'interpréterai comme une application linéaire, périodiquement comme une forme quadratique, et parfois simplement comme un ensemble de vecteurs. Tout cela sera clarifié dans son contexte.
Remplaçons les matrices concrètes par leur représentation symbolique :
Ensuite (alpha, bêta) peut être facilement trouvé :
Plus spécifiquement pour nos données précédentes :
Ce qui conduit à l'équation suivante de la droite passant par les points (1,1) et (3,2) :
D'accord, tout est clair ici. Trouvons l'équation de la droite passant par trois points : (x0,y0), (x1,y1) et (x2,y2) :
Oh-oh-oh, mais nous avons trois équations pour deux inconnues ! Un mathématicien standard dira qu’il n’y a pas de solution. Que dira le programmeur ? Et il va d’abord réécrire le système d’équations précédent sous la forme suivante :
Dans notre cas vecteurs i,j,b sont tridimensionnels, donc (dans le cas général) il n'y a pas de solution à ce système. Tout vecteur (alpha\*i + beta\*j) se trouve dans le plan couvert par les vecteurs (i, j). Si b n’appartient pas à ce plan, alors il n’y a pas de solution (l’égalité ne peut pas être obtenue dans l’équation). Ce qu'il faut faire? Cherchons un compromis. Notons par e(alpha, bêta) jusqu'où nous n'avons pas atteint l'égalité :
Et nous allons essayer de minimiser cette erreur :
Pourquoi carré ?
Nous ne recherchons pas seulement le minimum de la norme, mais le minimum du carré de la norme. Pourquoi? Le point minimum lui-même coïncide, et le carré donne une fonction lisse (une fonction quadratique des arguments (alpha, bêta)), tandis que simplement la longueur donne une fonction en forme de cône, non différentiable au point minimum. Brr. Un carré est plus pratique.
Évidemment, l’erreur est minimisée lorsque le vecteur e orthogonal au plan couvert par les vecteurs je Et j.
Illustration
Autrement dit : on recherche une droite telle que la somme des carrés des longueurs des distances de tous les points à cette droite soit minimale :
MISE À JOUR : j'ai un problème ici, la distance à la ligne droite doit être mesurée verticalement, et non par projection orthogonale. Ce commentateur a raison.
Illustration
En termes complètement différents (soigneusement, mal formalisés, mais cela devrait être clair) : nous prenons toutes les lignes possibles entre toutes les paires de points et cherchons la ligne moyenne entre tous :
Illustration
Une autre explication est simple : nous attachons un ressort entre tous les points de données (ici nous en avons trois) et la droite que nous recherchons, et la droite de l'état d'équilibre est exactement ce que nous recherchons.
Forme quadratique minimale
Alors, ayant vecteur donné b et un plan engendré par les vecteurs colonnes de la matrice UN(dans ce cas (x0,x1,x2) et (1,1,1)), on cherche le vecteur e avec un carré minimum de longueur. Évidemment, le minimum n'est atteignable que pour le vecteur e, orthogonal au plan engendré par les vecteurs colonnes de la matrice UN:Autrement dit, on recherche un vecteur x=(alpha, beta) tel que :
Je vous rappelle que ce vecteur x=(alpha, beta) est le minimum fonction quadratique||e(alpha, bêta)||^2 :
Ici, il serait utile de rappeler que la matrice peut également être interprétée comme une forme quadratique, par exemple, la matrice identité ((1,0),(0,1)) peut être interprétée comme une fonction x^2 + y^ 2 :
forme quadratique
Toute cette gymnastique est connue sous le nom de régression linéaire.
Équation de Laplace avec condition aux limites de Dirichlet
Maintenant la vraie tâche la plus simple : il y a une certaine surface triangulée, il faut la lisser. Par exemple, chargeons un modèle de mon visage :
Le commit original est disponible. Pour minimiser les dépendances externes, j'ai repris le code de mon logiciel de rendu, déjà sur Habré. Pour résoudre système linéaire J'utilise OpenNL, c'est un excellent solveur, qui est cependant très difficile à installer : vous devez copier deux fichiers (.h+.c) dans le dossier contenant votre projet. Tout lissage se fait avec le code suivant :
Pour (int d=0; d<3; d++) {
nlNewContext();
nlSolverParameteri(NL_NB_VARIABLES, verts.size());
nlSolverParameteri(NL_LEAST_SQUARES, NL_TRUE);
nlBegin(NL_SYSTEM);
nlBegin(NL_MATRIX);
for (int i=0; i<(int)verts.size(); i++) {
nlBegin(NL_ROW);
nlCoefficient(i, 1);
nlRightHandSide(verts[i][d]);
nlEnd(NL_ROW);
}
for (unsigned int i=0; i
Les coordonnées X, Y et Z sont séparables, je les lisse séparément. Autrement dit, je résous trois systèmes d'équations linéaires, chacun avec un nombre de variables égal au nombre de sommets de mon modèle. Les n premières lignes de la matrice A n'ont qu'un seul 1 par ligne et les n premières lignes du vecteur b ont les coordonnées du modèle d'origine. C'est-à-dire que j'attache un ressort entre la nouvelle position du sommet et l'ancienne position du sommet - les nouvelles ne doivent pas s'éloigner trop des anciennes.
Toutes les lignes suivantes de la matrice A (faces.size()*3 = nombre d'arêtes de tous les triangles du maillage) ont une occurrence de 1 et une occurrence de -1, le vecteur b ayant zéro composante opposée. Cela signifie que je mets un ressort sur chaque bord de notre maillage triangulaire : tous les bords essaient d'avoir le même sommet comme point de départ et d'arrivée.
Encore une fois : tous les sommets sont variables, et ils ne peuvent pas s'éloigner de leur position d'origine, mais en même temps ils essaient de devenir similaires les uns aux autres.
Voici le résultat :
Tout irait bien, le modèle est vraiment lissé, mais il s'est éloigné de son bord d'origine. Modifions un peu le code :
Pour (int i=0; je<(int)verts.size(); i++) { float scale = border[i] ? 1000: 1; nlBegin(NL_ROW); nlCoefficient(i, scale); nlRightHandSide(scale*verts[i][d]); nlEnd(NL_ROW); }
Dans notre matrice A, pour les sommets qui sont sur l'arête, j'ajoute non pas une ligne de la catégorie v_i = verts[i][d], mais 1000*v_i = 1000*verts[i][d]. Quelle différence cela fait-il ? Et cela change notre forme quadratique d’erreur. Désormais, un seul écart du haut au bord ne coûtera plus une unité, comme auparavant, mais 1 000 x 1 000 unités. C'est-à-dire que nous avons accroché un ressort plus fort aux sommets extrêmes, la solution préférera étirer les autres plus fortement. Voici le résultat :
Doublons la force du ressort entre les sommets :
nlCoefficient(face[ j ], 2);
nlCoefficient(face[(j+1)%3], -2);
Il est logique que la surface soit devenue plus lisse :
Et maintenant encore cent fois plus fort :
Qu'est-ce que c'est? Imaginez que nous ayons plongé un anneau métallique dans de l'eau savonneuse. En conséquence, le film de savon obtenu tentera d'avoir le moins de courbure possible, touchant la bordure - notre anneau métallique. C'est exactement ce que nous avons obtenu en fixant la bordure et en demandant une surface lisse à l'intérieur. Félicitations, nous venons de résoudre l'équation de Laplace avec les conditions aux limites de Dirichlet. Ça a l'air cool ? Mais en réalité, il suffit de résoudre un seul système d’équations linéaires.
L'équation de PoissonSouvenons-nous d'un autre nom sympa.
Disons que j'ai une image comme celle-ci :
Ça a l’air bien pour tout le monde, mais je n’aime pas la chaise. 
Je vais couper l'image en deux : 
Ensuite, je tirerai tout ce qui est blanc dans le masque vers la gauche de l'image, et en même temps tout au long de l'image, je dirai que la différence entre deux pixels voisins doit être égale à la différence entre deux pixels voisins de droite. image:
Pour (int i=0; je Voici le résultat : Code et photos disponibles L'analyse de régression est l'une des méthodes permettant d'étudier les relations stochastiques entre les caractéristiques. Le plus souvent utilisé pour estimer des paramètres méthode des moindres carrés (LSM).
Le problème de l'estimation des paramètres d'une équation linéaire par paire à l'aide de la méthode des moindres carrés est la suivante : pour obtenir de telles estimations de paramètres , , auxquelles la somme des écarts carrés des valeurs réelles de la caractéristique résultante - y i par rapport aux valeurs calculées - est minime. Illustrons le propos méthode classique des moindres carrés graphiquement. Pour ce faire, nous allons construire un nuage de points basé sur des données d'observation (x i, y i, i = 1; n) dans un système de coordonnées rectangulaires (un tel nuage de points est appelé champ de corrélation). Essayons de choisir une droite la plus proche des points du champ de corrélation. Selon la méthode des moindres carrés, la droite est sélectionnée pour que la somme des carrés des distances verticales entre les points du champ de corrélation et cette droite soit minimale. Évaluer l'étroitesse de la relation entre les caractéristiques
réalisée à l'aide du coefficient de corrélation de paire linéaire - r x,y. Il peut être calculé à l'aide de la formule : Tableau 1 Qui trouve l'application la plus large dans divers domaines de la science et de l'activité pratique. Cela peut être la physique, la chimie, la biologie, l’économie, la sociologie, la psychologie, etc. Par la volonté du destin, je dois souvent m'occuper de l'économie, et c'est pourquoi aujourd'hui je vais organiser pour vous un voyage dans un pays étonnant appelé Économétrie=) ...Comment peux-tu ne pas en vouloir ?! C'est très bien là-bas, il faut juste se décider ! ...Mais ce que vous voulez probablement, c'est apprendre à résoudre des problèmes méthode des moindres carrés. Et les lecteurs particulièrement assidus apprendront à les résoudre non seulement avec précision, mais aussi TRÈS RAPIDEMENT ;-) Mais d'abord énoncé général du problème+ exemple d'accompagnement : Supposons que dans un certain domaine, des indicateurs ayant une expression quantitative soient étudiés. En même temps, il y a tout lieu de croire que l'indicateur dépend de l'indicateur. Cette hypothèse peut être soit une hypothèse scientifique, soit être fondée sur le bon sens. Laissons cependant la science de côté et explorons des domaines plus appétissants, à savoir les épiceries. Notons par : – surface commerciale d'une épicerie, m², Il est tout à fait clair que plus la surface du magasin est grande, plus son chiffre d'affaires sera important dans la plupart des cas. Supposons qu’après avoir effectué des observations/expériences/calculs/danses avec un tambourin nous disposons de données numériques : Les données tabulaires peuvent également être écrites sous forme de points et représentées sous la forme familière Système cartésien . Répondons à une question importante : Combien de points faut-il pour une étude qualitative ? Plus c'est mieux. L'ensemble minimum acceptable se compose de 5 à 6 points. De plus, lorsque la quantité de données est faible, les résultats « anormaux » ne peuvent pas être inclus dans l’échantillon. Ainsi, par exemple, un petit magasin d'élite peut gagner des ordres de grandeur supérieurs à ceux de « ses collègues », faussant ainsi le modèle général que vous devez trouver ! Pour faire simple, nous devons sélectionner une fonction, calendrier qui passe au plus près des points Ainsi, la fonction recherchée doit être assez simple et en même temps refléter adéquatement la dépendance. Comme vous pouvez le deviner, l'une des méthodes permettant de trouver de telles fonctions s'appelle méthode des moindres carrés. Tout d’abord, examinons son essence en termes généraux. Soit une fonction approximant les données expérimentales : En rapprochant des points expérimentaux avec différentes fonctions, nous obtiendrons des valeurs différentes, et évidemment, là où cette somme est plus petite, cette fonction est plus précise. Une telle méthode existe et elle s'appelle méthode du moindre module. Cependant, dans la pratique, cette pratique est devenue beaucoup plus répandue. méthode des moindres carrés, dans lequel d'éventuelles valeurs négatives sont éliminées non pas par le module, mais en mettant au carré les écarts : Et maintenant, nous revenons à un autre point important : comme indiqué ci-dessus, la fonction sélectionnée doit être assez simple - mais il existe également de nombreuses fonctions de ce type : linéaire
, hyperbolique, exponentiel, logarithmique, quadratique
etc. Et bien sûr, je voudrais ici immédiatement « réduire le champ d’activité ». Quelle classe de fonctions dois-je choisir pour la recherche ? Une technique primitive mais efficace : – Le moyen le plus simple est de représenter des points Si les points sont situés, par exemple, le long hyperbole, alors il est évidemment clair que la fonction linéaire donnera une mauvaise approximation. Dans ce cas, nous recherchons les coefficients les plus « favorables » pour l'équation de l'hyperbole Notez maintenant que dans les deux cas nous parlons de fonctions de deux variables, dont les arguments sont paramètres de dépendance recherchés: Et essentiellement, nous devons résoudre un problème standard : trouver fonction minimale de deux variables. Rappelons notre exemple : supposons que les points « magasins » aient tendance à être situés en ligne droite et il y a tout lieu de croire que dépendance linéaire chiffre d'affaires de l'espace de vente au détail. Trouvons TELS coefficients « a » et « be » tels que la somme des écarts au carré Si vous souhaitez utiliser ces informations pour un essai ou une dissertation, je serai très reconnaissant pour le lien dans la liste des sources, vous trouverez de tels calculs détaillés à quelques endroits : Créons un système standard : On réduit chaque équation par « deux » et, en plus, on « décompose » les sommes : Note
: analyser indépendamment pourquoi « a » et « être » peuvent être supprimés au-delà de l'icône de somme. Soit dit en passant, cela peut formellement être fait avec la somme Réécrivons le système sous forme « appliquée » : Connaissons-nous les coordonnées des points ? Nous le savons. Montants Fonction Le problème à l'étude est d'une grande importance pratique. Dans notre exemple de situation, l’équation. Je n'analyserai qu'un seul problème avec des nombres « réels », car il ne présente aucune difficulté - tous les calculs sont au niveau du programme scolaire de la 7e à la 8e année. Dans 95 pour cent des cas, il vous sera demandé de trouver simplement une fonction linéaire, mais à la toute fin de l'article je montrerai qu'il n'est plus difficile de trouver les équations de l'hyperbole optimale, de l'exponentielle et de quelques autres fonctions. En fait, il ne reste plus qu'à distribuer les cadeaux promis - afin que vous puissiez apprendre à résoudre de tels exemples non seulement avec précision, mais aussi rapidement. Nous étudions attentivement la norme : Tâche À la suite de l'étude de la relation entre deux indicateurs, les paires de nombres suivantes ont été obtenues : Veuillez noter que les significations « x » sont naturelles, et cela a une signification significative caractéristique, dont je parlerai un peu plus tard ; mais ils peuvent bien sûr aussi être fractionnaires. De plus, selon le contenu d'une tâche particulière, les valeurs « X » et « jeu » peuvent être totalement ou partiellement négatives. Eh bien, on nous a confié une tâche « sans visage », et nous la commençons solution: On trouve les coefficients de la fonction optimale comme solution du système : Dans le but d'un enregistrement plus compact, la variable « compteur » peut être omise, car il est déjà clair que la sommation s'effectue de 1 à . Il est plus pratique de calculer les montants requis sous forme de tableau :
Ainsi, nous obtenons ce qui suit système: Ici, vous pouvez multiplier la deuxième équation par 3 et soustraire la 2ème de la 1ère équation terme par terme. Mais c'est une chance - dans la pratique, les systèmes ne sont souvent pas un cadeau, et dans de tels cas, cela permet d'économiser La méthode de Cramer: Vérifions. Je comprends que vous ne le vouliez pas, mais pourquoi sauter les erreurs là où elles ne peuvent absolument pas être manquées ? Remplaçons la solution trouvée dans le côté gauche de chaque équation du système : Ainsi, la fonction d’approximation recherchée : – de toutes les fonctions linéaires C'est elle qui se rapproche le mieux des données expérimentales. Contrairement à direct
dépendance du chiffre d'affaires du magasin à sa superficie, la dépendance trouvée est inverse
(principe « plus, moins »), et ce fait est immédiatement révélé par le négatif pente. Fonction Pour tracer la fonction d’approximation, trouvons ses deux valeurs : et exécutez le dessin : Calculons la somme des écarts au carré Résumons les calculs dans un tableau :
Nous répétons encore une fois : Quelle est la signification du résultat obtenu ? Depuis toutes les fonctions linéaires fonction y Trouvons la somme correspondante des écarts au carré - pour les distinguer, je les désignerai par la lettre « epsilon ». La technique est exactement la même : Conclusion: , ce qui signifie que la fonction exponentielle se rapproche moins bien des points expérimentaux qu'une ligne droite Mais ici, il convient de noter que « pire » est ça ne veut pas dire encore, ce qui est mauvais. Maintenant, j'ai construit un graphique de cette fonction exponentielle - et elle passe également à proximité des points Ceci conclut la solution, et je reviens à la question des valeurs naturelles de l'argument. Dans diverses études, généralement économiques ou sociologiques, les « X » naturels sont utilisés pour numéroter les mois, les années ou d’autres intervalles de temps égaux. Considérons, par exemple, le problème suivant. La méthode des moindres carrés (OLS) permet d'estimer diverses quantités en utilisant les résultats de nombreuses mesures contenant des erreurs aléatoires. Caractéristiques des multinationales L'idée principale de cette méthode est que la somme des erreurs quadratiques est considérée comme un critère de précision de la résolution du problème, qu'ils s'efforcent de minimiser. Lors de l'utilisation de cette méthode, des approches numériques et analytiques peuvent être utilisées. En particulier, en tant qu'implémentation numérique, la méthode des moindres carrés consiste à prendre autant de mesures que possible d'une variable aléatoire inconnue. De plus, plus il y a de calculs, plus la solution sera précise. Sur la base de cet ensemble de calculs (données initiales), un autre ensemble de solutions estimées est obtenu, parmi lequel la meilleure est ensuite sélectionnée. Si l’ensemble des solutions est paramétré, alors la méthode des moindres carrés se résumera à trouver la valeur optimale des paramètres. En tant qu'approche analytique de la mise en œuvre du LSM sur un ensemble de données initiales (mesures) et un ensemble attendu de solutions, une certaine (fonctionnelle) est déterminée, qui peut être exprimée par une formule obtenue comme une certaine hypothèse qui nécessite une confirmation. Dans ce cas, la méthode des moindres carrés revient à trouver le minimum de cette fonctionnelle sur l’ensemble des erreurs quadratiques des données originales. Veuillez noter qu'il ne s'agit pas des erreurs elles-mêmes, mais des carrés des erreurs. Pourquoi? Le fait est que les écarts de mesures par rapport à la valeur exacte sont souvent à la fois positifs et négatifs. Lors de la détermination de la moyenne, une simple sommation peut conduire à une conclusion incorrecte sur la qualité de l'estimation, car l'annulation des valeurs positives et négatives réduira la puissance d'échantillonnage de plusieurs mesures. Et, par conséquent, l'exactitude de l'évaluation. Pour éviter que cela ne se produise, les écarts au carré sont additionnés. De plus, afin d'égaliser la dimension de la valeur mesurée et l'estimation finale, la somme des erreurs quadratiques est extraite Quelques applications multinationales MNC est largement utilisé dans divers domaines. Par exemple, dans la théorie des probabilités et les statistiques mathématiques, la méthode est utilisée pour déterminer une caractéristique d'une variable aléatoire telle que l'écart type, qui détermine la largeur de la plage de valeurs de la variable aléatoire. Je suis mathématicien et programmeur. Le plus grand pas que j'ai fait dans ma carrière a été lorsque j'ai appris à dire : "Je ne comprends rien !" Maintenant, je n'ai pas honte de dire au sommité de la science qu'il me donne une conférence, que je ne comprends pas ce que lui, le sommité, me dit. Et c'est très difficile. Oui, admettre son ignorance est difficile et embarrassant. Qui aime admettre qu’il ne connaît pas les bases de quelque chose ? De par mon métier, je dois assister à un grand nombre de présentations et de conférences, où, je l'avoue, dans la grande majorité des cas j'ai envie de dormir parce que je ne comprends rien. Mais je ne comprends pas, car l’énorme problème de la situation actuelle de la science réside dans les mathématiques. Cela suppose que tous les auditeurs connaissent absolument tous les domaines des mathématiques (ce qui est absurde). Admettre qu’on ne sait pas ce qu’est un dérivé (nous parlerons de ce que c’est un peu plus tard) est honteux. Mais j'ai appris à dire que je ne sais pas ce qu'est la multiplication. Oui, je ne sais pas ce qu'est une sous-algèbre sur une algèbre de Lie. Oui, je ne sais pas pourquoi les équations quadratiques sont nécessaires dans la vie. Au fait, si vous êtes sûr de le savoir, alors nous avons de quoi parler ! Les mathématiques sont une série d'astuces. Les mathématiciens tentent de semer la confusion et d'intimider le public ; là où il n’y a pas de confusion, il n’y a pas de réputation, pas d’autorité. Oui, il est prestigieux de parler dans un langage aussi abstrait que possible, ce qui est un non-sens complet. J'ai maintenant l'honneur de donner des conférences à des étudiants qui effrayé mathématiques. Si vous avez peur des mathématiques, nous sommes sur le même chemin. Dès que vous essayez de lire un texte et qu’il vous semble que c’est trop compliqué, sachez qu’il est mal écrit. J'affirme qu'il n'y a pas un seul domaine des mathématiques qui ne puisse être discuté « sur les doigts » sans perdre en précision. Devoir pour le futur proche : J'ai demandé à mes étudiants de comprendre ce qu'est un régulateur quadratique linéaire. Ne soyez pas timide, passez trois minutes de votre vie et suivez le lien. Si vous ne comprenez rien, alors nous sommes sur le même chemin. Moi (un mathématicien-programmeur professionnel) je n’ai rien compris non plus. Et je vous assure que vous pouvez le comprendre « sur vos doigts ». Pour le moment, je ne sais pas ce que c'est, mais je vous assure que nous pourrons le découvrir. Donc, la première conférence que je vais donner à mes étudiants après qu'ils soient venus me voir avec horreur et m'aient dit qu'un régulateur linéaire-quadratique est une chose terrible que vous ne maîtriserez jamais de votre vie est méthodes des moindres carrés. Pouvez-vous résoudre des équations linéaires ? Si vous lisez ce texte, ce n’est probablement pas le cas. Ainsi, étant donné deux points (x0, y0), (x1, y1), par exemple (1,1) et (3,2), la tâche est de trouver l'équation de la droite passant par ces deux points : illustration Cette ligne devrait avoir une équation comme la suivante : Ici alpha et bêta nous sont inconnus, mais deux points de cette droite sont connus : On peut écrire cette équation sous forme matricielle : Il convient ici de faire une digression lyrique : qu'est-ce qu'une matrice ? Une matrice n'est rien de plus qu'un tableau à deux dimensions. Il s’agit d’une manière de stocker des données ; aucune autre signification ne doit y être attachée. Cela dépend de nous exactement comment interpréter une certaine matrice. Périodiquement, je l'interpréterai comme une application linéaire, périodiquement comme une forme quadratique, et parfois simplement comme un ensemble de vecteurs. Tout cela sera clarifié dans son contexte. Remplaçons les matrices concrètes par leur représentation symbolique : Ensuite (alpha, bêta) peut être facilement trouvé : Plus spécifiquement pour nos données précédentes : Ce qui conduit à l'équation suivante de la droite passant par les points (1,1) et (3,2) : D'accord, tout est clair ici. Trouvons l'équation de la droite passant par trois points : (x0,y0), (x1,y1) et (x2,y2) : Oh-oh-oh, mais nous avons trois équations pour deux inconnues ! Un mathématicien standard dira qu’il n’y a pas de solution. Que dira le programmeur ? Et il va d’abord réécrire le système d’équations précédent sous la forme suivante : Dans notre cas, les vecteurs i, j, b sont tridimensionnels, donc (dans le cas général) il n'y a pas de solution à ce système. Tout vecteur (alpha\*i + beta\*j) se trouve dans le plan couvert par les vecteurs (i, j). Si b n’appartient pas à ce plan, alors il n’y a pas de solution (l’égalité ne peut pas être obtenue dans l’équation). Ce qu'il faut faire? Cherchons un compromis. Notons par e(alpha, bêta) jusqu'où nous n'avons pas atteint l'égalité : Et nous allons essayer de minimiser cette erreur : Pourquoi carré ? Nous ne recherchons pas seulement le minimum de la norme, mais le minimum du carré de la norme. Pourquoi? Le point minimum lui-même coïncide, et le carré donne une fonction lisse (une fonction quadratique des arguments (alpha, bêta)), tandis que simplement la longueur donne une fonction en forme de cône, non différentiable au point minimum. Brr. Un carré est plus pratique. Évidemment, l’erreur est minimisée lorsque le vecteur e orthogonal au plan couvert par les vecteurs je Et j. Illustration Autrement dit : on recherche une droite telle que la somme des carrés des longueurs des distances de tous les points à cette droite soit minimale : MISE À JOUR : j'ai un problème ici, la distance à la ligne droite doit être mesurée verticalement, et non par projection orthogonale. Le commentateur a raison. Illustration En termes complètement différents (soigneusement, mal formalisés, mais cela devrait être clair) : nous prenons toutes les lignes possibles entre toutes les paires de points et cherchons la ligne moyenne entre tous : Illustration Une autre explication est simple : nous attachons un ressort entre tous les points de données (ici nous en avons trois) et la droite que nous recherchons, et la droite de l'état d'équilibre est exactement ce que nous recherchons. Autrement dit, on recherche un vecteur x=(alpha, beta) tel que : Je vous rappelle que ce vecteur x=(alpha, beta) est le minimum de la fonction quadratique ||e(alpha, beta)||^2 : Ici, il serait utile de rappeler que la matrice peut également être interprétée comme une forme quadratique, par exemple, la matrice identité ((1,0),(0,1)) peut être interprétée comme une fonction x^2 + y^ 2 : forme quadratique Toute cette gymnastique est connue sous le nom de régression linéaire. Le commit original est disponible. Pour minimiser les dépendances externes, j'ai repris le code de mon logiciel de rendu, déjà sur Habré. Pour résoudre le système linéaire, j'utilise OpenNL, c'est un excellent solveur, mais qui est très difficile à installer : vous devez copier deux fichiers (.h+.c) dans le dossier avec votre projet. Tout lissage se fait avec le code suivant : Pour (int d=0; d<3; d++) {
nlNewContext();
nlSolverParameteri(NL_NB_VARIABLES, verts.size());
nlSolverParameteri(NL_LEAST_SQUARES, NL_TRUE);
nlBegin(NL_SYSTEM);
nlBegin(NL_MATRIX);
for (int i=0; i<(int)verts.size(); i++) {
nlBegin(NL_ROW);
nlCoefficient(i, 1);
nlRightHandSide(verts[i][d]);
nlEnd(NL_ROW);
}
for (unsigned int i=0; i Les coordonnées X, Y et Z sont séparables, je les lisse séparément. Autrement dit, je résous trois systèmes d'équations linéaires, chacun avec un nombre de variables égal au nombre de sommets de mon modèle. Les n premières lignes de la matrice A n'ont qu'un seul 1 par ligne et les n premières lignes du vecteur b ont les coordonnées du modèle d'origine. C'est-à-dire que j'attache un ressort entre la nouvelle position du sommet et l'ancienne position du sommet - les nouvelles ne doivent pas s'éloigner trop des anciennes. Toutes les lignes suivantes de la matrice A (faces.size()*3 = nombre d'arêtes de tous les triangles du maillage) ont une occurrence de 1 et une occurrence de -1, le vecteur b ayant zéro composante opposée. Cela signifie que je mets un ressort sur chaque bord de notre maillage triangulaire : tous les bords essaient d'avoir le même sommet comme point de départ et d'arrivée. Encore une fois : tous les sommets sont variables, et ils ne peuvent pas s'éloigner de leur position d'origine, mais en même temps ils essaient de devenir similaires les uns aux autres. Voici le résultat : Tout irait bien, le modèle est vraiment lissé, mais il s'est éloigné de son bord d'origine. Modifions un peu le code : Pour (int i=0; je<(int)verts.size(); i++) {
float scale = border[i] ? 1000: 1;
nlBegin(NL_ROW);
nlCoefficient(i, scale);
nlRightHandSide(scale*verts[i][d]);
nlEnd(NL_ROW);
}
Dans notre matrice A, pour les sommets qui sont sur l'arête, j'ajoute non pas une ligne de la catégorie v_i = verts[i][d], mais 1000*v_i = 1000*verts[i][d]. Quelle différence cela fait-il ? Et cela change notre forme quadratique d’erreur. Désormais, un seul écart du haut au bord ne coûtera plus une unité, comme auparavant, mais 1 000 x 1 000 unités. C'est-à-dire que nous avons accroché un ressort plus fort aux sommets extrêmes, la solution préférera étirer les autres plus fortement. Voici le résultat : Doublons la force du ressort entre les sommets : nlCoefficient(face[(j+1)%3], -2); Il est logique que la surface soit devenue plus lisse : Et maintenant encore cent fois plus fort : Souvenons-nous d'un autre nom sympa. Disons que j'ai une image comme celle-ci : Ça a l’air bien pour tout le monde, mais je n’aime pas la chaise. Je vais couper l'image en deux : Ensuite, je tirerai tout ce qui est blanc dans le masque vers la gauche de l'image, et en même temps tout au long de l'image, je dirai que la différence entre deux pixels voisins doit être égale à la différence entre deux pixels voisins de droite. image: Pour (int i=0; je Voici le résultat : Code et photos disponibles
L'analyse de régression est la dérivation d'une équation de régression, à l'aide de laquelle la valeur moyenne d'une variable aléatoire (attribut de résultat) est trouvée si la valeur d'une autre (ou d'autres) variables (attributs de facteur) est connue. Il comprend les étapes suivantes :
Le plus souvent, une forme linéaire est utilisée pour décrire la relation statistique entre les entités. L'accent mis sur les relations linéaires s'explique par l'interprétation économique claire de ses paramètres, la variation limitée des variables et le fait que dans la plupart des cas, les formes de relations non linéaires sont converties (par logarithme ou substitution de variables) en une forme linéaire pour effectuer des calculs. .
Dans le cas d'une relation linéaire par paire, l'équation de régression prendra la forme : y i =a+b·x i +u i . Les paramètres a et b de cette équation sont estimés à partir des données d'observation statistique x et y. Le résultat d'une telle évaluation est l'équation : , où , sont des estimations des paramètres a et b , est la valeur de l'attribut résultant (variable) obtenu à partir de l'équation de régression (valeur calculée).
La méthode des moindres carrés fournit les meilleures estimations (cohérentes, efficaces et impartiales) des paramètres de l'équation de régression. Mais seulement si certaines hypothèses concernant le terme aléatoire (u) et la variable indépendante (x) sont remplies (voir hypothèses OLS).
Officiellement Critère OLS peut s'écrire ainsi : 
.Classification des méthodes des moindres carrés
Notation mathématique pour ce problème : 
.
Les valeurs de y i et x i =1...n nous sont connues ; ce sont des données d'observation. Dans la fonction S, ils représentent des constantes. Les variables de cette fonction sont les estimations requises des paramètres - , . Pour trouver le minimum d'une fonction de deux variables, il faut calculer les dérivées partielles de cette fonction pour chacun des paramètres et les assimiler à zéro, c'est-à-dire 
.
En conséquence, nous obtenons un système de 2 équations linéaires normales : 
En résolvant ce système, nous trouvons les estimations de paramètres requises : 
L'exactitude du calcul des paramètres de l'équation de régression peut être vérifiée en comparant les montants (il peut y avoir un certain écart en raison de l'arrondi des calculs).
Pour calculer les estimations des paramètres, vous pouvez créer le tableau 1.
Le signe du coefficient de régression b indique le sens de la relation (si b >0, la relation est directe, si b<0, то связь обратная). Величина b показывает на сколько единиц изменится в среднем признак-результат -y при изменении признака-фактора - х на 1 единицу своего измерения.
Formellement, la valeur du paramètre a est la valeur moyenne de y avec x égal à zéro. Si le facteur d'attribut n'a pas et ne peut pas avoir une valeur nulle, alors l'interprétation ci-dessus du paramètre a n'a pas de sens.
. De plus, le coefficient de corrélation linéaire des paires peut être déterminé grâce au coefficient de régression b : 
.
La plage de valeurs acceptables du coefficient de corrélation linéaire des paires va de –1 à +1. Le signe du coefficient de corrélation indique le sens de la relation. Si r x, y >0, alors la connexion est directe ; si r x, y<0, то связь обратная.
Si ce coefficient est proche de l'unité en grandeur, alors la relation entre les caractéristiques peut être interprétée comme une relation linéaire assez étroite. Si son module est égal à un ê r x , y ê =1, alors la relation entre les caractéristiques est fonctionnellement linéaire. Si les caractéristiques x et y sont linéairement indépendantes, alors r x,y est proche de 0.
Pour calculer r x,y, vous pouvez également utiliser le tableau 1.
Pour évaluer la qualité de l'équation de régression résultante, calculez le coefficient de détermination théorique - R 2 yx : N observations x je et je x je ∙y je
1
x1 et 1 x 1 et 1
2
x2 et 2 x 2 et 2
...
n xn o n x n y n
Somme de colonne ∑x ∑y ∑xy
Valeur moyenne
,
où d 2 est la variance de y expliquée par l'équation de régression ;
e 2 - variance résiduelle (inexpliquée par l'équation de régression) de y ;
s 2 y - variance totale (totale) de y.
Le coefficient de détermination caractérise la proportion de variation (dispersion) de l'attribut résultant y expliquée par la régression (et, par conséquent, le facteur x) dans la variation totale (dispersion) y. Le coefficient de détermination R 2 yx prend des valeurs de 0 à 1. En conséquence, la valeur 1-R 2 yx caractérise la proportion de variance y causée par l'influence d'autres facteurs non pris en compte dans les erreurs de modèle et de spécification.
Au hammam régression linéaire R 2 yx =r 2 yx.
– chiffre d'affaires annuel d'une épicerie, millions de roubles.
Avec les épiceries, je pense que tout est clair : - c'est la superficie du 1er magasin, - son chiffre d'affaires annuel, - la superficie du 2ème magasin, - son chiffre d'affaires annuel, etc. À propos, il n'est pas du tout nécessaire d'avoir accès à des documents classifiés - une évaluation assez précise du chiffre d'affaires commercial peut être obtenue au moyen de statistiques mathématiques. Cependant ne nous laissons pas distraire, le cours d'espionnage commercial est déjà payant =)
. Cette fonction est appelée rapprochement
(approximation - approximation) ou fonction théorique
. D'une manière générale, un « concurrent » évident apparaît immédiatement ici : un polynôme de haut degré dont le graphique passe par TOUS les points. Mais cette option est compliquée et souvent tout simplement incorrecte. (puisque le graphique « bouclera » tout le temps et reflétera mal la tendance principale).
Comment évaluer la précision de cette approximation ? Calculons également les différences (écarts) entre les valeurs expérimentales et fonctionnelles (on étudie le dessin). La première pensée qui nous vient à l’esprit est d’estimer le montant de la somme, mais le problème est que les différences peuvent être négatives. (Par exemple, 
)
et les écarts résultant d’une telle sommation s’annuleront. Par conséquent, comme estimation de la précision de l’approximation, il convient de prendre la somme modulesécarts :
ou effondré : (au cas où quelqu'un ne le saurait pas : – c'est l'icône de somme, et – une variable auxiliaire « compteur », qui prend des valeurs de 1 à ).
, après quoi les efforts visent à sélectionner une fonction telle que la somme des écarts au carré 
était aussi petit que possible. En fait, c’est de là que vient le nom de la méthode.
sur le dessin et analyser leur emplacement. S'ils ont tendance à courir en ligne droite, vous devriez alors rechercher équation d'une droite 
avec des valeurs optimales et . En d'autres termes, la tâche consiste à trouver TELS coefficients afin que la somme des écarts carrés soit la plus petite.
– ceux qui donnent la somme minimale des carrés 
.
était le plus petit. Tout est comme d'habitude - d'abord Dérivées partielles du 1er ordre. Selon règle de linéarité Vous pouvez différencier juste sous l'icône somme : 
après quoi l'algorithme pour résoudre notre problème commence à émerger :
peut-on le trouver ? Facilement. Faisons le plus simple système de deux équations linéaires à deux inconnues(« un » et « être »). Nous résolvons le système, par exemple, La méthode de Cramer, grâce à quoi nous obtenons un point stationnaire. Vérification condition suffisante pour un extremum, on peut vérifier qu'à ce stade la fonction 
atteint exactement minimum. Le contrôle implique des calculs supplémentaires et nous le laisserons donc en coulisses (si nécessaire, le cadre manquant peut être visualisé). Nous tirons la conclusion finale :
de la meilleure façon possible (au moins par rapport à toute autre fonction linéaire) rapproche les points expérimentaux 
. Grosso modo, son graphique passe le plus près possible de ces points. Dans la tradition économétrie la fonction d'approximation résultante est également appelée équation de régression linéaire appariée
.
vous permet de prédire quel chiffre d'affaires ("Igrec") le magasin aura à l'une ou l'autre valeur de la surface de vente (l’une ou l’autre signification de « x »). Oui, la prévision qui en résultera ne sera qu’une prévision, mais dans de nombreux cas, elle s’avérera assez précise.
À l’aide de la méthode des moindres carrés, trouvez la fonction linéaire qui se rapproche le mieux de la valeur empirique. (expérimenté) données. Faire un dessin sur lequel construire des points expérimentaux et un graphique de la fonction d'approximation dans un système de coordonnées rectangulaires cartésiennes 
. Trouvez la somme des carrés des écarts entre les valeurs empiriques et théoriques. Découvrez si la fonctionnalité serait meilleure (du point de vue de la méthode des moindres carrés) rapprocher les points expérimentaux.
Les calculs peuvent être effectués sur une microcalculatrice, mais il est bien préférable d'utiliser Excel - à la fois plus rapide et sans erreurs ; regardez une courte vidéo :
, ce qui signifie que le système a une solution unique.
Les membres droits des équations correspondantes sont obtenus, ce qui signifie que le système est résolu correctement.
nous dit qu'avec une augmentation d'un certain indicateur de 1 unité, la valeur de l'indicateur dépendant diminue en moyenne de 0,65 unités. Comme on dit, plus le prix du sarrasin est élevé, moins il est vendu.
La droite construite s’appelle ligne de tendance
(à savoir une ligne de tendance linéaire, c'est à dire que dans le cas général, une tendance n'est pas forcément une ligne droite). Tout le monde connaît l’expression « être à la mode » et je pense que ce terme n’a pas besoin de commentaires supplémentaires.
entre valeurs empiriques et théoriques. Géométriquement, c'est la somme des carrés des longueurs des segments « framboise » (dont deux sont si petits qu'ils ne sont même pas visibles).
Ils peuvent encore être effectués manuellement au cas où, je vais donner un exemple pour le 1er point : 
mais il est bien plus efficace de le faire de la manière déjà connue :
l'indicateur est le plus petit, c'est-à-dire que dans sa famille c'est la meilleure approximation. Et ici, d'ailleurs, la dernière question du problème n'est pas fortuite : et si la fonction exponentielle proposée 
vaudrait-il mieux rapprocher les points expérimentaux ?
Et encore, au cas où, calculs pour le 1er point : 
Dans Excel, nous utilisons la fonction standard EXP. (la syntaxe peut être trouvée dans l'aide d'Excel).
.
- à tel point que sans recherche analytique, il est difficile de dire quelle fonction est la plus précise.Introduction
Savez-vous ce qu'est un dérivé ? Très probablement, vous me parlerez de la limite du rapport de différence. En première année de mathématiques et de mécanique à l'Université d'État de Saint-Pétersbourg, Viktor Petrovich Khavin m'a dit déterminé dérivée comme coefficient du premier terme de la série de Taylor de la fonction en un point (c'était une gymnastique distincte pour déterminer la série de Taylor sans dérivées). J'ai longtemps ri de cette définition jusqu'à ce que je comprenne enfin de quoi il s'agissait. La dérivée n'est rien de plus qu'une simple mesure de la similitude de la fonction que nous différencions avec la fonction y=x, y=x^2, y=x^3.Forme quadratique minimale
Donc étant donné ce vecteur b et un plan engendré par les vecteurs colonnes de la matrice UN(dans ce cas (x0,x1,x2) et (1,1,1)), on cherche le vecteur e avec un carré minimum de longueur. Évidemment, le minimum n'est atteignable que pour le vecteur e, orthogonal au plan engendré par les vecteurs colonnes de la matrice UN:Équation de Laplace avec condition aux limites de Dirichlet
Maintenant la vraie tâche la plus simple : il y a une certaine surface triangulée, il faut la lisser. Par exemple, chargeons un modèle de mon visage :
nlCoefficient(face[ j ], 2);Qu'est-ce que c'est? Imaginez que nous ayons plongé un anneau métallique dans de l'eau savonneuse. En conséquence, le film de savon obtenu tentera d'avoir le moins de courbure possible, touchant la bordure - notre anneau métallique. C'est exactement ce que nous avons obtenu en fixant la bordure et en demandant une surface lisse à l'intérieur. Félicitations, nous venons de résoudre l'équation de Laplace avec les conditions aux limites de Dirichlet. Ça a l'air cool ? Mais en réalité, il suffit de résoudre un seul système d’équations linéaires.
L'équation de Poisson