Homotopic residual correction algorithms for general and structured matrices
Genel ve yapılı matrisler için homotopik rezidüel düzeltme algorıtmaları
- Tez No: 713691
- Danışmanlar: PROF. VICTOR PAN
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2001
- Dil: İngilizce
- Üniversite: The City University of New York
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Uygulamalı Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 55
Özet
Newton İterasyonu nümerik hesaplamalarda kullanılagelen temel bir algoritmadır. Bu tezde bir matrisin tersini ya da Moore-Penrose genelleştirilmiş tersini bulmada kullanımına odaklanılmaktadır. Bu yaklaşım 1933'de Schultz ve sonra da başka birçok bilim insanı tarafından çalışılmıştır. Ters matrise ya da genelleştirilmiş ters matrise bir başlangıç yaklaşım değerinin verilmesi halinde algoritma nümerik olarak kararlıdır ve kuadratik olarak yakınsamaktadır. Başlangıç yaklaşım değerinin normunun 1den küçük olması gerekir (bazı tanınmış yöntemler için [PS91]e bakınız). Newton iterasyonu uygulamaları özellikle giriş matrisinin yapılı matris olması halinde (örneğin Toeplitz, Hankel, Vandermonde ve Cauchy matrisleri) daha etkili olmaktadır. Yapılı matrisler için uygulamalarda Newton iterasyonu matris çarpımı tekrarlarından oluşan işlemlere indirgenmektedir. Genel matrisler için oldukça maliyetli olan matris çarpımı yapılı matrisler için son derece avantajlıdır. Öte yandan N.İ. ilerledikçe çarpma işlemleri sonucu matrisin özel yapısı bozulmaktadır. Matris çarpımı sonrası yapıyı korumak için çeşitli yöntemler [P92], [PBRZ99], [PRWa]'de sunulmaktadır. Öte yandan bu yöntemler yeterince yakın bir başlangıç değeri olmasını gerektirmektedir. Bu problem ise bu tezde de konumuz olan homotopik yaklaşım yöntemi ile çözülmektedir. Yöntem genel matrisler için uygulanabilmektedir. Hermityen (ya da reel simetrik) matrisler için homotopik yaklaşım yöntemi ile bulunan sonuçlar homotopik olmayan versiyonla yarışabilmektedir. Matris pozitif tanımlı iken homotopik versiyon için hesaplama maliyeti homotopik olmayanla yaklaşık olarak aynıdır. Tezde yöntem yapılı matrisler için uygulanmaktadır. Yapılı matris durumunda her iterasyon adımında hız dramatik olarak artmakta ve kullanılan teknikler ile yapılı matrisin yapısı da tüm iterasyon boyunca bozulmadan korunmaktadır. [PKRCa]'de elde edilen nümerik sonuçlar Toeplitz matris durumunda algoritmanın sonuçlarının etkinliğini göstermektedir.
Özet (Çeviri)
Newton's Iteration is a fundamental algorithm of numerical and algebraic computing. We focus on its approximation to the inverse or Moore-Penrose generalized inverse of a matrix. This application was studied by Schultz in 1933 and since then by many authors. The algorithm is strongly stable numerically (in fact it is self-correcting) and converges quadratically, provided that an initial approximation to the (generalized) inverse is available. An initial approximation can be crude, but must have a residual norm less than 1, and some known recipes (see in particular [PS91]) give approximations with the initial norms slightly below 1. Most effective, however, are applications of Newton's iteration where the input matrices are structured (celebrated examples are the Toeplitz, Hankel, Vandermonde, and Cauchy matrices), and in this case approximations obtained based on the above recipes is generally too crude. The approximation by N.I. is reduced essentialy to repeatedly performing matrix multiplication, and this operation can be performed very effectively, in nearly linear time, when the matrices are structured (versus cubic time for general matrices). The structure, however, tends to deteriorate gradually as N.I. progresses. Special techniques for preserving the structure have been proposed in [P92], [PBRZ99], [PRWa]. These techniques, however, require sufficiently close initial approximations, substantially closer than those supplied by the known recipes, including the recipes of [PS91]. The problem can be solved, however, based on a new homotopic approach which is our subject in the thesis. We apply this approach to general input matrices. The resulting homotopic version of N.I. turns out to be competitive with non-homotopic version for Hermitian (or real symmetric) input matrices. For the homotopic version, the computational cost is roughly the same as for the non-homotopic one where the input matrix is positive definite and and is substantially less where it is indefinite. We also study application of this approach to structured matrices, in which case each iteration step is dramatically accelerated and is performed in nearly linear time, because some special techniques preserve the structure during the entire iterative process. Numerical experiments reported in [PKRCa] confirm the effectiveness of the resulting algorithms in the case of Toeplitz input matrices.
Benzer Tezler
- Kesirli Navier-Stokes denkleminin sayısal çözümleri
Numerical solution of fractional Navier-Stokes equations
BEWAR SALAHADEEN FAREEQ
Yüksek Lisans
Türkçe
2024
MatematikKocaeli ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. MİNE AYLİN BAYRAK
- Adult ratlarda fötal kortikal greftlerin homotopik transplantasyonu ve hiperbarik oksijen tedavisinin greftler üzerine olan etkileri
Homotopic transplantation of fetal cortical grafts to adult rats and effects of hiperbaric oxygen treatment on grafts
AHMET MURAT KUTLAY
- Soft topolojik uzaylar kategorisinde homotopik kümeler
Homotopic sets in soft topological spaces categories
İMGE ECE KARADAŞ
- Homotopik uzaklık üzerine
On homotopic distance
ÖZGE GENÇ KARA
Yüksek Lisans
Türkçe
2023
MatematikBursa Teknik ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. AYŞE BORAT
- Funktorların genişletilmesi ve bunların homotopik invaryantlığı
Extending functors and their homotopic invariance
KUBİLAY TOPKAYA