Polynomial Evaluation Algorithm
Jump to navigation
Jump to search
A Polynomial Evaluation Algorithm is a recursive algorithm that is used to evaluate a linear combination of polynomials.
- Example(s):
- Counter-Example(s):
- See: Recurrence Relation, Numerical Analysis, Recursion, Chebyshev Polynomials, Charles William Clenshaw, Monomial.
References
2021a
- (Wikipedia, 2021a) ⇒ https://en.wikipedia.org/wiki/Polynomial_evaluation Retrieved:2021-9-5.
- In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial [math]\displaystyle{ P(x_1, x_2) = 2x_1x_2 + x_1^3 + 4 }[/math] at [math]\displaystyle{ x_1=2, x_2=3 }[/math] consists of computing [math]\displaystyle{ P(2,3)= 2\cdot 2\cdot 3 + 2^3+4=24. }[/math] See also For evaluating the univariate polynomial [math]\displaystyle{ a_nx^n+a_{n-1}x^{n-1}+\cdots +a_n, }[/math] the most naive method would use [math]\displaystyle{ n }[/math] multiplications to compute [math]\displaystyle{ a_n x^n }[/math] , use [math]\displaystyle{ n }[/math] multiplications to compute [math]\displaystyle{ a_{n-1} x^{n-1} }[/math] and so on for a total of [math]\displaystyle{ \tfrac{n(n+1)}{2} }[/math] multiplications and [math]\displaystyle{ n }[/math] additions.
Using better methods, such as Horner rule, this can be reduced to [math]\displaystyle{ n }[/math] multiplications and [math]\displaystyle{ n }[/math] additions. If some preprocessing is allowed, even more savings are possible.
- In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial [math]\displaystyle{ P(x_1, x_2) = 2x_1x_2 + x_1^3 + 4 }[/math] at [math]\displaystyle{ x_1=2, x_2=3 }[/math] consists of computing [math]\displaystyle{ P(2,3)= 2\cdot 2\cdot 3 + 2^3+4=24. }[/math] See also For evaluating the univariate polynomial [math]\displaystyle{ a_nx^n+a_{n-1}x^{n-1}+\cdots +a_n, }[/math] the most naive method would use [math]\displaystyle{ n }[/math] multiplications to compute [math]\displaystyle{ a_n x^n }[/math] , use [math]\displaystyle{ n }[/math] multiplications to compute [math]\displaystyle{ a_{n-1} x^{n-1} }[/math] and so on for a total of [math]\displaystyle{ \tfrac{n(n+1)}{2} }[/math] multiplications and [math]\displaystyle{ n }[/math] additions.
2021b
- (Wikipedia, 2021b) ⇒ https://en.wikipedia.org/wiki/Clenshaw_algorithm Retrieved:2021-9-5.
- In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials.[1] [2] The method was published by Charles William Clenshaw in 1955. It is a generalization of Horner's method for evaluating a linear combination of monomials.
It generalizes to more than just Chebyshev polynomials; it applies to any class of functions that can be defined by a three-term recurrence relation.
- In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials.[1] [2] The method was published by Charles William Clenshaw in 1955. It is a generalization of Horner's method for evaluating a linear combination of monomials.
- ↑ Note that this paper is written in terms of the Shifted Chebyshev polynomials of the first kind [math]\displaystyle{ T^*_n(x) = T_n(2x-1) }[/math] .
- ↑ Tscherning, C. C.; Poder, K. (1982), "Some Geodetic applications of Clenshaw Summation" (PDF), Bolletino di Geodesia e Scienze Affini, 41 (4): 349–375,