homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightlinear algebra

Polynomial Taylor Shift

The calculator evaluates Taylor shift of the given polynomial using Shaw and Traub algorithm.

To isolate polynomial roots by VAS method we need to evaluate Taylor shifts,
i.e. to transform the polyomial: p(x)->p(x+x0). There are few methods for Taylor shifts. One of the most optimal1 Taylor shift algorithms is the method, described by Shaw and Traub2, which we use in this calculator. The algorithm description is just below the calculator:

PLANETCALC, Polynomial shift

Polynomial shift

Polynomial coefficients, space separated.

Input polynomial
Polynomial with Taylor shift

Shaw and Traub method for the Taylor shift

q(x) = p(x+x0) transformation is accomplished by the three simpler transformation:

  • g(x) = p(x0x)
  • f(x) = g(x+1)
  • q(x) = f(x/x0)

The algorithm, step by step

Given the n-degree polynomial: p(x) = anxn+an-1xn-1+...+a1x+a0
We must obtain new polynomial coefficients qi, by Taylor shift q(x) = p(x+ x0).
We'll use the matrix t of dimensions m x m, m=n+1 to store data.

  1. Compute ti,0 = an-i-1x0n-i-1 for i=0..n-1
  2. Store ti,i+1 = anx0n for i=0..n-1
  3. Compute ti,j+1 = ti-1,j+ti-1,j+1 for j=0..n-1, i=j+1..n
  4. Compute the coefficients: qi = tn,i+1/x0i for i=0..n-1
  5. The highest degree coefficient is the same: qn = an

  1. Joachim von zur Gathen, Jürgen Gerhard Fast Algorithms for Taylor Shifts and Certain Difference Equations. 

  2. Mary Shaw, J.F. Traub On the number of multiplications for the evaluation of a polynomial and some of its derivatives.