[PYTHON] Minimum-Quadrat-Methode (Dreiecksmatrixberechnung)

Hallo. Die Methode der kleinsten Quadrate ist $ J (\ boldsymbol {x}) \ triangleq \ left (\ boldsymbol {y} - A \ boldsymbol {x} \ right) ^ \ textrm {T} \ left (\ boldsymbol {y} - A \ boldsymbol {x} \ right) Berechnet $ \ boldsymbol {x} _ {\ min} $ mit $ als Minimum. Es ist ein normaler Weg, eine dreieckige Matrix zu durchlaufen, um eine gute Berechnungseffizienz zu erzielen. Die Details sind die folgenden relationalen Ausdrücke, aber um die Berechnung zusammenzufassen,

Bereiten Sie die Matrix $ \ tilte {A} \ triangleq \ begin {bmatrix} A & \ boldsymbol {y} \ end {bmatrix} $ (`Ay``` im folgenden Beispiel) und dann (Quadrat) oben vor Dreiecksmatrix $ \ tilde {R} \ triangleq \ begin {bmatrix} R & \ tilde {\ boldsymbol {y}} \\\ \ boldsymbol {0} ^ \ textrm {T} & \ alpha \ end {bmatrix} $ ( Im folgenden Beispiel finden Sie `Ry```) und
Verwenden Sie diese Option, um $ R , \ boldsymbol {x} = \ tilde {\ boldsymbol {y}} $ zu lösen und $ \ boldsymbol {x} _ {\ min} $ zu finden.

Ein Beispiel für eine Python-Implementierung ist [^ 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]: Die Triangulation "triangulateupper ()" in diesem Beispiel verwendet die Cholesky-Zerlegung, die die Recheneffizienz betont. In vielen Fällen wird jedoch die QR-Zerlegung empfohlen, die die numerische Stabilität betont.

Um die relationalen Ausdrücke zusammenzufassen ($ \ tilde {Q} $, $ Q $ sind orthogonale Matrizen),

\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*}