Grami-Schmidti ortogonaliseerimine

Vali, kui lähestikku veerud asuvad. Seejärel uuri kahte tabelit, mis näitavad vektoritevahelisi nurki mõlema versiooni tulemustes.

Näidisarvutus — Grami-Schmidti ortogonaliseerimine

A tingimusarv	1,7321 × 10⁸
Mis jääb järele veerust 3	1,4142 × 10⁻⁸
Mida q₂ eraldab veerust 3	0
Suurim skalaarkorrutis kahe vektori vahel	0,5000
Nurk q₂ ja q₃ vahel	60,00°
Ortogonaalsuse kadu, klassikaline	0,7071
Ortogonaalsuse kadu, modifitseeritud	1,1547 × 10⁻⁸
Ortogonaalsuse kadu, klassikaline kaks korda	2,6158 × 10⁻²⁴

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Klassikaline Gram-Schmidt tagastab kaks vektorit 60° nurga all 🖖

Vajuta ε = 10⁻⁸, klassikaline. Klassikalises tabelis on kahes lahtris 60,00°. See on vektorite q₂ ja q₃ paar mõlemas nurgas, kusjuures kõik teised nurgad mõlemas tabelis on 90,00°. Nende taga olev skalaarkorrutis on 0,5000. See on täpselt pool, erinedes topelttäpsusega ujukomaarvu viimases kohas vaid ühe ühiku võrra.

Maatriks koosneb kolmest veerust. Igaüks neist on vektor (1, 0, 0, 0), mille ühte positsiooni on lisatud 10⁻⁸. Peter Läuchli kasutas seda juba 1961. aastal ja sellest ajast peale kannab see tema nime. Peaaegu korduvad veerud on vähimruutude meetodi jaoks ebamugavad, kuid nad tekivad alati, kui kaks mõõtmistulemust on peaaegu identsed.

Modifitseeritud Grami-Schmidti algoritm saab sisendiks samad kolm veergu ja iga tagastatud nurk on 90,00°. Korrutamiste arv on sealjuures täpselt sama.

Suurenda vahet ühe astme võrra väärtuseni 10⁻⁷ ja see lahter näitab 89,24°. Üks liuguri liigutus määrab, kas eksimus on kolmveerand kraadi või koguni kolmkümmend kraadi.

Kaks versiooni arvutavad üht väärtust erinevalt 🖖

Seadke lahenduskäik kolmandale veerule ja vajutage esmalt Classical, seejärel Modified. Rida Mida q₂ kolmandast veerust eemaldab muutub väärtuselt 0 väärtusele 7,0711 × 10⁻⁹. Kolme veeru korral on see ainus kordaja, mille need kaks algoritmi erinevalt arvutavad. Nii selle all asuv diagonaalielement kui ka iga nurk võrgustikus tuleneb otse sellest.

Klassikaline algoritm arvutab selle kordaja kujul q₂ᵀa₃, kasutades talle etteantud veergu. Modifitseeritud variant leiab q₂ᵀv, uurides vaid seda, mis pärast q₁ osa eemaldamist veerust üle jäi. Paberil on need üks ja sama arv, sest v erineb a₃-st vaid q₁ kordse võrra ning q₂ on q₁-ga risti. Aritmeetikas pole q₂ aga q₁-ga kunagi täielikult risti ja 7,0711 × 10⁻⁹ a₃-st osutab endiselt q₂ suunas. Klassikaline meetod ei pööra sellele mingit tähelepanu. Seega jätab q₃ selle komponendi alles ja just nii tekibki see 60°.

Lohistage liugurit 10⁻¹ juurest 10⁻⁸ juurde ning jälgige, kuidas kaks kõverat alumisel paneelil teineteisest eemalduvad. Selles vahemikus 113 punktile sobitatuna kasvab klassikalise algoritmi ortogonaalsuse kadu neil kolmel veerul kui κ^1,98 ja modifitseeritul kui κ^0,98. Paneel teeb vastavalt valitud veergude arvule uue sobituse, mistõttu maatriksit laiendades need kaks astendajat muutuvad. Üksainus ümberjärjestatud lahutustehe on väärt tervet tingimusarvu astet.

Baas on rikutud, kuid faktooring on täpne 🖖

Tulemuste tabeli viimane rida on ‖A − QR‖ / ‖A‖. Kui ε = 10⁻⁸, on seal klassikalise meetodi all kirjas 0. Korrutage rikutud Q selle kõrvalt saadud R-iga ning esialgne maatriks tuleb element-elemendilt tagasi, ilma et midagi üle jääks.

Läbides kõik juhtpaneelilt kättesaadavad seisundid – neli veergude arvu, kümme eraldatuse astet ja mõlemad algoritmid –, ei tõuse see suhteline jääk kordagi üle 5,5511 × 10⁻¹⁷. Arvu 1 ja järgmise topelttäpsusega arvu vahe on 2,2204 × 10⁻¹⁶, seega püsib tulemus viimase koha ühiku veerandi piires.

Grami-Schmidti meetod esitas maatriksi A tõepoolest tagastatud vektorite ja leitud kordajate korrutisena. Mida see aga enam ei teinud, oli omavahel risti olevate vektorite tagastamine. Kumb nendest kahest omadusest on teile vajalik, sõltub teie enda koodist. Vektori projekteerimine kujul Qᵀb tugineb omadusele, mis kadus, kuid maatriksi A taastamine Q ja R põhjal toetub sellele, mis paika pidas.

Ülesanne täielikult lahendatud

Kus klassikaline Gram-Schmidt kaotab täisnurga 8 sammu
Tööriist näitab kolme veergu, mis asuvad üksteisest 10⁻⁸ kaugusel, ja klassikalise Grami-Schmidti vastust nendele. Arvuta algoritm käsitsi läbi ja leia see üks ümardamine, mis maksab kolmkümmend kraadi. Seejärel hinda, kui kaugele võib kumbagi versiooni lükata, enne kui nende käivitamine muutub mõttetuks.

Ava see ülesanne tööriistas
1. Iga veerg on vektor (1, 0, 0, 0), mille ühte positsiooni on lisatud ε. AᵀA on ainult ühtedest koosnev 3 × 3 maatriks pluss ε²I. Selle omaväärtused on üks kord 3 + ε² ja kaks korda ε². Seetõttu on ainsusväärtused √(3 + ε²) ja ε ning tingimusarv on täpne, mitte hinnanguline. Tabeli ülemisel real on kirjas 1,7321 × 10⁸.
  
  $A = 1 ε 00 10 ε 0 100 ε, ε = 1 0^{- 8}, κ (A) = \frac{3 + ε ^{2}}{ε} = 1.7321 \times 1 0^{8}$
2. ‖a₁‖² on 1 + ε² ning ε² on 10⁻¹⁶. Topelttäpsusega ujukomaarv suudab esitada arvu 1 ja järgmine võimalik väärtus asub 2,2204 × 10⁻¹⁶ võrra edasi. Seega kaob arvu 1 liitmisel kõik, mis on väiksem kui pool sellest vahest ehk 1,1102 × 10⁻¹⁶. Kümme astmes miinus kuusteist jääb sellest allapoole. Ruutjuur on 1 ja sellega jagamine ei muuda midagi, mistõttu q₁ ongi veerg ise koos ajaloost kustutatud ε² komponendiga. Iga teine ümardamine selles ülesandes on väärt üht ühikut viimases kohas. See konkreetne ümardamine maksab aga kolmkümmend kraadi.
  
  $∥ a_{1} ∥^{2} = 1 + ε^{2} = 1 + 1 0^{- 16}, 1 0^{- 16} < 1.1102 \times 1 0^{- 16} ⟹ fl (1 + ε^{2}) = 1, q_{1} = a_{1}$
3. Järgmisena tuleb veerg 2 ja siin on mõlemad versioonid ühel meelel, sest selle taga on vaid üks vektor. Projektsiooni kordaja on q₁ᵀa₂ = 1. Selle lahutamisel jääb järele (0, −ε, ε, 0), mille pikkus on ε√2 = 1,4142 × 10⁻⁸. Ujukomaarvu täpsuse piires saabus veerg 2 pikkusega 1, millest q₁ kattis juba kõik peale 1,4142 × 10⁻⁸.
  
  $r_{12} = q_{1}^{T} a_{2} = 1, v_{2} = a_{2} - q_{1} = (0, - ε, ε, 0)^{T}, ∥ v_{2} ∥ = ε 2 = 1.4142 \times 1 0^{- 8}$
4. Veerg 3 klassikalisel meetodil. Kordaja q₁ suhtes on taas 1. Kordaja q₂ suhtes on q₂ᵀa₃ ning q₂ asub täielikult positsioonidel 2 ja 3, samas kui a₃ hoiab oma ε-i positsioonil 4. Seega on nende skalaarkorrutis 0. Just seda ütlebki rida Mida q₂ eraldab veerust 3. Ainult q₁ lahutamisel jääb järele (0, −ε, 0, ε), mille pikkus on uuesti ε√2. Seega on rea Mis jääb järele veerust 3 väärtus samuti 1,4142 × 10⁻⁸.
  
  $r_{13} = q_{1}^{T} a_{3} = 1, r_{23} = q_{2}^{T} a_{3} = 0, v_{3} = a_{3} - q_{1} = (0, - ε, 0, ε)^{T}, q_{3} = \frac{1}{2} (0, - 1, 0, 1)^{T}$
5. Nii q₂ kui ka q₃ konstrueeriti, lahutades q₁ veerust, millel on sama esialgne 1. Seega kannavad mõlemad positsioonil 2 väärtust −1/√2 ega oma enam midagi muud ühist. Nende skalaarkorrutis on pool. Tööriist väljastab 0,5000 ja 60,00°. Salvestatud väärtus on aga 0,4999999999999999. Kõrvalekalle algebra pakutud poolest on vaid üks ühik viimases kohas, sest ±1/√2 ei ole kahendmurd. See on viga, milleks selline arvutamine on võimeline. Kolmkümmend kraadi seda ei ole. Klassikalise ortogonaalsuse kao real seisab 0,7071, mis on √(2 × 0,5²). See on seesama pool, mida on arvestatud QᵀQ igas nurgas üks kord.
  
  $q_{2}^{T} q_{3} = \frac{1}{2} [(- 1) (- 1) + (1) (0)] = \frac{1}{2}, arccos \frac{1}{2} = 6 0^{\circ}, 2 \cdot 0 . 5^{2} = 0.7071$
6. Modifitseeritud meetod samal veerul. Pärast q₁ osa lahutamist on jääk (0, −ε, 0, ε) ning see versioon arvutab projektsiooni a₃ asemel just selle suhtes. Selle skalaarkorrutisel q₂-ga saame ε/√2 = 7,0711 × 10⁻⁹, mitte nulli. Kui see lahutada, jääb järele pikkusega ε√(3/2) = 1,2247 × 10⁻⁸ vektor (0, −ε/2, −ε/2, ε) ning q₂ᵀq₃ tulemuseks on poole asemel 1,1102 × 10⁻¹⁶. Modifitseeritud ortogonaalsuse kao real seisab 1,1547 × 10⁻⁸. Sinna on alles jäänud vaid see, mida q₁ ei suutnud eemaldada. Lahutamine jätab −ε² suunaga piki q₁-te ning jagamine pelgalt pikkusega ε√2 muudab selle uuesti väärtuseks ε/√2.
  
  $r_{23} = q_{2}^{T} v_{3} = \frac{ε}{2} = 7.0711 \times 1 0^{- 9}, v_{3} \mapsto (0, - \frac{ε}{2}, - \frac{ε}{2}, ε)^{T}, ∥ v_{3} ∥ = ε \frac{3}{2} = 1.2247 \times 1 0^{- 8}, q_{2}^{T} q_{3} = 0$
7. Sama arutluskäik kehtib iga veergude arvu korral, mida tööriist pakub. Klassikaline algoritm konstrueerib iga järgneva vektori q, lahutades q₁ veerust, millel on temaga ühine algus 1. Seega tuleb iga nendevahelise paari nurgaks 60°: kokku (n − 1)(n − 2)/2 paari ning ortogonaalsuse kadu võrdub poole selle arvu ruutjuurega. Kahe veeru korral selliseid paare ei eksisteeri ja järele jääb vaid ε suurune kalle, mida jagavad mõlemad versioonid.
  
  $n 2345 κ (A) 1.4142 \times 1 0^{8} 1.7321 \times 1 0^{8} 2.0000 \times 1 0^{8} 2.2361 \times 1 0^{8} # {6 0^{\circ}} 0136 ∥ Q_{C}^{T} Q_{C} - I ∥_{F} 1.0000 \times 1 0^{- 8} 0.7071 1.2247 1.7321 ∥ Q_{M}^{T} Q_{M} - I ∥_{F} 1.0000 \times 1 0^{- 8} 1.1547 \times 1 0^{- 8} 1.2247 \times 1 0^{- 8} 1.2649 \times 1 0^{- 8}$
8. Klassikalise meetodi sobitatud sirge jõuab kao väärtuseni 1 kohal κ = 2,35 × 10⁸, mistõttu on klassikaline kõver paneeli parempoolses otsas juba tasane. Modifitseeritud meetod saab aga ekstrapoleeritud piiri asemel mõõdetud piiri. Tema kõver pöörab pärast 10⁻⁸ alla ja nii kaugele tõmmatud sobitatud sirge lükkaks selle all olev paneel ümber: üle 724 mõõtepunkti ei ületanud kadu kordagi 1,25 masinaepsilomi ja κ korrutist. See piir ulatub väärtuseni 1 alles kohal κ = 3,60 × 10¹⁵. Masina epsiloni pöördväärtus on 4,50 × 10¹⁵.
  
  $lo g_{10} κ = \frac{16 . 5755}{1 . 9801} 1.25 \cdot (2.2204 \times 1 0^{- 16}) κ (2.2204 \times 1 0^{- 16})^{- 1} = = = 8.3710 ⟹ κ = 2.35 \times 1 0^{8} 1 ⟹ κ = 3.60 \times 1 0^{15} 4.50 \times 1 0^{15}$
Vastus

Kolmkümmend kraadi tulenevad ühestainsast reast. Klassikaline loeb q₂ᵀa₃ = 0, samas kui modifitseeritud loeb q₂ᵀv₃ = 7,0711 × 10⁻⁹, kuigi paberil on tegemist sama arvuga.

Vahekaugus 10⁻⁸ on esimene aste, kus ε² kaob avaldisest 1 + ε², sest √(pool masina epsiloni) on 1,0537 × 10⁻⁸. Sellest allapoole näitab lahter 60,00° ükskõik kui kaugele sa liugurit ka ei tõmbaks. Üks aste tagasi, väärtusel 10⁻⁷, on nurk 89,24° ning klassikaline meetod on kaotanud juba 1,88 × 10⁻² ortogonaalsust. Kokkuvarisemine algab ammu enne seda, kui liugur jõuab väärtuseni, mis probleemi selgelt esile toob.

Åke Björck avaldas modifitseeritud versiooni analüüsi 1967. aastal ning ümberjärjestamine on olnud standardiks alates sellest ajast. Mõlemad teevad sama arvu korrutamisi ning selle vahemaa juures erineb nende ortogonaalsuse kadu 6,1 × 10⁷ korda. Modifitseeritud algoritm säilitab täisnurgad kuni piirini, kus ujukomaarv ei suuda enam veerge üksteisest üldse eristada. Klassikaline aga loovutab need juba seitse suurusjärku varem.

$q_{2}^{T} a_{3} = 0 \neq = q_{2}^{T} v_{3} = \frac{ε}{2} = 7.0711 \times 1 0^{- 9}$

Allikad (5)

The matrix the tool is built on, and the name it carries: P. Läuchli, "Jordan-Elimination und Ausgleichung nach kleinsten Quadraten", Numerische Mathematik 3(1), 226–240, 1961. doi:10.1007/BF01386022
The analysis of the modified variant that made it the default: Åke Björck, "Solving linear least squares problems by Gram-Schmidt orthogonalization", BIT 7(1), 1–21, 1967. doi:10.1007/BF01934122
The corresponding rounding-error analysis of the classical variant: Luc Giraud, Julien Langou, Miroslav Rozložník and Jasper van den Eshof, "Rounding error analysis of the classical Gram-Schmidt orthogonalization process", Numerische Mathematik 101(1), 87–100, 2005. doi:10.1007/s00211-005-0615-4
Gram's paper of 1883, where the process is set out for least squares: J. P. Gram, "Ueber die Entwickelung reeller Functionen in Reihen mittelst der Methode der kleinsten Quadrate", Journal für die reine und angewandte Mathematik 1883(94), 41–73. doi:10.1515/crll.1883.94.41
And Schmidt's of 1907, where the form used today appears: Erhard Schmidt, "Zur Theorie der linearen und nichtlinearen Integralgleichungen", Mathematische Annalen 63, 433–476, 1907. doi:10.1007/BF01449770

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.