Jednoczesne metody znajdowania wartości szczególnych oraz zer wielomianów ortogonalnych

• Autorzy: Wróbel I.

Warianty tytułu

EN

Jednoczesne metody znajdowania wartości szczególnych oraz zer wielomianów ortogonalnych

• Języki publikacji: EN

Abstrakty

EN

We consider applications of certain rootfinding methods for the bidiagonal singular value problem. The problem of computing singular values of a bidiagonal n-by-n matrix is equivalent to computing eigenvalues of a symmetric tridiagonal n2-by-n2 matrix. The algorithms we propose are modifications of the classical Weierstrass, Aberth and Bairstow methods for computing all roots of a polynomial. We make use of the properties of the matrix, both in algorithms themselves and in the choice of the initial approximation and the stopping criterion. We also apply these modified methods to finding roots of orthogonal polynomials.

PL

Rozważamy zastosowania pewnych metod wyznaczania miejsc zerowych w problemie obliczania wartości szczególnych macierzy dwudiagonalnych. Proponujemy algorytmy będące modyfikacjami metod klasycznych: Weierstrassa, Abertha i Bairstowa obliczania wszystkich pierwiastków wielomianu. Wykorzystywane są własności rozpatrywanych macierzy zarówno w konstrukcji samego algorytmu jak i odpowiednim doborze wartości początkowych oraz w wyborze warunku zakończenia obliczeń. Rozważane zmodyfikowane metody mogą być również stosowane do wyznaczania pierwiastków wielomianów ortogonalnych.

Słowa kluczowe

EN

simultaneous rootfinding methods; singular values; eigenvalues; orthogonal polynomials

PL

metody jednoczesnego wyznaczania pierwiastków; wartości szczególne macierzy; wartości własne macierzy; wielomiany ortogonalne

• Wydawca: Wrocławska Wyższa Szkoła Informatyki Stosowanej "Horyzont"
• Czasopismo: Biuletyn Naukowy Wrocławskiej Wyższej Szkoły Informatyki Stosowanej. Informatyka
• Rocznik: 2012
• Tom: vol. 2
• Strony: 10--15
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Wróbel I.

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Pl. Politechniki 1, 00-661 Warsaw, POLAND

Bibliografia

• [1] O. Aberth, Iteration methods for finding all zeros of a polynomial simultaneously, Math. Comput. 27 (122) (1973), 339-344.
• [2] Å. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, PA, USA, 1996.
• [3] P. A. Clement, A class of triple-diagonal matrices for test purposes, SIAM Review 1 (1) (1959), 50-52.
• [4] J. Demmel and W. Kahan, Accurate singular values of bidiagonal matrices, SIAM J. Sci. Stat. Comput. 11 (1990), 873-912.
• [5] K. Doc ev, Modified Newton method for the simultaneous approximate calculation of all roots of a given algebraic equation, Mat. Spis. Bulgar. Akad. Nauk 5 (1962), 136-139, (in Bulgarian).
• [6] E. Durand, Solutions Numériques des Équations Algébraiques, Tome I: Equations du Type : Racines d'un Polynôme, Masson, Paris, 1960.
• [7] G. H. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, SIAM J. Num. Anal. Ser. B, 2 (2) (1965), 205-224.
• [8] G. H. Golub and Ch. F. Van Loan, Matrix Computations, Third Edition, The Johns Hopkins University Press, Baltimore and London, 1996.
• [9] G. H. Golub and J. H. Welsch, Calculation of Gauss quadrature rules, Math. Comp., 23 (1969), 221-230.
• [10] D. C. Handscomb, Computation of the latent roots of a Hessenberg matrix by Bairstow’s method, Computer J. 5 (1962), 139-141.
• [11] I. O. Kerner, Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numer. Math. 8 (1966), 290-294.
• [12] T. Y. Li, N. H. Rhee, Z. Zeng, An efficient and accurate parallel algorithm for the singular value problem of bidiagonal matrices, Numer. Math. 69 (1995), 283-301.
• [13] W. S. Luk, Finding roots of real polynomial simultaneously by means of Bairstow’s method, BIT 35 (2) (1996), 302-308.
• [14] M. Petković, Iterative Methods for Simultaneous Inclusion of Polynomial Zeros, Springer-Verlag, Berlin, New York, 1989.
• [15] G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973.
• [16] K. Weierstrass, Neuer Beweis des Fundamentalsatzes der Algebra, in Mathematische Werker, Tome III, Mayer und Mueller, Berlin, 1903, 251-269.
• [17] H. Wilf, Mathematics for Physical Sciences, Wiley, New York, 1962.