PHP & More

A technical blog about programming in PHP and about technology in general: programming, workarounds and troubleshooting

Month: June 2016

Cubic Equations And The Complex Field — June 27, 2016

Cubic Equations And The Complex Field

/phpandmore

One thing I wish to see in languages such as PHP is to find them supporting the complex type. Complex numbers are more than vectors in 2D, and I wish to see expression containing them parsed just like the ones with real numbers. Python supports them, and you have to import ‘cmath’ to use functions of a complex variable. To import cmath type

import cmath

For example, complex numbers are useful in solving cubic equations even if all its roots are real. And cubic equations can be used for Bézier curve manipulations.

Following is the Cardan formula for solving a cubic equation

Be x^3 + ax^2 + bx + c=0 a cubic equation.

Step 1

Convert the equation to the form latex y^3 + py + q = 0
Use the Taylor series formula, to find a k, such that y=x-k:
Be P(x) = x^3 + ax^2 + bx + c
Then, P(x) = P(k) + P'(k)x + {P''(k)x^2 \over 2} + {P'''(k)x^3 \over 6}
P(k) = k^3 + ak^2 + bk + c
P'(k) = 3k^2 + 2ak + b
P''(k) = 6k + 2a
P'''(k) = 6

Because P”(k)=0, 6k + 2a=0, thus:
k= - {a \over 3} .
p=P'(k) = b - {a^2 \over 3}
q=P(k) = {2a^3 \over 27} - {ba \over 3} + c

For example,
x^3 - 7x^2 +14x - 8 = 0
will become
y^3 -2{1 \over 3}y - {20 \over 27} = 0
In Python: 

a = -7
b = 14
c = -8
p = b - a**2 / 3.
q = 2*a**3 / 27. - b*a/3. - 8

Step 2

Find 2 numbers u and v that will help us solve the equation. If y=u+v , then the new equation will be:
u^3 + v^3 + (p + 3uv)(u + v) + q = 0
We can find u,v such that (p + 3uv) = 0,
Thus,

and latex u^3 + v^3 = -q
Since p+3uv=0, u^3{v^3} = {-p^3 \over 27}
From both equations, we get that latex u^3 and latex v^3 are the roots of the quadratic equations
t^2 +qt - {q^3 \over 27} = 0
The roots of the quadratic equations are:
(1) u^3 = - {q \over 2} + \sqrt{{q^2 \over 4} + {p^3 \over 27}}
(2) v^3 = - {q \over 2} - \sqrt{{q^2 \over 4} + {p^3 \over 27}}
In Python, the inner root can be computed using:

innerRoot = cmath.sqrt(q**2 / 4. + p**3/27.)

Now, u and v are cubic roots of (1) and (2) respectively. They must satisfy 3uv=-p.
In Python, you get your initial u using:

u=(-q / 2. + innerRoot) ** (1/3.)

If the pair u,v does not satisfy 3uv = -p, you can multiply your v by
$latex-1 + i \sqrt 3 \over 2 $
until the pair satisfies the condition.
Now, having a solution, get the next by multiplying u by $latex-1 + i \sqrt 3 \over 2 and v by latex-1 – i \sqrt 3 \over 2

In our example:
u^3 = {20 \over 54} + \sqrt{{-263 \over 729}}
v^3 = {20 \over 54} - \sqrt{{-263 \over 729}}

Let’s find our three solutions:
u_1= (0.8333333333333335+0.28867513459481187j), v_1=(0.8333333333333335-0.28867513459481187j)
Thus, latex $y_1 = (1.666666666666667+0j)$
u_2 = (-0.6666666666666659+0.5773502691896264j), v_2=(-0.6666666666666657-0.5773502691896264j)
Thus, y_2 = (-1.3333333333333317+0j)
u_3 = (-0.1666666666666676-0.8660254037844383j), v_3=(-0.1666666666666677+0.866025403784438j)
Thus, y_3 = (-0.3333333333333353-2.220446049250313e-16j)

(The above values are output from Python script. The real results look much better.)
Now, to get the roots of the original equation, add k={-a \over 3} to each y.
In our example,
k = 2{1 \over 3}
Thus,
x_1 = 4, x_2=1, x_3=2

Writing expressions is much easier and more readable when the language supports the complex type.

Advertisements