Vikipedio:Projekto matematiko/QR malkomponaĵo

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
QR malkomponaĵo
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En lineara algebro, la QR malkomponaĵo de matrico estas malkomponaĵo de la matrico enen perpendikulara kaj triangula matrico. La QR malkomponaĵo estas ofte kutima solvi la lineara plej malgranda (kvadratoj, placoj, kvadratigas) problemo. La QR malkomponaĵo estas ankaŭ la bazo por aparta ajgena algoritmo, la QR algoritmo.

Enhavo

1 Difino
2 Komputanta la QR malkomponaĵo
3 Komputanta _QR_ per Gramo-Schmidt-a
- 3.1 Ekzemplo
4 Komputanta _QR_ per Majstro (reflektoj, reflektas)
- 4.1 Ekzemplo
5 Komputanta _QR_ per _Givens_ (rotacioj, rotacias, turnadoj, turnadas)
- 5.1 Ekzemplo
6 Vidi ankaŭ
7 Ekstera (ligoj, ligas)

[redaktu] Difino

QR malkomponaĵo de (reala, reela) kvadrata matrico A estas malkomponaĵo de A kiel

$A = QR, \,$

kie Q estas perpendikulara matrico (signifo (tiu, ke, kiu) Q^TQ = Mi) kaj R estas supra triangula matrico.

Pli ĝenerale, ni povas faktoro $m$ × $n$ matrico (kun m ≥ n) de plena rango kiel la (produkto, produto) de $m$ × $n$ unuargumenta matrico (en la (senso, senco) (tiu, ke, kiu) Q^∗Q = Mi) kaj $n$ × $n$ supra triangula matrico.

Ĉi tiu faktorigo estas unika se ni postuli (tiu, ke, kiu) la diagonalaj eroj de R estas pozitiva.

[redaktu] Komputanta la QR malkomponaĵo

Estas kelkaj manieroj por reale komputanta la QR malkomponaĵo, kiel per _Givens_ (rotacioj, rotacias, turnadoj, turnadas), Majstraj transformoj, aŭ la Gramo-Schmidt-a malkomponaĵo. Ĉiu havas nombro de (avantaĝoj, avantaĝas) kaj malavantaĝoj.

[redaktu] Komputanta _QR_ per Gramo-Schmidt-a

Memori la Gramo-Schmidt-a maniero, kun la (vektoroj, vektoras) al esti konsiderata en la procezo kiel kolumnoj de la matrico $A=(\mathbf{a}_1| \cdots|\mathbf{a}_n)$ . Tiam

$\mathbf{u}_1 = \mathbf{a}_1, \qquad\mathbf{e}_1 = {\mathbf{u}_1 \over \|\mathbf{u}_1\|}$

$\mathbf{u}_2 = \mathbf{a}_2-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_2, \qquad\mathbf{e}_2 = {\mathbf{u}_2 \over \|\mathbf{u}_2\|}$

$\mathbf{u}_3 = \mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_2}\,\mathbf{a}_3, \qquad\mathbf{e}_3 = {\mathbf{u}_3 \over \|\mathbf{u}_3\|}$

$\vdots$

$\mathbf{u}_k = \mathbf{a}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{e}_j}\,\mathbf{a}_k,\qquad\mathbf{e}_k = {\mathbf{u}_k\over\|\mathbf{u}_k\|}$

(Naive, Krude, Nature) tiam, ni reordigi la ekvacioj (do, tiel) la a_mis estas la subjekto, al preni jeno

$\mathbf{a}_1 = \mathbf{e}_1\|\mathbf{u}_1\|$

$\mathbf{a}_2 = \mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_2+\mathbf{e}_2\|\mathbf{u}_2\|$

$\mathbf{a}_3 = \mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_3+\mathrm{proj}_{\mathbf{e}_2}\,\mathbf{a}_3+\mathbf{e}_3\|\mathbf{u}_3\|$

$\vdots$

$\mathbf{a}_k = \sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{e}_j}\,\mathbf{a}_k+\mathbf{e}_k\|\mathbf{u}_k\|$

Ĉiu de ĉi tiuj projekcioj de la (vektoroj, vektoras) $\mathbf{a}_i$ sur unu de ĉi tiuj $e j$ estas nure la ena (produkto, produto) de la du, ekde la (vektoroj, vektoras) estas normigita.

Nun ĉi tiuj ekvacioj povas esti skribita en matrico (formo, formi), nome,

$\left(\mathbf{e}_1\left|\ldots\right|\mathbf{e}_n\right) \begin{pmatrix} \|\mathbf{u}_1\| & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \|\mathbf{u}_2\| & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \|\mathbf{u}_3\| & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

Sed la (produkto, produto) de ĉiu (linio, vico) kaj kolumno de la matricoj pli supre doni ni respektiva kolumno de A (tiu, ke, kiu) ni startita kun, kaj kune, ili doni ni la matrico A, (do, tiel) ni havi faktorigita A enen perpendikulara matrico Q (la matrico de e_ks), tra Gramo Schmidt-a, kaj la evidenta supra triangula matrico kiel resto R.

Alternative, $\begin{matrix} R \end{matrix}$ povas esti kalkulita kiel sekvas:

Memori (tiu, ke, kiu) $\begin{matrix}Q\end{matrix} = \left(\mathbf{e}_1\left|\ldots\right|\mathbf{e}_n\right).$ Tiam, ni havi

$\begin{matrix} R = Q^{T}A = \end{matrix} \begin{pmatrix} \langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$

(Tononomo, Noto, Noti) (tiu, ke, kiu) $\langle\mathbf{e}_j,\mathbf{a}_j\rangle = \|\mathbf{u}_j\|,$ $\langle\mathbf{e}_j,\mathbf{a}_k\rangle = 0 \mathrm{~~for~~} j > k,$ kaj $Q Q T = I$ , (do, tiel) $Q T = Q - 1$ .

[redaktu] Ekzemplo

Konsideri la malkomponaĵo de

$A = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix} .$

Memori la perpendikulara matrico $Q$ tia (tiu, ke, kiu)

$\begin{matrix} Q\,Q^{T} = I. \end{matrix}$

Tiam, ni povas kalkuli $Q$ per Gramo-Schmidt-a kiel sekvas:

$U = \begin{pmatrix} \mathbf u_1 & \mathbf u_2 & \mathbf u_3 \end{pmatrix} = \begin{pmatrix} 12 & -69 & -58 \\ 6 & 158 & 6 \\ -4 & 30 & -165 \end{pmatrix};$

$Q = \begin{pmatrix} \frac{\mathbf u_1}{\|\mathbf u_1\|} & \frac{\mathbf u_2}{\|\mathbf u_2\|} & \frac{\mathbf u_3}{\|\mathbf u_3\|} \end{pmatrix} = \begin{pmatrix} 6/7 & -69/175 & -58/175 \\ 3/7 & 158/175 & 6/175 \\ -2/7 & 6/35 & -33/35 \end{pmatrix};$

Tial, ni havi

$\begin{matrix} A = Q\,Q^{T}A = Q R; \end{matrix}$

$\begin{matrix} R = Q^{T}A = \end{matrix} \begin{pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & 35 \end{pmatrix}.$

Konsiderantaj ciferecaj eraroj de finia precizeca operacio en _MATLAB_, ni havi (tiu, ke, kiu)

$\begin{matrix} Q = \end{matrix} \begin{pmatrix} 0.857142857142857 & -0.394285714285714 & -0.331428571428571 \\ 0.428571428571429 & 0.902857142857143 & 0.034285714285714 \\ -0.285714285714286 & 0.171428571428571 & -0.942857142857143 \end{pmatrix};$

$\begin{matrix} R = \end{matrix} \begin{pmatrix} 14 & 21 & -14 \\ 1.11022302462516 \times 10^{-16} & 175 & -70 \\ -1.77635683940025 \times 10^{-15} & -5.32907051820075 \times 10^{-14} & 35 \end{pmatrix}.$

[redaktu] Komputanta _QR_ per Majstro (reflektoj, reflektas)

Majstra reflekto (aŭ Majstra transformo) estas transformo (tiu, ke, kiu) prenas vektoro kaj reflektas ĝi pri iu ebeno. Ni povas uzi ĉi tiu propraĵo al kalkuli la _QR_ faktorigo de matrico.

Q povas kutimi reflekti vektoro en tia vojo (tiu, ke, kiu) ĉiuj (koordinatoj, koordinatas) sed unu sveni.

Estu $\mathbf{x}$ esti ajna m-dimensia kolumna vektoro tia (tiu, ke, kiu) || $\mathbf{x}$ || = |α| por skalaro α (se la algoritmo estas realigita uzanta (glitpunkta, glitkoma) aritmetiko, tiam α devus preni la sama signo kiel la unua koordinato de $\mathbf{x}$ al eviti malprofito de signifeco).

Tiam, kie $\mathbf{e}_1$ estas la vektoro (1,0,...,0)^T, kaj ||·|| la Eŭklida normo, aro

$\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1,$

$\mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|},$

$Q = I - 2 \mathbf{v}\mathbf{v}^T.$

$Q$ estas Majstra matrico kaj

$Qx = (\alpha, 0, \cdots, 0)^T.\,$

Ĉi tiu povas kutimi (laŭgrade, pomalmulte) (konverti, konverto) m-per-n matrico A al supra triangula (formo, formi). Unua, ni multipliki A kun la Majstra matrico Q₁ ni ricevi kiam ni elekti la unua matrica kolumno por x. Ĉi tiuj rezultoj en matrico Qa kun nuloj en la (maldekstre, restis) kolumno (krom la unua (linio, vico)).

$Q_1A = \begin{bmatrix} \alpha_1&\star&\dots&\star\\ 0 & & & \\ \vdots & & A' & \\ 0 & & & \end{bmatrix}$

Ĉi tiu povas ripetiĝi por A′ (ricevis de A per (forviŝanta, foriganta) la unua (linio, vico) kaj unua kolumno), rezultanta en Majstra matrico Q′₂. (Tononomo, Noto, Noti) (tiu, ke, kiu) Q′₂ estas (pli minuskla, pli malgranda) ol Q₁. Ekde ni bezona ĝi (reale, reele) al operacii sur Q₁A anstataŭ A′ ni (bezoni, bezono, necesa) al elvolvi ĝi al la supra (maldekstre, restis), enspacanta en 1, aŭ en ĝenerala:

$Q_k = \begin{pmatrix} I_{k-1} & 0\\ 0 & Q_k'\end{pmatrix}.$

Post $t$ (ripetoj, ripetas) de ĉi tiu procezo, $t = min(m - 1, n)$ ,

$R = Q_t \cdots Q_2Q_1A$

estas supra triangula matrico. (Do, Tiel), kun

$Q = Q_1Q_2 \cdots Q_t$

$A = Q R$ estas QR malkomponaĵo de $A$ .

Ĉi tiu maniero havas pli granda cifereca stabileco ol la Gramo-Schmidt-a maniero pli supre.

[redaktu] Ekzemplo

Estu ni kalkuli la malkomponaĵo de

$A = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix}.$

Unua, ni (bezoni, bezono, necesa) al trovi reflekto (tiu, ke, kiu) (konvertas, konvertoj) la unua kolumno de matrico A, vektoro $\mathbf{a}_1 = (12, 6, -4)^T$ , al $\|\mathbf{a}_1\| \;\mathrm{e}_1 = (14, 0, 0)^T.$

Nun,

$\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1,$

kaj

$\mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|},$ .

Ĉi tie,

α = 14

kaj $\mathbf{x} = \mathbf{a}_1 = (12, 6, -4)^T$

Pro tio

$\mathbf{u} = (-2, 6, -4)^T$ kaj $\mathbf{v} = {1 \over \sqrt{14}}(-1, 3, -2)^T$ , kaj tiam

$Q_1 = I - {2 \over \sqrt{14}\sqrt{14}} \begin{pmatrix} -1 \\ 3 \\ -2 \end{pmatrix}\begin{pmatrix} -1 & 3 & -2 \end{pmatrix}$

$= I - {1 \over 7}\begin{pmatrix} 1 & -3 & 2 \\ -3 & 9 & -6 \\ 2 & -6 & 4 \end{pmatrix}$

$= \begin{pmatrix} 6/7 & 3/7 & -2/7 \\ 3/7 &-2/7 & 6/7 \\ -2/7 & 6/7 & 3/7 \\ \end{pmatrix}.$

Nun observi:

$Q_1A = \begin{pmatrix} 14 & 21 & -14 \\ 0 & -49 & -14 \\ 0 & 168 & -77 \end{pmatrix},$

(do, tiel) ni jam havi preskaŭ triangula matrico. Ni nur (bezoni, bezono, necesa) al nulo la (3, 2) (termo, koeficiento, elemento).

Preni la (1, 1) minoro, kaj tiam apliki la procezo denove al

$A' = M_{11} = \begin{pmatrix} -49 & -14 \\ 168 & -77 \end{pmatrix}.$

Per la sama maniero kiel pli supre, ni ricevi la matrico de la Majstra transformo

$Q_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -7/25 & 24/25 \\ 0 & 24/25 & 7/25 \end{pmatrix}$

post plenumante direkta sumo kun 1 al fari certa la venonta (ŝtupo, paŝi) en la procezo (laboroj, laboras) pozitive.

Nun, ni trovi

$Q=Q_1Q_2=\begin{pmatrix} 6/7 & -69/175 & 58/175 \\ 3/7 & 158/175 & -6/175 \\ -2/7 & 6/35 & 33/35 \end{pmatrix}$

$R=Q^\top A=\begin{pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & -35 \end{pmatrix}.$

La matrico Q estas perpendikulara kaj R estas supra triangula, (do, tiel) A = _QR_ estas la postulis _QR_-malkomponaĵo.

[redaktu] Komputanta _QR_ per _Givens_ (rotacioj, rotacias, turnadoj, turnadas)

_QR_ (malkomponaĵoj, malkomponaĵas) povas ankaŭ esti komputita kun serio de _Givens_ (rotacioj, rotacias, turnadoj, turnadas). Ĉiu turnada nula ero en la kromdiagonalo suba de la matrico, (formante, formanta) la R matrico. La kunmeto de ĉiu _Givens_ (rotacioj, rotacias, turnadoj, turnadas) (formoj, formas) la perpendikulara Q matrico.

En praktiko, _Givens_ (rotacioj, rotacias, turnadoj, turnadas) estas ne reale (aperis, plenumita) per konstruaĵa tuta matrico kaj farante matrica multipliko. _Givens_ turnada proceduro estas uzita anstataŭe kiu faras la ekvivalento de la _sparse_ _Givens_ matrica multipliko, sen la superflua laboro de ansanta la _sparse_ eroj. La _Givens_ turnada proceduro estas utila en (situacioj, situacias) kie nur relative kelkaj for diagonalaj eroj (bezoni, bezono, necesa) al esti (nuligantita, radikita, nulita), kaj estas pli facile _parallelized_ ol Majstraj transformoj.

[redaktu] Ekzemplo

Estu ni kalkuli la malkomponaĵo de

$A = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix}$

Unua, ni (bezoni, bezono, necesa) al (formo, formi) rotacia matrico (tiu, ke, kiu) estos nulo la _lowermost_ (maldekstre, restis) ero, $\mathbf{a}_{31} = -4$ . Ni (formo, formi) ĉi tiu matrico uzanta la _Givens_ turnada maniero, kaj (voko, voki) la matrico $G 1$ . Ni estos unua turni la vektoro $(6, - 4)$ , al punkto laŭ la X akso. Ĉi tiu vektoro havas angulo $\theta = \arctan({-4 \over 6})$ . Ni krei la perpendikulara _Givens_ rotacia matrico, $G 1$ :

$G_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos(\theta) & \sin(\theta) \\ 0 & -\sin(\theta) & \cos(\theta) \end{pmatrix}$

$\approx \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0.83205 & -0.55470 \\ 0 & 0.55470 & 0.83205 \end{pmatrix}$

Kaj la rezulto de $G 1 A$ nun havas nulo en la $\mathbf{a}_{31}$ ero.

$G_1A \approx \begin{pmatrix} 12 & -51 & 4 \\ 7.21110 & 125.63959 & -33.83671 \\ 0 & 112.60414 & -71.83368 \end{pmatrix}$

Ni povas simile (formo, formi) _Givens_ matricoj $G 2$ kaj $G 3$ , kiu estos nulo la sub-diagonalaj eroj $a 21$ kaj $a 32$ , (formante, formanta) rekta matrico $R$ . La perpendikulara matrico $Q T$ estas (formita, formularita, knedita) de la kunmeto de ĉiu _Givens_ matricoj $Q T = G 3 G 2 G 1$ . Tial, ni havi $G 3 G 2 G 1 A = Q T A = R$ , kaj la _QR_ malkomponaĵo estas $A = Q R$ .

[redaktu] Vidi ankaŭ

Polusa malkomponaĵo
Ajgena malkomponaĵo
Spektra malkomponaĵo

[redaktu] Ekstera (ligoj, ligas)

Surlinia Matrica Kalkulilo Plenumas QR malkomponaĵo de matricoj.

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_QR_malkompona%C4%B5o_f317.html"

Kategorioj: Artikoloj por polurado kaj movo | Matrica teorio | Cifereca lineara algebro

Vikipedio:Projekto matematiko/QR malkomponaĵo

El Vikipedio

Enhavo

[redaktu] Difino

[redaktu] Komputanta la QR malkomponaĵo

[redaktu] Komputanta _QR_ per Gramo-Schmidt-a

[redaktu] Ekzemplo

[redaktu] Komputanta _QR_ per Majstro (reflektoj, reflektas)

[redaktu] Ekzemplo

[redaktu] Komputanta _QR_ per _Givens_ (rotacioj, rotacias, turnadoj, turnadas)

[redaktu] Ekzemplo

[redaktu] Vidi ankaŭ

[redaktu] Ekstera (ligoj, ligas)

Views

Navigado

Serĉu

Aliaj lingvoj