Mathematics of Computation

Author(s): Marko Huhtanen.
Journal: Math. Comp. 72 (2003), 355-373.
MSC (2000): Primary 42C05; Secondary 15A57
Posted: February 22, 2002
Retrieve article in: PDF DVI PostScript

Abstract: The Hermitian Lanczos method for Hermitian matrices has a well-known connection with a 3-term recurrence for polynomials orthogonal on a discrete subset of $\mathbb{R}$ . This connection disappears for normal matrices with the Arnoldi method. In this paper we consider an iterative method that is more faithful to the normality than the Arnoldi iteration. The approach is based on enlarging the set of polynomials to the set of polyanalytic polynomials. Denoting by

the number of elements computed so far, the arising scheme yields a recurrence of length bounded by $\sqrt{8d}$ for polyanalytic polynomials orthogonal on a discrete subset of $\mathbb{C}$ . Like this slowly growing length of the recurrence, the method preserves, at least partially, the properties of the Hermitian Lanczos method. We employ the algorithm in least squares approximation and bivariate Lagrange interpolation.

1.: W.E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Apll. Math., 9, , 17-29. MR 13:163e
2.: M.B. Balk, Polyanalytic functions, WileyVCH, Weinh., 1991. MR 93k:30076
3.: C. de Boor, Polynomial interpolation in several variables, Studies in Computer Science, R. DeMillo and J. R. Rice (eds.), Plenum Press, New York, (1994), pp. 87-119.
4.: C. de Boor and A. Ron, Computational aspects of polynomial interpolation in several variables, Math. Comp., 58, (1992), 705-727. MR 92i:65022
5.: P. Borwein, The arc length of the lemniscate $\{\vert p(z)\vert=1\}$ , Proc. Amer. Math. Soc., 123, (1995), 797-799. MR 95d:31001
6.: C. Brezinski, Formal orthogonality on an algebraic curve, Annals of Numer. Math., 2, (1995), 21-33. MR 97a:42017
7.: A. Bultheel and M. Van Barel, Vector orthogonal polynomials and least squares approximation, SIAM J. Matrix Anal. Appl., 16, (1995), 863-885. MR 96h:65060
8.: J. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997. MR 98m:65001
9.: S. Elhay, G. Golub and J. Kautsky, Updating and downdating of orthogonal polynomials with data fitting applications, SIAM J. Matrix Anal. Appl., 12, 1991, 327-353. MR 91m:65054
10.: L. Elsner and KH.D. Ikramov, On a condensed form for normal matrices under finite sequence of elementary similarities, Lin. Alg. Appl., 254, , 79-98. MR 98b:15011
11.: W. Gautschi, On generating orthogonal polynomials, SIAM J. Sci. Comp., 3 , 289-317. MR 84e:65022
12.: W. Gautschi, Orthogonal Polynomials: Applications and Computations, Acta Numerica 1996, Cambridge University Press, 1996, 45-119. MR 99i:65019
13.: W. Gautschi and G. Inglese, Lower bounds for the condition number of Vandermonde matrices, Numer. Math., 52 , 241-250. MR 89b:65108
14.: G. H. Golub and C. F. Van Loan, Matrix Computations, The John Hopkins University Press, Baltimore and London, the $3^{rd}$ ed., 1996. MR 97g:65006
15.: R.A. Horn and C.R. Johnson, Topics in Matrix Analysis, Cambridge Univ. Press, 1991. MR 92e:15003
16.: A.S. Householder, Lectures on Numerical Algebra, Mathematical Association of America, Buffalo, N.Y., 1972. MR 53:11952
17.: M. Huhtanen, A stratification of the set of normal matrices, SIAM J. Matrix Anal. Appl., to appear.
18.: M. Huhtanen, A Hermitian Lanczos method for normal matrices, SIAM J. Matrix Anal. Appl., to appear.
19.: M. Huhtanen and R. M. Larsen, Exclusion and inclusion regions for the eigenvalues of a normal matrix, Stanford University, SCCM-01-02 report, 2001.
20.: G. G. Lorentz and R. A. Lorentz, Bivariate Hermite interpolation and applications to algebraic geometry, Numer. Math. 57, (1990), 669-680. MR 92f:41004
21.: O. Nevanlinna, Convergence of Iterations for Linear Equations, Lectures in Mathematics ETH Zürich, Birkäuser Verlag, Basel, 1993. MR 94h:65055
22.: L. Reichel, Fast QR decomposition of Vandermonde-like matrices and polynomial least squares approximation, SIAM J. Matrix Anal. Appl., 12, (1991), 552-564. MR 92a:65126
23.: Y. Saad, Numerical Methods for Large Eigenvalue Problems, Halstead Press, NY, 1992. MR 93h:65052
24.: L. A. Santalo, Integral geometry and geometric probability, Addison-Wesley, Reading, MA, 1976. MR 55:6340
25.: T. Sauer, Polynomial interpolation of minimal degree, Numer. Math., 78, (1997), 59-85. MR 99f:41042
26.: P. K. Suetin, Orthogonal polynomials in two variables, Anal. Meth. and Spec. Funct., 3, Gordon and Breach Sci. Publ., Amsterdam, 1999. MR 2000h:42020
27.: I. G. Sprinkhuizen-Kuyper, Orthogonal polynomials in two variables. A further analysis of the polynomials orthogonal over a region bounded by two lines and a parabola, SIAM J. Math. Anal., 7, (1976), 501-518. MR 54:3278
28.: M.J. Zygmunt, Recurrence formula for polynomials of two variables, orthogonal with respect to a rotation invariant measure, Constr. Approx., 15 1999, 301-309. MR 2000b:33008

Marko Huhtanen
Affiliation: SCCM program, Computer Science Department, Stanford University, Stanford, California 94305
Address at time of publication: Department of Mathematics, MIT, 77 Massachusetts Avenue, Cambridge, Massachusetts 01239
Email: Marko.Huhtanen@hut.fi

DOI: 10.1090/S0025-5718-02-01417-5
PII: S 0025-5718(02)01417-5
Keywords: Normal matrix, orthogonal polynanalytic polynomial, slowly growing length of the recurrence, least squares approximation, bivariate Lagrange interpolation
Received by editor(s): September 12, 2000
Received by editor(s) in revised form: March 1, 2001
Posted: February 22, 2002
Additional Notes: This work was supported by the Academy of Finland and the Alfred Kordelin Foundation
Copyright of article: Copyright 2002, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS