/Numerical-Analysis

A collection of Python programs that helps in Numerical Analysis.

Primary LanguagePython

Numerical Analysis Package

Currently working on hosting all these algorithms online in my web-app Numalyze.

This repository contains the Python implementation of the following method:

Please do note that your f(x) needs to be defined in the main part of the program. You will also need to specify the Tolerance level. Input handling hasn't been implemented yet.

  1. Reduced Row Echelon Form: Implemented here to avoid the use of Numpy library in Cubic Splines computation. Helps in keeping the app lightweight and minimizing dependencies.
  2. Finding the roots of a polynomial:
    • Bisection Method: Used to find the roots of a polynomial. Guaranteed to converge.
    • Fixed Point Iteration: x = g(x)
    • Newton-Raphson: The fastest converging method, with an order of 2. Need extra computation for the derivative and might fail when f'(x) = 0. Also added the modified Newton's method that uses the second derivative for computations, thereby possibly reducing the iterations needed for convergence.
    • Secant Method: Uses the same methodology of Newton's method, but without the need of calculating the derivative. Needs two point for manual slope calculation.
    • Müeller's Method: Faster than Secant method, slower than Newton's. The benefit of using this method is that it can find Complex Roots without the need of a derivative. But in order to do so, we need to have an idea of the curve on which our root lies and needs three points so it can plot a parabola passing through it.
  3. Accelerating techniques:
    • Aitken's Method: His method speeds up the convergence of any of the above methods by calculating 𝝙 after we have 3 points.
    • Steffensen's Method: A combination of Fixed-Point Iteration and the acceleration of Aitken's Method. Compute three points using Fixed-Point and apply Aitken's on those three to get another point. Then again perform Fixed-Point Iteration on it and profit.
  4. Interpolation:
    • Chebyshev's Interpolating Polynomial: Uses Chebyshev's Node to interpolate a given function by calculating the Divided Difference Table.
    • Cubic Spline Interpolation:There are two kinds of Cubic Splines:
      1. Natural Cubic Spline: The derivatives at the end-points are set to 0.
      2. Clamped Cubic Spline: The derivatives at the end-points are set to actual function's derivative at the end points.