Foundations of Numerical Methods — the Pythonic way

Background

While there are multiple numerical methods that are applied to a variety of problems, in this article, we focus on only a couple of them. The article has been written to help readers develop a good understanding of the numerical method, along with the implementation of the same in Python. For clarity, there are charts and figures included to help relate with the logic of a certain numerical method. Further, we have attempted to implement such methods in Python via two ways:

a. The hard way (i.e., pure Python approach)

b. Using a ready Python library

While most of the times on projects, we use ready libraries available in scripting tools, it’s always a good idea to explore the pure implementation of the same to get a good understanding of the logic behind a certain technique. Having clarity on the foundations of numerical methods also helps the user decide which method to use for which problem.

Root Finding Problem

For this exercise, we assume a certain polynomial equation and attempt to solve for its roots using a couple of numerical techniques and implement the same via Python. Further, we assume that the function is continuous and differentiable. Having a function that is free from discontinuities plays an important role in arriving at the roots.

Root finding exercise is a form of an approximation (i.e., it’s hard to find the exact value). Therefore, it is imperative that we define a certain upper and lower bounds for searching the root and also define a tolerance threshold that may be acceptable to us.

Numerical Method 1: Bisection Method

Assume that we have two points: j and k such that j < k and f(j) < 0 and f(k) > 0. Points j and k lie along the continuous function. We take a mid-point of j and k say m, such that m = (j+k)/2. The bisection method will evaluate the value f(m).

A general diagram for this method is as below:

The bisection method assumes that the root will lie somewhere between points j and k. We say this because we know that f(j) < 0 and f(k) > 0.

If we find f(m) = 0 OR very close to zero under a tolerance level then we say the root is found. If f(m) < 0 then we say that the root exists along the interval j and m otherwise on the interval m and k. On the second iteration of the method, m is replaced as either j or k, and the new shortened interval is used to evaluate the next value of m. This process of shrinking the interval continues until we find a root.

Advantages of the bisection method:

b. It does not require calculation of derivatives (this at times is an advantage because there are certain functions for which computing derivatives may be challenging).

Shortcomings of the bisection method:

b. If the interval j and k is very large it take longer to arrive at a solution.

Python implementation of the bisection method:

Using Pure Python:

Using SciPy

Numerical Method 2: Newton Raphson Method

x* = x — f(x)/f’(x)

The tangent line intersects the x axis as x* that results in y = 0. This can be considered like a Taylor series expansion about a certain point x* such that the new point x* = x + delta (x) gives

f(x* + delta(x)) = 0

The above process gets repeated until maximum iterations are completed or a result within tolerance threshold is reached.

A general diagram for this method is as below:

Advantages of the Newton Raphson method:

b. Well suited for smooth functions that are differentiable

Shortcomings of the Newton Raphson method:

b. It may not guarantee global convergence if there are multiple roots.

Python implementation of the Newton Raphson method:

Using Pure Python:

Using SciPy

Numerical Method 3: Secant Method

A secant line is drawn as y = f(b) — f(a) / (b-a) * (c-b) + f(b)

We get a solution to c

On the next iteration, the value is updated and we continue with the root finding exercise until solution converges. Or when maximum number of iterations are reached.

A general diagram for this method is as below:

Advantages of the Secant method:

b. Maybe faster because it requires computation of its function at each step

Shortcomings of the Secant method:

Python implementation of the Secant method:

Application to Finance

a. Implying bond yields when prices are given

b. Numerical optimization

c. Implied vol surface computations , and many more applications

Conclusion

--

--

Founder: FinQuest Institute | Ekspert Consulting; www.finquestinstitute.com; www.ekspertconsulting.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store