[PYTHON] Méthode du carré minimum (calcul de la matrice triangulaire)

Bonjour. La méthode des moindres carrés est $ J (\ boldsymbol {x}) \ triangleq \ left (\ boldsymbol {y} --A \ boldsymbol {x} \ right) ^ \ textrm {T} \ left (\ boldsymbol {y} --A \ boldsymbol {x} \ right) Calcule $ \ boldsymbol {x} _ {\ min} $ avec $ comme minimum. C'est une manière normale de passer par une matrice triangulaire pour une bonne efficacité de calcul. Les détails sont les expressions relationnelles suivantes, mais pour résumer le calcul,

1. Préparez la matrice $ \ tilte {A} \ triangleq \ begin {bmatrix} A & \ boldsymbol {y} \ end {bmatrix} $ (Ay dans l'exemple ci-dessous), puis (carré) ci-dessus Matrice triangulaire $ \ tilde {R} \ triangleq \ begin {bmatrix} R & \ tilde {\ boldsymbol {y}} \\ \ boldsymbol {0} ^ \ textrm {T} & \ alpha \ end {bmatrix} $ ( Dans l'exemple ci-dessous, recherchez Ry```) et
2. Utilisez ceci pour résoudre $ R , \ boldsymbol {x} = \ tilde {\ boldsymbol {y}} $ pour trouver $ \ boldsymbol {x} _ {\ min} $.

Un exemple d'implémentation Python de ceci est [^ 1],

def lsqsolv(Ay):
    n = Ay.shape[1] - 1
    Ry = triangulateupper(Ay)
    return numpy.linalg.solve(Ry[0:n,0:n], Ry[0:n,n]) # x_min

def triangulateupper(A):
    return numpy.linalg.cholesky(numpy.dot(A.transpose(),A)).transpose()

[^ 1]: La triangulation `` triangulateupper () '' dans cet exemple utilise la décomposition de Cholesky, qui met l'accent sur l'efficacité du calcul, mais dans de nombreux cas la décomposition QR, qui met l'accent sur la stabilité numérique, est recommandée.

Pour résumer les expressions relationnelles ($ \ tilde {Q} $, $ Q $ sont des matrices orthogonales),

\begin{align*}
J (\boldsymbol{x}) &\triangleq \left(\boldsymbol{y} - A \boldsymbol{x} \right)^\textrm{T} \left(\boldsymbol{y} - A \boldsymbol{x} \right) \\
&= \begin{bmatrix} \boldsymbol{x}\\ -1\end{bmatrix}^\textrm{T} \tilde{A}^\textrm{T} \, \tilde{A} \,\begin{bmatrix}  \boldsymbol{x}\\ -1\end{bmatrix} \\
&= \begin{bmatrix} \boldsymbol{x}\\ -1\end{bmatrix}^\textrm{T} \tilde{R}^\textrm{T} \, \tilde{R} \,\begin{bmatrix}  \boldsymbol{x}\\ -1\end{bmatrix} \\
A &= Q R \\
\tilde{A} &= \tilde{Q} \tilde{R} \\
\tilde{R}^\textrm{T} \, \tilde{R} &= \tilde{A}^\textrm{T} \tilde{A} \\
\tilde{A} &\triangleq \begin{bmatrix} A & \boldsymbol{y} \end{bmatrix} \\
\tilde{R} &\triangleq \begin{bmatrix} R  & \tilde{\boldsymbol{y}} \\ \boldsymbol{0}^\textrm{T} & \alpha \end{bmatrix} \\
\tilde{\boldsymbol{y}} &\triangleq Q^\textrm{T} \boldsymbol{y} \\
\alpha &\triangleq \left( \min_{\boldsymbol{x}} J (\boldsymbol{x}) \right)^{1/2} \\
 \\
\end{align*}