Polynomial Evaluation Algorithm

From GM-RKB
(Redirected from polynomial computation)
Jump to navigation Jump to search

A Polynomial Evaluation Algorithm is a recursive algorithm that is used to evaluate a linear combination of polynomials.



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.

2021b

  1. 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] .
  2. Tscherning, C. C.; Poder, K. (1982), "Some Geodetic applications of Clenshaw Summation" (PDF), Bolletino di Geodesia e Scienze Affini, 41 (4): 349–375,