Root Finder and Example

From: Jon (jon8338_at_peoplepc.com)
Date: 07/02/04 

Date: Fri, 02 Jul 2004 00:53:12 GMT

                  DERIVING ALL ROOTS TO ANY POLYNOMIAL (with example)

Let
N=(a[1],a[2],...,a[n])
T=(t,t^2,t^3,...,t^n)
then
N*T+a[0]=0 = nth degree polynomial in t. N=(a[1],a[2],a[3],...,a[n]) is
the normal to the plane and T is a space curve in t. Define
Q=(-a[0]/|N|^2)N and let B,P be 2 points on the plane such that
(Q-B)*(P-B)/(|Q-B||P-B|) does not equal 1 or -1. (B,P are selected so
that (Q-B) and (P-B) are not parallel). The unit vector R on the plane
perpendicular to Q-B is,

"P-B minus the reflection of P-B onto the unit vector of Q-B, divided by
the magnitude of the same."

             (P-B)*(Q-B)
       P-B - -----------(Q-B)
               |Q-B|^2
R = ---------------------------
     | (P-B)*(Q-B) |
     | P-B - -----------(Q-B) |
     | |Q-B|^2 | also define,

      Q-B
S = -----
     |Q-B|

then

T = B + uR + mS where u is some ratio and m is some ratio. Taking
the dot product of S with both sides and of R with both sides, note that
R*S=0 and

m=(T-B)*S= S*T-B*S
u=(T-B)*R= R*T-B*R

T = B + (R*T-B*R)R + (S*T-B*S)S
T' = (R*T')R + (S*T')S
T'' = (R*T'')R + (S*T'')S
.
.
T^{n}=(R*T^{n})R + (S*T^{n})S where T^{n} is the nth derivative of T
with respect to t. For t=0,

T(0)=(0,0,0,..,0)
T'(0)=(1,0,0,...,0)
T''(0)=(0,2,0,...,0)
.
.
T^{n}(0)=(0,0,0,...,0,n!)

If R=(r[1],r[2],r[3],...,r[n]) and S=(s[1],s[2],s[3],...,s[n]),

T(0)=B-(B*R)R-(B*S)S
T'(0)= r[1]R + s[1]S
T''(0)=2r[2]R+2s[2]S
.
.
T^{n}(0)=n!r[n]R+n!s[2]S

         n
T(t) = SUM[(1/p!)T^{p}(0)t^p]
        p=0

Where T^{p}(0) is t=0 in the pth derivative of T (Maclaurin) Otherwise,

T(t) =
      B-(B*R)R-(B*S)S +
     (r[1]R+s[1]S)t +
     (r[2]R+s[2]S)t^2 +
     (r[3]R+s[3]S)t^3 +
             .
             .
     (r[n]R+s[n]S)t^n Let B=(b[1],b[2],...,b[n])

Decoding T(t),

(r[1]r[1]+s[1]s[1]-1)t +
(r[2]r[1]+s[2]s[1] )t^2+
(r[3]r[1]+s[3]s[1] )t^3+
.
.
(r[n]r[1]+s[n]s[1] )t^n + (b[1]-(B*R)r[1]-(B*S)s[1]) = 0
==
(r[1]r[2]+s[1]s[2] )t +
(r[2]r[2]+s[2]s[2]-1)t^2+
(r[3]r[2]+s[3]s[2] )t^3+
.
.
(r[n]r[2]+s[n]s[2] )t^n + (b[2]-(B*R)r[2]-(B*S)s[2]) = 0
==
(r[1]r[3]+s[1]s[3] )t +
(r[2]r[3]+s[2]s[3] )t^2+
(r[3]r[3]+s[3]s[3]-1)t^3+
.
.
(r[n]r[3]+s[n]s[3] )t^n + (b[3]-(B*R)r[3]-(B*S)s[3]) = 0
==
This continues until we arrive at,
(r[1]r[n]+s[1]s[n] )t +
(r[2]r[n]+s[2]s[n] )t^2+
(r[3]r[n]+s[3]s[n] )t^3+
.
.
(r[n]r[n]+s[n]s[n]-1)t^n + (b[n]-(B*R)r[n]-(B*S)s[n]) = 0

Generalizing n equations into n planes,

(r[1]r[1]+s[1]s[1]-1)x[1]+
(r[2]r[1]+s[2]s[1] )x[2]+
(r[3]r[1]+s[3]s[1] )x[3]+
.
. D R14 S14
(r[n]r[1]+s[n]s[1] )x[n] + (b[1]-(B*R)r[1]-(B*S)s[1]) = 0
==
(r[1]r[2]+s[1]s[2] )x[1]+
(r[2]r[2]+s[2]s[2]-1)x[2]+
(r[3]r[2]+s[3]s[2] )x[3]+
.
.
(r[n]r[2]+s[n]s[2] )x[n] + (b[2]-(B*R)r[2]-(B*S)s[2]) = 0
==
(r[1]r[3]+s[1]s[3] )x[1]+
(r[2]r[3]+s[2]s[3] )x[2]+
(r[3]r[3]+s[3]s[3]-1)x[3]+
.
.
(r[n]r[3]+s[n]s[3] )x[n] + (b[3]-(B*R)r[3]-(B*S)s[3]) = 0
==
This continues until we arrive at,
(r[1]r[n]+s[1]s[n] )x[1]
(r[2]r[n]+s[2]s[n] )x[2]+
(r[3]r[n]+s[3]s[n] )x[3]+
.
.
(r[n]r[n]+s[n]s[n]-1)x[n] + (b[n]-(B*R)r[n]-(B*S)s[n]) = 0

These n planes intersect each other with various lines (they can all be
found), they have angles between all of their normals (also easily
obtained), and share a common point (the n equations can be solved for
the n unknowns using linear algebra). Supposing this common point is
calculated as C=(c[1],c[2],c[3],..,c[n]). It can be deduced that while
the point C is a solution to the intersection of all the planes, it does
not necessarily follow that c[2]=c[1]^2, c[3]=c[1]^3, etc as in
T=(t,t^2,t^3,..,t^n). Supposing the solution t=w exists. It can be
inferred that if w is a root, it must also satisfy the point of
intersection of the planes at C. Supposing, then, that C is a solution.
  Selecting the last component c[n]=t^n,

t = c[n]^(1/n)[cos(2k*pi/n)+ i sin(2k*pi/n)] if c[n] is positive

t = |c[n]|^(1/n)[cos((2k+1)pi/n)+ i sin((2k+1)pi/n)] if c[n] is negative

where k = 0,1,2,3,...,n-1 Binomial Equation

Rendering the n roots for the nth degree polynomial N*T+a[0]=0.

EXAMPLE

Solve Bx/(2A)=sin(x/2) for B/A = 2*(2^*1/2)/pi

x = pi/2

B=chord
A=arclength
x=angle subtending arc and chord

sin(x/2) is expanded as a power series, and x/2 is canceled from both
sides. Let t=(x/2)^2 and carry the series out to the 8th power of t.
The resulting values were obtained using the above method calculated on
a spread***:

a[j] x[j]=t^j c*pi
a[0] 0.099683684
a[1] -0.166666667 -6.14244E-12
a[2] 0.008333333 -11.53827506
a[3] -0.000198413 18.70774654 0.845001123
a[4] 2.20459E-05 8.206996951 0.538761056
a[5] -2.50521E-08 18.71340883 0.571848134
a[6] 1.6059E-10 8.206367733 0.452073056
a[7] -7.64716E-13 18.71340954 0.483711329
a[8] 2.81146E-15 8.206367728 0.414113129
                        
B P Q
0.645853126 2 0.596609723
1 28.05647943 -0.029830486
2 1 0.00071025
1 2 -7.89166E-05
2 1 8.9678E-08
1 2 -5.74859E-10
2 1 2.73742E-12
1 2 -1.00641E-14

DISCUSSION

All the values in the c*pi column should be equal to 1/2. The values
obtained are somewhat of a disappointment, especially after carrying out
the power series to the 8th power of t (the 8th term is on the order of
1/17!). The negative values in the x[j]=t^j column give complex
solutions, as do each t^j decomposed with the Binomial Equations.

The B and P that I selected were designed so that P-B and Q-B are not
parallel (they are close to pi/2 apart). However, the 28.05647943 term
may have been too large and introduced error.

Nonetheless, it is somewhat heartening that the c*pi column values are
somewhat close to 1/2, showing that within some range of certainty, the
method pans out the right answers.

Jon Giffen