Geri Dön

Lanczos metodunun esasları

Başlık çevirisi mevcut değil.

  1. Tez No: 55815
  2. Yazar: GÜNDÜZ ÜMİT
  3. Danışmanlar: PROF.DR. METİN GÜRGÖZE
  4. Tez Türü: Yüksek Lisans
  5. Konular: Makine Mühendisliği, Mechanical Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 1996
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 51

Özet

ÖZET LANCZOS METODU Bu çalışmada büyük özdeğer problemlerinin özdeğerlerinin bulunmasında etkin bir biçimde kullanılan Lanczos metodu incelenmiş, metodla ilgili bilgiler biraraya toplanmış ve sonra da iki örnek üzerine uygulanmıştır. Değişik kaynaklardan parça parça, çoğunlukla teorik olarak hayli yüklü ve de farklı notasyonlarla yazılı olarak bulunan bilgilerin homojen bir notasyon sistemiyle ve anlaşılır bir biçimde toparlanmasına gayret edilmiştir. Yöntemin anlaşılabilmesi için gerekli ön bilgilerin kapsamlı bir biçimde verilmesi suretiyle konunun bağımsız bir bütünlük içerisinde derlenmesine çalışılmıştır.Çalışma beş ana bölümde düşünülmüş olup, bunlardan 2. BÖLÜM vektör ve matrisler hakkında genel bilgilerin verilmesine ayrılmıştır. 3. BÖLÜM'de özdeğer problemi tanımlanmış ve çözüm yöntemleriyle çözüm yöntemlerinin seçimi tartışılmıştır. 4. BÖLÜM'de yuvarlatma hatalarından dolayı bozulan ortogonaliteyi yeniden tesis etmekte kullanılan Gram-Schmidt ortogonalizasyon işlemi ve tridiagonal bir matrisin özdeğerlerini bulmakta kullanılan LR Algoritması incelenmiştir. 5. BÖLÜM'de Lanczos metodunun esası incelenmiş olup yöntemin avantaj ve dezavantajları tartışılmıştır. 6. BÖLÜM'de ise Lanczos metodu iki ayrı örneğe uygulanmıştır.

Özet (Çeviri)

SUMMARY LANCZOS METHOD The Lanczos method, first introduced m 1950, is an efficient algorithm for extracting some frequencies and mode shapes of an eigensystem, Lonczos intended his algorithm to be used for computing a few of the extreme eigenvalues and corresponding eigenvectors of a symmetric matrix. However, the algorithm was taken up as a method for reducing a symmetric matrix to tridiagonal form. Lanczos himself observed that round-off error has a significant effect on the algorithm performance and expensive modifications seemed to be necessary to overcome this defect. By 1955 the Householder method replaced the Lanczos algorithm as a more efficient method for tridiagonalizing a matrix [7]. Most engineering applications require only a few eigenvalues at the end of the spectrum, but for small problems the Householder-QR algorithm can find all the eigenvalues almost as fast as a few. For large problems however it is a waste to tridiagonalize the whole matrix. The Lanczos iteration has the property that well-isolated eigenvalues are approximated accurately after a comparatively small number of steps. For example, that largest eigenvalues will be captured after 20 steps, almost independently of the order the problem, n. Moreover, the number of steps taken by the Lanczos method to compute these eigenvalues will always be less than that for the power method. This property makes the Lanczos algorithm very efficient. However, the eigenvalues most frequently wanted are the smaller ones. The Lanczos algorithm is so powerful that it can compute the smaller eigenvalues of a matrix without any factorization. However, they will not be well approximated until nearly n step have been taken. Consequently it is necessary, in this cases, to apply the iteration to an inverted form of the matrix. In this respect the Lanczos algorithm is just like the subspace iteration algorithms[12]. Lanczos vectors can be used to formulate a very efficient means of dynamic response analysis without solving the vibration eingenproblem. These vectors do not have the full uncoupling property of the mode shapes, but they are much less expensive to generate. Moreover, they are derived from the applied load vector and include the static displaced shape as the first vector; thus 'no static correction' is required no matter what the shape of the loading is nor how few vectors are employed in the analysis. Moreover, an indication of the number of vectors required to obtain the desired degre of accuracy may be determined during the derivation of the Lanczos vectors[12]. The Lanczos algorithm is closely related to the inverse iteration and power methods for calculating a single vibration mode shape and frequency of an eigenproblem. Given a pair of matices K and M, and a starting vector x \ these methods generate a sequence of vectors, [3c i, K1 Mx u (/f ' Mfx,,..., (if1 Mj x,],during j iterations. These vector are refered to as the Krylov sequence; the sequence converges to the eigenvector corresponding to the smallest eigenvalue, in magnitude, of the eigenproblem (K-XM)x=0. The basic difference between the Lanczos method and the other methods is that the information contained in each successive vector of the Krylov sequence is employed in the dynamic response analysis, instead of using only the final converged vector. To be more specific, the Lanczos algorithm involves supplementing the Krylov sequence with a Gram- Schmidt orthogonolization process at each step; the result is a set of M-orthonormal vectors that is used to reduce the dimension of the dynamic equation set. In the form of the Lanczos algorithm described here, orthogonolization is applied only with respect to two preceding vectors, leading to a tridiagonal form of the dynamic equations that can be used to great advantage either directly in time step integration or in solution of the free vibration eigenproblem[ 1 2]. The Lanczos transformation matrix X consists of a series of mutually ortogonal vectors xu x2, -*n such that X*X=T (1) The transformation can be expressed as XlAX=T (2a) or AX=XT (2b) where A is the symmetric matrix to be tridiagonalized and T is the tridiagonal matrix. When written in its expanded form, equation (2) becomes [A][x\,..., *N ] = [*i,...,xn]. a, p2 0 P2 «2 P3 0 0 0 0 0 0 0 0 Pn-, 0 0 0 a N-! Pn 0 0 Pn (3) or Ax\ ~ a\X\ + P2X2 Ax2 = $2x\+ a2x2+ $3X3 Axi= P3XJ-1+ apg+ pVi*j+i (4) AXk = Pn*N-I + «N*NThe process of finding the Lanczos vectors begins with an arbitrary selection for Xu where *ı = Pı*ı - (5) The unknown parameter Pi and hence x\ is determined considering that x\ should be orthonormal. Thus X i Tx 1 = PıAX|TXı = Pi2 (6a) x, and x\ = - (6b) H/ Multiplication of the first equation (4) byxiT gives X\TAx\ = aıXıTA'ı + P2*iT*2. (7) If we now select ai so that ai =x\TAx] (8) then substituting equation (8) in equation (7) and using the relationship X\7 X] - 1, we have *iTx2 =0 (9) implying that vectors x\ andx2 are mutually orthogonal. Using similar expressions the complete iteration process can be summarized as Pj = X j x j *j = * j / Pj T OCj Xi J\Xi Xj+i =/lXj-PjXj-i -OCjXN. (10) The eigenvalues of the tridiagonal matrix can be evaluated by any of the standart methods, such as the LR or the QR method. Theoretically, the Lanczos method vectors jc]} X2,..jcn are mutually orthogonal to each other. However, because of round-off errors during computations, orthogonality relationship breaks down when vectors are sufficiently seperated from each other. For large systems, this source of error makes Lanczos method unstable. It is therefore necassary to reorthogonalize a newly determined Lanczos vector by sweeping off any contribution from vectors determined previously. Purification is carried out by using the Gram-Schmidt process. Denoting the purified vector by w>j, we have wi=xrH (*kT*j)*j. (li) k = \The computations involved in the reorthogonalization procedure are very substantial. This makes the Lanczos procedure much less efficient, say, Householder's method for the reduction of symmetric matrices. The Lanczos method is, however, most effective when used to obtain the first few eigenvalues of large symmetric matrices[8]. Thus if only p eigenvalues are required where p« N, the tridiagonalization may be terminated after the first m Lanczos vectors have been found, m being sufficently larger than p. The Nxm transformation matrix Xm can now be used to give a tridiogonal matrix Tm = Xm AXm (12) An eigensolution of Tm will give a good estimate of the p most dominant eigenvalues. To verify whether convergence has been achieved for the eigenvalues, it may be necessary to solve the eigenvalues for Tm-i as well, and to compare the magnitude of the desired eigenvalues obtained from Tm.j and Tm. In general, the starting vector x ı for the Lanczos Method may be chosen arbitrarily. Then, setting xo = 0 the procedure defined by equations (10) will produce the second Lanczos vector X2, and the process may be continued to produce as many vectors as are desired. It should be noted that the cost of evaluating each successive vector is constant after X3 has been obtained because it is necessary to impose orthogonality only with respect to the two preceding vectors[13]. The Lanczos algorithm is particulary advantageous in dynamic analysis when the applied load is of the form f=Mt) (13) that is, when the distribution of the load, b, remains constant and only its amplitude varies with time. The starting vector in this case is taken in the direction of the static displacement. Thus, x^M^K-'b (14) This choice gives the Lanczos vectors the important advantage noted before, that they automatically include the static displacement and avoid any possible need for a static correction[12,13]. The Lanczos vectors are selected to be orthonormal with respect to the mass matrix, so that XTMX = I (15) The eigenvalue problem is now expressed as K = ?JM (16a) K-'M=;rÇ (18) T = XrMKlMX (19) Using again similar expressions the complete iteration process is easily deduced as Xj = X j / Pj Kxi+\=Mx] (20) a.j = x^Mx j+i * j+i = * j+i - P>Vj-i - OjXj The eigenvalues of the tridiagonal matrix can be evaluated by the LR algorithm. The LR algorithm developed by Rutishauser is a straight forward process, readily programmed for a computer, to resolve a matrix A into the product LjRj,where Lj is a lower triangular matrix having units in its diagonal, and Rj is an upper triangular matrix. After A is resolved into the product LıRı, the LR algorithm multiplies the factors in reverse order to obtain a new matrix B. Since A = LjRj and then B = RıLı = Li1 ALi (21) is a similar transform of A When B is found, it is in turn resolved into the product 1,2^2 and C = R2L2 evaluated, and so on. As the succession of similar transforms proceeds, it is found that - the elements below the diagonal become progressively smaller, - the diagonal elements tend to the eigenvalues, in descending order or moduls down the diagonal. The Lanczos-LR algorithm may be regarded as the most powerful algorithm for extracting the first part of the spectrum of a very large eigenvalue problem. That is the reason why it is currently available in most large finite element softwares for structural analysis[3,15,16,17].

Benzer Tezler

  1. Tez No

    338312

    Comparison of five regularization methods for the solution of inverse electrocardiography problem

    Ters elektrokardiyografi probleminin çözümünde beş değişik düzenlileştirme yönteminin karşılaştırılması

    ALPEREN GÜÇLÜ

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. YEŞİM SERİNAĞAOĞLU DOĞRUSÖZ

  2. Tez No

    23258

    A Study of eigensolution methods in structural engineering

    Yapı mekaniğinde özdeğer probleminin çözüm metotları üzerine bir çalışma

    USAMA ZAKOUT

    Yüksek Lisans

    İngilizce

    İngilizce

    1992

    İnşaat MühendisliğiOrta Doğu Teknik Üniversitesi

    PROF. DR. POLAT GÜLKAN

  3. Tez No

    251882

    A comparison of Lanczos decomposition method (LDM) and conventional implicit time-stepping method (ITSM) for numerical reservoir simulation

    Sayısal rezervuar simülasyonu için Lanczos ayrışım (LDM) yöntemi ile geleneksel örtük zaman adımlı (ITSM) yönteminin karşılaştırılması

    KORAY YILMAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2009

    Petrol ve Doğal Gaz Mühendisliğiİstanbul Teknik Üniversitesi

    Petrol ve Doğal Gaz Mühendisliği Ana Bilim Dalı

    PROF. DR. MUSTAFA ONUR

  4. Tez No

    538735

    Large sparse matrix-vector multiplication over finite fields

    Sonlu cisimler üzerinde büyük seyrek matris-vektör çarpımı

    CEYDA MANGIR

    Doktora

    İngilizce

    İngilizce

    2019

    MatematikOrta Doğu Teknik Üniversitesi

    Kriptografi Ana Bilim Dalı

    DOÇ. DR. MURAT CENK

  5. Tez No

    198748

    Hermite tipi ağırlık fonksiyonlarına göre Gauss integrasyon kurallarının oluşturulması

    Construction of Gauss integration rules with respect to hermite type weight functions

    ŞÜKRAN KAYADELEN

    Yüksek Lisans

    Türkçe

    Türkçe

    2005

    MatematikGaziantep Üniversitesi

    Matematik Ana Bilim Dalı

    YRD. DOÇ. DR. ALİ İHSAN HASÇELİK

Geri Dön