NDLI: Finding the Zeros of a Univariate Equation: Proxy Rootfinders, Chebyshev Interpolation, and the Companion Matrix

Please wait, while we are loading the content...

Finding the Zeros of a Univariate Equation: Proxy Rootfinders, Chebyshev Interpolation, and the Companion Matrix

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Boyd, John P.
Copyright Year	2013
Abstract	When a function $f(x)$ is holomorphic on an interval $x \in [a, b]$, its roots on the interval can be computed by the following three-step procedure. First, approximate $f(x)$ on $[a, b]$ by a polynomial $f_{N}(x)$ using adaptive Chebyshev interpolation. Second, form the Chebyshev--Frobenius companion matrix whose elements are trivial functions of the Chebyshev coefficients of the interpolant $f_{N}(x)$. Third, compute all the eigenvalues of the companion matrix. The eigenvalues $\lambda$ which lie on the real interval $\lambda \in [a, b]$ are very accurate approximations to the zeros of $f(x)$ on the target interval. (To minimize cost, the adaptive phase can automatically subdivide the interval, applying the Chebyshev rootfinder separately on each subinterval, to keep $N$ bounded or to solve rare dynamic range complications.) We also discuss generalizations to compute roots on an infinite interval, zeros of functions singular on the interval $[a, b]$, and slightly complex roots. The underlying ideas are undergraduate-friendly, but link the disparate fields of algebraic geometry, linear algebra, and approximation theory.
Starting Page	375
Ending Page	396
Page Count	22
File Format	PDF
ISSN	00361445
DOI	10.1137/110838297
e-ISSN	10957200
Journal	SIAM Review (SIREAD)
Issue Number	2
Volume Number	55
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-05-08
Access Restriction	Subscribed
Subject Keyword	Connections with real algebraic geometry transcendental equations rootfinding Chebyshev polynomials Single equations
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Theoretical Computer Science Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Computing Zeros on a Real Interval through Chebyshev Expansion and Polynomial Rootfinding

Roots of Polynomials Expressed in Terms of Orthogonal Polynomials

Univariate polynomials: nearly optimal algorithms for factorization and rootfinding

Computing the zeros , maxima and inflection points of Chebyshev , Legendre and Fourier series : Solving transcendental equations by spectral interpolation and polynomial rootfinding

Computing the zeros, maxima and inflection points of Chebyshev, Legendre and Fourier series: solving transcendental equations by spectral interpolation and polynomial rootfinding

An Iterative Scheme for Finding the Real Zeros of Certain Polynomials

A method for finding the zeros of polynomials using a companion matrix

Modified Gershgorin Disks for Companion Matrices

Zeros of Chebyshev Polynomials Associated with a Compact Set in the Plane

Finding the Zeros of a Univariate Equation: Proxy Rootfinders, Chebyshev Interpolation, and the Companion Matrix

Similar Documents

Computing Zeros on a Real Interval through Chebyshev Expansion and Polynomial Rootfinding

Roots of Polynomials Expressed in Terms of Orthogonal Polynomials

Univariate polynomials: nearly optimal algorithms for factorization and rootfinding

Computing the zeros , maxima and inflection points of Chebyshev , Legendre and Fourier series : Solving transcendental equations by spectral interpolation and polynomial rootfinding

Computing the zeros, maxima and inflection points of Chebyshev, Legendre and Fourier series: solving transcendental equations by spectral interpolation and polynomial rootfinding

An Iterative Scheme for Finding the Real Zeros of Certain Polynomials

A method for finding the zeros of polynomials using a companion matrix

Modified Gershgorin Disks for Companion Matrices

Zeros of Chebyshev Polynomials Associated with a Compact Set in the Plane

Finding the Zeros of a Univariate Equation: Proxy Rootfinders, Chebyshev Interpolation, and the Companion Matrix