A matematikában a Householder-tükrözés vagy Householder-transzformáció az euklidészi térben egy origón átmenő hipersíkra való tükrözés. Három dimenziós térben ez egy origón átmenő síkra való tükrözés. Egy ilyen transzformációt ábrázoló mátrix egy Householder-mátrix. Legfontosabb alkalmazása a numerikus matematikában mátrixok átalakítása, például QR-felbontás készítése.
Az eljárást 1958-ban az amerikai Alston Scott Householder dolgozta ki. Definíció A tükrözés hipersíkját normálvektorával határozzuk meg. tehát egy vektorral, ami ortogonális a hipersíkra. Ha -t oszlopvektornak tekintjük, és egységmátrix, aki a fent leírt transzformációt a következő mátrix fejezi ki:
Itt a vektor transzponáltja, tehát sorvektor. A nevező a vektor önmagával vett skalárszorzata, pedig diadikus szorzat. A mátrix a által megadott irányba való ortogonális vetítés.
Ha normált, akkor , és a forma a következő alakra egyszerűsödik:
A transzformáció tükrözés volta abban nyilvánul meg, hogy: ,
ahol a standard skalárszorzat. A kifejezés az pont távolsága a hipersíktól. Az vektor két komponens összegére bomlik, ahol az első komponens a hipersíkban fekszik, a második pedig a vektor többszöröse. A tükrözés során a hipersíkban levő komponens invariáns marad, a komponens irányát pedig ellenkezőjére változik: ahelyett, hogy hozzáadódna, levonódik. Tulajdonságok A Householder-mátrix tulajdonságai: Szimmetrikus, Ortogonális, Involutorikus, (a szimmetria és az ortogonális tulajdonságok következménye) A sajátvektorhoz tartozó sajátértéke egyszeres, és -1. Az 1 -szeres sajátérték. Az 1 sajátértékhez tartozó hipersík, ami a által generált egydimenziós altér ortogonális kiegészítője. A -val vett mátrix-vektor szorzás könnyen számítható. Adott tükrözés előállítása Adva legyen egy vektor, amit egy vektor többszörösébe akarunk tükrözni. Vagyis keresünk egy egységvektort, úgy, hogy a hozzá tartozó Householder-mátrixra legyen. Geometriai értelemben az és vektorok által bezárt szög egyik szögfelezőjének iránya. A szögfelező úgy számítható, hogy mindkét egyenesen az origótól ugyanolyan távolságra kiválasztunk egy-egy pontot, és megkeressük a két pontot összekötő szakasz felezőpontját. Az origót a felezőponttal összekötő szakasz éppen a szögfelező irányát adja meg. Az ebbe az irányba mutató egységvektor lesz a megfelelő vektor. A másik szögfelezőt úgy kapjuk, hogy a konstrukciót az és a vektorokra végezzük el.
Az egyszerűség kedvéért feltételezzük, hogy normált, . Ekkor a tükrözés ortogonalitása miatt . A keresett tükrözésvektor normálásával adódik, azaz . Mindkét előjelváltozat megfelelő eredményt ad, amennyiben a nevező nullától különbözik. A numerikus stabilitás miatt előjelét úgy választják, hogy a nevező a legnagyobb legyen, vagyis
Ellenőrzés:
Példa A leggyakrabban azt az esetet tekintik, amikor , vagyis az első kanonikus bázisvektor. Legyen az felbontva az első koordinátára és a maradék vektorra. Ekkor a normára teljesül, hogy . előjelét úgy választjuk, hogy megegyezzen előjelével. Ekkor a tükrözés iránya . Tehát
A vektor ennek az iránynak a normálásával kapható. Átalakítással
adódik, ahol már előre kiszámított részeredményeket használunk. QR-felbontás A Householder-tükrözések stabilan kiszámítják egy mátrix QR-felbontását. Az első oszlopot a mátrixszal az első egységvektor többszörösére tükrözik, ahogy azt az előzőekben leírtuk.
Ezután a mátrixhoz kiszámítják a mátrixot, azonban mivel háromszög formára akarják hozni a mátrixot, itt rögzítik, hogy a tükrözővektor első koordinátája nulla, azaz egy hipersíkban keresik, így az első oszloppal nem kell foglalkozni. Ezután a mátrixot úgy számolják ki, hogy a tükrözővektor első két koordinátája nulla, így a teljes tér dimenziójánál kettővel kisebb dimenziójú altérben keresik. Általában, az -edik lépésben a mátrix pozíciója alatti részmátrixot alakítják át, mígnem a mátrixot háromszög alakra hozzák: .
A felbontással adódik az felbontás, ahol
Figyeljük meg, hogy négyzetes mátrix. Többnyire nem számítják ki a , illetve a mátrixot, hanem a szorzatformát használják. A tükrözővektorokat a mátrixokhoz az mátrix felszabaduló helyein tárolják.
Egy mátrix QR-felbontása a Householder-eljárásban:
Az esetben lépés elég, mivel az utolsó oszlophoz nem kell hozzányúlni. Pszeudokód Mivel a legtöbb esetben nincs szükség explicit kiszámítására, azért elég az mátrixot kiszámítani. az aktuális részmátrix bal oszlopa. Az alább megadott függvény az eredményt közvetlenül az mátrixba írja, így futás után -t az mátrix tartalmazza. Az sor elhagyható.
function GetR(A) for k=1…n z=A(k…m,k)
uk=z uk(1)+=sign(z(1))*norm(z) uk=uk/norm(uk)
vk=zeros(m) vk(k…m)= uk
A=A-(2*vk)*(vk'*A)
R=A return R Ha mégis szükség lenne a mátrixra, akkor a fenti példa egyszerűen bővíthető: function GetR(A) Q=eye(m) for k=1…n z=A(k…m,k)
uk=z uk(1)+=sign(z(1))*norm(z) uk=uk/norm(uk)
vk=zeros(m) vk(k…m)= uk
A=A-(2*vk)*(vk'*A) Q=Q-Q*vk*(2*vk')
R=A return R Program Az alábbi C++ kód a Householder-eljárást valósítja meg. A program belépési pontja a main, ami az eredményt a konzolra írja. Rosetta Code: QR decomposition#include <iostream> #include <vector> using namespace std;
// Ez a függvény számolja a c = a + b * s mennyiséget void vmadd(const Vector& a, const Vector& b, double s, Vector& c) { if (c.size != a.size || c.size != b.size)
return;
for (int i = 0; i < c.size; i++)
c(i) = a(i) + s * b(i);
// Ez a függvény számolja az I - 2 * v * v^T mátrixot void computeHouseholderFactor(Matrix& matrix, const Vector& v) { int n = v.size; matrix.allocate(n, n); for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
matrix(i, j) = -2 * v(i) * v(j);
for (int i = 0; i < n; i++)
matrix(i, i) += 1;
void Matrix::extractColumn(Vector& vector, int c) { if (m != vector.size)
cerr << "[Matrix::extract_column]: Matrix and Vector sizes don't match\n"; return;
for (int i = 0; i < m; i++)
vector(i) = (*this)(i, c);
// Ez a függvény kiírja a mátrixot a konzolra void matrixShow(const Matrix& matrix, const string& str = "") { cout << str << "\n"; for (int i = 0; i < matrix.m; i++)
for (int j = 0; j < matrix.n; j++)
printf(" %8.3f", matrix(i, j));
printf("\n");
printf("\n"); }
// Ez a függvény számítja az ||A - B||^2 L2-normát double matrixCompare(const Matrix& A, const Matrix& B) { if (A.m != B.m or A.n != B.n)
return numeric_limits<double>::max();
double norm = 0; for (int i = 0; i < A.m; i++)
for (int j = 0; j < A.n; j++)
norm += (A(i, j) - B(i, j)) * (A(i, j) - B(i, j));
norm /= A.m * A.n; return norm; }
// Ez a függvény számítja ki a mátrix QR-felbontását void householder(Matrix& matrix, Matrix& R, Matrix& Q) { int m = matrix.m; int n = matrix.n; vector<Matrix> qArray(m); Matrix z(matrix); Matrix z1; for (int k = 0; k < n && k < m - 1; k++)
Vector e(m), x(m); double a; z1.computeMinor(z, k); z1.extractColumn(x, k); a = x.calculateNorm(); if (matrix(k, k) > 0)
a = -a;
for (int i = 0; i < e.size; i++)
e(i) = i == k;
vmadd(x, e, a, e); e.rescaleUnit(); computeHouseholderFactor(qArray[k], e); z.multiply(qArray[k], z1);
Q = qArray; for (int i = 1; i < n && i < m - 1; i++)
z1.multiply(qArray[i], Q); Q = z1;
R.multiply(Q, matrix); Q.transpose(); }
// HA program fő függvénye, a belépési pont int main() { double in[] = { { 12, -51, 4}, { 6, 167, -68}, { -4, 24, -41}, { -1, 1, 0}, { 2, 0, 3},
Matrix A(in); Matrix Q, R; matrixShow(A, "A"); // Függvényhívás, kiírja az A mátrixot a konzolra // A QR-felbontás kiszámítása householder(A, R, Q); matrixShow(Q, "Q"); // Függvényhívás, kiírja a Q mátrixot a konzolra matrixShow(R, "R"); // Függvényhívás, kiírja az R mátrixot a konzolra Matrix ACheck; ACheck.multiply(Q, R); // A Q * R mátrixszorzás kiszámítása // Az L2-norma kiszámítása ||A - ACheck||^2 double l2norm = matrixCompare(A, ACheck); // Függvényhívás, összehasonlítja a Q * R szorzatot az eredeti A mátrixszal if (l2norm < 1e-12)
cout << "A QR-felbontás korrekt." << endl; // Konzolra írás
else
cout << "A QR-felbontás nem korrekt." << endl; // Konzolra írás
Jegyzetek
Források Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989 Gerhard Opfer: Numerische Mathematik für Anfänger. Eine Einführung für Mathematiker, Ingenieure und Informatiker, 5. Aufl., Vieweg + Teubner, Wiesbaden 2008, Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage, Walter de Gruyter Verlag, Berlin und Boston 2020, Fordítás
Kategória:Lineáris algebra