Warum können Haushaltsreflexionen eine Matrix nicht diagonalisieren?

Bei der Berechnung der QR-Faktorisierung in der Praxis werden Householder-Reflexionen verwendet, um den unteren Teil einer Matrix auf Null zu setzen. Ich weiß, dass für die Berechnung von Eigenwerten symmetrischer Matrizen das Beste, was Sie mit Householder-Reflexionen tun können, darin besteht, sie in eine tridiagonale Form zu bringen. Gibt es eine offensichtliche Möglichkeit zu erkennen, warum es auf diese Weise nicht vollständig diagonalisiert werden kann? Ich versuche das einfach zu erklären, aber ich kann keine klare Darstellung finden.

Bei der Berechnung der Eigenwerte der symmetrischen Matrix $M\in\mathbb{R}^{n\times n}$ das Beste, was Sie mit dem Householder-Reflektor tun können, die Ansteuerung von $M$ in eine tridiagonale Form. Wie in einer früheren Antwort erwähnt , weil $M$ symmetrisch ist eine orthogonale Ähnlichkeitstransformation was eine Diagonalmatrix ist, das heißt, $D=S^TMS$ . Es wäre praktisch, wenn wir die Wirkung der unbekannten orthogonalen Matrix finden konnte $S$ durch Berechnen einer Folge von Reflektoren und Anwendung von streng Householder Reflektoren $H^T$ von links nach $M$ und $H$von rechts nach . Dies ist jedoch nicht möglich, da der Householder-Reflektor so konzipiert ist, dass Spalten auf Null gesetzt werden. Wenn wir den Householder-Reflektor so berechnen, dass alle Zahlen unter M 11 auf Null gesetzt werden, erhalten wir M = $M$$M_{11}$ Die Einträge M 12 - M 1 n wurden nun jedoch durchden links angebrachtenReflektor H T 1 geändert. Wenn wir also H 1 auf der rechten Seiteanwenden, wird die erste Reihe vonMnicht mehr auf Null gesetzt, sodass nur noch M 11 übrigbleibt. Stattdessen erhalten wir H T 1 M=

$$M=\left(\!\!{\begin{array}{ccccc} * &* & * & *&* \\ * &* & * & *&* \\ * &* & * & *&* \\ * &* & * & *&* \\ * &* & * & *&* \\ \end{array}}\!\!\right)\rightarrow H^T_1M=\left(\!\!{\begin{array}{ccccc} * &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ \end{array}}\!\!\right).$$ $M_{12}-M_{1n}$$H^T_1$$H_1$$M$$M_{11}$ Wo nicht nurdass Null aus wir die Zeile nichtaber wir können die Null Struktur zerstören wir nur mit dem Reflektor eingeführt H T 1 . $$H^T_1M=\left(\!\!{\begin{array}{ccccc} * &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ \end{array}}\!\!\right)\rightarrow H^T_1MH_1=\left(\!\!{\begin{array}{ccccc} * &*'' & *'' & *''&*'' \\ *' &*'' & *'' & *''&*'' \\ *' &*'' & *'' & *''&*'' \\ *' &*'' & *'' & *''&*'' \\ *' &*'' & *'' & *''&*'' \\ \end{array}}\!\!\right).$$ $H^T_1$

Wenn Sie sich jedoch dafür entscheiden, zu einer tridiagonalen Struktur zu fahren , bleibt die erste Reihe von der Wirkung von H T 1 unberührt , sodass M = $M$$H^T_1$ Wenn wir also den gleichen Reflektor von rechts anwenden, erhalten wir H T 1 M=

$$M=\left(\!\!{\begin{array}{ccccc} * &* & * & *&* \\ * &* & * & *&* \\ * &* & * & *&* \\ * &* & * & *&* \\ * &* & * & *&* \\ \end{array}}\!\!\right)\rightarrow H^T_1M=\left(\!\!{\begin{array}{ccccc} * &* & * & *&* \\ *' &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ \end{array}}\!\!\right).$$ $$H^T_1M=\left(\!\!{\begin{array}{ccccc} * &* & * & *&* \\ *' &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ 0 &*' & *' & *'&*' \\ \end{array}}\!\!\right)\rightarrow H^T_1MH_1=\left(\!\!{\begin{array}{ccccc} * &*' & 0 & 0&0 \\ *' &*'' & *'' & *''&*'' \\ 0 &*'' & *'' & *''&*'' \\ 0 &*'' & *'' & *''&*'' \\ 0 &*'' & *'' & *''&*'' \\ \end{array}}\!\!\right).$$

$M$$T$$M$$S^T$$S$

Wie die Kommentare zu anderen Antworten verdeutlichen, handelt es sich hier nicht um einen Mangel an Householder-Matrizen, sondern vielmehr um die Frage, warum iterative anstatt direkter ("geschlossener") Methoden verwendet werden, um (echte) symmetrische Matrizen (über Orthogonalität) zu diagonalisieren Ähnlichkeit).

In der Tat kann jede orthogonale Matrix als Produkt von Householder-Matrizen ausgedrückt werden. Wenn wir also die diagonale Form einer symmetrischen Matrix (ihre Eigenwerte) kennen, könnten wir nach einem vollständigen Satz orthonormalisierter Eigenvektoren suchen und die entsprechende Änderung der Basismatrix als a darstellen Produkt der Verwandlung von Hausbesitzern in der Polynomzeit.

Wenden wir uns also Victors Klammerkommentar "anders als Abels Theorem" zu, weil wir uns tatsächlich fragen, warum iterative Methoden verwendet werden sollten, um die Wurzeln eines Polynoms und nicht einer direkten Methode zu finden. Natürlich sind die Eigenwerte einer reellen symmetrischen Matrix die Wurzeln ihres charakteristischen Polynoms, und es ist auch möglich, in die andere Richtung zu gehen. Bei einem reellen Polynom mit nur reellen Wurzeln ist es möglich, aus einer Sturm-Folge für das Polynom eine tridiagonal symmetrische Begleitmatrix zu konstruieren . Siehe auch das Poster Denis Serres Übung 92 in diesem Set. Dies ist sehr hilfreich, um die Äquivalenz dieser Probleme zu demonstrieren, da (@AndrewWinters) die direkte Anwendung von Householder-Matrizen eine echte symmetrische Matrix tridiagonalisiert.

$O(n \log^3 n)$$O(n^2)$

Das Abel-Galois-Ruffini-Theorem besagt, dass keine allgemeine Formel für Wurzeln von Polynomen über Grad vier in Form von Radikalen (und der üblichen Arithmetik) angegeben werden kann. Es gibt jedoch geschlossene Formen für Wurzeln in Bezug auf exotischere Operationen . Im Prinzip könnte man Eigenwert- / Diagonalisierungsmethoden auf solchen Ansätzen aufbauen , aber man stößt auf einige praktische Schwierigkeiten:

1. $t^5 + t - a = 0$$t(a)$

2. Dies zerfällt mit Polynomen der Stufe sechs und höher, obwohl verschiedene Möglichkeiten gefunden werden können, um sie mit Funktionen von nur zwei Variablen zu lösen. Hilberts 13. Problem war die Vermutung, dass Polynome des allgemeinen Grades 7 nicht nur mit Funktionen von höchstens zwei Variablen gelöst werden konnten, aber 1957 zeigte VI Arnold, dass dies möglich war. Zu den multivariablen Funktionsfamilien, die verwendet werden können, um Lösungen für Polynome beliebigen Grades zu erhalten, gehören Mellin-Integrale, hypergeometrische und Siegel-Theta-Funktionen.

3. Neben der Implementierung etwas exotischer Sonderfunktionen aus mehr als einem Argument benötigen wir direkte Methoden zur Lösung von Polynomen, die für den allgemeinen Grad funktionieren$n$$C_f: Y^2 = f(x)$$f(x)$$O(n^3)$

Daher haben die indirekten / iterativen Verfahren zum Isolieren reeller Wurzeln (äquivalente Eigenwerte symmetrischer Matrizen), selbst mit hoher Genauigkeit, gegenwärtig praktische Vorteile gegenüber den bekannten direkten / exakten Verfahren für diese Probleme.

Aus welchem ​​Grund gehen Sie davon aus, dass dies unmöglich ist?

$S$$S = G D G^t$$G$$D$

Jede orthogonale Matrix der Größe n × n kann als ein Produkt von höchstens n solchen Reflexionen konstruiert werden. Wikipedia . Deshalb hast du diese Zersetzung.

Ich bin mir bei der letzten Aussage nicht sicher, ich zitiere sie nur (und ich denke, dass sie richtig ist). Soweit ich Ihre Frage verstehe, läuft es darauf hinaus, ob eine orthogonale Matrix in eine Folge von Householder-Transformationen zerlegt werden kann.

$n-1$$k$$k$

Es ist tatsächlich nützlich für Methoden, bei denen man wiederholt die orthoginale Matrix in einer numerisch stabilen faktorisierten Form benötigt.