Write A Program to Calculate The Roots of The Polynomial

Introduction

A polynomial is an expression consisting of variables and coefficients, involving only the operations of addition, subtraction, multiplication, and non-negative integer exponentiation. Finding the roots of a polynomial means solving for the values of the variable that make the polynomial equal to zero.

For polynomials of degree 2 or 3, exact algebraic solutions exist. However, for higher-degree polynomials, exact solutions become increasingly complex, and numerical methods are often used to approximate the roots.

Numerical Methods for Root Finding

Numerical methods provide approximate solutions to equations that cannot be solved algebraically. Common methods for finding polynomial roots include:

1. Bisection Method: Divides the interval and selects a subinterval in which a root must lie.
2. Newton-Raphson Method: Uses the function's derivative to rapidly converge to a root.
3. Secant Method: Similar to Newton-Raphson but uses finite differences instead of derivatives.

These methods are iterative and require an initial guess or interval where the root is known to exist.

Python Implementation

Here's a Python implementation of the Newton-Raphson method to find roots of a polynomial:

import numpy as np

def polynomial(x, coefficients):
    """Evaluate polynomial at x given coefficients."""
    return sum(c * (x ** i) for i, c in enumerate(coefficients))

def derivative(x, coefficients):
    """Evaluate derivative of polynomial at x."""
    return sum(i * c * (x ** (i - 1)) for i, c in enumerate(coefficients) if i > 0)

def newton_raphson(coefficients, initial_guess, tolerance=1e-6, max_iterations=100):
    """Find root using Newton-Raphson method."""
    x = initial_guess
    for _ in range(max_iterations):
        fx = polynomial(x, coefficients)
        dfx = derivative(x, coefficients)
        if abs(fx) < tolerance:
            return x
        if dfx == 0:
            raise ValueError("Derivative is zero. Cannot continue.")
        x = x - fx / dfx
    raise ValueError("Maximum iterations reached without convergence.")

# Example usage:
coefficients = [1, -3, 2]  # Represents x² - 3x + 2
root = newton_raphson(coefficients, initial_guess=2.0)
print(f"Root found at x = {root:.6f}")

The code defines a polynomial function, its derivative, and the Newton-Raphson method. The example finds a root of the quadratic polynomial x² - 3x + 2.

JavaScript Implementation

Here's a JavaScript implementation of the Bisection method:

function polynomial(x, coefficients) {
    // Evaluate polynomial at x given coefficients
    return coefficients.reduce((sum, coeff, power) => sum + coeff * Math.pow(x, power), 0);
}

function bisectionMethod(coefficients, a, b, tolerance=1e-6, maxIterations=100) {
    // Find root using bisection method
    let fa = polynomial(a, coefficients);
    let fb = polynomial(b, coefficients);

    if (fa * fb >= 0) {
        throw new Error("Function must have opposite signs at endpoints.");
    }

    let c, fc;
    for (let i = 0; i < maxIterations; i++) {
        c = (a + b) / 2;
        fc = polynomial(c, coefficients);

        if (Math.abs(fc) < tolerance) {
            return c;
        }

        if (fa * fc < 0) {
            b = c;
            fb = fc;
        } else {
            a = c;
            fa = fc;
        }
    }

    throw new Error("Maximum iterations reached without convergence.");
}

// Example usage:
const coefficients = [2, -3, 1]; // Represents 2x² - 3x + 1
const root = bisectionMethod(coefficients, 0, 2);
console.log(`Root found at x = ${root.toFixed(6)}`);

This implementation uses the bisection method to find a root between two points where the polynomial changes sign. The example finds a root of the quadratic polynomial 2x² - 3x + 1.

Worked Example

Let's find the roots of the cubic polynomial x³ - 6x² + 11x - 6 = 0 using the Newton-Raphson method.

1. Identify coefficients: [1, -6, 11, -6]
2. Choose initial guess: x₀ = 0
3. First iteration:
   • f(0) = 0 - 0 + 0 - 6 = -6
   • f'(0) = 3(0)² - 12(0) + 11 = 11
   • x₁ = 0 - (-6)/11 ≈ 0.545
4. Second iteration:
   • f(0.545) ≈ -0.17
   • f'(0.545) ≈ 11 - 12(0.545) ≈ 4.618
   • x₂ ≈ 0.545 - (-0.17)/4.618 ≈ 0.582
5. Continue until convergence to x ≈ 1.0

The exact roots of this polynomial are x = 1, x = 2, and x = 3. The numerical method approximates one of these roots.