Introduction to Numerical Methods

Round-Off Errors

The error that is produced when a calculator or computer is used to perform real number calculations. Real numbers are typically represented in computers using floating-point form.

Machine Numbers

Represented in the normalized decimal floating-point form.

Aka. -digit decimal machine numbers. Any positive real number can be written in the above form.

Floating point form

Denoted as . Obtained by terminating the mantissa of at decimal digits. The termination can be done in 2 ways:

• chopping: chop off the digits to produce the floating-point form
• rounding: when , add to to obtain and then chop off all but the first k digits.

Measuring Errors

Suppose is an approximation of .

Absolute Error

Relative Error

Successive relative error

When is unknown and is found through iterations, the relative error can be used as:

Here means the -th approximation of .

Finite-Digit Arithmetic

Machine arithmetic are done on finite-digits and are not exact. Suppose are machine addition, subtraction, multiplication and division.

Due to this, the accuracy is lost to some extent. The accuracy can be increased by rearranging calculations.

Truncating Error

Occurs because of using approximation in place of an exact mathematical procedure. For example, the error due to the approximation of for the n-th term in its Taylor expansion.

Note

Taylor series is commonly used to approximate functions. The remainder term is also known as truncation error.

Suppose a function must be approximated at and it has an associated Taylor series. It’s preferred to have the Taylor series centered around a close point to , to decrease the error.

Algorithm

An algorithm is a set of well-defined instructions to solve a problem.

Stable

If a small change in the input causes a small change in the output, the algorithm is stable.

Unstable

When a algorithm is not stable.

Conditionally Stable

When an algorithm is stable only within a certain input range.

Growth of Error

Suppose denotes an error introduced in a calculation. represents the error after subsequent operations.

Linear growth

When and is a constant independent of .

Exponential growth

When for some .

Rate of convergence

A measure of how fast a sequence is converging.

Suppose converges to and converges to a number .

If such that,

Then we say that converges to with rate of (or order of) convergence . It is written as .

For limits

Suppose and .

If such that,

Then .

Numerical solution of non-linear equations

Non-linear function is a function whose graph is not a straight line.

In many situations, non-linear equations cannot be solved analytically. In that case, the solutions of the equations must be approached using iterative methods. The principle of these methods of solving consists in starting from an arbitrary point, the closest possible point to the solution sought, and involves arriving at the solution gradually through successive tests.

The 2 criteria to take into account when choosing a method for solving non-linear equations are:

• Method convergence (conditions of convergence, speed of convergence etc.).
• The cost of calculating of the method.