Real & Imaginary Root Finder using Bisection method

• Download Bisection_method_Root_Finder.zip
• Download demo

Introduction

Present algorithm finds Polynomials' Real and Imaginary Roots. The Polynomial may have only real coefficients, but roots may be imaginary conjugate and a root may have or not multiplicity more than one. The algorithm will find out real and imaginary roots.

Background

For example, (x^2+1)*(x-2) has two conjugate imaginary roots at -i, +i; and a real root x=2. The code will find the three roots. The code first does the multiplication

(x^2+1)*(x-2) = x^3-2*x^2+x-2

and then obtains the roots. So, you may enter the polynomial in either way x^3-2*x^2+x-2 or (x^2+1)*(x-2)

Using the code

There is one class: BisectionRootFinder. To instantiate, it is possible to pass a Math10 polynomial (Math10 is the code from my CAS calculator). More presumably, you will call shared method BisectionRootFinder.ParseFromString(strPolynomial) passing the polynomial as a string.

When instantiating, finding roots is performed.

Now, you may get the roots as an array of Double, calling rrf.GetRealRoots and rrf.GetImaginayRoots.

 

Private Sub btnRoots_Click(sender As Object, e As RoutedEventArgs) Handles btnRoots.Click
    Dim sb As New System.Text.StringBuilder
    Try
        Globalization.CultureInfo.CurrentCulture = New Globalization.CultureInfo("en-US")
        Dim ts As Int64 = Now.Ticks
        Dim rrf As BisectionRootFinder = BisectionRootFinder.ParseFromString(tbPolynomial.Text)
        sb.Append("From polynomial " + vbCrLf + rrf.GetInitialPolynomial.ToString + vbCrLf + vbCrLf)
        sb.Append("Real Roots are:" + vbCrLf)
        If rrf.GetRealRoots.Length = 0 Then
            sb.Append("No real roots where found.")
        Else
            sb.Append(rrf.ToString)
        End If
        sb.Append(vbCrLf)
        sb.Append("Imaginary Roots are:" + vbCrLf)
        If rrf.GetImaginaryRoots.Length = 0 Then
            sb.Append("No imaginary roots where found.")
        Else
            sb.Append(rrf.ToStringImaginaryRoots)
        End If
        sb.Append(vbCrLf)
        Dim ts2 As New TimeSpan(Now.Ticks - ts)
        sb.Append(" " + Math.Round(ts2.TotalMilliseconds).ToString + " ms")
        tbRoots.Text = sb.ToString
    Catch ex As Exception
        tbRoots.Text = ex.Message
    End Try
End Sub

 

Basically, if "p" is our polynomial and is of degree 4, for example, it will obtain the polynomials' successive derivatives of "p", of degree 3, 2 an 1. Then it will obtain the bounds of polynomial degree 1 (by Cauchy's bounds); next of degree 2 and 3. Through bisection method, degree 1 polynomial root (if any) is added as a new bound (interval) for degree 2 polynomial and, here on, up to polynomial of degree 4. Each new root, in polynomials of degree < 4 is evaluated in "p", to ackwnoledge if there is multiplicity. In case of multiplicity, "p" is deflated and .FindRoots is invoked recursively.

History

Version (1.0.2 2024/05/20

Naturally, the next step was to find the imaginary roots. This is done by changes of variable: y=-i*x; and z=sqr(y)