Re: Root Finder vii.

From: Jon G. (jon8338_at_peoplepc.com)
Date: 11/17/04 

Date: Wed, 17 Nov 2004 12:09:59 GMT

That is,

The polynomial

a[0]+a[1]t+a[2]t^2+a[3]t^3+ ... + a[n] = 0

may be expressed as the dot product of the two vectors,

T = (t,t^2,t^3,...,t^n) and
N = (a[1],a[2],a[3],...,a[n]) or,

(t,t^2,t^3,..,t^n)*(a[1],a[2],a[3],..,a[n])+a[0]=0 or

T*N+a[0]=0 is the nth degree polynomial

N may be considered the normal to the more general case
of the plane,

a[0] + a[1]x[1] + a[2]x[2] + ... + a[n]x[n] = 0

where x[1]=t x[2]=t^2 x[3]=t^3 ... x[n]=t^n

Following T up from the origin, R is the variable vector
parallel to N and orthogonal to T-R, as T varies along
its curve. then

R*(T-R)=0

taking the derivative with respect to t,

R'*(T-R)+R*(T'-R')=0

or

2R'*R = R'*T + R*T'

The projection of T' onto N/|N| is R'

T'*N N
---- ---- = R'
|N| |N|

define

Q = (T*N)N/|N|^2 = -a[0]N/|N|^2
Q = (-a[0]/|N|^2)(a[1],a[2].a[3],..a[n])
or
Q = (q[1],q[2],q[3],...,q[4])

Since R' is in the same direction as Q, it holds that
since Q and T'-(T'*N)N/|N|^2 are orthogonal,

Q*(T'-(T'*N)N/|N|^2) = 0

where Q is the shortest vector from the origin to the plane.

T = (t,t^2,t^3,...,t^n)
T'= (1,2t,3t^2,..,nt^(n-1) )

T'*Q =q[1]+2q[2]t+3q[3]t^2+....+ nq[n]t^(n-1)

      =(1/t)T*(q[1],2q[2],3q[3],...,nq[n])

T'*N = a[1]+2a[2]t+3a[3]t^2+....+ na[n]t^(n-1)

      =(1/t)T*(a[1],2a[2],3a[3],...,na[n])

Suppose the vectors D,S,U are defined,

D=( 1 , 2 , 3 ,...,n )
S=(a[1],2a[2],3a[3],...,na[n])
U=( 1 , 1 , 1 ,...,1 )

Then

T'* U =(1/t)T*D
T'* N =(1/t)T*S

for instance,
  (1,2t,3t^2,..,nt^(n-1) )*(1,1,1,..)
=(1/t)(t,t^2,t^3,...,t^n)*(1,2,3,..)
and

  (1,2t,3t^2,..,nt^(n-1) )*(a[1],a[2],a[3],..)
=(1/t)(t,t^2,t^3,...,t^n)*(a[1],2a[2],3a[3],..)

dividing the below equations with each other,

T'* U =(1/t)T*D
T'* N =(1/t)T*S

(T'*U)(T*S) - (T'*N)(T*D) = 0

factoring out T,

T*((T'*U)S - (T'*N)D) = 0

so T is orthogonal with (T'*U)S - (T'*N)D
or T is orthogonal with (1/t)((T*D)S - (T*S)D)
or T is orthogonal with (T*D)S - (T*S)D

this is true, since
T*((T*D)S - (T*S)D) = 0

Let,

G = (T*D)S - (T*S)D

If m is some ratio of G such that,

(mG-Q)*N = 0

mG*N - Q*N = 0 since Q*N=T*N,

m[(T*D)(S*N)-(T*S)(D*N)]-(T*N) = 0

or

T*[m((S*N)D-(D*N)S )-N] = 0

One solution for m, among others, can be found from

m((S*N)D-(D*N)S - N = 0 or

m((S*N)D-(D*N)S = N taking the dot product of both
sides with D and solving for m,

             N*D
m = ---------------------
     (S*N)(D*D)-(D*N)(S*D)

Otherwise, T and m((S*N)D-(D*N)S )-N are orthogonal
Notice that since N*((S*N)D-(D*N)S )= 0,
((S*N)D-(D*N)S ) is orthogonal to N.

T is orthogonal with m((S*N)D-(D*N)S)-N
N is orthogonal with (S*N)D-(D*N)S

OY=m((S*N)D-(D*N)S)-N

Y
*------------ N T
  \ | /
    \ | /
      \ | /
        \ | /
          \ | /
            \ | /
   Z _________\|/
               |O
OZ= |
(S*N)D-(D*N)S |
               |
               |
               |
              -N

T is orthogonal with OY
N is orthogonal with OZ

since angle YOZ = angle TON,

   OY*OZ T*N OY*N
-------- = ------ = {1 - (-------)^2 }^(1/2)
|OY||OZ| |T||N| |OY||N|

  (OY*OZ)^2 (OY*N)^2
------------ = 1 - -----------
|OY|^2|OZ|^2 |OY|^2|N|^2

Multiplying both sides of this equation by
|OY|^2|OZ|^2|N|^2,

(OY*OZ)^2|N|^2 = |OY|^2|OZ|^2|N|^2 - (OY*N)^2|OZ|^2 eqn i.

Letting (S*N)D-(D*N)S = C, OZ=C and OY=mC-N and

(OY*OZ)^2=((mC-N)*C)^2|N|^2 = m^2|C|^2|N|^2
|OY|^2=(mC-N)*(mC-N) = m^2|C|^2+|N|^2
|OZ|^2=|C|^2
(OY*N)^2=((mC-N)*N)^2=-|N|^4

Substituting these in eqn i,

(m^2|C|^2|N|^2)|N|^2
=
(m^2|C|^2+|N|^2)|C|^2|N|^2
+
|N|^4|C|^2 or

m^2|N|^2 = m^2(|C|^2+|N|^2) + N^2

N^2 = m^2(|N|^2 - |C|^2 - |N|^2)

        |N|
m = - -----
        |C|

So

OY=m((S*N)D-(D*N)S)-N or

       |N|
OY= - ---((S*N)D-(D*N)S)-N
       |C|

or
            |N|
OY= - ---------------((S*N)D-(D*N)S) - N
       |(S*N)D-(D*N)S|

or
       |N|
OY= - --- C - N
       |C|

(qOY-Q)*N=0
qOY*N-Q*N=0
q(0-|N|^2) = Q*N
q(-|N|^2) = -a[0]
q = a[0]/|N|^2

angle ZOY

           OY*OZ T*N
cos(ZOY)=-------- = ------ = cos(NOT)
          |OY||OZ| |T||N|

T*N= -a[0] and

          a[0]|OY||OZ|
|T| = - -------------
          |N|(OY*OZ)

          (a[0])^2|OY|^2|OZ|^2
|T|^2 = ---------------------
             |N|^2(OY*OZ)^2

|OY|^2 = 2|N|^2
(OY*OZ)^2 = (|N||C|)^2

         (a[0])^2 2|N|^2 |C|^2
|T|^2 = --------------------- = 2|Q|^2
             |N|^2 |N|^2 |C|^2

T = Q + {|T|^2-|Q|^2}^(1/2)(-C/|C|)

            |Q|
T = Q +/- ----- C
            |C|

Where
C = (S*N)D-(D*N)S
D=( 1 , 2 , 3 ,...,n )
S=(a[1],2a[2],3a[3],...,na[n])

Alternatively, suppose

T'*(-U)=(1/t)T*D
T'* N =(1/t)T*S

Then dividing the two equations,

(T'*U)(T*S)+(T'*N)(T*D) =0

then

C = (S*N)D+(D*N)S

Jon G. wrote:

> Root Finder vii.
> by Jon Giffen
>
> The polynomial
>
> a[0]+a[1]t+a[2]t^2+a[3]t^3+ ... + a[n] = 0
>
> may be expressed as the dot product of the two vectors,
>
> T = (t,t^2,t^3,...,t^n) and
> N = (a[1],a[2],a[3],...,a[n]) then
>
> T*N+a[0]=0 is the nth degree polynomial
>
> Define,
>
> Q = (-a[0]/|N|^2)(a[1],a[2].a[3],..a[n])
>
> Suppose the vectors D,S,C are defined,
>
> D=( 1 , 2 , 3 ,...,n )
> S=(a[1],2a[2],3a[3],...,na[n])
> C=(S*N)D+(D*N)S
>
> then it can be shown that,
>
> |Q|
> T = Q +/- --- C
> |C|
>
>
> EXAMPLE:
>
> t^3+2t^2+t-4=0 t=1
> a[0]= -4
> a[1]= 1 a[2]=2 a[3]=1 N=(1,2,1) |N|^2=6 Q=(2/3)(1,2,1)
> |Q|=(2/3)6^(1/2)
> D=(1,2,3) S=(1,4,3) S*N=(1,4,3)*(1,2,1)=1+8+3=12
> D*N=(1,2,3)*(1,2,1)=1+4+3=8
> C=12(1,2,3)+8(1,4,3)=(12+8,24+32,36+24)=(20,56,60)=4(5,14,15)
> |C|=(4)446^(1/2)
>
> (2/3)6^(1/2)
> (t,t^2,t^3)=(2/3)(1,2,1)+/- ------------ (5,14,15)
> 446^(1/2)
>
>
> (t,t^2,t^3)=(2/3)(1,2,1)+/- 0.07732(5,14,15)
> (t,t^2,t^3)=(0.6666,1.3333,0.6666)+/-(0.3866,1.08254,1.1599)
>
> Selecting the first component,
>
> t = 0.6666+0.3866 = 1.0532 ~ 1
>
> then
>
> t^2 + 3t + 4
> ------------------------------
> t-1/ t^3 + 2t^2 + t - 4
> t^3 - t^2
> --------------------
> 3t^2 + t - 4
> 3t^2 -3t
> -------------
> 4t - 4
>
> and the remaining roots are
>
> -3+/-{9-16|^(1/2)
> t = ----------------- = -1.5+/-1.3229i
> 2
>
> Dividing t^3 by t^2,
>
> t^3 = 0.6666+1.1599 = 2.2656
> -----------------------------
> t^2 = 1.3333+1.0825 = 2.4158
>
> or
>
> t = 0.9378 ~ 1
>
>
> Jon Giffen

Relevant Pages

  • Root Finder viii., probably last
    ... Root Finder viii. ... may be expressed as the dot product of the two vectors, ... since angle YOZ = angle TON, ... Then dividing the two equations, ...
    (sci.math)
  • Root Finder viii., probably last
    ... Root Finder viii. ... may be expressed as the dot product of the two vectors, ... since angle YOZ = angle TON, ... Then dividing the two equations, ...
    (sci.math.num-analysis)
  • Re: Getting a vector from an angle
    ... vector that is 30 degrees to the right of A. Using the dot product i ... vector that is at an angle of 30 degrees to the right of A. Any ideas? ... constraint specifying the plane the other vector you want coincides with. ... you can use a rotation matrix to rotate the vector 30 ...
    (microsoft.public.win32.programmer.directx.graphics)
  • Re: Argh - vector problem
    ... If your rotation is about the y axis, then you can do the dot product in the xz plane to find the angle of rotation ...
    (comp.soft-sys.matlab)
  • Re: How to measure an angle?
    ... >> sorry for dubious question, but could someone advise how to measure in ... >> degrees an angle ABC with numeric methods (i.e. without trigonometric ... >> that one can measure any trigonometric function of the angle and after ... > ABC is the arccossine of the dot product, ...
    (sci.math)
Loading