Muszę zaimplementować funkcję, która bierze macierz \(\displaystyle{ A}\) i wektor \(\displaystyle{ y}\) oraz zwraca: wektor \(\displaystyle{ x}\) (będący rozwiązaniem liniowego zadania najmniejszych kwadratów), macierz \(\displaystyle{ R}\) (z rozkładu \(\displaystyle{ QR}\)) i macierz \(\displaystyle{ B}\), której kolumny składają się z wektorów \(\displaystyle{ h_i}\) (wektory te definiują kolejne macierze Householdera, \(\displaystyle{ Q = H_1*...*H_n}\)). Dodatkowo podczas wyliczania potrzebnych rzeczy nie można jawnie wyznaczyć żadnej macierzy \(\displaystyle{ H_i}\) oraz macierzy \(\displaystyle{ Q}\). W związku z tym:
1) Jak mogę obliczyć potrzebne rzeczy bez złamania powyższego zakazu?
2) Jeśli już dostanę macierz \(\displaystyle{ R}\) i \(\displaystyle{ B}\) z funkcji, jak mogę obliczyć \(\displaystyle{ QR}\), nadal trzymając się powyższego zakazu?
Rozkład QR
Re: Rozkład QR
Szukam również odpowiedzi. Pomoc jest bardzo ceniona.splinter pisze: ↑12 gru 2019, o 18:47 Muszę zaimplementować funkcję, która bierze macierz \(\displaystyle{ A}\) i wektor \(\displaystyle{ y}\) oraz zwraca: wektor \(\displaystyle{ x}\) (będący rozwiązaniem liniowego zadania najmniejszych kwadratów), macierz \(\displaystyle{ R}\) (z rozkładu \(\displaystyle{ QR}\)) i macierz \(\displaystyle{ B}\), której kolumny składają się z wektorów \(\displaystyle{ h_i}\) (wektory te definiują kolejne macierze Householdera, \(\displaystyle{ Q = H_1*...*H_n}\)). Dodatkowo podczas wyliczania potrzebnych rzeczy nie można jawnie wyznaczyć żadnej macierzy \(\displaystyle{ H_i}\) oraz macierzy \(\displaystyle{ Q}\). W związku z tym:
1) Jak mogę obliczyć potrzebne rzeczy bez złamania powyższego zakazu?
2) Jeśli już dostanę macierz \(\displaystyle{ R}\) i \(\displaystyle{ B}\) z funkcji, jak mogę obliczyć \(\displaystyle{ QR}\), nadal trzymając się powyższego zakazu?
Z góry dziękuję,
pozdrowienia
Oliver
-
janusz47
- Użytkownik
- Posty: 7917
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Re: Rozkład QR
Dokonujemy rozkładu \(\displaystyle{ Q R}\) macierzy \(\displaystyle{ A\in R^{m, n}}\) za pomocą odbić Housoldera
\(\displaystyle{ Q = H_{1}\cdot H_{2}\cdot ...\cdot H_{l}, \ \ l = min(m, m-1). }\)
Czynniki \(\displaystyle{ H_{k} = I - \frac{v_{k} \cdot v^{T}_{k}}{\gamma _{k}} , \ \ k=1,2,...,l }\), należy reprezentować wektorami \(\displaystyle{ \vec{v}_{k} = [ 0,...,0, v_{kk},...,v_{mk}]^{T} }\) spełniającymi warunek \(\displaystyle{ v_{kk} = \gamma_{k} = \frac{v^{T}_{k}\cdot v_{k}}{2}.}\)
Znaczące składowe \(\displaystyle{ v_{ik}, \ i \geq k }\) oraz naddiagonalne elementy \(\displaystyle{ r_{kj} , \ \ k< j }\) macierzy \(\displaystyle{ R }\) przechowujemy osobno.
Algorytm 1
\(\displaystyle{ l:= min\{ n, m-1\} }\)
\(\displaystyle{ for \ \ k:= 1 \ \ to \ \ l \ \ do }\)
\(\displaystyle{ K1: \rho_{k} : = \parallel [a_{kk}, ..., a_{mk}]^{T} \parallel , \ \ if \ \ a_{kk}> 0 \ \ then \ \ \rho_{k} = -\rho_{k} }\)
\(\displaystyle{ a_{kk} := 1 - \frac{a_{kk}}{\rho_{k}}, \ \ for \ \ i:= k+1 \ \ to \ \ m \ \ do \ \ a_{ik}:= \frac{a_{ik}}{\rho_{k}} }\)
\(\displaystyle{ K2: \ \ for \ \ j:= k+1 \ \ to \ \ n \ \ do }\)
\(\displaystyle{ \beta: = 0, \ \ for \ \ i:= k \ \ to \ \ m \ \ do \ \ \beta:= \beta + a_{ik} \ast a_{ij} }\)
\(\displaystyle{ \beta:= \frac{\beta}{a_{kk}}, \ \ for \ \ i:= k \ \ to \ \ m \ \ do \ \ a_{ij} := a_{ij} - a_{ik} \ast \beta }\)
\(\displaystyle{ if \ \ l< n \ \ then \ \ \rho_{n}: = a_{nn} .}\)
Zadanie najmniejszych kwadratów
Stosując rozkład \(\displaystyle{ A = Q R }\) macierzy \(\displaystyle{ A\in R^{m,n} }\) wyznaczony powyższym algorytmem, gdzie \(\displaystyle{ r_{kk} = \rho_{k} \neq 0 , \ \ k = 1,2,...,n }\), można znaleźć rozwiązanie \(\displaystyle{ x\in R^{n} }\) zadania \(\displaystyle{ Ax = b }\) dla danego wektora \(\displaystyle{ b }\) , a także wektor residualny \(\displaystyle{ r = b - Ax \in R^{m} }\) i jego normę \(\displaystyle{ \parallel r \parallel .}\)
Algorytm 2
\(\displaystyle{ l: = min \{ n, m-1 \} }\)
\(\displaystyle{ ( b: = Q^{T}\cdot b):}\)
\(\displaystyle{ for \ \ k:= 1 \ \ to \ \ l \ \ do }\)
\(\displaystyle{ \beta:= 0 }\)
\(\displaystyle{ for \ \ i:= k \ \ to \ \ m \ \ do \ \ \beta:= \beta + a_{ik}\ast b_{i} }\)
\(\displaystyle{ \beta: = \frac{\beta}{a_{kk}} }\)
\(\displaystyle{ for \ \ i:= k \ \ to \ \ m \ \ do \ \ b_{i}:= b_{i} - a_{ik} \ast \beta }\)
Algorytm 3
\(\displaystyle{ K3: }\) Oblicz wektor \(\displaystyle{ b: = fl(Q^{T}\cdot b) }\) algorytmem 2
\(\displaystyle{ K4: }\) Przedstaw \(\displaystyle{ b }\) w postaci \(\displaystyle{ [ c_{n}, \overline{c}_{m-n}]^{T} }\)
Przymij \(\displaystyle{ x: = c , \ \ b = [ 0, \overline{c} ]^{T}, \ \ r:= \parallel \overline{c} \parallel }\)
\(\displaystyle{ K5: }\) Oblicz \(\displaystyle{ b = fl( Q\cdot b) }\)
\(\displaystyle{ K6: }\) Oblicz \(\displaystyle{ x:= fl(R^{-1}\cdot x) }\)
\(\displaystyle{ Q = H_{1}\cdot H_{2}\cdot ...\cdot H_{l}, \ \ l = min(m, m-1). }\)
Czynniki \(\displaystyle{ H_{k} = I - \frac{v_{k} \cdot v^{T}_{k}}{\gamma _{k}} , \ \ k=1,2,...,l }\), należy reprezentować wektorami \(\displaystyle{ \vec{v}_{k} = [ 0,...,0, v_{kk},...,v_{mk}]^{T} }\) spełniającymi warunek \(\displaystyle{ v_{kk} = \gamma_{k} = \frac{v^{T}_{k}\cdot v_{k}}{2}.}\)
Znaczące składowe \(\displaystyle{ v_{ik}, \ i \geq k }\) oraz naddiagonalne elementy \(\displaystyle{ r_{kj} , \ \ k< j }\) macierzy \(\displaystyle{ R }\) przechowujemy osobno.
Algorytm 1
\(\displaystyle{ l:= min\{ n, m-1\} }\)
\(\displaystyle{ for \ \ k:= 1 \ \ to \ \ l \ \ do }\)
\(\displaystyle{ K1: \rho_{k} : = \parallel [a_{kk}, ..., a_{mk}]^{T} \parallel , \ \ if \ \ a_{kk}> 0 \ \ then \ \ \rho_{k} = -\rho_{k} }\)
\(\displaystyle{ a_{kk} := 1 - \frac{a_{kk}}{\rho_{k}}, \ \ for \ \ i:= k+1 \ \ to \ \ m \ \ do \ \ a_{ik}:= \frac{a_{ik}}{\rho_{k}} }\)
\(\displaystyle{ K2: \ \ for \ \ j:= k+1 \ \ to \ \ n \ \ do }\)
\(\displaystyle{ \beta: = 0, \ \ for \ \ i:= k \ \ to \ \ m \ \ do \ \ \beta:= \beta + a_{ik} \ast a_{ij} }\)
\(\displaystyle{ \beta:= \frac{\beta}{a_{kk}}, \ \ for \ \ i:= k \ \ to \ \ m \ \ do \ \ a_{ij} := a_{ij} - a_{ik} \ast \beta }\)
\(\displaystyle{ if \ \ l< n \ \ then \ \ \rho_{n}: = a_{nn} .}\)
Zadanie najmniejszych kwadratów
Stosując rozkład \(\displaystyle{ A = Q R }\) macierzy \(\displaystyle{ A\in R^{m,n} }\) wyznaczony powyższym algorytmem, gdzie \(\displaystyle{ r_{kk} = \rho_{k} \neq 0 , \ \ k = 1,2,...,n }\), można znaleźć rozwiązanie \(\displaystyle{ x\in R^{n} }\) zadania \(\displaystyle{ Ax = b }\) dla danego wektora \(\displaystyle{ b }\) , a także wektor residualny \(\displaystyle{ r = b - Ax \in R^{m} }\) i jego normę \(\displaystyle{ \parallel r \parallel .}\)
Algorytm 2
\(\displaystyle{ l: = min \{ n, m-1 \} }\)
\(\displaystyle{ ( b: = Q^{T}\cdot b):}\)
\(\displaystyle{ for \ \ k:= 1 \ \ to \ \ l \ \ do }\)
\(\displaystyle{ \beta:= 0 }\)
\(\displaystyle{ for \ \ i:= k \ \ to \ \ m \ \ do \ \ \beta:= \beta + a_{ik}\ast b_{i} }\)
\(\displaystyle{ \beta: = \frac{\beta}{a_{kk}} }\)
\(\displaystyle{ for \ \ i:= k \ \ to \ \ m \ \ do \ \ b_{i}:= b_{i} - a_{ik} \ast \beta }\)
Algorytm 3
\(\displaystyle{ K3: }\) Oblicz wektor \(\displaystyle{ b: = fl(Q^{T}\cdot b) }\) algorytmem 2
\(\displaystyle{ K4: }\) Przedstaw \(\displaystyle{ b }\) w postaci \(\displaystyle{ [ c_{n}, \overline{c}_{m-n}]^{T} }\)
Przymij \(\displaystyle{ x: = c , \ \ b = [ 0, \overline{c} ]^{T}, \ \ r:= \parallel \overline{c} \parallel }\)
\(\displaystyle{ K5: }\) Oblicz \(\displaystyle{ b = fl( Q\cdot b) }\)
\(\displaystyle{ K6: }\) Oblicz \(\displaystyle{ x:= fl(R^{-1}\cdot x) }\)