What are roots?

We will start this series by learning the easiest root finding algorightm: Bisection Method. We will explore the ins and outs of this algorithm, how it works and why it works.

To understand roots, it is essential to understand the definition of functions. Think of a function as a machine that follows precise rules - you put something in, and it gives you something back. For example, a simple function might take a number, double it, and subtract 4. But here's where roots come in: sometimes we're particularly interested in finding what we need to put into our function to get zero as the output. Why zero? Zero is special - it's like a balancing point where positive numbers meet negative numbers. When a function's output crosses zero, it switches from positive to negative (or vice versa), making zero a crucial threshold.

These "special inputs" that give us zero are what we call roots. Finding roots might sound abstract, but they show up in surprisingly practical situations. Imagine you're tracking two cars driving toward each other on a highway - finding when they meet means finding when the distance between them becomes zero. Or picture throwing a ball into the air - finding when it hits the ground means finding when its height becomes zero. Even in finance, if you're watching your bank account gradually decrease, finding when you'll run out of money means finding when your balance hits zero. In each case, we're really hunting for roots - those special input values that make something become zero.

Different types of roots require different way of handling. There are 3 types of roots:

1. Simple Roots: $x - 2 = 0$ has root at $x = 2$. They converge the fastest.
2. Multiple Roots: $(x - 2)^2 = 0$, root at $x = 2$ with multiplicity 2. They require modified algorithms.
3. Complex Roots: $x^2 + 1 = 0$, roots are $\pm i$. They exist in complex plane in $\alpha + \beta i$ form (real + imaginary component). They have conjugate pair property. They need specialized complex-number techniques.

Why Do We Need Numerical Methods?

Remember the root finding formula of $ax^2 + bx + c = 0$? It was,$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$It was the first root finding formula we learned and still use to this day. It was so easy and straigtforward. However, certain equations, such as $e^x = x^2$ or $\sin(x) = x^3$, cannot be solved algebraically. These equations don't have closed-form solutions, meaning there is no straightforward formula to compute their roots or values. Numerical methods allow us to approximate these solutions by iteratively getting closer to the real root or value. This iterative process ensures that we can get as close as needed to the exact solution, even if it cannot be expressed explicitly. Exact math often gives you perfect theoretical answers (like $\pi$ or $e$) which lack true measurement ($\pi$ and $e$ are irrational), but real-world usage require real value or approximations. Numerical methods help bridge that gap by giving us answers that are “close enough” to be practical.

Introduction to Numerical Methods for Root Finding

Two important thing to remember about numerical root finding is that,

1. In numerical root finding, we run an iterative process that approximates the root. In each iteration/step, we do some calculation and get close to the original root.
2. Since numerical root finding approximates the original root, there will be some error present in our approximation and in each iteration/step, we reduce this error and get a more accurate approximation.

Because we are dealing with approximations, it's crucial to understand the concept of convergence. A good root-finding method will converge towards the true root, meaning that with each iteration, the approximation gets progressively better. We continue this process until the change between successive approximations becomes sufficiently small, indicating that we are close enough to the actual root for our purposes.

Now, let's take a look at the Bisection Method, the simplest algorightm to find roots.

Bisection Method

Bisection Method is one of the easiest, reliable, begginer-friendly and convergence guarenteed method for finding roots of equations. It only works on continuous functions.

1. Define the function f(x) that you want to find the root of.

2. Input:
a - Start of the interval
b - End of the interval
tolerance - Acceptable error in the root value

3. Repeat until the width of the interval (b - a) is greater than tolerance:
a. Calculate the midpoint:
c = (a + b) / 2

b. Check if the function value at the midpoint is zero:
If f(c) == 0:
Return c (The exact root is found)

c. Narrow down the interval:
If f(a) * f(c) < 0:
The root is in the left half, so set b = c
Else:
The root is in the right half, so set a = c

4. When the interval is small enough:
Return (a + b) / 2 as the approximate root.

function bisectionMethod(a, b, tolerance) {
  while (b - a > tolerance) {
      let c = (a + b) / 2;
      if (f(c) === 0) {
          return c;
      }
      if (f(a) * f(c) < 0) {
          b = c;
      } else {
          a = c;
      }
  }
  return (a + b) / 2;
}
const f = (x) => x**5 - x**3 - 1/2 * x
const root = bisectionMethod(1, 2, 0.001)
console.log("Root: ", root)

Important Terms

• Continuous Function: A continuous function is a smooth curve with no breaks, jumps, or sudden changes. It means you can draw the function without lifting your pencil from the paper.

Below is a non-continuous function $\frac{1}{x}$, where Bisection Method won't work because for this function $x=0$ is undefined.

• Convergence/Converging/Converge: This means an algorithm steadily approaches the true solution, systematically reducing the gap between the current estimate and the exact answer. It's like getting closer to a target with each step, where the distance between your current position and the target keeps shrinking.
• Multiplicity: Multiplicity refers to how many times a root appears or touches the x-axis. A root with multiplicity 2 means the function just touches the x-axis without crossing it. Higher multiplicity means the function "lingers" near the x-axis more.

For example, $f(x) = (x-3)^2(x+1)$ has roots: $x=3$ with multiplicity 2 and $x=-1$ with multiplicity 1.

At $x = 3$, function touches x-axis gently. At $x = -1$, function crosses x-axis normally.

• Complex Plane: The complex plane is a 2D graph where real numbers $(\alpha)$ are plotted horizontally and imaginary numbers $(\beta i)$ vertically. Each point represents a complex number as a coordinate, with $\alpha$ representing the real part and $\beta$ the imaginary coefficient.
• Complex Conjugates: Complex conjugates are pairs of complex numbers that have the same real part but opposite imaginary parts. For example, 3 + 2i and 3 - 2i are complex conjugates: they're mirror images across the real axis.

Conclusion

Bisection Method is one of the easiest numerical methods. Understanding the core concepts and the implementation of this algorithm will help us get familiarized with the world of computational mathematics. The upcoming posts in this series will refer back to this post because this is one of the foudational algorithms in numerical analysis. So, if there's still any doubts or confusions, read the steps slowly and try to understand why each step was done, ask yourself, "If this step was not executed, how would it affect the end result?" and try to visualize using the graphs how each iteration depends on the previous iteration's data. This concludes the Bisection Method. In the next post, we will explore Newton-Raphson Method .