Oppiskele Matriisihajotelman Perusteet | Lineaarialgebran Perusteet

Järjestelmien, kuten $A \vec{x} = \vec{b}$ , ratkaiseminen voi olla laskennallisesti raskasta, erityisesti suurissa järjestelmissä.

Matriisin hajotelma yksinkertaistaa tätä prosessia jakamalla matriisin $A$ yksinkertaisempiin osiin, jotka voidaan ratkaista vaiheittain.

LU vs QR

Matriisi $A$ hajotetaan muihin rakenteellisiin matriiseihin.

LU-hajotelma

Hajotetaan $A$ alemmaksi ja ylemmäksi kolmiomatriisiksi:

Rakennetaan Gaussin eliminaatiolla;
Toimii parhaiten neliömatriiseille.

A = LU

QR-hajotelma

Hajotetaan $A$ ortogonaaliseksi ja ylemmäksi matriisiksi:

Käytetään usein ei-neliömatriiseille;
Ihanteellinen pienimmän neliösumman ongelmiin tai kun LU ei toimi.

A = QR

LU-hajotelma

Aloitetaan neliömatriisilla:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Tavoitteena on kirjoittaa tämä muodossa:

A = LU

Missä:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Tämä hajotelma on mahdollinen jos A on neliö ja kääntyvä.

Tärkeitä huomioita:

Alemmissa kolmiomatriiseissa kaikki päädiagonaalin yläpuoliset alkiot ovat nollia, mikä helpottaa eteenpäinsuuntaista sijoitusta;
Ylemmissä kolmiomatriiseissa diagonaalin alapuolella on nollia, mikä tekee taaksepäinsuuntaisesta sijoituksesta suoraviivaista;
Ortogonaalisessa matriisissa sarakkeet ovat ortonormaaleja vektoreita (vektorit, joiden pituus on 1 ja jotka ovat kohtisuorassa toisiinsa nähden);
Tämä ominaisuus säilyttää vektorin pituuden ja kulmat, mikä on hyödyllistä pienimmän neliösumman ratkaisuissa ja parantaa numeerista vakautta.

Gaussin eliminointi

Sovella Gaussin eliminointia poistaaksesi ylävasemman pivotin alapuolella olevan alkion:

R_2 \rarr R_2 - \frac{6}{4}R_1

Tämä antaa meille:

R'_2 = [0, -1.5]

Joten päivitetyt matriisit ovat:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Ja rivitoimituksesta tiedämme:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Tärkeitä huomioita:

Gaussin eliminointi poistaa järjestelmällisesti pivot-alkion alapuolella olevat alkiot jokaisessa sarakkeessa vähentämällä pivot-rivin skaalattuja versioita alemmista riveistä;
Tämä prosessi muuntaa A:n yläkolmiomatriisiksi U;
Eliminoinnissa käytetyt kertoimet tallennetaan matriisiin L, jolloin A voidaan esittää tulona LU.

LU-hajotelman tulos

Tarkistetaan:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nyt järjestelmä $A \vec{x} = \vec{b}$ voidaan ratkaista kahdessa vaiheessa:

Ratkaise $L \vec{y} = \vec{b}$ eteenpäin sijoittamalla;
Ratkaise $U \vec{x} = \vec{y}$ taaksepäin sijoittamalla.

QR-hajotelma

Halutaan esittää matriisi $A$ kahden matriisin tulona:

A = QR

Missä:

$A$ on syötematriisi (esim. data, kertoimet jne.);
$Q$ on ortogonaalinen matriisi (sen sarakkeet ovat ortonormaalivektoreita);
$R$ on yläkolmiomatriisi.

Esimerkki muotojen jaosta:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Tätä hajotelmaa käytetään usein kun:

Matriisi A ei ole neliömatriisi;
Ratkaistaan pienimmän neliösumman ongelmia;
LU-hajotelma ei ole stabiili.

Mitä ovat ortonormaalit vektorit?

Ortogonaaliset vektorit

Kaksi vektoria $u, v$ ovat ortogonaalisia, jos niiden pistetulo on nolla:

u \cdot v = 0

Normalisoitu vektori

Vektori $u$ on normalisoitu, kun $|u| = 1$ .

Ortonormaali joukko

Vektorijoukko $\{q_1, q_2, ..., q_k\}$ on ortonormaali, jos jokainen vektori on yksikköpituinen ja ne ovat keskenään ortogonaalisia:

q_i \cdot q_j = \begin{cases} 1,\ \text{jos}\ \ i = j,\\ 0,\ \text{jos}\ \ i \neq j. \end{cases}

Merkitys: Ortonormaalit sarakkeet matriisissa $Q$ säilyttävät geometrian, yksinkertaistavat projisointeja ja parantavat numeerista vakautta.

Määrittele matriisi A

Aloitetaan tällä esimerkillä:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Käytämme Gram-Schmidt-menetelmää löytääksemme matriisit $Q$ ja $R$ siten, että $A=QR$ . Gram-Schmidt-menetelmä muodostaa ortonormaalin vektorijoukon matriisin $A$ sarakkeista.

Tämä tarkoittaa, että $Q$ :n vektorit ovat kaikki keskenään kohtisuorassa (ortogonaalisia) ja yksikköpituudella (normalisoituja). Tämä ominaisuus yksinkertaistaa monia laskuja ja parantaa numeerista vakautta yhtälöitä ratkaistaessa.

Tavoitteena on siis:

Tehdä $Q$ :n sarakkeista ortonormaaleja;
Luoda matriisi $R$ , joka sisältää projisoinnit.

Ensimmäisen kantavektorin laskeminen

Otetaan matriisin $A$ ensimmäinen sarake:

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

Normalisoidaan tämä laskemalla normi:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Tällöin:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Tämä on ensimmäinen ortonormaali vektori matriisille $Q$ .

Vektorin normalisointi

Annetaan vektori:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Lasketaan sen normi:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Normalisoidaan:

\hat{v} = \frac{1}{|v|}v

Esimerkki:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Normalisoitu vektori on siis:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Kun osaamme normalisoida ja ortogonalisoida vektoreita, voimme soveltaa Gram-Schmidt-menetelmää $Q$ -matriisin muodostamiseen ja käyttää sitä $R$ :n laskemiseen QR-hajotelmassa.

Laske q₂ Gram-Schmidt-menetelmällä

Lasketaan $q_2$ aloittamalla matriisin $A$ toisesta sarakkeesta:

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Seuraavaksi projisoidaan $a_2$ vektorin $q_1$ suuntaan:

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Poistetaan projektion osuus $a_2$ :sta:

u_2 = a_2 - r_{12}q_1

Normalisoidaan (kuten yllä esitettiin):

q_2 = \frac{u_2}{|u_2|}

Nyt sekä $q_1$ että $q_2$ muodostavat ortonormaalin kannan matriisille $Q$ . Kootaan lopullinen tulos:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Nämä toteuttavat ehdon:

A = QR

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 4. Luku 8

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Awesome!

Completion rate improved to 1.96

Pyyhkäise näyttääksesi valikon

Järjestelmien, kuten $A \vec{x} = \vec{b}$ , ratkaiseminen voi olla laskennallisesti raskasta, erityisesti suurissa järjestelmissä.

Matriisin hajotelma yksinkertaistaa tätä prosessia jakamalla matriisin $A$ yksinkertaisempiin osiin, jotka voidaan ratkaista vaiheittain.

LU vs QR

Matriisi $A$ hajotetaan muihin rakenteellisiin matriiseihin.

LU-hajotelma

Hajotetaan $A$ alemmaksi ja ylemmäksi kolmiomatriisiksi:

Rakennetaan Gaussin eliminaatiolla;
Toimii parhaiten neliömatriiseille.

A = LU

QR-hajotelma

Hajotetaan $A$ ortogonaaliseksi ja ylemmäksi matriisiksi:

Käytetään usein ei-neliömatriiseille;
Ihanteellinen pienimmän neliösumman ongelmiin tai kun LU ei toimi.

A = QR

LU-hajotelma

Aloitetaan neliömatriisilla:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Tavoitteena on kirjoittaa tämä muodossa:

A = LU

Missä:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Tämä hajotelma on mahdollinen jos A on neliö ja kääntyvä.

Tärkeitä huomioita:

Alemmissa kolmiomatriiseissa kaikki päädiagonaalin yläpuoliset alkiot ovat nollia, mikä helpottaa eteenpäinsuuntaista sijoitusta;
Ylemmissä kolmiomatriiseissa diagonaalin alapuolella on nollia, mikä tekee taaksepäinsuuntaisesta sijoituksesta suoraviivaista;
Ortogonaalisessa matriisissa sarakkeet ovat ortonormaaleja vektoreita (vektorit, joiden pituus on 1 ja jotka ovat kohtisuorassa toisiinsa nähden);
Tämä ominaisuus säilyttää vektorin pituuden ja kulmat, mikä on hyödyllistä pienimmän neliösumman ratkaisuissa ja parantaa numeerista vakautta.

Gaussin eliminointi

Sovella Gaussin eliminointia poistaaksesi ylävasemman pivotin alapuolella olevan alkion:

R_2 \rarr R_2 - \frac{6}{4}R_1

Tämä antaa meille:

R'_2 = [0, -1.5]

Joten päivitetyt matriisit ovat:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Ja rivitoimituksesta tiedämme:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Tärkeitä huomioita:

Gaussin eliminointi poistaa järjestelmällisesti pivot-alkion alapuolella olevat alkiot jokaisessa sarakkeessa vähentämällä pivot-rivin skaalattuja versioita alemmista riveistä;
Tämä prosessi muuntaa A:n yläkolmiomatriisiksi U;
Eliminoinnissa käytetyt kertoimet tallennetaan matriisiin L, jolloin A voidaan esittää tulona LU.

LU-hajotelman tulos

Tarkistetaan:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nyt järjestelmä $A \vec{x} = \vec{b}$ voidaan ratkaista kahdessa vaiheessa:

Ratkaise $L \vec{y} = \vec{b}$ eteenpäin sijoittamalla;
Ratkaise $U \vec{x} = \vec{y}$ taaksepäin sijoittamalla.

QR-hajotelma

Halutaan esittää matriisi $A$ kahden matriisin tulona:

A = QR

Missä:

$A$ on syötematriisi (esim. data, kertoimet jne.);
$Q$ on ortogonaalinen matriisi (sen sarakkeet ovat ortonormaalivektoreita);
$R$ on yläkolmiomatriisi.

Esimerkki muotojen jaosta:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Tätä hajotelmaa käytetään usein kun:

Matriisi A ei ole neliömatriisi;
Ratkaistaan pienimmän neliösumman ongelmia;
LU-hajotelma ei ole stabiili.

Mitä ovat ortonormaalit vektorit?

Ortogonaaliset vektorit

Kaksi vektoria $u, v$ ovat ortogonaalisia, jos niiden pistetulo on nolla:

u \cdot v = 0

Normalisoitu vektori

Vektori $u$ on normalisoitu, kun $|u| = 1$ .

Ortonormaali joukko

Vektorijoukko $\{q_1, q_2, ..., q_k\}$ on ortonormaali, jos jokainen vektori on yksikköpituinen ja ne ovat keskenään ortogonaalisia:

q_i \cdot q_j = \begin{cases} 1,\ \text{jos}\ \ i = j,\\ 0,\ \text{jos}\ \ i \neq j. \end{cases}

Merkitys: Ortonormaalit sarakkeet matriisissa $Q$ säilyttävät geometrian, yksinkertaistavat projisointeja ja parantavat numeerista vakautta.

Määrittele matriisi A

Aloitetaan tällä esimerkillä:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Käytämme Gram-Schmidt-menetelmää löytääksemme matriisit $Q$ ja $R$ siten, että $A=QR$ . Gram-Schmidt-menetelmä muodostaa ortonormaalin vektorijoukon matriisin $A$ sarakkeista.

Tavoitteena on siis:

Tehdä $Q$ :n sarakkeista ortonormaaleja;
Luoda matriisi $R$ , joka sisältää projisoinnit.

Ensimmäisen kantavektorin laskeminen

Otetaan matriisin $A$ ensimmäinen sarake:

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

Normalisoidaan tämä laskemalla normi:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Tällöin:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Tämä on ensimmäinen ortonormaali vektori matriisille $Q$ .

Vektorin normalisointi

Annetaan vektori:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Lasketaan sen normi:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Normalisoidaan:

\hat{v} = \frac{1}{|v|}v

Esimerkki:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Normalisoitu vektori on siis:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Kun osaamme normalisoida ja ortogonalisoida vektoreita, voimme soveltaa Gram-Schmidt-menetelmää $Q$ -matriisin muodostamiseen ja käyttää sitä $R$ :n laskemiseen QR-hajotelmassa.

Laske q₂ Gram-Schmidt-menetelmällä

Lasketaan $q_2$ aloittamalla matriisin $A$ toisesta sarakkeesta:

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Seuraavaksi projisoidaan $a_2$ vektorin $q_1$ suuntaan:

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Poistetaan projektion osuus $a_2$ :sta:

u_2 = a_2 - r_{12}q_1

Normalisoidaan (kuten yllä esitettiin):

q_2 = \frac{u_2}{|u_2|}

Nyt sekä $q_1$ että $q_2$ muodostavat ortonormaalin kannan matriisille $Q$ . Kootaan lopullinen tulos:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Nämä toteuttavat ehdon:

A = QR

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 4. Luku 8

Matriisihajotelman Perusteet

LU vs QR

LU-hajotelma

QR-hajotelma

LU-hajotelma

Gaussin eliminointi

LU-hajotelman tulos

QR-hajotelma

Mitä ovat ortonormaalit vektorit?

Ortogonaaliset vektorit

Normalisoitu vektori

Ortonormaali joukko

Määrittele matriisi A

Ensimmäisen kanta­vektorin laskeminen

Vektorin normalisointi

Laske q₂ Gram-Schmidt-menetelmällä

Awesome!

Matriisihajotelman Perusteet

LU vs QR

LU-hajotelma

QR-hajotelma

LU-hajotelma

Gaussin eliminointi

LU-hajotelman tulos

QR-hajotelma

Mitä ovat ortonormaalit vektorit?

Ortogonaaliset vektorit

Normalisoitu vektori

Ortonormaali joukko

Määrittele matriisi A

Ensimmäisen kanta­vektorin laskeminen

Vektorin normalisointi

Laske q₂ Gram-Schmidt-menetelmällä

Ensimmäisen kantavektorin laskeminen

Ensimmäisen kantavektorin laskeminen