Numerika pro teoretické fyziky ← →

Kapitola 12

Numerická lineární algebra. Řešení přeurčené soustavy

Řešení přeurčeného systému \(Ax = b\) metodou nejmenších čtverců

Úlohou je nalézt takové \(x\), aby norma \(\|Ax - b\|_2\) byla nejmenší. Geometricky jde o situaci v prostoru \(\mathbb{C}^m\), kterou znázorňuje interaktivní ukázka: hledáme kolmý průmět vektoru \(b\) do oboru hodnot \(\mathcal{R}(A)\), přičemž reziduum \(r = b - Ax\) je na tento podprostor kolmé. Rozměry jednotlivých činitelů soustavy ukazuje interaktivní ukázka.

Interaktivní ukázka · Geometrie metody nejmenších čtverců

Geometrie nejmenších čtverců: šikmá přímka \(\mathcal{R}(A)\) procházející počátkem, čárkovaná šipka k bodu \(b\) a kolmice z něj na tuto přímku (s vyznačeným pravým úhlem). Situace je vykreslena v rovině, tedy pro \(m = 2\) a \(n = 1\): \(\mathcal{R}(A)\) je přímka daná jediným sloupcem \(a\) matice \(A\). Táhněte bodem \(b\) i úchytem \(a\) — průmět \(y = Ax = Pb\), reziduum \(r\) i skalární součin \(a^\dagger r\) se přepočítávají průběžně. Posuvníkem \(s\) pak odjeďte od optima podél \(\mathcal{R}(A)\) a ověřte si, že vzdálenost od \(b\) roste přesně jako \(\sqrt{\|r\|^2 + s^2}\) — to je Pythagorova věta, o kterou se opírá třetí z podmínek \eqref{eq:11:kolmost} níže.

Interaktivní ukázka · Rozměry soustavy \(Ax = b\)

Rozměrové schéma soustavy: obdélník \(A\) s rozměry \(m \times n\) násobený úzkým vysokým obdélníkem \(x\), rovná se úzkému vysokému obdélníku \(b\). Posuvníky mění \(m\) a \(n\), takže je vidět, kdy je soustava přeurčená, čtvercová či nedourčená, a posuvník „řádek \(i\)“ zvýrazní jednu konkrétní rovnici soustavy. Ze zvolených \(m\) a \(n\) se zároveň počítají odhady náročnosti všech tří metod této kapitoly — vyzkoušejte si na nich tvrzení z odstavce pod vztahem \eqref{eq:11:narocnost_qr}, že pro \(m \gg n\) je QR dvakrát dražší než normální rovnice, kdežto pro \(m \sim n\) jsou obě náročnosti srovnatelné.

Zde \(P\) je projektor na \(\mathcal{R}(A)\).

Příklad

Typickým příkladem je lineární či polynomiální regrese, obecně proložení dat lineární kombinací určitých funkcí

\begin{equation}\label{eq:11:regrese} f(x) = c_1 \phi_1(x) + \dots + c_n \phi_n(x) , \end{equation}

přičemž máme zadány dvojice \((x_i, f_i)\) pro \(i = 1, \dots, m\). Pokud \(m > n\), dostáváme přeurčenou soustavu a hledáme \(c_1, \dots, c_n\) takové, aby

\[ \sum_{i=1}^{m} |f(x_i) - f_i|^2 \]

bylo nejmenší.

Existují tři základní metody hledání \(x\):

  1. řešením normálních rovnic,
  2. pomocí QR rozkladu,
  3. pomocí SVD rozkladu.

Normální rovnice

Normální rovnice mají tvar

\begin{equation}\label{eq:11:normalni_rovnice} A^\dagger A x = A^\dagger b . \end{equation}

Pokud má \(A\) plnou hodnost \(n\), pak ji má také \(A^\dagger A\), tuto matici lze invertovat, a dostáváme tak jednoznačné řešení

\begin{equation}\label{eq:11:pseudoinverze} x = \underbrace{(A^\dagger A)^{-1} A^\dagger}_{\substack{\text{pseudoinverze } A^+ \text{ matice } A \\ \text{jde o matici } n \times m}}\, b . \end{equation}
Věta (Charakterizace řešení ve smyslu nejmenších čtverců)

Nechť \(A \in \mathbb{C}^{m \times n}\), kde \(m \geq n\), a \(b \in \mathbb{C}^m\). Vektor \(x \in \mathbb{C}^n\) minimalizuje \(\|r\|_2 = \|b - Ax\|_2\) právě tehdy, když

\begin{equation}\label{eq:11:kolmost} A^\dagger r = 0 \iff A^\dagger A x = A^\dagger b \iff Pb = Ax . \end{equation}

První z podmínek v \eqref{eq:11:kolmost} je vyjádřením kolmosti rezidua \(r\) na \(\mathcal{R}(A)\). Druhá z nich z ní plyne dosazením za \(r\) a třetí je zřejmá z Pythagorovy věty.

Projektor \(P\) lze vyjádřit tak, že vztah pro řešení

\[ x = (A^\dagger A)^{-1} A^\dagger b \]

vynásobíme zleva maticí \(A\), čímž dostaneme

\begin{equation}\label{eq:11:projektor} P = A (A^\dagger A)^{-1} A^\dagger , \end{equation}

pokud má \(A\) hodnost \(n\).

Matice \(A^\dagger A\) je symetrická a pozitivně definitní, lze tedy použít Choleského faktorizaci.

Náročnost je následující: sestavení \(A^\dagger A\) stojí \(mn^2\) flops (díky symetrii, jinak dvakrát tolik), výpočet \(A^\dagger b\) stojí \(2mn\) flops a Choleského řešení soustavy \(A^\dagger A x = c\) stojí \(\tfrac{1}{3} n^3\) flops. Celkem tedy

\begin{equation}\label{eq:11:narocnost_normalni} \sim mn^2 + \tfrac{1}{3} n^3 \ \text{flops} . \end{equation}

QR rozklad

Použijeme redukovaný QR rozklad matice \(A\), tedy \(A = \hat{Q}\hat{R}\), jehož schéma ukazuje interaktivní ukázka.

Interaktivní ukázka · Redukovaný QR rozklad \(A = \hat{Q}\hat{R}\)

Schéma redukovaného QR rozkladu — vysoký obdélník rozdělený svislými čarami na sloupce (rozměry \(m\), \(n\)) násobený menším čtvercem \(n \times n\) s nulou \(0\) v dolním trojúhelníku a šrafovaným horním trojúhelníkem. Rozklad se přitom počítá: sloupce zvolené matice se ortogonalizují Gramovou–Schmidtovou metodou (klasickou nebo modifikovanou) a pod plátnem se ukazují hodnoty \(r_{ij}\) i kontrolní veličiny \(\|A - \hat{Q}\hat{R}\|_F\) a \(\|\hat{Q}^\dagger\hat{Q} - I\|_F\). Posuvník „sloupec \(j\)“ zvýrazní vztah \(a_j = r_{1j}q_1 + \dots + r_{jj}q_j\), tedy přesně důvod, proč je \(\hat{R}\) horní trojúhelníková. U Vandermondeovy matice (uzly namačkané k jedničce, tedy téměř závislé sloupce) a \(n = 4\) srovnejte ztrátu ortogonality obou variant — je to ukázka toho, že i matematicky ekvivalentní postupy se numericky chovají velmi různě.

Vektory v \(\hat{Q}\) tvoří bázi v \(\mathcal{R}(A)\), a proto je projektor \(P = \hat{Q}\hat{Q}^\dagger\). Tedy

\begin{equation}\label{eq:11:qr_odvozeni} \hat{Q}\hat{R}x = Ax = Pb = \hat{Q}\hat{Q}^\dagger b , \qquad \text{neboli} \qquad \hat{R}x = \hat{Q}^\dagger b . \end{equation}

Matice \(\hat{R}\) je horní trojúhelníková, takže poslední soustavu vyřešíme zpětnou substitucí, pokud je \(A\) nesingulární.

Náročnost QR faktorizace pomocí Householderových reflexí je

\begin{equation}\label{eq:11:narocnost_qr} \sim 2mn^2 - \tfrac{2}{3}n^3 \ \text{flops} , \end{equation}

což je pro \(m \gg n\) dvakrát více než u metody normálních rovnic, zatímco pro \(m \sim n\) jsou obě náročnosti srovnatelné.

SVD rozklad

Umíme-li spočítat redukovaný SVD rozklad \(A = \hat{U}\hat{\Sigma}\hat{V}^\dagger\), pak \(P = \hat{U}\hat{U}^\dagger\), a tedy

\begin{align*} \hat{U}\hat{\Sigma}V^\dagger x &= Ax = Pb = \hat{U}\hat{U}^\dagger b , \\ \hat{\Sigma}V^\dagger x &= \hat{U}^\dagger b , \end{align*}

odkud

\begin{equation}\label{eq:11:svd_reseni} x = \hat{V}\hat{\Sigma}^{-1}\hat{U}^\dagger b , \end{equation}

pokud jsou všechna \(\sigma_i \neq 0\).

Náročnost je typicky

\begin{equation}\label{eq:11:narocnost_svd} \sim 2mn^2 + 11n^3 , \end{equation}

jde tedy obecně o nejpomalejší z uvedených metod.

Porovnání metod

Metoda normálních rovnic je obecně nejrychlejší, avšak ne vždy stabilní. Doporučeným algoritmem je proto druhá metoda, tedy řešení pomocí QR rozkladu. Jsou-li ovšem některé singulární hodnoty \(\sigma_i\) blízké nule, tj. je-li matice \(A\) téměř singulární, pak je nejstabilnější třetí metoda využívající SVD rozklad.

Poznámka

Pokud \(A\) nemá hodnost \(n\), je nutné specifikovat dodatečnou podmínku, aby bylo \(x\) jednoznačné, například požadovat, aby \(\|x\|_2\) byla nejmenší. V těchto případech je obecně stabilní pouze SVD rozklad.