Coding Challenge for Vieta's Formulas

[Valentin Albillo]

.
Hi, Namir:

This is my entry for your challenge, which fully meets your requirements. I'm not sure if you consider HP-71B BASIC a "high-level" language but this 4-liner (199 bytes) delivers the goods in the most efficient, economical way and further, if you don't like 71B BASIC you can convert it to your preferred dialect (VBA, Excel, Maple, Python, HPPPL, even RPL) in 5 minutes flat as it's eminently understandable. Let's see:

>LIST

      1  DESTROY ALL @ OPTION BASE 0 @ INPUT "Deg: ";N @ COMPLEX A(N),B(N),X(N-1)
      2  MAT INPUT X,A @ MAT B=ZER @ B(N)=1 @ FOR I=1 TO N @ FOR J=N-I TO N-1
      3  B(J)=B(J+1)-B(J)*X(I-1) @ NEXT J @ B(N)=-B(N)*X(I-1) @ NEXT I @ MAT DISP B
      4  MAT A=(1/A(0))*A @ MAT B=B-A @ DISP "F(X,a) = ";FNORM(B)^2

Notes:

• Both X() and a() are declared as COMPLEX arrays so the program works for both real/complex roots and/or real/complex coefficients
• Complex values are represented as an ordered pair (a, b) = a + i*b. The pair (a, 0) is the real value a
• The coefficients of a() should ideally begin with 1 (i.e.: a(n)=1) for efficiency but the program works equally well with any non-zero a(n)
• If your preferred language doesn't have FNORM (Frobenius Norm), then use this line 4 instead:
  
        4  MAT A=(1/A(0))*A @ S=0 @ FOR I=1 TO N @ S=S+ABS(B(I)-A(I))^2 @ NEXT I @ DISP "F(X,a) =";S
  
  which gives the same result but takes more time and more RAM than FNORM.
• For complex arrays FNORM^2 is the sum of the squares of the absolute values of each (possibly complex) element.

1) Let's see some examples. First a 3rd degree polynomial with 3 real roots (2, 3 and 4):

      P(x) = 5*x^3 -45*x^2 +130*x -120

>RUN

Deg: 3
X(0)? 2.1,3.2,3.9    { approximations to the exact roots }
A(0)? 5,-45,130,-120 { coefficients, its roots are 2, 3 and 4 }

      (1,0)          { always 1 }
      (-9.2,-0)      { x1 + x2 + x3 = 2.1 + 3.2 + 3.9 = 9.2 }
      (27.39,0)      { x1*x2 + x1*x3 + x2*x3 = 2.1*3.2+2.1*3.9+3.2*3.9 = 27.39 }
      (-26.208,-0)   { x1 * x2 * x3 = 2.1*3.2*3.9 = 26.208 }

            F(X,a) = 6.847364 { (-9.2-(-9))^2+(27.39-26)^2+(-26.208-(-24))^2 = 6.847364 }

When the approximate roots finally converge to the exact roots, you get F(X,a) = 0 as it should:

>RUN

Deg: 3
X(0)? 2,3,4
A(0)? 5,-45,130,-120

      (1,0)
      (-9,-0)
      (26,0)
      (-24,-0)

             F(X,a) = 0

2) Let's see a more complicated example, this time a 6th degree polynomial with 2 real roots and 4 complex roots:

      P(x) = 5*x^6 -45*x^5 +225*x^4 -425*x^3 +170*x^2 +370*x -500

>RUN

Deg: 6
X(0)? (0.99,1.01),(0.99,-1.01),-1.02,1.98,(2.99,3.99),(2.99,-3.99)  { approximations }
A(0)? 5,-45,225,-425,170,370,-500                                   { its roots are (1,+-1), -1, 2, (3,+-4) }

      (1,0)                { always 1 }
      (-8.92,0)            { (0.99,1.01)+(0.99,-1.01)-1.02+1.98+(2.99,3.99)+(2.99,-3.99) = 8.92 }
      (44.3228,0)
      (-82.261144,0)
      (30.30225268,0)
      (75.8316409248,0)
      (-100.425361372,0)   { (0.99,1.01)*(0.99,-1.01)*(-1.02)*1.98*(2.99,3.99)*(2.99,-3.99) = -100.425361372 }

            F(X,a) = 25.1755080455

3) Finally, a 3rd degree polynomial with complex coefficients: (3 complex roots, none are conjugates):

      P(x) = x^3 +(-9 -12*i)*x^2 +(-21 +64*i)*x +(85 -20*i)

>RUN
Deg: 3

X(0)? (1.1,1.9),(2.9,4.1),(4.9,6.1)   { complex approximations }
A(0)? 1,(-9,-12),(-21,64),(85,-20)    { coefficients, its roots are (1,2), (3,4), (5,6) }

      (1,0)                { always 1 }
      (-8.9,-12.1)         { (1.1,1.9)+(2.9,4.1)+(4.9,6.1) = (8.9,12.1) }
      (-21.6,63.82)        { (1.1,1.9)*(2.9,4.1)+(1.1,1.9)*(4.9,6.1)+(2.9,4.1)*(4.9,6.1) = (-21.6,63.82) }
      (83.662,-21.038)     { (1.1,1.9)*(2.9,4.1)*(4.9,6.1) = (-83.662,21.038) }

            F(X,a) = 3.280088

Bst regards and have a nice weekend.
V.
.