Root-finding algorithms
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function f, from the real numbers to real numbers or from the complex numbers to the complex numbers, is a number x such that f(x) = 0. As, generally, the zeros of a function cannot be computed exactly nor expressed in closed form, root-finding algorithms provide approximations to zeros, expressed either as floating-point numbers or as small isolating intervals, or disks for complex roots (an interval or disk output being equivalent to an approximate output together with an error bound).
- Comment
- enIn mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function f, from the real numbers to real numbers or from the complex numbers to the complex numbers, is a number x such that f(x) = 0. As, generally, the zeros of a function cannot be computed exactly nor expressed in closed form, root-finding algorithms provide approximations to zeros, expressed either as floating-point numbers or as small isolating intervals, or disks for complex roots (an interval or disk output being equivalent to an approximate output together with an error bound).
- Has abstract
- enIn mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function f, from the real numbers to real numbers or from the complex numbers to the complex numbers, is a number x such that f(x) = 0. As, generally, the zeros of a function cannot be computed exactly nor expressed in closed form, root-finding algorithms provide approximations to zeros, expressed either as floating-point numbers or as small isolating intervals, or disks for complex roots (an interval or disk output being equivalent to an approximate output together with an error bound). Solving an equation f(x) = g(x) is the same as finding the roots of the function h(x) = f(x) – g(x). Thus root-finding algorithms allow solving any equation defined by continuous functions. However, most root-finding algorithms do not guarantee that they will find all the roots; in particular, if such an algorithm does not find any root, that does not mean that no root exists. Most numerical root-finding methods use iteration, producing a sequence of numbers that hopefully converge towards the root as a limit. They require one or more initial guesses of the root as starting values, then each iteration of the algorithm produces a successively more accurate approximation to the root. Since the iteration must be stopped at some point these methods produce an approximation to the root, not an exact solution. Many methods compute subsequent values by evaluating an auxiliary function on the preceding values. The limit is thus a fixed point of the auxiliary function, which is chosen for having the roots of the original equation as fixed points, and for converging rapidly to these fixed points. The behaviour of general root-finding algorithms is studied in numerical analysis. However, for polynomials, root-finding study belongs generally to computer algebra, since algebraic properties of polynomials are fundamental for the most efficient algorithms. The efficiency of an algorithm may depend dramatically on the characteristics of the given functions. For example, many algorithms use the derivative of the input function, while others work on every continuous function. In general, numerical algorithms are not guaranteed to find all the roots of a function, so failing to find a root does not prove that there is no root. However, for polynomials, there are specific algorithms that use algebraic properties for certifying that no root is missed, and locating the roots in separate intervals (or disks for complex roots) that are small enough to ensure the convergence of numerical methods (typically Newton's method) to the unique root so located.
- Is primary topic of
- Root-finding algorithms
- Label
- enRoot-finding algorithms
- Link from a Wikipage to an external page
- apps.nrbook.com/empanel/index.html%23pg=442
- Link from a Wikipage to another Wikipage
- Abel–Ruffini theorem
- Aberth method
- Algebra
- Algorithm
- Arbitrary-precision arithmetic
- Bairstow's method
- Bernoulli's method
- Bisection method
- Bit
- Brent's method
- Broyden's method
- Budan's theorem
- Category:Root-finding algorithms
- Closed form expression
- Companion matrix
- Complex number
- Complex plane
- Computational complexity
- Computer algebra
- Computer algebra system
- Computing
- Continued fraction
- Continuous function
- Cube root
- Cubic convergence
- Cubic polynomial
- Derivative
- Descartes' rule of signs
- Disk (mathematics)
- Durand–Kerner method
- Eigenvalue algorithm
- Eigenvalues
- Equation (mathematics)
- Equation solving
- Euclidean division of polynomials
- False position method
- Fast Fourier transform
- Finite difference
- Fixed point (mathematics)
- Fixed-point iteration
- Floating-point arithmetic
- Free software
- Fundamental theorem of algebra
- GNU Scientific Library
- Golden ratio
- GP
- Graeffe's method
- Halley's method
- Horner's method
- Horner method
- Householder's method
- Ill-conditioned
- Integer
- Intermediate value theorem
- Interpolation
- Interval (mathematics)
- Inverse function
- Inverse power method
- Inverse quadratic interpolation
- Iteration
- Iterative method
- ITP Method
- Jenkins–Traub algorithm
- Laguerre's method
- Lehmer–Schur algorithm
- Limit of a sequence
- Linear polynomial
- List of root finding algorithms
- Maple (software)
- Mathematica
- Mathematics
- MPSolve
- Muller's method
- Multidimensional Newton's method
- Multiplicity (mathematics)
- Newton's method
- Nikolai Ivanovich Lobachevsky
- Nth root
- Nth root algorithm
- Numerical analysis
- Numerical instability
- Numerical stability
- Parabola
- Polynomial
- Polynomial evaluation
- Polynomial greatest common divisor
- Polynomial transformations
- Power method
- Properties of polynomial roots
- Quadratic convergence
- Quadratic formula
- Quadratic function
- Quadratic polynomial
- Radical expression
- Rate of convergence
- Rate of variation
- Rational number
- Real number
- Real-root isolation
- Regula falsi
- Ridders' method
- SageMath
- Secant method
- Sequence
- Splitting circle method
- Square-free factorization
- Steffensen's method
- Sturm's theorem
- Theory of equations
- Up to
- Vieta's formulas
- Vincent's theorem
- Wilkinson's polynomial
- X-intercept
- Zero of a function
- SameAs
- Af3g
- Algorithme de recherche d'un zéro d'une fonction
- Algoritmo para encontrar raiz
- Calcolo di uno zero di una funzione
- Gyökkereső algoritmus
- Kök bulma algoritması
- Q1085860
- Resolución numérica de ecuaciones no lineales
- Rodfindingsalgoritme
- Методи розв'язання нелінійних рівнянь
- Численное решение уравнений
- الگوریتمهای پیداکردن ریشه
- خوارزمية إيجاد جذور دالة
- मूल निकालने की विधियाँ
- 求根アルゴリズム
- 求根算法
- 근 찾기 알고리즘
- Subject
- Category:Root-finding algorithms
- WasDerivedFrom
- Root-finding algorithms?oldid=1101747227&ns=0
- WikiPageLength
- 27221
- Wikipage page ID
- 153299
- Wikipage revision ID
- 1101747227
- WikiPageUsesTemplate
- Template:!
- Template:Annotated link
- Template:Citation needed
- Template:Cite book
- Template:Colend
- Template:Cols
- Template:Main
- Template:Math
- Template:Mvar
- Template:Refbegin
- Template:Refend
- Template:Reflist
- Template:Root-finding algorithms
- Template:Short description