Sayısal doğrusal cebir

Pistonlu bir pistonun (dizel motor) gerilim analizi için burada gösterildiği gibi, sonlu elemanların kullanıldığı modelleme , çok sayıda denklem ve bilinmeyenli doğrusal denklem sistemlerine yol açar.

Sayısal doğrusal cebir bir merkezi dalı olan sayısal matematik . Doğrusal cebirdeki problemler için hesaplama süreçlerinin ( algoritmalar ) geliştirilmesi ve analizi, özellikle de doğrusal denklem sistemlerinin ve özdeğer problemlerinin çözümü ile ilgilenir . Bu tür sorunlar, tüm doğa ve mühendislik bilimlerinde , aynı zamanda ekonometri ve istatistikte de önemli bir rol oynar.

Sayısal doğrusal cebirin algoritmaları kabaca iki gruba ayrılabilir: sınırlı sayıda hesaplama adımından sonra bir probleme kesin çözümü teorik olarak sunan doğrudan yöntemler ve kesin çözümün kademeli olarak yaklaştırıldığı yinelemeli yöntemler . Bununla birlikte, doğrudan yöntemler, sonlu doğrulukla hesaplanırken ortaya çıkan yuvarlama hataları nedeniyle yalnızca kesin çözüm için yaklaşık değerler sağladığından, bu ayrım yalnızca yöntemin kendisinin geliştirilmesi ve araştırılması için önemlidir; pratik kullanımda önemli bir rol oynamaz. Tarihsel olarak, her iki gruptan ilk sistematik yöntemler - doğrudan Gauss eleme yöntemi ve yinelemeli Gauss-Seidel yöntemi  - Carl Friedrich Gauß'a geri dönüyor . Çok sayıda iyileştirmeler ve başka gelişmeler ile sonuçlandı 20. yüzyılın önemli yöntemlerine örnekler ayrıştırma yöntemi ile Andre Louis Cholesky , QR yöntemi ile değer problemi için John G. F. Francis ve Wera Nikolajewna Kublanowskaja ve CG yöntemi ile Eduard Stiefel ve Magnus Hestenes önemli Krylow alt uzay yöntemlerinin ilk temsilcisi olarak .

Problemlere giriş

Temel doğrusal cebirin merkezi bir başlangıç ​​noktası - aynı zamanda tarihsel bir bakış açısından - doğrusal denklem sistemleridir. Şekil denklemlerini düşünüyoruz${\ displaystyle n}$

${\ displaystyle a_ {i1} x_ {1} + \ ldots + a_ {in} x_ {n} = b_ {i}}$

için yabancılara . Katsayıları ve verilen sayılardır; için aranan değerler , tüm denklemler yerine getirilecek şekilde belirlenmelidir. Katsayılar bir matris halinde birleştirilebilir ; numaraları ve bilinmeyenler oluşturan kolon vektörleri ve . Bu matris vektör gösterimi ile sonuçlanır ${\ displaystyle n}$${\ displaystyle x_ {1}, \ dotsc, x_ {n}}$ ${\ displaystyle a_ {ij}}$${\ displaystyle b_ {i}}$${\ displaystyle x_ {1}, \ dotsc, x_ {n}}$ ${\ displaystyle A = (a_ {ij})}$${\ displaystyle b_ {i}}$${\ displaystyle x_ {j}}$ ${\ displaystyle \ mathbf {b} = (b_ {i})}$${\ displaystyle \ mathbf {x} = (x_ {j})}$

${\ displaystyle A \ cdot \ mathbf {x} = \ mathbf {b}}$

Doğrusal bir denklem sistemi için: Verilen vektörü verilen matris ile matris-vektör çarpımında veren bir vektör arıyoruz . Sayısal doğrusal cebir, sayısal bilimin bir alt alanı olarak, yalnızca doğru olarak ortaya konulan problemleri, yani özellikle sadece bir çözümü olan ve çözümü benzersiz bir şekilde belirlenmiş problemleri dikkate alır. Özellikle, aşağıda her zaman matrisin düzenli olduğu , yani bir tersi olduğu varsayılır . Sonra, her bir sağ taraf için doğrusal denklem sisteminin resmen olarak belirtilebilecek benzersiz bir şekilde belirlenmiş çözümü vardır . ${\ displaystyle \ mathbf {x}}$${\ displaystyle A}$${\ displaystyle \ mathbf {b}}$${\ displaystyle A}$ ${\ displaystyle A ^ {- 1}}$${\ displaystyle \ mathbf {b}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {x} = A ^ {- 1} \ mathbf {b}}$

Bununla birlikte, birçok önemli uygulama, bilinmeyenlerden daha fazla denklem içeren doğrusal denklem sistemlerine yol açar. Bu durumda, matris vektör gösteriminde , matrisin sütundan daha fazla satırı vardır . Bu tür aşırı belirlenmiş sistemlerin genellikle bir çözümü yoktur. Dolayısıyla, vektörü , farkın , artığın , henüz belirlenemeyen bir anlamda "olabildiğince küçük" hale geleceği şekilde seçmekten kaçınır . Kadarki en önemli durum, sözde doğrusal tarafından ne de dengeleme problemi , bir en küçük kareler yöntemi Burada,: Kullanılan seçim yapılır böylece karelerinin toplamı olduğuna minimal ile farkı bileşenleri vektörü kullanılıyor . Öklid normunun yardımıyla , şu şekilde de yazılabilir: Minimal olması için seçersiniz . ${\ displaystyle A \ cdot \ mathbf {x} = \ mathbf {b}}$${\ displaystyle A}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {r} = A \ cdot \ mathbf {x} - \ mathbf {b}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle r_ {1} ^ {2} + \ ldots + r_ {m} ^ {2}}$${\ displaystyle r_ {1}, \ dotsc, r_ {m}}$${\ displaystyle \ mathbf {r}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ | A \ cdot \ mathbf {x} - \ mathbf {b} \ | _ {2} ^ {2}}$

Doğrusal denklemlere ek olarak, özdeğer problemleri doğrusal cebirin başka bir ana konusudur. Bir matris ile satır ve sütun burada verilir ; sayıları ve vektörleri arıyoruz, böylece denklem ${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle \ lambda}$${\ displaystyle \ mathbf {x} \ neq \ mathbf {0}}$

${\ displaystyle A \ cdot \ mathbf {x} = \ lambda \ mathbf {x}}$

memnun. Biri daha sonra özdeğerin özvektörünü çağırır . Bir matrisin tüm özdeğerlerini ve özvektörlerini bulma problemi, onları köşegenleştirmekle eşdeğerdir . Bunun anlamı: Düzenli bir matris ve ile köşegen bir matris bulun . Köşegen girişleri daha sonra özdeğerleridir ve sütunları ilişkili özvektörlerdir. ${\ displaystyle \ mathbf {x}}$${\ displaystyle A}$${\ displaystyle \ lambda}$${\ displaystyle S}$ ${\ displaystyle D}$${\ displaystyle S ^ {- 1} \ cdot A \ cdot S = D}$${\ displaystyle D}$${\ displaystyle A}$${\ displaystyle S}$

Bu sorunlar tüm doğa ve mühendislik bilimlerinde ortaya çıkar. Ama aynı zamanda ekonomi ve istatistikte ve dolayısıyla istatistiksel yöntemleri kullanan tüm alanlarda önemli bir rol oynarlar . Doğrusal denklem sistemleri, örneğin, statik , elektrik ağları veya ekonomik karşılıklı bağımlılıklardaki modelleri tanımlar . Bu tür kararlılık analizi Görünüşe göre farklı görevler dinamik sistemleri , rezonans fenomeni ile titreşim , bir belirlenmesi PageRank veya ana bileşen analizi istatistik özdeğer sorunlara yol açarlar. Doğrusal denklemler ayrıca diğer sayısal yöntemler içinde doğrusallaştırma ve ayrıklaştırma ile oluşturulur . Örneğin, bilim ve teknolojideki sayısız model kısmi diferansiyel denklemlerle tanımlanabilir. Fark veya sonlu eleman yöntemlerini kullanan sayısal çözümleri , çok sayıda bilinmeyenli sistemlere yol açar.

Basitlik adına, bu incelemede, verilen tüm matrislerin ve vektörlerin gerçek olduğu, yani tüm girişlerinin gerçek sayılar olduğu varsayılmaktadır . Çoğu zaman, bahsedilen yöntemler doğrudan karmaşık sayılara genelleştirilebilir; Ortogonal matrislerin yerine, örneğin karmaşık karşılıkları olan birim matrisler görünür . Bazen, belirli bir karmaşık problemi gerçek olana kadar takip etmek de avantajlıdır - örneğin gerçek ve hayali kısmı dikkate alarak . Bununla birlikte, simetrik olmayan gerçek matrislerle özdeğer problemleri söz konusu olduğunda, bunlar da gerçek olmayan özdeğerlere ve özvektörlere sahip olabileceğinden, ek hususlar ortaya çıkar.

hikaye

Başlangıçlar: Gauss ve Jacobi

Astronomische Nachrichten'de Gauß tarafından litografi, Bendixen tarafından 1828

Belirli problemlere çözümler, eski zamanlardan beri verilmiştir ve günümüz perspektifinden doğrusal denklem sistemleri olarak görülebilir. Aritmetik dokuz bölüm devlet hangi, Çin matematik 1. yüzyıla özetlenmiştir zaten matris temsilinde eleme yöntemlerine karşılık tablo hesaplama kurallarını içeriyordu. Doğrusal denklem sistemlerinin sistematik olarak incelenmesi, genel katsayılar kullanılarak formüle edilmesiyle 17. yüzyılın sonlarına doğru başlamıştır. Gabriel Cramer , Gottfried Wilhelm Leibniz ve Colin Maclaurin'in ön çalışmalarından sonra 1750'de belirleyiciler yardımıyla herhangi bir sayıda bilinmeyen için açık bir çözüm formülü yayınladı . Bu Cramer kuralıyla , sorun teorik olarak tamamen çözüldü, ayrıca çözümlerin varlığı ve benzersizliği ile ilgili olarak. Pratik hesaplamaları için formülün tamamen uygunsuz olduğu kanıtlandı çünkü hesaplama çabası bilinmeyenlerin sayısı ile astronomik olarak hızla artıyor (ayrıca bkz. Cramer'in kuralı # Hesaplamalı çaba ).

Doğrusal denklemler için sistematik hesaplama yöntemlerinin ilk kullanımı ve açıklaması Carl Friedrich Gauß'a ( 1777–1855 ) kadar uzanmaktadır . 19. yüzyılın başında yörünge verilerinin belirlenmesi astronomik nesneler ve ölçme ülkeyi tarafından nirengi vardı matematiksel uygulamada en önemli uygulama görevleri. 1801'de Gauss, yeni keşfedilen küçük gezegen Ceres'in yörüngesini o kadar kesin bir şekilde belirlemeyi başardığında bir sansasyon yarattı ki , Ceres yıl sonunda yeniden bulunabildi. İlişkili üst belirlenmiş denklem sistemi için, keşfettiği en küçük kareler yöntemini kullandı . Gauss, asteroid Pallas'ın yörüngesini belirlemenin bir parçası olarak 1809'dan itibaren çözümü hesaplamak için kullandığı eleme yöntemini sistematik olarak tanımladı , ancak yine de doğrudan karelerin toplamına uyguladı.

Carl Jacobi

Doğrusal denklem sistemlerini çözmek için ilk iterasyon yöntemi - Gauß-Seidel yöntemi - Gauß tarafından da geliştirilmiştir. Christian Ludwig Gerling'e 1823'te yazdığı bir mektupta , çözüme giderek adım adım yaklaştırılabilecek yeni ve basit bir prosedür hakkında bilgi verdi. Bu sırada Hannover Krallığı'nın nirengi ile meşgul olan Gauss, neredeyse her akşam bir yineleme adımı daha hesapladığını yazıyor; bu, ölçüm verilerinin tekdüze kaydedilmesinden hoş bir değişikliktir. İşlemin hatalara o kadar az eğilimli olduğu söyleniyor ki, "yarı uykuda" bile gerçekleştirilebilir. 1845'te Carl Gustav Jacob Jacobi , benzer bir yineleme yöntemi olan Jacobi yöntemini yayınladı . Ne zaman Philipp Ludwig von Seidel , Jacobi bir öğrenci, 1874 yılında 72 bilinmeyenli bir sistem çözmek zorunda kaldığına bu yöntemin değiştirilmiş, geliştirilmiş versiyonunu geliştirdi. Geçmişe bakıldığında ortaya çıktığı gibi, bu yöntem, Seidel'in muhtemelen bilmediği Gauss'un yineleme yöntemine eşdeğerdir. Jacobi ayrıca 1846'da matrisleri dönüştürmek için, simetrik matrisler için özdeğer problemini çözmek için uygun olan ve günümüzde Jacobi yöntemi olarak da bilinen yinelemeli bir yöntem yayınladı . Bununla birlikte, kendisi bunu sadece matrisin köşegen girişlerini daha baskın hale getirmek için bir hazırlık adımı olarak kullandı.

20. yüzyıl

1923'te, André-Louis Cholesky tarafından geliştirilen ve katsayı matrisini iki daha basit matrisin ürünü olan Cholesky ayrışımına ayırarak belirli doğrusal denklem sistemlerini çözen bir prosedür yayınlandı . Gauss eleme sürecinin de böyle bir matris ayrıştırma işleminin özel bir durumu olduğu ortaya çıktı. Bu yöntem grubundan elde edilen algoritmalar, günümüzde orta büyüklükteki sistemleri çözmek için hala standart yöntemlerdir.

1920'lerin sonundan itibaren, 1929'da Richard von Mises tarafından güç yönteminin tanıtılmasıyla başlayan, özdeğer problemlerinin yinelemeli çözümü için yeni fikirler ortaya çıktı . 1944'te Helmut Wielandt tarafından ters iterasyonun daha da geliştirilmesinde olduğu gibi , bu basit vektör yineleme yöntemleri yalnızca tek bir özdeğer için özvektörleri hesaplayabilir. Keyfi matrisler için özdeğer probleminin tam çözümü karmaşık kaldı. Atılım 1961–1962'de İngiliz bilgisayar bilimcisi John GF Francis ve bundan bağımsız olarak Rus matematikçi Vera Nikolajewna Kublanowskaja tarafından QR yönteminin geliştirilmesiyle geldi . Kublanowskaja, yöntemin yakınsama özelliklerini en başından itibaren derinlemesine kavrarken, Francis esas olarak yöntemi hızlı ve kararlı hale getiren uygulama ayrıntıları üzerinde çalıştı. QR yöntemi, çok büyük olmayan tüm özdeğerleri ve özvektörleri hesaplamak için hala standart yöntemdir.

Eduard Stiefel, 1955

Kısmi diferansiyel denklemlerin ayrıklaştırılmasında meydana gelen çok büyük matrisli doğrusal denklem sistemlerinin çözümü zor kaldı. Bu matrisler nispeten az sayıda sıfır olmayan girdiye sahiptir ve sayısal bir yöntemin bu özellikten yararlanması çok önemlidir. Buna yeni bir yaklaşım, birçok gelişmenin başlangıç ​​noktası haline geldi, 1952'de Eduard Stiefel ve Magnus Hestenes tarafından geliştirilen CG süreciydi . Matrisin simetrik olduğu ve aynı zamanda pozitif tanımlı olduğu özel durumda, doğrusal denklem sistemi eşdeğer bir optimizasyon problemi ile değiştirilir . Cornelius Lanczos tarafından aynı zamanda keşfedilen CG yöntemine bir başka yaklaşımın daha da verimli olduğu ortaya çıktı : CG yöntemiyle hesaplanan yaklaşımlar , Krylow uzaylarının yükselen bir alt uzay zincirinde yer alıyor .

Bu bağlantıların keşfedilmesine rağmen, CG yönteminin spesifik genellemelerini geliştirmek nispeten uzun zaman aldı. Roger Fletcher tarafından 1974'te yayınlanan BiCG yöntemi teorik olarak herhangi bir matris için kullanılabilir, ancak birçok durumda uygulamada kararsız olduğu kanıtlanmıştır. 1975'te yayınlanan MINRES yöntemi , matrisin simetrik olması gereken, ancak CG yöntemindeki gibi pozitif olarak kesin olması gerekmeyen bir Krylow alt uzay yöntemidir. Takip eden dönemde, özellikle BiCG süreci için stabilizasyon testleri olmak üzere çok sayıda gelişme incelendi. Denklem herhangi lineer sistem için yaygın olarak kullanılan bir Krylow alt uzay yönteminin bir örneği MINRES yönteminin bir genellemedir, GMRES yöntemi sunulan tarafından 1986 Yusuf Saad ve Martin H. Schultz . QMR yöntemi ( Roland W. Freund ve Noel M. Nachtigal , 1991) ve TFQMR yöntemi (Freund, 1993) gibi diğer yöntemler BiCG grubu ve GMRES fikirlerinden sentezleri kullanır . Başından itibaren, Krylow en alt uzay yöntemleri ayrıca başlayarak hesaplamak özdeğerler için kullanılmıştır Lanczos göre yöntem 1950 Arnoldi yöntemi ile Walter Edwin Arnoldi 1951.

Temel prensipler

Yapıların sömürülmesi

Bir seyrek matrisin meslek yapısı, sonlu elemanlar yönteminde olduğu gibi; küçük siyah kareler sıfır olmayan matris girişlerini temsil eder.

Bilim ve teknolojideki modeller ve sorular milyonlarca denklem içeren doğrusal cebir sorunlarına yol açabilir. Bir milyon satır ve sütuna sahip bir matrisin girişleri, çift ​​duyarlıklı formatta 8  terabayt depolama alanı gerektirir . Bu, bir problem için verinin sağlanmasının, çözümü bir yana, özel yapısı da hesaba katılmadığı takdirde bir zorluk olduğunu göstermektedir. Neyse ki, birçok önemli uygulama - sonlu elemanlar yöntemini kullanarak kısmi diferansiyel denklemlerin ayrıklaştırılması gibi  - çok sayıda denkleme yol açar, ancak her bir denklemde nispeten az bilinmeyen vardır. İlişkili matris için bu, her satırda sıfıra eşit olmayan yalnızca birkaç giriş olduğu anlamına gelir; matris, dedikleri gibi, seyrek . Bu tür matrisleri verimli bir şekilde depolamak ve yapılarını kullanmak için çok sayıda yöntem vardır. Matrislerin sadece matris vektör ürünlerinde göründüğü yöntemler, özellikle seyrek problemler için çok uygundur, çünkü sıfır ile tüm çarpma ve toplamaların açıkça yapılması gerekmez. Öte yandan, matrisin kendisinin yeniden şekillendirildiği algoritmaların uygulanması genellikle zordur çünkü seyrek nüfus daha sonra genellikle kaybolur.

Genel olarak meslek yapısı, yani sıfıra eşit olmayan matris girişlerinin sayısı ve konumu, bir problemin teorik ve sayısal özellikleri üzerinde çok büyük bir etkiye sahiptir. Bu, özellikle köşegen matrislerin uç durumunda , yani ana köşegende sıfırdan farklı girdileri olan matrislerde özellikle netleşir . Köşegen matrisli doğrusal bir denklem sistemi, basitçe sağ taraftaki girişleri köşegen elemanlara bölerek, yani bölümler aracılığıyla çözülebilir . Doğrusal kompanzasyon problemleri ve özdeğer problemleri de diyagonal matrisler için önemsizdir. Köşegen bir matrisin özdeğerleri köşegen elemanlarıdır ve ilişkili özvektörler standart temel vektörlerdir . ${\ displaystyle n}$${\ displaystyle \ mathbf {e} _ {1}, \ dotsc, \ mathbf {e} _ {n}}$

Bir diğer önemli özel durum , ana köşegenin üstündeki veya altındaki tüm girişlerin sıfır olduğu üçgen matrislerdir . Bu tür matrislere sahip denklem sistemleri, basitçe yukarıdan aşağıya veya aşağıdan yukarıya, ileri veya geri yerleştirilerek sırayla çözülebilir. Üçgen matrislerin özdeğerleri yine önemsiz bir şekilde ana köşegendeki girişlerdir; İlişkili özvektörler, ileriye veya geriye doğru eklenerek de belirlenebilir. Seyrek olarak doldurulmuş matrislerin bir başka yaygın özel durumu bant matrisleridir : Burada sadece ana köşegen ve birkaç bitişik ikincil köşegen sıfıra eşit olmayan girişlerle doldurulur. Üst Hessenberg matrisleri , ana köşegenin altındaki ikincil köşegenin de işgal edildiği üst üçgen matrislerin zayıflamasıdır . Özdeğer problemleri, Hessenberg için eşdeğer problemlere veya üç köşeli matrislere nispeten az çabayla dönüştürülebilir .

Ancak sadece meslek yapısı değil, diğer matris özellikleri de sayısal yöntemlerin geliştirilmesi ve analizinde önemli bir rol oynamaktadır. Birçok uygulama simetrik matrislerle ilgili sorunlara yol açar . Özellikle, verilen matris simetrikse özdeğer problemlerinin üstesinden gelmek çok daha kolaydır, ancak doğrusal denklem sistemlerinde bile, bu durumda çözüm çabası genellikle yarı yarıya azalır. Özel algoritmaların mevcut olduğu matris türlerinin diğer örnekleri, Vandermonde matrisleri , Toeplitz matrisleri ve dolaşım matrisleridir .

Başarısızlık analizi: vektör ve matris normları

Matematikte bir vektörün "boyutunu" ölçmek için farklı vektör normları kullanılır. En iyi bilinen ve en yaygın olanı Öklid normudur${\ displaystyle \ mathbf {x} = (x_ {i}) \ in \ mathbb {R} ^ {n}}$

${\ displaystyle \ | \ mathbf {x} \ | _ {2} = {\ sqrt {\ sum _ {i = 1} ^ {n} x_ {i} ^ {2}}}}$,

dolayısıyla tüm vektör bileşenlerinin karelerinin toplamının karekökü. İki veya üç boyutlu uzayda oklar olarak vektörlerin bilinen geometrik gösteriminde bu, tam olarak okun uzunluğuna karşılık gelir. Bununla birlikte, araştırma sorusuna bağlı olarak, maksimum norm veya 1 norm gibi diğer vektör normları daha uygun olabilir . ${\ displaystyle \ | \ mathbf {x} \ | _ {\ infty}}$ ${\ displaystyle \ | \ mathbf {x} \ | _ {1}}$

Eğer vektörler anlaşılmalıdır için bir yaklaşım olarak , bu yaklaşım doğruluğu ölçülebilir bir vektör yardımıyla norm. Fark vektörünün normu ${\ displaystyle \ mathbf {x}, {\ tilde {\ mathbf {x}}} \ in \ mathbb {R} ^ {n}}$${\ displaystyle {\ tilde {\ mathbf {x}}}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ | \ cdot \ |}$

${\ displaystyle \ | {\ tilde {\ mathbf {x}}} - \ mathbf {x} \ |}$

(normal) mutlak hata olarak adlandırılır . "Kesin" vektörün normuna ilişkin olarak mutlak hata dikkate alınırsa , göreceli hata (norm-bazında) elde edilir.${\ displaystyle \ mathbf {x} \ neq \ mathbf {0}}$

${\ displaystyle {\ frac {\ | {\ tilde {\ mathbf {x}}} - \ mathbf {x} \ |} {\ | \ mathbf {x} \ |}}}$.

Relatif hata etkilenmeyen yana ölçekleme arasında ve bu iki vektör arasındaki farkın standart ölçüsüdür ve genellikle sadece "hata" olarak ifade edilir.${\ displaystyle \ mathbf {x}}$${\ displaystyle {\ tilde {\ mathbf {x}}}}$

Matrislerin "boyutu" da matris normları olan normlar kullanılarak ölçülür . Bir matris norm seçimi için buna “uyan” Vektör esastır norm kullanılan özellikle eşitsizlik olmalıdır yerine herkes için . Herkes için geçerli olacak şekilde belirli bir vektör normu için en küçük sayı tanımlanırsa , o zaman doğal matris normu elde edilir . Her vektör normu için, kendisinden kaynaklanan doğal bir matris normu vardır: Öklid normu için bu, spektral normdur, maksimum norm için satır toplamı normu ve 1 norm için sütun toplamı normudur . Vektörlere benzer, göreceli hata ${\ displaystyle \ | A \ |}$${\ displaystyle \ | A \ mathbf {x} \ | \ leq \ | A \ | \ | \ mathbf {x} \ |}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ | A \ |}$${\ displaystyle L}$${\ displaystyle \ | A \ mathbf {x} \ | \ leq L \ | \ mathbf {x} \ |}$${\ displaystyle \ mathbf {x}}$ ${\ displaystyle \ | A \ | _ {2}}$ ${\ displaystyle \ | A \ | _ {\ infty}}$ ${\ displaystyle \ | A \ | _ {1}}$

${\ displaystyle {\ frac {\ | {\ tilde {A}} - A \ |} {\ | A \ |}}}$

bir matris yaklaştırıldığında, bir matris ile nicelendirilebilir.${\ displaystyle A}$${\ displaystyle {\ tilde {A}}}$

Durum ve istikrar

İki boyutlu örnek: Bir matris A ile çarpma , birim çemberi (mavi) bir elips (yeşil) olarak bozar. A'nın koşul numarası , büyük yarı eksen λ _1'in küçük yarı eksen λ _2'ye oranıdır , bu nedenle distorsiyonun gücünü ölçer.

Uygulamadan kaynaklanan sorunlar olması durumunda, verilen boyutlar genellikle hatalara, veri hatalarına tabidir . Örneğin, bir doğrusal denklem sistemi durumunda, sağ taraf bir ölçümden kaynaklanabilir ve bu nedenle bir ölçüm hatası olabilir. Ancak teorik olarak herhangi bir hassasiyetle bilinen miktarlarda bile , bilgisayarda kayan nokta sayıları olarak gösterildiklerinde yuvarlama hatalarından kaçınılamaz. Bu nedenle, tam sistem yerine, gerçekte sağ tarafı rahatsız olan ve buna bağlı olarak "yanlış" bir çözümün olduğu varsayılmalıdır . Şimdi temel soru, verilen niceliklerdeki bozulmaların, aranan niceliklerin bozulmalarını ne kadar güçlü etkilediğidir. Çözümün göreceli hatası, girdi değişkenlerinin göreceli hatasından önemli ölçüde büyük değilse, iyi koşullandırılmış bir sorundan , aksi takdirde kötü koşullandırılmış bir sorundan söz edilir. Doğrusal denklem sistemleri örneği için bu tahmin edilebilir ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle \ mathbf {b}}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle A {\ tilde {\ mathbf {x}}} = {\ tilde {\ mathbf {b}}}}$${\ displaystyle {\ tilde {\ mathbf {b}}}}$${\ displaystyle {\ tilde {\ mathbf {x}}}}$

${\ displaystyle {\ frac {\ | {\ tilde {\ mathbf {x}}} - \ mathbf {x} \ |} {\ | \ mathbf {x} \ |}} \ leq \ | A \ | \ | A ^ {- 1} \ | \ cdot {\ frac {\ | {\ tilde {\ mathbf {b}}} - \ mathbf {b} \ |} {\ | \ mathbf {b} \ |}}}$

kanıtlamak. Öyleyse, katsayı matrisinin normunun ve tersinin normunun çarpımı küçük olduğunda sorun iyi koşullandırılır . Bu önemli parametre, matrisin durum numarası olarak adlandırılır ve ile gösterilir. Gerçek problemlerde, burada gösterildiği gibi genellikle sadece sağ taraf değil, aynı zamanda matristir . Daha sonra benzer, daha karmaşık bir tahmin uygulanır, ancak bu aynı zamanda küçük veri hataları durumunda sorunun durumunu belirlemek için anahtar figürdür. Koşul numarasının tanımı kare olmayan matrislere genelleştirilebilir ve daha sonra doğrusal eşitleme problemlerinin analizinde önemli bir rol oynar. Ne kadar iyi böyle bir sorun şartına değil sadece katsayı matrisinin koşul sayısına bağlıdır , Lineer denklem sistemlerinin olduğu gibi , aynı zamanda sağ tarafta , daha doğrusu üzerinde açı vektörler arasında ve . Göre Bauer-FIKE teoremi , özdeğer problemi durumu da durum numaraları ile tarif edilebilir. Ancak burada, bu sayı değildir özdeğerin bozuklukları tahmin edilebileceği ile değil, matrisin durum numarası olduğu köşegenleştirerek yoluyla .${\ displaystyle \ | A \ | \ | A ^ {- 1} \ |}$${\ displaystyle A}$${\ displaystyle \ kappa (A)}$${\ displaystyle \ mathbf {b}}$${\ displaystyle A}$${\ displaystyle \ kappa (A)}$${\ displaystyle A}$${\ displaystyle \ mathbf {b}}$${\ displaystyle A \ mathbf {x}}$${\ displaystyle \ mathbf {b}}$${\ displaystyle \ kappa (A)}$${\ displaystyle \ kappa (S)}$${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle S ^ {- 1} AS = D}$

Koşul, çözülmesi gereken sorunun bir özelliği iken, kararlılık, kullanılan sürecin bir özelliğidir. Sayısal bir algoritma, kesin olarak hayal edilmiş girdi verileriyle bile, genellikle soruna kesin çözümü sağlamaz. Örneğin, doğru bir çözüme giderek daha kesin bir şekilde yaklaşan yinelemeli bir prosedür, sonlu sayıda adımdan sonra, o noktaya kadar elde edilen yaklaşık çözümle sona ermelidir. Ancak teorik olarak sınırlı sayıda hesaplama adımında kesin çözüm üreten doğrudan yöntemlerle bile, her hesaplama işlemi için bilgisayardaki uygulama sırasında yuvarlama hataları meydana gelir. Sayısal matematikte iki farklı kararlılık terimi kullanılmaktadır, ileri kararlılık ve geri kararlılık. Genel olarak, uygulanan bir fonksiyonun değeri olarak anlaşılan bir problemin girdi miktarı ve onun kesin çözümü olalım . Giriş değişkeni tam olarak verildiği düşünülür olsa bile, bir algoritma ile hesaplama olacaktır teslim başka, "yanlış" sonuç başka değeri olarak yorumlanır, "yanlış" fonksiyonu da uygulanır . Bir algoritma denir ileri kararlı o eğer gelmez farklılık daha belirgin daha zaten beklenen nedeniyle giriş değişkeni hatalardan ve sorunun koşulu. Bu terimin resmi bir tanımı, açık ve nispeten net bir kararlılık ölçüsü verir, ancak karmaşık algoritmalarla bunların ileriye dönük kararlılığını incelemek genellikle zordur. Bu nedenle, James H. Wilkinson'ın bir fikrine dayanarak, sözde bir geriye dönük analiz genellikle ilk olarak ele alınır: Bu amaçla, bir değer belirlenir , yani: Yöntemle hesaplanan "yanlış" değer, " doğru "değer, ancak farklı bir değere sahip olan giriş değişkeni hesaplandı. Bir algoritma, bu girdi değişkenindeki hatalar nedeniyle zaten beklenenden çok daha fazla farklılık göstermiyorsa , geriye doğru kararlı olarak adlandırılır . Geriye dönük kararlı bir algoritmanın ileriye doğru kararlı olduğu kanıtlanabilir.${\ displaystyle u}$${\ displaystyle v = f (u)}$${\ displaystyle f}$${\ displaystyle u}$${\ displaystyle {\ tilde {v}} = \ operatöradı {alg} (u)}$${\ displaystyle \ operatöradı {alg}}$${\ displaystyle u}$${\ displaystyle {\ tilde {v}}}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle {\ tilde {u}}}$${\ displaystyle \ operatöradı {alg} (u) = f ({\ tilde {u}})}$${\ displaystyle {\ tilde {u}}}$${\ displaystyle u}$

Ortogonallik ve Ortogonal Matrisler

Doğrusal cebirin gösterdiği gibi, vektör uzayında matrisler ve bazlar arasında yakın bir bağlantı vardır . Eğer doğrusal bağımsız vektörler im olan göz önüne alındığında, daha sonra bu alana bir taban vardır ve diğer her vektörü olarak benzersiz temsil edilebilir lineer kombinasyonu baz vektörleri. Bir baz değişimi , bir dönüşüm matrisi ile verilen vektör ve matris çarpımına tekabül. Ortonormal tabanlar önemli bir özel durum oluşturur . Burada baz vektörleridir dik olarak birbirine çiftleri ( “nin her biri birbirine dik”) ve aynı zamanda tüm edilir normalize etmek Öklid gibi, uzunluk 1 standart olarak üç boyutlu uzayda. Bir matris oluşturmak için temel vektörleri sütuna göre birleştirirseniz ${\ displaystyle \ mathbb {R} ^ {n}}$${\ displaystyle n}$ ${\ displaystyle \ mathbf {b} _ {1}, \ dotsc, \ mathbf {b} _ {n}}$${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle (\ mathbf {e} _ {1}, \ mathbf {e} _ {2}, \ mathbf {e} _ {3})}$

${\ displaystyle (\ mathbf {b} _ {1} | \ cdots | \ mathbf {b} _ {n})}$

birlikte, bir ortonormal taban durumunda bir ortogonal matris elde edilir .

Ortonormal tabanlar ve ortogonal matrisler, modern sayısal doğrusal cebirin en önemli yöntemlerinin dayandığı birçok dikkate değer özelliğe sahiptir. Ortogonal bir matris içinde olması , sütunlar ortonormal temelini oluşturan matris gösterimde denklem ile tanımlanabilir ifade olup, burada transpoze matris ve birim matris arama. Bu gösterileri dik matris düzenli ve onun tekrar ters devrik eşittir: . Doğrusal bir denklem sisteminin çözümü bu nedenle çok kolay belirlenebilir, geçerlidir . Diğer bir temel özellik, bir vektörü ortogonal bir matrisle çarpmanın Öklid normunu değiştirmeden bırakmasıdır. ${\ displaystyle Q}$${\ displaystyle Q ^ {T} Q = I}$${\ displaystyle Q ^ {T}}$${\ displaystyle I}$${\ displaystyle Q ^ {- 1} = Q ^ {T}}$${\ displaystyle Q \ mathbf {x} = \ mathbf {b}}$${\ displaystyle \ mathbf {x} = Q ^ {T} \ mathbf {b}}$

${\ displaystyle \ | Q \ mathbf {x} \ | _ {2} = \ | \ mathbf {x} \ | _ {2}}$.

Bu aynı zamanda spektral norm ve koşul numarası için de geçerlidir ${\ displaystyle \ | Q \ | _ {2} = 1}$

${\ displaystyle \ kappa (Q) = \ | Q \ | _ {2} \ | Q ^ {- 1} \ | _ {2} = 1}$,

o zaman aynı zamanda ortogonal bir matristir. Ortogonal matrislerle çarpmalar, göreceli hatayı artırmaz.${\ displaystyle Q ^ {- 1} = Q ^ {T}}$

Ortogonal matrisler ayrıca özdeğer problemlerinin teori ve sayısal işlenmesinde önemli bir rol oynar. Spektral teoremin en basit versiyonuna göre , simetrik matrisler ortogonal olarak köşegenleştirilebilir. Bunun anlamı: Uygulanacak bir matris için , bir ortogonal matris ve bir diyagonal matris vardır. ${\ displaystyle A}$${\ displaystyle A ^ {T} = A}$${\ displaystyle Q}$ ${\ displaystyle D}$

${\ displaystyle Q ^ {T} AQ = D}$.

Özdeğerleri köşegen üzerindedir ve sütunları özvektörlerden ortonormal bir temel oluşturur. Özellikle, yukarıda bahsedilen Bauer-Fike teoremine göre, simetrik matrisler için özdeğer problemi her zaman iyi koşullandırılmıştır. Sözde Schur'un normal formu ile simetrik olmayan matrisler için bu ortogonal dönüşümün bir genellemesi vardır.${\ displaystyle D}$${\ displaystyle A}$${\ displaystyle Q}$

Bir Householder matrisiyle çarpma, belirli bir vektörü, x ekseni üzerinde uygun bir ayna düzlemi seçimi ile yansıtır.

Sayısız somut sayısal doğrusal cebir yöntemlerinde kullanılan iki özel, kullanımı kolay ortogonal matris türü vardır: Householder matrisleri ve Givens dönüşleri . Hanehalkı matrislerinin şekli vardır

${\ displaystyle H = I-2 \ mathbf {v} \ mathbf {v} ^ {T}}$

ile bir vektör ile . Geometrik olarak, bu tarif yansımalarını boyutlu alan üzerinde boyutlu hiper dik olan sıfır noktasından, . Temel özelliği şudur: Belirli bir vektör için , bir vektör kolayca belirlenebilir, böylece ilişkili Householder matrisi vektörü bir katına dönüştürür : with . Bu , tüm girişleri ilkinden sıfıra dönüştürür. Uygun Householder dönüşümlerini bu şekilde bir matrise sütun sütun uygularsanız , tüm girişler ana köşegenin altından sıfıra dönüştürülebilir. $\ mathbb {R} ^ {n}} içinde {\ displaystyle \ mathbf {v} \$${\ displaystyle \ | \ mathbf {v} \ | _ {2} = 1}$${\ displaystyle n}$${\ displaystyle \ mathbb {R} ^ {n}}$${\ displaystyle (n-1)}$${\ displaystyle \ mathbf {v}}$${\ displaystyle \ mathbf {a}}$${\ displaystyle \ mathbf {v}}$${\ displaystyle H = I-2 \ mathbf {v} \ mathbf {v} ^ {T}}$${\ displaystyle \ mathbf {a}}$${\ displaystyle \ mathbf {e} _ {1}}$${\ displaystyle H \ mathbf {a} = \ sigma \ mathbf {e} _ {1}}$${\ displaystyle \ sigma = \ pm \ | a \ | _ {2}}$${\ displaystyle H}$${\ displaystyle \ mathbf {a}}$${\ displaystyle A}$${\ displaystyle A}$

Givens rotasyonlar özeldir dönüşleri bir ya da iki boyutlu bir düzlemini döndürme ve bırakmak için diğer sabit boyutlara. Bir vektörü Givens dönüşüyle ​​dönüştürmek, bu nedenle yalnızca iki girişi değiştirir . İki girişten biri, uygun bir dönüş açısı seçimi ile sıfıra ayarlanabilir. Matrislere uygulanan Householder dönüşümleri tüm alt sütunları dönüştürürken, Givens rotasyonları bireysel matris girişlerini özel olarak değiştirmek için kullanılabilir. ${\ displaystyle \ mathbb {R} ^ {n}}$${\ displaystyle n-2}$${\ displaystyle \ mathbf {a}}$${\ displaystyle \ mathbf {a}}$

Ev sahibi dönüşümleri ve Givens rotasyonları bu nedenle belirli bir matrisi bir üst üçgen matrise dönüştürmek için veya başka bir deyişle, bir QR ayrışmasını ortogonal bir matrise ve bir üst üçgen matrise hesaplamak için kullanılabilir . QR ayrıştırması, sayısal doğrusal cebirin tüm alanlarından sayısız prosedürde kullanılan önemli ve çok yönlü bir araçtır.${\ displaystyle A}$ ${\ displaystyle A = QR}$

Benzerlik dönüşümleri

Doğrusal cebirde, bir derece polinomu olan karakteristik polinom , satır ve sütun içeren bir matrisin özdeğer problemini araştırmak için kullanılır . Özdeğerlerinin tam olarak sıfır arasında . İle temel teoremi cebirin o bu doğrudan takip özdeğerlere sahip tam onlar eğer sayılır onların ile çokluğu . Ancak, gerçek matrislerle bile, bu özdeğerler karmaşık sayılar olabilir. Bununla birlikte, gerçek bir simetrik matris varsa, özdeğerlerinin tümü gerçektir. ${\ displaystyle A \ mathbf {x} = \ lambda \ mathbf {x}}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle \ chi _ {A} (\ lambda) = \ det (\ lambda IA)}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle \ chi _ {A}}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle A}$

Karakteristik polinom özdeğer problemi için büyük teorik öneme sahiptir, ancak sayısal hesaplama için uygun değildir. Bunun temel nedeni, belirli katsayılardan ilişkili polinomun sıfırlarını hesaplama sorununun genellikle çok zayıf koşullandırılmış olmasıdır: Bir polinomun katsayılarındaki yuvarlama hataları gibi küçük düzensizlikler, sıfırlarında büyük bir kaymaya yol açabilir. Bu, muhtemelen iyi koşullandırılmış bir problemin - özdeğerlerin hesaplanması - matematiksel olarak eşdeğer ancak kötü koşullandırılmış bir problemle - karakteristik polinomun sıfırlarının hesaplanmasıyla değiştirilir. Özdeğerleri ve özvektörleri hesaplamak için birçok sayısal yöntem bu nedenle başka bir temel fikre dayanmaktadır, benzerlik dönüşümleri: İki kare matris ve buna sahip normal bir matris varsa benzer olarak adlandırılır.${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle S}$

${\ displaystyle B = S ^ {- 1} AS}$

verir. Matrisin bir benzerlik dönüşümü durumunda, başka bir benzeri olan özdeğerlere sahip matrisler olduğu gösterilebilir matrise , özdeğerler değişmez arandı. İlişkili özvektörler de kolaylıkla birbirine dönüştürülebilir: Bir özvektör ise , o zaman bir özvektör aynı öz değere sahiptir. Bu, çok sayıda algoritmada kullanılan temel fikirlere yol açar. Matris , özdeğer probleminin daha verimli bir şekilde çözülebildiği benzerlik dönüşümü ile bir matrise dönüştürülür veya matrisin köşegen veya üçgen bir matrise daha yakın yaklaştığı bir benzerlik dönüşümleri dizisi oluşturulur. Yukarıda belirtilen nedenlerden ötürü, ortogonal matrisler çoğunlukla dönüşüm matrisleri için kullanılır .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle \ mathbf {x}}$${\ displaystyle B}$${\ displaystyle S \ mathbf {x}}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle S}$

Süreç ve süreç sınıfları

Gauss eleme yöntemi

Doğrusal denklem sistemlerini çözmek için klasik Gauss eliminasyon yöntemi, bir başlangıç ​​noktası ve daha fazla geliştirilmiş yöntemler için bir mihenk taşıdır. Bununla birlikte, pratikte de çok büyük olmayan iyi şartlandırılmış sistemler için basit ve güvenilir bir yöntem olarak - özellikle LR ayrıştırması olarak modifikasyonunda (aşağıya bakınız) - hala yaygın olarak kullanılmaktadır. Yöntem, alttan üste sırayla çözülebilen adım adım bir sistem sonucuna kadar bir denklemin uygun katlarını başka bir denklemden çıkararak değişkenleri verilen denklemlerden sistematik olarak ortadan kaldırır.

Sürecin istikrarı düşünüldüğünde sayısal hususlar devreye girer. Aynı sütundaki bir eleman , matrisin-. Köşegen elemanı ile elenecekse , bölüm kullanılmalıdır. ${\ displaystyle k}$${\ displaystyle a_ {kk}}$${\ displaystyle A}$${\ displaystyle a_ {ik}}$

${\ displaystyle l_ {ik}: = {\ frac {a_ {ik}} {a_ {kk}}}}$

çıkarma ve kat gelen inci hat -line. Bu amaçla, en azından düzenli bir matris için uygun hat değişimleri ile her zaman elde edilebilenler uygulanmalıdır . Ama bundan daha fazlası, eğer ona göre çok küçükse , o zaman bu çok büyük bir miktarla sonuçlanacaktır . Aşağıdaki adımlarda, büyük sayıların çıkarılmasıyla pozisyonların silinmesi riski olacaktır ve yöntem istikrarsız olacaktır. Bu nedenle , meblağların olabildiğince küçük kalmasını sağlamak için pivot olarak bilinen hatları değiştirmek önemlidir .${\ displaystyle l_ {ik}}$${\ displaystyle k}$${\ displaystyle i}$${\ displaystyle a_ {kk} \ neq 0}$${\ displaystyle A}$${\ displaystyle | a_ {kk} |}$${\ displaystyle | a_ {ik} |}$${\ displaystyle l_ {ik}}$${\ displaystyle | l_ {ik} |}$

Faktorizasyon yöntemi

Doğrusal denklem sistemlerini çözmek için en önemli doğrudan yöntemler çarpanlara ayırma yöntemleri olarak gösterilebilir. Temel fikirleri, sistemin katsayı matrisini genel olarak iki veya daha fazla matrisin çarpımına bölmektir . Doğrusal denklem sistemi bu nedenle iki aşamada çözülür: Önce sistemin çözümü hesaplanır ve sonra sistemin çözümü . Daha sonra , orijinal sorunun çözümü de öyle . İlk bakışta, yalnızca bir doğrusal denklem sistemini çözme görevi, iki doğrusal denklem sistemini çözme görevi ile değiştirilmiş gibi görünüyor . Bununla birlikte, bunun arkasındaki fikir, faktörleri seçmektir ve bu iki alt sistemin çözülmesi ilk sistemden çok daha kolay olur. Yöntem sınıfının açık bir avantajı, aynı katsayı matrisine sahip ancak farklı sağ taraflara sahip birkaç doğrusal denklem sisteminin çözülmesi durumunda ortaya çıkar : Genelde en karmaşık yöntem adımının çarpanlara ayrılması , o zaman yalnızca bir kez hesaplanmalıdır. . ${\ displaystyle A}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle A = BC}$${\ displaystyle BC \ mathbf {x} = \ mathbf {b}}$${\ displaystyle \ mathbf {y}}$${\ displaystyle B \ mathbf {y} = \ mathbf {b}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle C \ mathbf {x} = \ mathbf {y}}$${\ displaystyle A \ mathbf {x} = BC \ mathbf {x} = B \ mathbf {y} = \ mathbf {b}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle B}$${\ displaystyle C}$${\ displaystyle A}$${\ displaystyle A}$

LR ayrışması

Gauss eleme yöntemi, çarpanlara ayırma yöntemi olarak görülebilir. Katsayıları halinde için olan bir matris içinde girilen, sonuç satırlarını değişimci olmadan daha düşük bir üçgen matris ile ve bir üst üçgen matris . Ek olarak, tek kutupludur , yani ana köşegenindeki tüm girişler 1'e eşittir. Gördüğümüz gibi, satırları genellikle Gauss eliminasyonu ile değiştirilmelidir. Bu, aşağıdakiler yerine satır permütasyon matrisini çarpanlarına ayırarak bir permütasyon matrisi yardımıyla resmi olarak temsil edilebilir : ${\ displaystyle l_ {ik}}$${\ displaystyle 1 \ leq k \ leq i \ leq n}$${\ displaystyle A = LR}$${\ displaystyle L}$${\ displaystyle R}$${\ displaystyle L}$ ${\ displaystyle L}$${\ displaystyle A}$ ${\ displaystyle P}$${\ displaystyle A}$${\ displaystyle PA}$

${\ displaystyle PA = LR}$.

Çarpanlara ayırma yönteminin temel ilkesine göre , üçgen matrisler ve uygunsa, ilişkili permütasyon, çözmek için açıklandığı şekilde belirlenir. Bir sonraki adımda, sağ tarafa izin verilen sıra ileriye ve sonra geriye doğru sokularak çözülür . ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle L}$${\ displaystyle R}$${\ displaystyle L \ mathbf {y} = P \ mathbf {b}}$${\ displaystyle R \ mathbf {x} = \ mathbf {y}}$

LR ayrıştırması ve dolayısıyla Gauss eleme yöntemi, uygun döndürme ile "neredeyse her zaman kararlıdır", bu da çoğu pratik uygulama görevinde hatalarda büyük bir artış olmadığı anlamına gelir. Bununla birlikte, prosedür hatalarının bilinmeyenlerin sayısı ile katlanarak arttığı patolojik örnekler verilebilir .

Cholesky ayrışma

Cholesky ayrışımı, LR ayrışması gibi, simetrik ve pozitifin kesin olduğu , yani yerine getirildiği ve yalnızca pozitif özdeğerlere sahip olduğu birçok uygulamada ortaya çıkan durum için matrisin iki üçgen matrise çarpanlarına ayrılmasıdır . Bu koşullar altında, daha düşük bir üçgen matris vardır. ${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A ^ {T} = A}$${\ displaystyle L}$

${\ displaystyle A = LL ^ {T}}$.

Matris girdileri için genel bir yaklaşım, bunların sütun sütun veya satır satır hesaplanabilmesini sağlayan açık bir yönteme, Cholesky yöntemine götürür. Simetrisinin bu kullanımı , LR ayrıştırmasına kıyasla hesaplama çabasını yaklaşık yarıya indirir.${\ displaystyle L}$${\ displaystyle A}$

Simetrik ve pozitif belirli katsayı matrisleri, klasik olarak doğrusal kompanzasyon problemlerinin çözümü için normal denklemlerin formülasyonunda ortaya çıkar . Minimize etme probleminin doğrusal denklemler sistemine eşdeğer olduğu gösterilebilir. ${\ displaystyle \ | A \ mathbf {x} - \ mathbf {b} \ | _ {2} ^ {2}}$

${\ displaystyle A ^ {T} A \ mathbf {x} = A ^ {T} \ mathbf {b}}$

çözmek için. Bu normal denklemlerin katsayı matrisi simetriktir ve sütunlar doğrusaldan bağımsızsa, aynı zamanda pozitif tanımlıdır. Bu yüzden Cholesky yöntemi kullanılarak çözülebilir. Bununla birlikte, bu yaklaşım yalnızca birkaç bilinmeyenli iyi koşullandırılmış sorunlar için önerilir. Genel olarak, normal denklemler sistemi aslında başlangıçta verilen doğrusal eşitleme probleminden önemli ölçüde daha kötü koşullandırılmıştır. O halde, normal denklemler yoluyla sapmaya gitmek değil, doğrudan QR ayrışımını kullanmak daha iyidir . ${\ displaystyle A ^ {T} A}$${\ displaystyle A}$${\ displaystyle A}$

QR ayrıştırması

Doğrusal denklem sistemi bir QR ayrıştırmasından sonra hesaplanabilir ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

${\ displaystyle A = QR}$

doğrudan faktoring prosedürlerinin genel ilkesine göre çözülebilir; Bu sadece ile geriye doğru yer değiştirme ile belirlenebilir. Ortogonal matrislerin iyi durumda olması nedeniyle, LR ayrışmasının olası kararsızlıkları oluşmaz. Bununla birlikte, hesaplama çabası genellikle yaklaşık iki kat daha fazladır, bu nedenle yöntemlerin tartılması gerekebilir.${\ displaystyle R \ mathbf {x} = \ mathbf {y}}$${\ displaystyle \ mathbf {y} = Q ^ {T} \ mathbf {b}}$

QR ayrışımı aynı zamanda çok büyük olmayan, iyi koşullandırılmış doğrusal kompanzasyon problemlerini çözmek için yaygın bir yöntemdir. Sorun için

küçültmek ${\ displaystyle \ | A \ mathbf {x} - \ mathbf {b} \ | _ {2} ^ {2}}$

ve ile geçerlidir${\ displaystyle A = QR}$${\ displaystyle \ mathbf {r} = A \ mathbf {x} - \ mathbf {b}}$

${\ displaystyle \ | \ mathbf {r} \ | _ {2} ^ {2} = \ | Q ^ {T} \ mathbf {r} \ | _ {2} ^ {2} = \ | Q ^ {T } QR \ mathbf {x} -Q ^ {T} \ mathbf {b} \ | _ {2} ^ {2} = \ | R \ mathbf {x} -Q ^ {T} \ mathbf {b} \ | _ {2} ^ {2}}$.

Öyle ki kullanılmıştır , yani Öklid norm alır, ortogonal ve bu geçerlidir. Son ifade , geriye doğru ilk satırlar eklenerek küçültülebilir.${\ displaystyle Q ^ {T}}$${\ displaystyle Q ^ {T} Q = I}$${\ displaystyle n}$${\ displaystyle R \ mathbf {x} = Q ^ {T} \ mathbf {b}}$

Bölme yöntemiyle sabit nokta yinelemesi

A tamamen farklı bir fikir çözmek, bir başlangıç vektörü sağlamaktır seçme ve yavaş yavaş o , istenen çözüme daha yeni yaklaşımları hesaplamak için. Durumunda yakınsama sekansı karşı da bu iterasyon sonra bir sona uygun bir süre geçtikten sonra , yeterince hassas bir yaklaşım ile adımları için . Bu türün en basit ve en önemli yöntemleri, şeklin bir yinelemesini kullanır. ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle \ mathbf {x} _ {0}}$${\ displaystyle \ mathbf {x} _ {1} = F (\ mathbf {x} _ {0})}$${\ displaystyle \ mathbf {x} _ {2} = F (\ mathbf {x} _ {1})}$${\ displaystyle (\ mathbf {x} _ {0}, \ mathbf {x} _ {1}, \ mathbf {x} _ {2}, \ dotsc)}$${\ displaystyle \ mathbf {x}}$${\ displaystyle N}$${\ displaystyle \ mathbf {x} _ {N}}$${\ displaystyle \ mathbf {x}}$

${\ displaystyle \ mathbf {x} _ {k + 1} = M \ mathbf {x} _ {k} + \ mathbf {c}}$

uygun bir matris ve vektör ile . Bu tür yöntemlerin ancak ve ancak tüm özdeğerlerinin 1'den küçük bir mutlak değere sahip olması durumunda yakınsadığı gösterilebilir . Bu durumda, yinelemeler denklemin bir çözümüne , yani yineleme fonksiyonunun sabit bir noktasına yakınsar . ${\ displaystyle M}$${\ displaystyle \ mathbf {c}}$${\ displaystyle M}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle \ mathbf {x} = M \ mathbf {x} + \ mathbf {c}}$${\ displaystyle F (\ mathbf {y}) = M \ mathbf {y} + \ mathbf {c}}$

Bu türden uygun algoritmaların araştırılmasında sistematik bir yaklaşım, bölme işlemi fikrini sağlar. Bu, matrisi bir toplama dönüştürür ${\ displaystyle A}$

${\ displaystyle A = B + C}$

kolayca ters çevrilen bir matris ve geri kalanıyla ayrışır . Sabit nokta denkleminde denklem sonuçlarının eklenmesi ve yeniden düzenlenmesi${\ displaystyle B}$${\ displaystyle C = AB}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

${\ displaystyle \ mathbf {x} = -B ^ {- 1} C \ mathbf {x} + B ^ {- 1} \ mathbf {b}}$.

İle ve biri , yakınsama durumunda çözümünü veren yinelemeli bir şeklin yöntemi elde edilir. Yakınsama hızı artar, en büyük büyüklüğe sahip yineleme matrisinin öz değeri ne kadar küçük olursa . Bu, herhangi bir matris normu kullanılarak da tahmin edilebilir.${\ displaystyle M = -B ^ {- 1} C}$${\ displaystyle \ mathbf {c} = B ^ {- 1} \ mathbf {b}}$${\ displaystyle \ mathbf {x} _ {k + 1} = M \ mathbf {x} _ {k} + \ mathbf {c}}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle M}$${\ displaystyle M}$

Bölme prosedürü için klasik durum , ana köşegen ile köşegen matris için Jacobi yöntemini , üçgen kısmını düşürmek için Gauss-Seidel yöntemini kullanır . Gevşeme fikri, sabit nokta yönteminin yakınsamasını hızlandırmak için kullanılabilir . Formdaki yinelemeyi düşünün ${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$

${\ displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ Delta \ mathbf {x} _ {k}}$

düzeltilmesi de inci aşaması, uygun bir şekilde seçilmiş gevşeme parametresi ile gelinir gösterilen için ${\ displaystyle \ Delta \ mathbf {x} _ {k}}$${\ displaystyle k}$${\ displaystyle \ omega}$

${\ displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ omega \ Delta \ mathbf {x} _ {k}}$

hakkında. Örneğin, SOR yöntemi Gauss-Seidel yönteminden bu şekilde elde edilir .

Özdeğerlerin hesaplanması için Jacobi yöntemi

Simetrik matrisler için özdeğer problemini çözmek için basit ama güvenilir bir yinelemeli yöntem, Jacobi yöntemidir. Givens dönüşleri ile art arda benzerlik dönüşümleri ile , tümü verilen simetrik matrise benzer olan ve köşegen bir matrise yakınsayan bir simetrik matris dizisi oluşturur . Prosedür, uygun sayıda adımdan sonra iptal edilirse, bu nedenle , aranan özdeğerler için diyagonal girişlerle yaklaşık değerler elde edilir . ${\ displaystyle A}$${\ displaystyle D}$${\ displaystyle D}$${\ displaystyle A}$

Her adımda, bu bağlamda Jacobi dönüşü olarak da adlandırılan Givens dönüşü, matris konumundaki giriş ve ona simetrik olan giriş sıfıra dönüştürülecek şekilde seçilir . Dönüşüm bütün sahip olduğunu, ancak not edilmelidir inci ve inci satır yanı sıra tüm th ve matrisin sütunda değiştirilir. Bu nedenle, bir adımda üretilen sıfırlar genellikle aşağıdaki adımlarda tekrar iptal edilir. Bununla birlikte, Jacobi dönüşleri için uygun bir konum seçimi verildiğinde, tüm diyagonal olmayan elemanlar sıfıra yakınsar. Bu amaçla, klasik Jacobi yöntemi , en büyük mutlak değere sahip diyagonal dışı elemanın bulunduğu her yineleme adımında bu konumu seçer . Manuel bir hesaplamada, bu pozisyon genellikle hızlı bir şekilde tanınabilir, ancak bir bilgisayar programı olarak uygulandığında, onu arama çabası, diğer aritmetik işlemlere kıyasla oldukça fazladır. Bu nedenle döngüsel Jacobi yöntemi günümüzde en çok kullanılmaktadır. Pozisyonlar, önceden sabitlenmiş bir sırayla, örneğin sadece sütunlarda döngüsel olarak çalıştırılır. Hem klasik hem de döngüsel Jacobi yönteminin her zaman yakınsadığı gösterilebilir. Daha modern algoritmalarla karşılaştırıldığında yakınsama nispeten yavaştır. Jacobi yöntemi, seyrek olarak doldurulmuş matrisler için uygun değildir, çünkü yineleme sırasında matris, sıfırdan farklı girdilerle doldurulur.${\ displaystyle (i, j)}$${\ displaystyle (j, i)}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle (i, j)}$

Vektör yinelemesi

Bir matrisin özvektörlerinin hesaplanması için basit bir başlangıç ​​fikri , güç yöntemidir . Bir başlangıç ​​vektörü yinelemeli olarak tekrar tekrar çarpılır ${\ displaystyle A}$${\ displaystyle \ mathbf {x} _ {0} \ neq \ mathbf {0}}$${\ displaystyle A}$

${\ displaystyle \ mathbf {x} _ {k + 1} = A \ mathbf {x} _ {k}}$

veya -th matris gücü ile ifade edilir , hesaplanır. Bunun arkasında, vektörün her adımda en büyük özdeğerle özvektör yönünde en güçlü şekilde gerildiği geometrik düşüncedir . Bununla birlikte, bu basit biçimde, vektör yinelemesi pratik için uygun değildir, çünkü genel olarak girdiler hızla çok küçük veya çok büyük hale gelir. Bu nedenle vektör, ile çarpmaya ek olarak bir vektör normu ile normalize edilir . Öyleyse, özdeğerlerin konumu için belirli ön koşullar altında, bu yöntemin bir skaler önfaktör haricinde bir özvektöre karşı en büyük öz değere yakınsadığı kanıtlanabilir. ${\ displaystyle k}$${\ displaystyle \ mathbf {x} _ {k} = A ^ {k} \ mathbf {x} _ {0}}$${\ displaystyle A}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle A}$${\ displaystyle \ | \ mathbf {x} _ {k} \ | = 1}$

Bu fikir resmi olarak ters matrise uygulanırsa , en küçük özdeğeri olan bir özvektör elde edilir . Bunun için, elbette, tersinin kendisi hesaplanmaz, ancak her adımda doğrusal denklem sistemi kullanılır. ${\ displaystyle A ^ {- 1}}$${\ displaystyle A}$

${\ displaystyle A \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k}}$

çözüldü. Sözde bir shift parametresi yardımıyla fikrin bir başka genellemesi elde edilir . Kendisine en yakın özdeğerin özvektörü, aynı zamanda en küçük miktara sahip "kaydırılmış" matrisin özdeğerinin özvektörüdür . İlişkili yinelemeyle ${\ displaystyle \ sigma}$${\ displaystyle A}$${\ displaystyle \ sigma}$${\ displaystyle A- \ sigma I}$

${\ displaystyle (A- \ sigma I) \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k}}$

ve her adımda normalizasyonu, ters vektör yineleme yöntemiyle sonuçlanır . ${\ displaystyle \ mathbf {x} _ {k}}$

Vektör iterasyon yöntemleri böylece ilk önce belirli bir özvektörünü hesaplar , ilişkili özdeğer Rayleigh bölümü yardımıyla elde edilebilir . Belli uygulamalarda sıklıkla olduğu gibi, yalnızca en büyük, yalnızca en küçük veya daha genel olarak, özvektörünü içeren tek bir özdeğer aranıyorsa, bunlar açıkça çok uygundur.${\ displaystyle A}$

QR prosedürü

QR yöntemi şu anda çok büyük olmayan, tam olarak doldurulmuş matrislerin tüm özdeğerlerini ve özvektörlerini hesaplamak için en önemli algoritmadır . Yinelenen benzerlik dönüşümleri yoluyla, hızlı bir şekilde üst üçgen matrise yakınlaşan bir matris dizisi oluşturmak için her adımda QR ayrıştırmasını kullanan yinelemeli bir yöntemdir . Çıktı matrisinden başlayarak , -inci adımdaki temel fikir , QR-demonte, ${\ displaystyle A}$${\ displaystyle A_ {0}: = A}$${\ displaystyle k}$

${\ displaystyle A_ {k} = Q_ {k} R_ {k}}$,

ve sonra iki faktör ters sırada tekrar çarpılır:

${\ displaystyle A_ {k + 1}: = R_ {k} Q_ {k}}$,

yeni yaklaşım matrisini elde etmek için. Çünkü doğar ve ondan ; bu dönüşüm aslında ortogonal bir matrisle bir benzerlik dönüşümüdür. Daha ayrıntılı bir analizin gösterdiği gibi, güç yöntemiyle yakın bir bağlantı vardır: QR yinelemesi, bir ortonormal tabandaki tüm vektörlere aynı anda uygulanan bir güç yöntemi olarak anlaşılabilir; Her adımdaki QR ayrıştırması, bu vektörlerin yineleme sırasında sayısal olarak sabit ortonormal kalmasını sağlar (ayrıca bkz . Alt uzay yinelemesi ). Bu temsil ayrıca, yöntemin düşük koşullar altında bir üst üçgen matrise yakınsadığına dair bir kanıt sağlar .${\ displaystyle Q_ {k} ^ {- 1} = Q_ {k} ^ {T}}$${\ displaystyle R_ {k} = Q_ {k} ^ {T} A_ {k}}$${\ displaystyle A_ {k + 1} = Q_ {k} ^ {T} A_ {k} Q_ {k}}$${\ displaystyle A}$

Bu basit haliyle, QR yöntemi iki nedenden dolayı henüz pratik kullanım için uygun değildir. Bir yandan, her adımda belirlenmesi gereken QR ayrıştırması için hesaplama çabası çok büyüktür. Öte yandan, yakınsama genellikle yalnızca yavaş gerçekleşir, bu nedenle istenen doğruluğa ulaşmak için birçok adımın gerçekleştirilmesi gerekir. Bir hazırlık aşamasında matrisin benzerlik dönüşümleri yoluyla bir Hessenberg şekline getirilmesindeki ilk noktayla tanışabilirsiniz . Bu, uygun Householder matrisleri ile dönüşümler yoluyla elde edilebilir . Bir Hessenberg matrisi yalnızca ana köşegenin altında sıfır olmayan girişlere sahip olduğundan, karşılık gelen Givens dönüşleri kullanılarak QR hızlı bir şekilde sökülebilir. Kolayca görülebileceği gibi, QR sürecinin bir adımına simetri ve Hessenberg şekli verilmiştir. Simetrik bir Hessenberg matrisi üç köşeli bir matris olduğundan, prosedür simetrik durumda yine önemli ölçüde basitleştirilmiştir. Ters vektör yinelemesine benzer şekilde, yakınsama hızı, matris her adımda matris yerine akıllıca seçilmiş bir kaydırma parametresi ile dönüştürülürse önemli ölçüde artırılabilir . Seçim için , değerin bir özdeğerine yaklaşık olması gerekir , çeşitli sözde kaydırma stratejileri vardır.${\ displaystyle A}$${\ displaystyle n-2}$${\ displaystyle n-1}$${\ displaystyle n-1}$${\ displaystyle A_ {k}}$${\ displaystyle A_ {k} - \ sigma _ {k} I}$${\ displaystyle \ sigma _ {k}}$${\ displaystyle \ sigma _ {k}}$${\ displaystyle A}$

QR yönteminin bir varyantı ile, bir matrisin sözde tekil değer ayrışımı da hesaplanabilir. Köşegenleştirmenin herhangi bir - hatta kare olmayan matrislere genelleştirilmesi, görüntü sıkıştırma gibi bazı uygulamalarda doğrudan kullanılır. Tekil değer ayrışımı, büyük, kötü koşullandırılmış doğrusal telafi problemlerini çözmek için de kullanılabilir.

Krylov alt uzay yöntemi

Krylow alt uzay yöntemleri, çeşitli varyantları ve uzmanlıkları ile, verilen matris çok büyükse ve seyrek nüfusluysa, hem doğrusal denklem sistemlerini hem de özdeğer problemlerini çözmek için en önemli yöntem grubudur . Bu gruptan tarihsel olarak ilk algoritma, simetrik ve pozitif tanımlı katsayı matrisli doğrusal denklem sistemlerini çözmek için kısaca ( İngilizce c onjugate g radyantlarından ) eşlenik gradyan yöntemi , CG yöntemidir . ${\ displaystyle A}$

CG prosedürü

CG yönteminin Krylow alt uzayları ile verimli bağlantısı ancak daha sonra fark edildi, temel fikri farklı: Denklemler sistemi yerine ona eşdeğer bir optimizasyon problemini çözüyor . Yani simetrik ve pozitif tanımlıysa, çözüm , fonksiyonun benzersiz olarak belirlenmiş minimum yeridir. ${\ displaystyle A}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

İki boyutlu durumda, küçültülecek fonksiyonun kontur çizgileri elipslerdir. Her zaman en dik iniş yönünü seçerseniz, bu zikzak bir rotaya (yeşil) götürür. CG yöntemi eşlenik yönleri kullanır ve tam olarak minimumda (kırmızı) iki adımla sonuçlanır.

${\ displaystyle E (\ mathbf {x}) = {\ frac {1} {2}} \ mathbf {x} ^ {T} A \ mathbf {x} - \ mathbf {b} ^ {T} \ mathbf { x}}$.

Bu, temelde optimizasyon problemlerini çözmek için tüm sayısal yöntemlerin doğrusal denklem sistemi, özellikle de sözde iniş yöntemi için de mevcut olduğu anlamına gelir . Bu iteratif, mevcut yaklaşım başlayarak bu işlediğinde içinde , uygun bir ara yönü boyunca inci aşaması, tek boyutlu optimizasyon problemi ${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle k}$${\ displaystyle \ mathbf {s} _ {k}}$

"Arama böylece minimum düzeyde olur."${\ displaystyle \ alpha _ {k} \ in \ mathbb {R}}$${\ displaystyle E (\ mathbf {x} _ {k} + \ alpha _ {k} \ mathbf {s} _ {k})}$

çözmek için. Bulunan konum , bir sonraki adım için yeni yaklaşım haline gelir. Arama yönü için başlangıçta açık bir seçim , en dik inişin yönüdür ve bu , minimum noktayı belirlemek için gradyan yöntemine götürür . Ancak, bu şekilde hesaplanan yaklaşımların genellikle sadece doğru çözüme çok yavaş ve “zikzak bir seyir” içinde yaklaştığı ortaya çıkmaktadır . En aza indirilecek fonksiyonun özel şeklini dikkate alan arama talimatları çok daha uygundur . Düzeyi kümeleri arasında olan boyutlu elipsoidler (örnek iki boyutlu durumda, elips tavsiye edilir, böylece) seçmek için arama tarifi konjuge için birbirlerine (üzere, bu durumda, bu karşılık gelir eşlenik çap ). Burada iki yönün isimleri ve doğruysa konjuge . Bu nedenle CG yöntemi, birinci arama yönü için en dik alçalış yönünü seçer, ancak bunu, tüm arama yönleri birbirine eşlenik olacak şekilde seçer. İnişten sonra gerçek çözüme ulaşıldığı gösterilebilir . Bununla birlikte, genellikle, yeterince doğru bir yaklaşık çözüm, önemli ölçüde daha az adımdan sonra elde edilir ve işlem erken sonlandırılabilir.${\ displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ alpha _ {k} \ mathbf {s} _ {k}}$${\ displaystyle \ mathbf {s} _ {k}}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle E}$${\ displaystyle E}$${\ displaystyle (n-1)}$${\ displaystyle \ mathbf {s} _ {k}}$${\ displaystyle \ mathbf {s} _ {l}}$${\ displaystyle \ mathbf {s} _ {k} ^ {T} A \ mathbf {s} _ {l} = 0}$${\ displaystyle n}$

CG yönteminden Krylow alt uzay yöntemine

CG yönteminin hesaplama adımlarında, matris yalnızca matris-vektör ürünleri biçiminde dahil edilir. Kendi başına sökülmez veya yeniden şekillendirilmez - ince bir şekilde dökülürse büyük bir avantaj. Basitlik için (ancak genelliği kaybetmeden ) bir başlangıç ​​vektörü olarak , sıfır vektörünün seçildiği varsayıldığında , vektörlerin doğrusal bir kombinasyonunun herhangi bir yaklaşımla sağ taraf ile tekrarlanan çarpımlarının kurulduğu daha ayrıntılı bir analizi gösterir . Diğer bir deyişle, her biri bir Krylov alt uzayındadır.${\ displaystyle A}$${\ displaystyle \ mathbf {x} _ {0}}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle \ mathbf {b}, A \ mathbf {b}, A ^ {2} \ mathbf {b}, \ dotsc, A ^ {k-1} \ mathbf {b}}$${\ displaystyle \ mathbf {b}}$${\ displaystyle A}$${\ displaystyle \ mathbf {x} _ {k}}$

${\ displaystyle {\ mathcal {K}} _ {k} (A, \ mathbf {b}) = \ operatorname {span} (\ mathbf {b}, A \ mathbf {b}, A ^ {2} \ mathbf {b}, \ dotsc, A ^ {k-1} \ mathbf {b})}$.

Bu özellik, Krylow altuzay yönteminin özelliğidir: Yaklaşık değerler için yinelemeli olarak üretirler . Ayrıca, kalıntı, henüz belirlenemeyen bir anlamda mümkün olduğunca küçük olacak şekilde seçilir . CG yönteminde, durum mutlaka açık değildir, ancak problemin özel yapısı için çok uygundur: Ağırlıklı vektör normu ile her adım minimumdur. Buradaki dezavantaj, bunun sadece gerçekten simetrik olması ve pozitifin kesin olması, aksi takdirde bir norm olmamasıdır. Genel olarak, Krylow'un alt uzay yönteminin seçim üzerine yerleştirdiği ek koşullar, projeksiyon koşulları olarak formüle edilir. Biri, kalıntının, bir boyutlu altuzaydan tüm vektörlere , semboller halinde dikgen olmasını talep eder.${\ displaystyle k = 0,1,2, \ dotsc}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle \ mathbf {x} _ {k} \ içinde {\ mathcal {K}} _ {k} (A, \ mathbf {b})}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle \ mathbf {r} _ {k} = A \ mathbf {x} _ {k} - \ mathbf {b}}$${\ displaystyle A ^ {- 1}}$${\ displaystyle \ | \ mathbf {v} \ | _ {A ^ {- 1}} = {\ sqrt {\ mathbf {v} ^ {T} A ^ {- 1} \ mathbf {v}}}}$${\ displaystyle \ | \ mathbf {r} _ {k} \ | _ {A ^ {- 1}}}$${\ displaystyle A}$${\ displaystyle \ | \ cdot \ | _ {A ^ {- 1}}}$${\ mathcal {K}} _ {k}} içinde {\ displaystyle \ mathbf {x} _ {k} \$${\ displaystyle \ mathbf {r} _ {k}}$${\ displaystyle k}$${\ displaystyle {\ mathcal {L}} _ {k}}$

${\ displaystyle \ mathbf {r} _ {k} \ perp {\ mathcal {L}} _ {k}}$.

Örneğin CG yöntemi ile olduğu gibi, en basit durumda, normal olarak kendinden-Krylov alt uzay, . Yaklaşımların somut hesaplaması için, ilgili Krylow alt uzaylarının ardışık ortonormal tabanları oluşturulur. Ortonormalizasyon için iyi bilinen Gram-Schmidt yöntemi maalesef standart biçiminde sayısal olarak kararsızdır. Ancak küçük bir değişiklikle stabilize edilebilir.${\ displaystyle {\ mathcal {L}} _ {k}}$${\ displaystyle {\ mathcal {L}} _ {k} = {\ mathcal {K}} _ {k}}$

Daha fazla Krylow alt uzay yöntemi

Hatanın normu ile CG yöntemindeki (mavi) ve MINRES yöntemindeki (yeşil) kalıntıların karşılaştırılması. Matrisleri pozitif olarak tanımlamada uzmanlaşmış CG yöntemi, daha genel MINRES yönteminden daha hızlı birleşir.

Yukarıda bahsedilen temel fikirler, bu süreç sınıfında çok sayıda varyasyon, uyarlama ve iyileştirme ile sonuçlanır ve bunlardan sadece birkaçı örnek olarak adlandırılır. CG yönteminin doğrudan bir genellemesi BiCG yöntemidir . Simetrik matrislerle ilgili kısıtlamayı ortadan kaldırır , çünkü oluşturulan Krylow alt uzaylarına ek olarak, transpoze matrise ait olanları da kullanır. Ek çarpımlardan kaçınan bir optimizasyon , CGS yöntemidir . Her iki tür işlem de birçok pratik durumda istikrarsızdır, ancak örneğin BiCGSTAB süreçleri grubunda çeşitli stabilizasyon girişimlerinin temelini oluşturur . Önemli ve genellikle kararlı yöntemler GMRES ve simetrik matrisler, MINRES için uzmanlığıdır . Doğrudan kalıntılarla başlarsınız ve minimum olan Krylow alt uzayında belirlenirsiniz . Bu temel ilkeye yapılan diğer iyileştirmeler, QMR ve TFQMR süreçlerini içerir .${\ displaystyle A}$${\ displaystyle A ^ {T}}$${\ displaystyle A ^ {T}}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle \ | A \ mathbf {x} _ {k} - \ mathbf {b} \ | _ {2}}$

Krylow'un alt uzay yöntemleri yalnızca çok büyük seyrek doğrusal denklem sistemleri için değil, aynı zamanda bu tür özdeğer problemlerini çözmek için de kullanılabilir - modern sayısal doğrusal cebirdeki büyük önemlerinin bir başka nedeni. Doğal olarak, özdeğer problemleriyle başlamak mümkün değildir ( tanım gereği bu bir özvektör değildir). Yaklaşımlar ve ilişkili olanlar burada belirlenir, böylece ${\ displaystyle \ mathbf {x} _ {0} = \ mathbf {0}}$${\ displaystyle \ mathbf {0}}$${\ displaystyle \ mathbf {x} _ {k}}$${\ displaystyle \ lambda _ {k}}$

${\ displaystyle A \ mathbf {x} _ {k} - \ lambda _ {k} \ mathbf {x} _ {k} \ perp {\ mathcal {K}} _ {k} (A, \ mathbf {x} _ {0})}$

ile geçerlidir. Bu yaklaşım , küçük olanlar için kolayca çözülebilen ve bazı özdeğerlerine yaklaşan boyutsal bir özdeğer problemine yol açar . İlişkili temel algoritma, Arnoldi yöntemidir . Özdeğer problemlerinde her zaman olduğu gibi, simetrik matrisler için önemli basitleştirmeler vardır; bunlar Lanczos prosedürüne götürür .${\ displaystyle \ mathbf {x} _ {0} \ neq \ mathbf {0}}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle A}$

Edebiyat

Ders kitapları

• Steffen Börm, Christian Mehl: Özdeğer Problemleri için Sayısal Yöntemler . Walter de Gruyter, Berlin / Boston 2012, ISBN 978-3-11-025033-6 . 
• Folkmar Bornemann : Sayısal Doğrusal Cebir - MATLAB ve Julia ile Kısa Bir Giriş . Springer Spectrum, Wiesbaden 2016, ISBN 978-3-658-12883-8 . 
• Biswa Nath Datta: Sayısal Doğrusal Cebir ve Uygulamalar . 2. Baskı. SIAM, Philadelphia 2010, ISBN 978-0-89871-685-6 . 
• James W. Demmel : Uygulamalı Sayısal Doğrusal Cebir . SIAM, Philadelphia 1997, ISBN 978-0-89871-389-3 . 
• Gene H. Golub , Charles F. Van Kredisi : Matris Hesaplamaları . 3. Baskı. Johns Hopkins University Press, Baltimore 1996, ISBN 0-8018-5413-X . 
• Nicholas J. Higham : Sayısal Algoritmaların Doğruluğu ve Kararlılığı . 2. Baskı. SIAM, Philadelphia 2002, ISBN 0-89871-521-0 . 
• Andreas Meister: Doğrusal denklem sistemlerinin sayısalları . 5. baskı. Springer Spectrum, Wiesbaden 2015, ISBN 978-3-658-07199-8 . 
• Granville Sewell: Doğrusal Cebirin Hesaplamalı Yöntemleri . 3. Baskı. World Scientific, Singapur 2014, ISBN 978-981-4603-85-0 . 
• Lloyd N. Trefethen , David Bau, III: Sayısal Doğrusal Cebir . SIAM, Philadelphia 1997, ISBN 978-0-89871-361-9 . 

Tarih hakkında

• Jean-Luc Chabert ve diğerleri. (Ed.): Algoritmaların Tarihi . Springer, Berlin / Heidelberg 1999, ISBN 978-3-540-63369-3 . 
• Yousef Saad, Henk A. van der Vorst: 20. yüzyılda doğrusal sistemlerin yinelemeli çözümü . In: Hesaplamalı ve Uygulamalı Matematik Dergisi . bant 123 , 2000, s. 1-33 . 
• Gene H. Golub, Henk A. van der Vorst: 20. yüzyılda özdeğer hesaplaması . In: Hesaplamalı ve Uygulamalı Matematik Dergisi . bant 123 , 2000, s. 35-65 . 

İnternet linkleri

• Sayısal doğrusal cebir. En Enstitüsü Hesaplamalı Matematik TU Braunschweig , 20 Ağustos 2018 tarihinde erişilen (konunun genel bakış). 
• Peter Spellucci: Sayısal Doğrusal Cebir. (PDF) 16 Temmuz 2009, erişim tarihi 20 Ağustos 2018 ( TU Darmstadt'tan ders notları ). 
• Frank Wübbeling: 2012/13 kış döneminde Sayısal Doğrusal Cebir. (PDF) 29 Mart 2013, erişim tarihi 20 Ağustos 2018 ( Münster Üniversitesi ders notları ). 
• Netlib. Erişim tarihi: 20 Ağustos 2018 (Sayısal Doğrusal Cebir Üzerine Özgür Yazılım Koleksiyonu). 

Bireysel kanıt

Bu makale, 23 Mayıs 2016 tarihinde bu sürümde mükemmel makaleler listesine eklenmiştir .