Gram-Schmidt'in ortogonalleştirme yöntemi

Gram-Schmidt yöntemi bir bir algoritma ile ilgili matematiksel dalı arasında lineer cebir . Her sistem için lineer bağımsız vektörleri, o oluşturur bir ortogonal sistemi bir mesafede Prähilbert alanı (bir vektör uzayı bir ile skalar ürün ) , oluşturur aynı alt vektör uzayı . Gram-Schmidt ortonormalizasyon yöntemi bir uzantıyı temsil eder : Ortogonal bir sistem yerine ortonormal bir sistemi hesaplar . Algoritmalar için girdi olarak bir temel vektörler sistemi kullanılırsa , bunlar bir ortogonal veya ortonormal temeli hesaplar .

İki işlemin adı Jørgen Pedersen Gram ve Erhard Schmidt'ten alınmıştır . Ancak, Pierre-Simon Laplace ve Augustin-Louis Cauchy'nin eserlerinde daha önce kullanılmışlardır .

Gram-Schmidt yöntemleri, kayan nokta aritmetiği olan bir bilgisayar tarafından sayısal hesaplama için pek uygun değildir. Birikmiş yuvarlama hataları nedeniyle , hesaplanan vektörler artık ortogonal değildir. Bununla birlikte, bu dezavantaja sahip olmayan yöntem değişiklikleri vardır . Diğer ortogonalleştirme yöntemleri, evsel dönüşümlere veya Givens rotasyonlarına dayanır .

Ön açıklama

Aşağıda, söz konusu vektör uzayı (vektörler) elemanları, basit Latince gibi harfler ile belirtilmiştir ve , örneğin, indisli gerektiğinde ve . Hem bindirme oklarından hem de kalın yazıdan vazgeçilir. Nokta ürün açılı parantez ile temsil edilmektedir: . Karmaşık durumda, kural, skaler çarpımın ilk bağımsız değişkende yarı doğrusal ve ikinci bağımsız değişkende doğrusal olduğu, yani ${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle v_ {i}}$${\ displaystyle w_ {j}}$${\ displaystyle \ langle v, w \ rangle}$

${\ displaystyle \ langle \ lambda v, w \ rangle = {\ overline {\ lambda}} \ langle v, w \ rangle, \ quad \ langle v, \ lambda w \ rangle = \ lambda \ langle v, w \ rangle }$

Tüm vektörler için , ve . Karmaşık durumda, skaler çarpımdaki faktörlerin sırası, aşağıda gösterilen formüllerde önemlidir, ancak gerçek durumda değildir. ${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle \ lambda \ in \ mathbb {C}}$

Buna ek olarak, temsil eder normunu vektörü . ${\ displaystyle \ | v \ | = {\ sqrt {\ langle v, v \ rangle}}}$${\ displaystyle v}$

Ortogonalleştirme sürecinin algoritması

Üç vektörlü bir örnek kullanarak Gram-Schmidt yönteminin gösterimi

Aşağıdaki algoritma hesaplar bir ortogonal sistemi arasında ikişerli ortogonal vektörler lineer bağımsız için aynı altuzaya oluşturur vektörleri. ${\ displaystyle w_ {1}, \ noktalar, w_ {n}}$${\ displaystyle n}$

Ortogonal sistemin münferit vektörleri şu şekilde hesaplanır: ${\ displaystyle v_ {1}, \ noktalar, v_ {n}}$

${\ displaystyle v_ {1} = w_ {1} \,}$

${\ displaystyle v_ {2} = w_ {2} - {\ frac {\ langle v_ {1}, w_ {2} \ rangle} {\ langle v_ {1}, v_ {1} \ rangle}} \, v_ {1}}$

${\ displaystyle v_ {3} = w_ {3} - {\ frac {\ langle v_ {1}, w_ {3} \ rangle} {\ langle v_ {1}, v_ {1} \ rangle}} \, v_ {1} - {\ frac {\ langle v_ {2}, w_ {3} \ rangle} {\ langle v_ {2}, v_ {2} \ rangle}} \, v_ {2}}$

${\ displaystyle \ vdots}$

${\ displaystyle v_ {n} = w_ {n} - {\ frac {\ langle v_ {1}, w_ {n} \ rangle} {\ langle v_ {1}, v_ {1} \ rangle}} \, v_ {1} - {\ frac {\ langle v_ {2}, w_ {n} \ rangle} {\ langle v_ {2}, v_ {2} \ rangle}} \, v_ {2} - \ dotsb - {\ frac {\ langle v_ {n-1}, w_ {n} \ rangle} {\ langle v_ {n-1}, v_ {n-1} \ rangle}} \, v_ {n-1} = w_ {n } - \ toplam _ {i = 1} ^ {n-1} {\ frac {\ langle v_ {i}, w_ {n} \ rangle} {\ langle v_ {i}, v_ {i} \ rangle}} \, v_ {i}}$

Başka bir deyişle, for , yinelemeli olarak ${\ displaystyle v_ {j}}$${\ displaystyle j = 1,2, \ noktalar, n}$

${\ displaystyle v_ {j} = w_ {j} - \ toplam _ {i = 1} ^ {j-1} {\ frac {\ langle v_ {i}, w_ {j} \ rangle} {\ langle v_ { i}, v_ {i} \ rangle}} \, v_ {i}}$

Tanımlanmıştır.

misal

Olarak birlikte verilen standart skalar iki lineer bağımsız vektörler, bir alt uzay sağlamak belirlenir: ${\ displaystyle \ mathbb {R} ^ {3}}$ ${\ displaystyle \ langle \ cdot, \ cdot \ rangle}$

${\ displaystyle w_ {1} = {\ begin {pmatrix} 3 \\ 1 \\ 2 \ end {pmatrix}}, \ quad w_ {2} = {\ begin {pmatrix} 2 \\ 2 \\ 2 \ end {pmatrix}}}$

İki ortogonal vektörler ve artık aynı alt vektör alan oluşturmak hesaplanan: ${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$

${\ displaystyle v_ {1} = w_ {1} = {\ begin {pmatrix} 3 \\ 1 \\ 2 \ end {pmatrix}}}$

${\ displaystyle v_ {2} = w_ {2} - {\ frac {\ langle v_ {1}, w_ {2} \ rangle} {\ langle v_ {1}, v_ {1} \ rangle}} \ cdot v_ {1} = {\ begin {pmatrix} 2 \\ 2 \\ 2 \ end {pmatrix}} - {\ frac {12} {14}} \ cdot {\ begin {pmatrix} 3 \\ 1 \\ 2 \ end {pmatrix}} = {\ frac {1} {7}} {\ begin {pmatrix} -4 \\ 8 \\ 2 \ end {pmatrix}}}$

Ortonormalizasyon yönteminin algoritması

Aşağıdaki algoritma hesaplar bir ortonormal sistemi arasında normalize, çiftli ortogonal vektörler lineer bağımsız için aynı altuzaya oluşturur vektörleri. Yukarıdaki algoritma ile belirlenen ortogonal vektörlerin normalleştirilmesiyle aynıdır. ${\ displaystyle w_ {1}, \ noktalar, w_ {n}}$${\ displaystyle n}$

Ortonormal sistemin ayrı vektörleri, önce ortogonal bir vektörün hesaplanması ve ardından normalleştirilmesiyle elde edilir: ${\ displaystyle v_ {1}, \ noktalar, v_ {n}}$

${\ displaystyle v_ {1} = {\ frac {w_ {1}} {\ sol \ | w_ {1} \ sağ \ |}}}$(İlk vektörü normalleştirin )${\ displaystyle w_ {1}}$

${\ displaystyle v_ {2} ^ {\ prime} = w_ {2} - \ langle v_ {1}, w_ {2} \ rangle \ cdot v_ {1}}$(İkinci vektörün ortogonalleştirilmesi )${\ displaystyle w_ {2}}$

${\ displaystyle v_ {2} = {\ frac {v_ {2} ^ {\ prime}} {\ sol \ | v_ {2} ^ {\ prime} \ sağ \ |}}}$(Vektörü normalleştirin )${\ displaystyle v_ {2} ^ {\ prime}}$

${\ displaystyle v_ {3} ^ {\ prime} = w_ {3} - \ langle v_ {1}, w_ {3} \ rangle \ cdot v_ {1} - \ langle v_ {2}, w_ {3} \ rangle \ cdot v_ {2}}$(Üçüncü vektörün ortogonalleştirilmesi )${\ displaystyle w_ {3}}$

${\ displaystyle v_ {3} = {\ frac {v_ {3} ^ {\ prime}} {\ sol \ | v_ {3} ^ {\ prime} \ sağ \ |}}}$(Vektörü normalleştirin ) ${\ displaystyle v_ {3} ^ {\ prime}}$

${\ displaystyle \ vdots}$

${\ displaystyle v_ {n} ^ {\ prime} = w_ {n} - \ sum _ {i = 1} ^ {n-1} \ langle v_ {i}, w_ {n} \ rangle \ cdot v_ {i }}$( -Nci vektörün ortogonalleştirilmesi )${\ displaystyle n}$${\ displaystyle w_ {n}}$

${\ displaystyle v_ {n} = {\ frac {v_ {n} ^ {\ prime}} {\ sol \ | v_ {n} ^ {\ prime} \ sağ \ |}}}$(Vektörü normalleştirin )${\ displaystyle v_ {n} ^ {\ prime}}$

Başka bir deyişle, ve için özyinelemeli olur ${\ displaystyle v_ {j}}$${\ displaystyle v_ {j} ^ {\ prime}}$${\ displaystyle j = 1,2, \ noktalar, n}$

${\ displaystyle v_ {j} ^ {\ prime} = w_ {j} - \ sum _ {i = 1} ^ {j-1} \ langle v_ {i}, w_ {j} \ rangle \ cdot v_ {i }}$ve tanımlanmıştır.${\ displaystyle v_ {j} = {\ frac {v_ {j} ^ {\ prime}} {\ sol \ | v_ {j} ^ {\ prime} \ sağ \ |}}}$

Genel olarak, bu yöntem özellikle mükemmel bir sistem sağlamaz. Im zorunluluk z. B. Sağ veya sol bir sistem elde etmek için yalnızca bir yeniden düzenleme adımı izlenebilir. ${\ displaystyle \ mathbb {R} ^ {3}}$

misal

Gelen ile donatılmış standart bir skaler iki baz vektörler verilebilir: ${\ displaystyle \ mathbb {R} ^ {2}}$ ${\ displaystyle \ langle \ cdot, \ cdot \ rangle}$

${\ displaystyle w_ {1} = {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}, \ quad w_ {2} = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}}}$

İki vektör ve şimdi hesaplanır, bunlar . ${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$${\ displaystyle \ mathbb {R} ^ {2}}$

${\ displaystyle v_ {1} = {\ frac {w_ {1}} {\ sol \ | w_ {1} \ sağ \ |}} = {\ frac {1} {\ sqrt {10}}} \ cdot { \ başlangıç ​​{pmatrix} 3 \\ 1 \ end {pmatrix}}}$

${\ displaystyle v_ {2} ^ {\ prime} = w_ {2} - \ langle v_ {1}, w_ {2} \ rangle \ cdot v_ {1} = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}} - {\ frac {1} {\ sqrt {10}}} \ cdot \ left \ langle {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}, {\ begin {pmatrix} 2 \ \ 2 \ end {pmatrix}} \ right \ rangle \ cdot {\ frac {1} {\ sqrt {10}}} {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}} = {\ frac {1 } {5}} {\ başlangıç ​​{pmatrix} -2 \\ 6 \ end {pmatrix}}}$

${\ displaystyle v_ {2} = {\ frac {v_ {2} ^ {\ prime}} {\ left \ | v_ {2} ^ {\ prime} \ sağ \ |}} = {\ sqrt {\ frac { 25} {40}}} \ cdot {\ frac {1} {5}} {\ begin {pmatrix} -2 \\ 6 \ end {pmatrix}} = {\ frac {1} {\ sqrt {10}} } \ cdot {\ begin {pmatrix} -1 \\ 3 \ end {pmatrix}}}$

Uyarılar

Her iki yöntemin de özel bir özelliği, her ara adımdan sonra şimdiye kadar hesaplanan vektörlerin, vektörlerle aynı vektör uzayını oluşturmasıdır . Dolayısıyla vektörler , karşılık gelen alt vektör uzaylarının ortogonal veya ortonormal bir temelini oluşturur. Diğer bir deyişle, bir sistemin koordinatlarını diğerinde ifade eden dönüşüm matrisi, sağ üstte üçgen bir matristir. Bunun aynı zamanda pozitif bir determinantı vardır, dolayısıyla ortaya çıkan ortogonal veya ortonormal temel, başlangıç ​​tabanıyla aynı yönelime sahiptir. Biri bir Q matrisinin sütunları olarak ortonormal vektörleri ve bir A matrisini oluşturmak için ilk sistemin vektörlerini özetlerse , o zaman A = QR olan üçgen bir R matrisi vardır , dolayısıyla bir QR ayrışımı belirlenir. Buna göre, Gram-Schmidt ortonormalizasyonunun sonucu, Givens rotasyonları veya Householder yansımaları ile çalışan diğer QR ayrıştırma yöntemleriyle de belirlenebilir . ${\ displaystyle v_ {1}, \ noktalar, v_ {i}}$${\ displaystyle w_ {1}, \ noktalar, w_ {i}}$${\ displaystyle v_ {1}, \ noktalar, v_ {i}}$${\ displaystyle v_ {1}, \ noktalar, v_ {n}}$${\ displaystyle w_ {1}, \ noktalar, w_ {n}}$

Bir ortogonal sistemi elle hesaplarsanız, önce ortogonal bir sistemi hesaplamak ve sonra tek tek vektörleri normalleştirmek genellikle daha kolaydır. Bu, sizi iki kez standartlaştırma zorunluluğundan kurtarır ve genellikle daha basit değerler kullanabilirsiniz. Ortogonal sistemi / ortonormal sistemi oluşturmadan önce Gauss eleme yöntemini uygulamak faydalı olabilir .

Prosedürün prensibi

Ortogonal vektörler zaten belirlenmişse, vektörlerin uygun bir doğrusal kombinasyonunu buradan çıkarmaya çalışırız , böylece fark vektörü${\ displaystyle v_ {1}, \ ldots, v_ {k-1}}$${\ displaystyle w_ {k}}$${\ displaystyle v_ {1}, \ ldots, v_ {k-1}}$

${\ displaystyle v_ {k} = w_ {k} - \ toplam _ {i = 1} ^ {k-1} \ lambda _ {i} v_ {i}}$

tüm vektörlere ortogonal hale gelir . Bu, hepsi için 0 değerini veren skaler çarpımla eş anlamlıdır . Her ifade için böyle bir doğrusal kombinasyon elde edilir.${\ displaystyle v_ {1}, \ ldots, v_ {k-1}}$${\ displaystyle \ langle v_ {j}, v_ {k} \ rangle}$${\ displaystyle j = 1, \ ldots, k-1}$${\ displaystyle i}$

${\ displaystyle \ lambda _ {i} = {\ frac {\ langle v_ {i}, w_ {k} \ rangle} {\ langle v_ {i}, v_ {i} \ rangle}}}$

seçilmiş. Tüm skaler ürünlerin olduğu bir kontrol hesaplama gösterileri ile 0 değerini varsayalım: ${\ displaystyle \ langle v_ {j}, v_ {k} \ rangle}$${\ displaystyle j \ neq k}$

${\ displaystyle {\ begin {align} \ langle v_ {j}, v_ {k} \ rangle & = \ left \ langle v_ {j}, w_ {k} - \ sum _ {i = 1} ^ {k- 1} \ lambda _ {i} v_ {i} \ right \ rangle \\ & = \ langle v_ {j}, w_ {k} \ rangle - \ sum _ {i = 1} ^ {k-1} {\ frac {\ langle v_ {i}, w_ {k} \ rangle} {\ langle v_ {i}, v_ {i} \ rangle}} \ langle v_ {j}, v_ {i} \ rangle \\ & = \ langle v_ {j}, w_ {k} \ rangle - \ langle v_ {j}, w_ {k} \ rangle \\ & = 0 \ end {hizalı}}}$

Sonsuz vektör sistemlerinin ortonormalizasyonu

Herhangi birinde Hilbert alan yöntem ayrıca bağımsızlık bir eleman bulunmaktadır anlamında anlaşılmalıdır, burada bağımsız vektörlerin sonsuz sistemlerine uygulanabilir sonunda doğrusal zarf başka vektörler. Bir olgu sayılabilir sistem (yani a, ayrılabilir Hilbert alanı ) yukarıda sunulan sonlu durum doğrudan takip edilebilir: Bağımsız bir sekansı göz önüne alındığında , karşılık gelen bir ortonormal dizisi elde edilir tarafından uygulanması ve elde Yukarıdaki prosedür her biri için . Daha genel olarak, her bağımsız bir sistem iyi sırasına göre izlenebilir teoremi bir dizi olarak bir için önemli sayıda ve sıra sayıları (a durumunda , yoğun lineer kaplama bağımsız sistemi, boyutu arasında bir tam ). Şimdi tayin ortogonal projeksiyonu kapalı bir matrisini nedeniyle alan eksiksizliği her zaman vardır, normalleştirme belirlemek . Ortonormal sistemde bu sonuçlar sayesinde ${\ displaystyle H}$${\ displaystyle H}$${\ displaystyle \ sol (w_ {n} \ sağ) _ {n \ in \ mathbb {N}}}$${\ displaystyle \ sol (v_ {n} \ sağ) _ {n \ in \ mathbb {N}}}$${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle v_ {n}}$${\ displaystyle \ sol (w _ {\ alpha} \ sağ) _ {\ alpha <d}}$ ${\ displaystyle d}$ ${\ displaystyle \ alpha}$${\ displaystyle d}$${\ displaystyle H}$${\ displaystyle \ pi _ {A} \ iki nokta üst üste H \ - A}$${\ displaystyle A}$${\ displaystyle {\ şapka {x}}}$${\ displaystyle \ textstyle {\ frac {x} {\ sol \ | x \ sağ \ |}}}$${\ displaystyle \ sol (v _ {\ alpha} \ sağ) _ {\ alpha <d}}$

${\ displaystyle A _ {\ alpha}: = {\ overline {\ operatöradı {span} \ sol (\ sol \ {w _ {\ beta} \ iki nokta üst üste \ beta <\ alfa \ sağ \} \ sağ)}}}$

${\ displaystyle v _ {\ alpha}: = {\ widehat {\ sol (w _ {\ alpha} - \ pi _ {A _ {\ alpha}} \ sol (w _ {\ alpha} \ sağ) \ sağ )}}}$.

Kullanılması o sonluötesi indüksiyon o gösterilebilir için bile, . Prosedür, transfinite özyineleme yoluyla aşağıdaki gibi daha açık bir şekilde yazılabilir : ${\ displaystyle A _ {\ alpha} = {\ overline {\ operatör adı {span} \ sol (\ sol \ {v _ {\ beta} \ iki nokta üst üste \ beta <\ alfa \ sağ \} \ sağ)}}}$${\ displaystyle \ alpha = d}$

${\ displaystyle v _ {\ alpha}: = {\ widehat {\ left (w _ {\ alpha} - \ sum _ {\ beta <\ alpha} \ langle v _ {\ beta}, w _ {\ alpha} \ rangle \ cdot v _ {\ beta} \ sağ)}}}$

Burada toplam, Bessel eşitsizliği nedeniyle iyi tanımlanmıştır (özellikle, her zaman sıfıra eşit olmayan yalnızca sayılabilecek kadar çok sayıda zirve vardır).

Edebiyat

• K. Kirchgessner, M. Schreck: Kuklalar için vektör analizi. Cep kitabı ciltsiz . Wiley-VCH, 2012. ISBN 978-3-527-70742-3