EXPLANATION FILE OF PROGRAM ROOT4
=================================
The program root4 calculates the real or complex roots of a polynomial of degree two,
three or four.
1. Numerical Methods
-----------------
1.1 Case 2nd degree: x^2 + bx + c = 0 (1)
The real roots depend on the sign of q = sqrt(b*b-4*c).
a) q >= 0: two real roots exist:
x1 = -b/2 - sqrt(q)/2
x2 = -b/2 + sqrt(q)/2
b) q < 0: two complex roots exist:
x1 = -b/2 - i * sqrt(-q)/2
x2 = -b/2 + i * sqrt(-q)/2
1.2 Case 3rd degree: x^3 + a2 x^2 + a1 x + a0 = 0 (2)
Let be lambda the greatest absolute value of a coefficients.
i
It is known that:
a) if a0 > 0, one real negative root exists in interval [-(1+lambda), 0].
b) if a0 < 0, one real positive root exists in interval [0, (1+lambda)].
First, we calculate this real root x1 by the bisector method.
Then we divide equation (2) by (x - x1 ), the other two roots are solutions
of quadratic equation:
x^2 + (a2 + x1) x + (a1 + (a2 + x1) x1) = 0 (3)
that can be easily solved.
1.3 Case 4th degree: x^4 + a x^3 + b x^2 + c x + d = 0 (4)
Let us put x = y - a/4, then equation (4) can be transformed into a product
of two quadratic equations (2nd degree):
(y^2 + 2ky + l)(y^2 - 2ky + m) = 0 (5)
where: l + m -4k^2 = q (q = b - 3a^2/8)
2k (m - 1) = r (r=c-(ab/2)+(a^3/8) ) (6)
lm = s (s=d-(ac/4)+(a^2b/16)-(3a^4/256) )
k^2 = z is a real root of cubic equation:
z^3 + alpha z^2 + beta z + gamma = 0 (7)
with alpha = q/2, beta = (q^2-4s)/16, gamma = -r^2/64
So the method consists in:
a) solving equation (7) as shown in § 1.2
b) solving linear system (6) to find l and m
c) solving the two equations (5) to find the four roots of (4).
2. Programming Technique
---------------------
We define a vector R of size 4 to store roots and a matrix A of size (4,4)
to store the coefficients of equation of degree N:
i=N
Sum A(N, i) x^i = 0 (N=2,3,4)
i=0
In the Quick Basic program, subroutine 1000 is the main search root driver,
subroutine 2000 solves equation x^3 + A(3,2) x^2 + A(3,1) x + A(3,0) = 0,
subroutine 3000 solves equation x^2 + A(2,1) x + A(2,0) = 0 .
Except the bisector method (not explained here), the program is linear.
However, please note the different ways to solve the linear system (6):
a) if gamma <> 0, then k^2 <> 0 and (6) can be solved by:
l + m = q + 4 k^2
(8)
l - m = r / 2k
b) if gamma = 0, then k=0 is a solution of (7)
1) if q^2 - 4s >= 0, we have: l + m = q and lm = s
id est l + m = q and l - m = sqrt(q^2 - 4s)
easily solved.
2) if q^2 - 4s < 0, the above method does not work. However,
in that case, equation(7) is reduced to z^2 + alpha z + beta =0
and has two real roots (because beta < 0) with opposite signs.
We then choose the positive root and can use (8) to calculate
l and m.
-------------------------------------------------------------
End of file root4.txt