A system of linear equations

The most common mathematical component that arises in most applications of scientific computing and applied mathematics is the system of linear algebraic equations. Generally, this system may occur due to approximations of nonlinear equations by linear equations or differential equations by algebraic equations.

A system of linear equations is a collection of simultaneous linear equations involving a set of variables, like this for example:

2 x1  +  1 x2  + 1 x3  =  1
1 x1   -  2 x2  - 1 x3  =  2
1 x1  +  1 x2  + 2 x3  =  2

This is a system of three linear equations with three unknown variables: x1, x2, and x3. A solution for this system is the assignment of numbers to these unknown variables such that the values satisfy all three equations simultaneously. The solution for these equations is shown as follows:

x1  =  (1/2)
x2  =  (-3/2)
x3  =  (3/2)

This solution satisfies all three equations. This is why we call these linear equations a system of linear equations—the equations are supposed to be considered as a system rather than individual equations. Generally, iterative methods are methods that require repetition of steps to compute the solution. In programming, this repetition is performed using any of the available loops. On the other hand, a non-iterative method uses computational formulas to find the solution. There is a wide variety of methods of solving systems of linear equations. There are iterative and non-iterative methods. For example, the Gaussian LU-factorization method and elimination method are two examples of non-iterative methods. The Jacobi iteration method and the Gauss-Seidel iteration method are two popular iterative methods.

A system of nonlinear equations

A nonlinear system of equations is a set of simultaneous equations in which the unknown variables appear as polynomials of degree higher than 1. The system can be single-dimensional or multi-dimensional. Generally, a linear equation is of the following form. For a given function f, we need to find the value x for which this condition is true:

f(x) = 0

This value of x is called the root or zero of the equation.

There are two different cases when solving linear equations, as follows. In the first case, there is a single nonlinear equation with one variable:

f: RàR (scalar)

The solution for such equation is a scalar x for which f(x) = 0. The second case is a system of n nonlinear equations with n unknown variables:

f: Rn à Rn (vector)

The solution for such types of equations is a vector x for which all components of the function f are simultaneously zero for all f(x) = 0.

For example, a one-dimensional nonlinear equation is as follows:

3x + sin(x) -ex = 0

Its approximate solution up to two decimal digits is 0.36. An example of a system of nonlinear equations in two dimensions is given here:

3-x2=y
x+1=y

The solution vectors for the preceding system are [1, 2] and [-2, -1].

There are a number of methods of solving nonlinear equations and systems of nonlinear equations. For one-dimensional equations, the methods are listed as follows:

Similarly, for a system of nonlinear equations, again we have a number of methods, as follows:

As these methods are iterative methods, their rate of convergence is an important property to be observed. By convergence, we mean that these methods start with an approximate solution and proceed towards obtaining the exact solution. The speed of converging towards a solution is known as the rate of convergence. A faster converging method is better for obtaining the exact solution as it will take less time. For some faster methods, such as Newton's method, choosing the initial approximation is an important step. There is always a possibility that some methods may not converge to the solution if their initial approximation is not close enough to the solution. There are some hybrid methods as a trade-off between performance and guaranteed solution; the damped Newton's method is an example of such a method. The SciPy package has implementations of a number of methods for solving systems of nonlinear equations. You can refer to the http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.optimize.newton.html to get more information about the Newton-Raphson method and its implementation.

Optimization

Optimization is the process of trying to obtain the best possible solution. Generally, it will be the solution that has the maximum or minimum values among all. For example, if we need to know the cost of any project an organization is working on, then the option that gives minimum cost will be the optimized option. Similarly, if the comparison is among various sales strategies, then the strategy that produces maximum profit will be the optimized option. SciPy has a package for optimization techniques. You can refer to http://docs.scipy.org/doc/scipy/reference/optimize.html for more details and the implementation of these methods. Optimization has applications in various science and engineering domains. Some of these are as follows:

Interpolation

In science and engineering domains, users have a number of data points obtained from sampling or some experimentation. These data points represent the values of a function for particular values of the independent variable. Now, it is often a requirement to estimate the value of this function for the remaining points within the range. This process of estimation is called interpolation. It may be achieved by curve fitting or regression analysis.

For example, consider the following values of an independent variable x and the corresponding values of the function f:

x  4  5   6  7  8  9  10
f(x)  48   75  108  147  192  243  300

Using the interpolation methods, we can estimate the value of this function for other values of the variable, such as x=7.5, that is, f(7.5) or f(5.25). Although the function given in the preceding example is very simple (f(x) = 3x2), it may be any function from real-life examples. For example, this function may be the temperature reading of a server room of an Internet data center of an e-commerce organization. These temperature readings may be taken at some different points in time. The time for a temperature reading may be a fixed time interval between two readings, or it may be completely random. In this example, the function is the temperature of the server room for discrete values of independent, variable time. We need to estimate, or interpolate, the temperature for the remaining time of the day.

Another example can be as follows: the function is the average number of hours in a day that the users under study invest/waste in using Facebook or WhatsApp based on age. Based on this data, we can estimate the number of hours of Facebook or WhatsApp usage by users of some age other than the age in the data points.

Extrapolation

Another closely related problem is extrapolation. As the name suggests, it is the extension of interpolation for an estimation beyond the range of values of the independent variable. For example, if we have been given the values of the number of hours of Facebook/WhatsApp usage for the values of ages of users from 12 years to 65 years, then the problem of estimating the number of hours spent by users who are less than 12 years old and more than 65 years old comes under the scope of extrapolation. This is because it is beyond the range of the given data points of independent variables.

We have a number of methods available for both interpolation and extrapolation. The following are the names of some methods of interpolation:

The followings are some methods of extrapolation:

Numerical integration

Numerical integration is the process of approximating the values of an integral using any numerical techniques. The numerical computation of an integral is also called a quadrature. We need to approximate numerical integration as there are some functions that cannot be analytically integrated. Even if a formula exists, it may not be the most efficient way of calculating the integral. In some situations, we are supposed to integrate an unknown function for which only some samples of the function are known. Using numerical integration, we approximate the values of the definite integrals. This is also based on polynomial fitting through a specified set of points and then integrating the approximating function. In Python, the SciPy package has a module for integration. For details about the integration module and its implementation, refer to http://docs.scipy.org/doc/scipy/reference/integrate.html. There are a number of methods of solving numerical integration, as follows:

Numerical differentiation

Numerical differentiation is the process of estimating the derivative of a function using the known values of the function. It is highly useful in several situations. Generally, there are situations wherein we are not well aware whether an underlying function exists or not and we only have a discrete dataset. In such situations, users are interested in studying changes in the data that are related to the derivatives. Sometimes, for the sake of performance and simplicity, we prefer to approximate the derivative instead of computing its exact value, as the exact formulas are available but they are very complicated to solve. Differentiation is frequently used to solve optimization problems. Machine learning techniques also depend on numerical differentiation most of the time.

The methods of numerical differentiation are as follows:

Differential equations

A differential equation is a mathematical equation that can relate a function to its derivative. The function represents a physical quantity, the derivative corresponds to the rate of change of this quantity, and the equation is the relationship between the two. For example, the motion of a freely falling object under the force of gravity is generally represented using a set of differential equations. Differential equations have applications in a wide range of fields, including pure and applied mathematics, physics, engineering, and other subjects. Mainly, these subjects are concerned with various types of differential equations.

Differential equations are mainly used to model every physical, technical, and biological process. In many situations, differential equations may not be directly solvable. Hence, the solutions should be approximated using numerical methods. Most fundamental laws of physics (for example, Newton's second law and Einstein's field equations) and chemistry, such as the rate law or rate equation, have been formulated as differential equations. Differential equations have been used to model the behavior of complex systems in biology (for example, biological population growth) and economics (for example, the simple exponential growth model).

Differential equations can be categorized into two types: ordinary differential equations (ODE) and partial differential equations (PDE). An ODE is an equation that contains a function of one independent variable and its derivatives. On the other hand, a PDE contains functions of multiple independent variables and their partial derivatives. The partial derivative of a function with multiple variables is the derivative of this function with respect to one of the variables. You may refer to http://docs.scipy.org/doc/scipy-0.13.0/reference/generated/scipy.integrate.ode.html for the conceptual details and implementation of these methods in SciPy.

Various methods of solving ODEs are as follows:

The followings are some methods used to solve PDEs:

Random number generator

In computation, the random number generator is an algorithm or process that generates a sequence of numbers that doesn't follow any pattern, which is why they are called random numbers. It is almost impossible to predict the number to be generated. The number of applications using random numbers is increasing day by day, and so it has led to the development of many methods for random number generation. This concept has been used for a long time, such as using dice, coin flipping, using playing cards, and many more methods. However, these methods have limited values for random numbers.

Computational methods of random number generation soon became popular for a wide variety of applications, such as statistical sampling, gambling, designing for random design generation, computerized simulation of various science and engineering concepts, and a number of other areas that demand unpredictable results, such as cryptography.

There are two main categories of random number generators, namely true random number generators and pseudo-random number generators. A true random number generator uses some physical phenomenon to generate a random number, for example, the actual read or write time taken by hard disk, whereas a pseudo-random number generator uses a computational algorithm for random number generation. There is also a third category of random number generators. They are based on statistical distributions, such as Poison distribution, exponential distribution, normal distribution, Gaussian distribution, and many more.

Various pseudo-random number generators are as follows: