numerical-analysis-algorithms

Some numerical analysis algorithms, written from scratch in Octave.

Contents

Root finding in continuous non linear functions

• bisection.m a bisection method implementation. The bisection method converges lineary.

• newton_raphson.m an implementation of the Newton-Ramphson's method. The Newton-Raphson's method converges quadraticly, if certain criteria are met.

• b_nr.m a combination of the Newton-Raphson's method. The algorithm, intilally, finds a solution using the Newton-Raphson's method (which is a heavy computational task) and then enchanches the solution's estimation using (the much simpler) bisection method.

Linear algebra methods

• gauss_partial_pivoting.m an implementaion of the Gauss elimination using partial pivoting in order to avoid rounding errors.

• gaussian_solve.m after using the gauss_partial_pivoting to transform a matrix in an upper triangular, you may use this method to solve the linear system.

• gaussina_inv.m this algorithm uses the gauss_partial_pivoting and the gaussian_solve methods to calculate the invert of a given matrix.

Ιnterpolation

• @newton_dd_interpolation a class implementing Newton's interpolation method, using divided differences. The class provides the method @newton_dd_interpolation/estimate.m to estimate the value of a function in a given point. To calculate the divided differences, we use the algorithm divided_differences.m. Also the user may add a new known point of the estimated function via the classes method @newton_dd_interpolation/add_point.m. In order to recalculate the interpolation polynomial more efficiently, we use the divided_differences_incrimental.m.

• @newton_fd_interpolation a class implementing Newton's interpolation method, using forward differences. The class provides the method @newton_fd_interpolation/estimate.m to estimate the value of a function in a given point. To calculate the divided differences, we use the algorithm forward_differences.m. Also the user may add a new known point of the estimated function via the classes method @newton_fd_interpolation/add_point.m. In order to recalculate the interpolation polynomial more efficiently, we use the forward_differences_incrimental.m.

Eigenvalues

• power_iteration.m an implemantation of the power iteration method for finding the greatest (in absolute value) eigenvalue. The user may use different iteration steps to calculate the gretest eigenvalue:

  • modified step: uses the supremum norm to normalize the eigen vector in each step.

  • reyleigh step: uses the euclidean norm to normalize the eigen vector in each step. This method makes use of the Rayleigh quotient.

  • aitikens step: uses the modified step above, but also makes use of the Aitiken's delta-squared process for accelerating the rate of convergence.

  The preffered variant of the algorithm is passed as last parameter. The default iteration step is the modified step.

Numerical quadrature (integration)

• midpoint_integral.m an implementation of the midpoint rule.

• simpsons_integral.m an implementation of the Simpson's rule.

• trapezodial_integral.m an implementation of the trapezoidal rule.

All the functions above for numerical quadrature are using the method split_intertval.m as helper function.

Notes

The code above has been tested in GNU Octave, version 5.1.0.