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:
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.
- Compute ti,0 = an-i-1x0n-i-1 for i=0..n-1
- Store ti,i+1 = anx0n for i=0..n-1
- Compute ti,j+1 = ti-1,j+ti-1,j+1 for j=0..n-1, i=j+1..n
- Compute the coefficients: qi = tn,i+1/x0i for i=0..n-1
- The highest degree coefficient is the same: qn = an