Numerical Methods Project: Root Finding Solver

This project is a Streamlit-based graphical user interface (GUI) application designed to solve non-linear equations by finding their roots using three fundamental numerical methods: Bisection, False Position, and Fixed Point Iteration.

The project was developed for the Numerical Methods course at the Faculty of Computer and Information Sciences at Ain Shams University, in collaboration with the University of East London

💻 Project Structure

The application is built using several Python modules:

File Name	Description
GUI.py	The main Streamlit application file. Handles user input, method selection, continuity checks, execution of methods, and visualization (graphs and tables).
BisectionMethod.py	Core implementation of the Bisection Method and the calculation of required iterations.
FalsePositionMethod.py	Core implementation of the False Position Method.
fixedpoint.py	Core implementation of the Fixed Point Iteration Method, including workability and convergence checks using sympy.

✨ Numerical Methods Implemented

1. Bisection Method

This method is a simple, robust bracketing method based on the Intermediate Value Theorem.

• Phases:
  • Function Conversion: The input string $f(x)$ is converted into a callable function using string_to_function (utilizing the math library and eval).
  • Workability (Existence Condition):
    • Checks that $f(a)$ and $f(b)$ have opposite signs (i.e., $f(a) \cdot f(b) < 0$). If the signs are equal, the method is "Not Workable".
    • Checks for continuity across the interval $[a, b]$ using sympy and numpy to detect issues like division by zero, $\log$ of negative numbers, infinities, and $\text{NaNs}$.
  • Convergence Test : If the function passes the workability condition, the Bisection method is guaranteed to converge ($\checkmark$).
  • Rate of Convergence: The required number of iterations ($N$) to achieve $d$ significant digits is calculated using the formula: $$\text{tol} = 0.5 \cdot 10^{-d} \text{ }$$ $$N = \max\left(0, \left\lceil\frac{\ln(|b-a|) - \ln(\text{tol})}{\ln(2)} - 1\right\rceil\right) \text{ }$$
  • Iterations: In each iteration, the midpoint $c$ and $f(c)$ are calculated, the relative error is determined, and the new interval $[a, b]$ is set based on the sign of $f(c)$.

2. False Position Method

This bracketing method uses linear interpolation to find the root approximation, often converging faster than the Bisection Method.

• Workability: The conditions are the same as the Bisection Method (opposite signs and continuity)

• Convergence Test: The method converges if the workability conditions are met.

• Root Calculation ($c$): The new approximation $c$ is calculated differently from the Bisection Method using the formula: $$c = b - \frac{f(b)(a-b)}{f(a)-f(b)}$$

• Rate of Convergence: Unlike the Bisection Method, the False Position method does not calculate the theoretical number of required iterations## 3. Fixed Point Iteration Method This method finds the root of the equation $x = g(x)$ by iterative substitution, $p_i = g(p_{i-1})$.

• Phases:

  • Workability (Existence Condition) : The user enters the function $g(x)$. The function checks if $g(a)$ and $g(b)$ both lie within the interval $[a, b]$, verifying $g([a,b]) \subseteq [a,b]$.
  • Convergence Test: Checks the condition $\max_{x \in [a,b]} |g'(x)| < 1$.
    • The derivative $g'(x)$ is calculated.
    • Rule Set:
      • If $|g'(a)| < 1$ and $|g'(b)| < 1 \rightarrow$ Convergence factor $k = \max(|g'(a)|, |g'(b)|)$.
      • If one is $< 1$ and the other $\ge 1 \rightarrow$ Convergence factor $k = \min(|g'(a)|, |g'(b)|)$ (Special Case).
      • If both are $\ge 1 \rightarrow$ Not convergent.
  • Rate of Convergence: The rate is calculated by comparing how much the error decreases from one iteration to the next: $$\text{ratio} = \frac{\text{error}}{\text{prev_error}} \text{ }$$ $$\text{where } \text{error} = |p_{\text{new}} - p_{\text{prev}}| \text{ }$$ The theoretical required iterations ($N$) can also be calculated using $k$: $$N \approx \frac{\log((b-a)/0.5) + d)}{\log(1/k)} \text{ }$$
  • Iterations: The iterations stop when the calculated absolute error is less than the tolerance ($\text{tol}$).

📊 Output and Visualization

The GUI provides comprehensive results for each method:

• Iteration Table: A Pandas DataFrame displaying the step-by-step history, including $n$, $a$, $b$, $c$ (or $p_{\text{new}}$), $f(c)$ (or $\text{Abs Error}$), and $\text{relative error}$.
• Relative Error Graph: Plots the Relative Error vs. Iteration Number on a logarithmic scale to show the convergence rate.
• Convergence Graph: Plots the Approximated Root $c$ vs. Iteration Number to visualize how the root settles.