CHAPTER 8

Numerical Algorithms: Equations, Derivatives, Integrals and Differential Equations

8.1 Solving Non-Linear Equations

MATLAB is able to implement a number of algorithms which provide numerical solutions to certain problems which play a central role in the solution of non-linear equations. Such algorithms are easy to construct in MATLAB and are stored as M-files. From previous chapters we know that an M-file is simply a sequence of MATLAB commands or functions that accept arguments and produces output. The M-files are created using the text editor.

8.1.1 The Fixed Point Method for Solving x = g(x)

The fixed point method solves the equation x = g(x), under certain conditions on the function g, using an iterative method that begins with an initial value p₀ (a first approximation to the solution) and defines p_k+1 = g(p_k). The fixed point theorem ensures that, in certain circumstances, this sequence will converges to a solution of the equation x = g(x). In practice the iterative process will stop when the absolute or relative error corresponding to two consecutive iterations is less than a preset value (tolerance). The smaller this value, the better the approximation to the solution of the equation.

This simple iterative method can be implemented using the M-file shown in Figure 8-1.

As an example we solve the following non-linear equation:

In order to apply the fixed point algorithm we write the equation in the form x = g(x) as follows:

We will start by finding an approximate solution which will be the first term p₀. To plot the x axis and the curve defined by the given equation on the same graph we use the following syntax (see Figure 8-2):

>> fplot ('[x-2^(-x), 0]',[0, 1])

The graph shows that one solution is close to x = 0.6. We can take this value as the initial value. We choose p₀ = 0.6. If we consider a tolerance of 0.0001 for a maximum of 1000 iterations, we can solve the problem once we have defined the function g(x) in the M-file g1.m (see Figure 8-3).

We can now solve the equation using the MATLAB syntax:

>> [k, p] = fixedpoint('g1',0.6,0.0001,1000)

k =

    10


p =

    0.6412

We obtain the solution x = 0.6412 at the 1000th iteration. To check if the solution is approximately correct, we must verify that g1(0.6412) is close to 0.6412.

>> g1 (0.6412)

ans =

    0.6412

Thus we observe that the solution is acceptable.

8.1.2 Newton’s Method for Solving the Equation f(x) = 0

Newton’s method (also called the Newton–Raphson method) for solving the equation f(x) = 0, under certain conditions on f, uses the iteration

for an initial value x₀ close to a solution.

The M-file in Figure 8-4 shows a program which solves equations by Newton’s method to a given precision.

As an example we solve the following equation by Newton’s method:

The function f (x) is defined in the M-file f1.m (see Figure 8-5), and its derivative f'(x) is given in the M-file derf1.m (see Figure 8-6).

We can now solve the equation up to an accuracy of 0.0001 and 0.000001 using the following MATLAB syntax, starting with an initial estimate of 1.5:

>> [x,it]=newton('f1','derf1',1.5,0.0001)

x =

1.6101


it =

2

>> [x,it]=newton('f1','derf1',1.5,0.000001)
x =

1.6100

it =

3

Thus we have obtained the solution x = 1.61 in just 2 iterations for a precision of 0.0001 and in just 3 iterations for a precision of 0.000001.

8.1.3 Schröder’s Method for Solving the Equation f(x)=0

Schröder's method, which is similar to Newton’s method, solves the equation f(x) = 0, under certain conditions on f, via the iteration

for an initial value x₀ close to a solution, and where m is the order of multiplicity of the solution being sought.

The M-file shown in Figure 8-7 gives the function that solves equations by Schröder's method to a given precision.

8.2 Systems of Non-Linear Equations

As for differential equations, it is possible to implement algorithms with MATLAB that solve systems of non-linear equations using classical iterative numerical methods.

Among a diverse collection of existing methods we will consider the Seidel and Newton–Raphson methods.

8.2.1 The Seidel Method

The Seidel method for solving systems of equations is a generalization of the fixed point iterative method for single equations.

In the case of a system of two equations x = g₁(x,y) and y = g₂(x,y) the terms of the iteration are defined as:

Similarly, in the case of a system of three equations x=g₁(x,y,z),

y = g₂(x,y,z) and z = g₃(x,y,z) the terms of the iteration are defined as:

p_k+₁= g₁(p_k,q_k,r_k),  q_k+₁= g₂(p_k,q_k,r₄) and r_k+₁= g₃(p_k,q_k,r₄).

The M-file shown in Figure 8-8 gives a function which solves systems of equations using Seidel’s method up to a specified accuracy.

8.2.2 The Newton-Raphson Method

The Newton–Raphson method for solving systems of equations is a generalization of Newton’s method for single equations.

The idea behind the algorithm is familiar. The solution of the system of non-linear equations F(X) = 0 is obtained by generating from an initial approximation P₀ a sequence of approximations P_k which converges to the solution. Figure 8-9 shows the M-file containing the function which solves systems of equations using the Newton–Raphson method up to a specified degree of accuracy.

As an example we solve the following system of equations by the Newton–Raphson method:

taking as an initial approximation to the solution P = [2 3].

We start by defining the system F(X) = 0 and its Jacobian matrix JF according to the M-files F.m and JF.m shown in Figures 8-10 and 8-11.

Then the system is solved with a tolerance of 0.00001 and with a maximum of 100 iterations using the following MATLAB syntax:

>> [P,it,absoluteerror]=raphson('F','JF',[2 3],0.00001,0.00001,100)

P =

1.9007 0.3112

it =

6

absoluteerror =

8. 8751e-006

The solution obtained in 6 iterations is x = 1.9007, y = 0.3112, with an absolute error of 8.8751e-006.

8.3 Interpolation Methods

There are many different methods available to find an interpolating polynomial that fits a given set of points in the best possible way.

Among the most common methods of interpolation, we have Lagrange polynomial interpolation, Newton polynomial interpolation and Chebyshev approximation.

8.3.1 Lagrange Polynomial Interpolation

The Lagrange interpolating polynomial which passes through the N+1 points (x_k y_k), k= 0,1,…, N, is defined as follows:

where:

The algorithm for obtaining P and L is easily implemented by the M-file shown in Figure 8-12.

As an example we find the Lagrange interpolating polynomial that passes through the points (2,3), (4,5), (6,5), (7,6), (8,8), (9,7).

We will simply use the following MATLAB syntax:

>> [F, L] = lagrange([2 4 6 7 8 9],[3 5 5 6 8 7])

C =

-0.0185 0.4857 -4.8125 22.2143 -46.6690 38.8000

L =

-0.0006 0.0202 -0.2708 1.7798 -5.7286 7.2000
0.0042 -0.1333 1.6458 -9.6667 26.3500 -25.2000
-0.0208 0.6250 -7.1458 38.3750 -94.8333 84.0000
0.0333 -0.9667 10.6667 -55.3333 132.8000 -115.2000
-0.0208 0.5833 -6.2292 31.4167 -73.7500 63.0000
0.0048 -0.1286 1.3333 -6.5714 15.1619 -12.8000

We can obtain the symbolic form of the polynomial whose coefficients are given by the vector C by using the following MATLAB command:

>> pretty(poly2sym(C))

   31     5    1093731338075689      4   77       3      311     2   19601
- ----   x  + -----------------     x  - ----    x  +    ---    x  - --------    x + 194/5
  1680         2251799813685248          16              14          420

8.3.2 Newton Polynomial Interpolation

The Newton interpolating polynomial that passes through the N+1 points (x_k y_k) = (x_k, f(x_k)), k= 0,1,…, N, is defined as follows:

where:

Obtaining the coefficients C of the interpolating polynomial and the divided difference table D is easily done via the M-file shown in Figure 8-13.

As an example we apply Newton’s method to the same interpolation problem solved by the Lagrange method in the previous section. We will use the following MATLAB syntax:

>> [C, D] = pnewton([2 4 6 7 8 9],[3 5 5 6 8 7])
C =
-0.0185 0.4857 - 4.8125 22.2143 - 46.6690 38.8000
D =
3.0000         0         0         0         0         0
5.0000    1.0000         0         0         0         0
5.0000         0       - 0.2500    0         0         0
6.0000    1.0000         0.3333    0.1167    0         0
8.0000    2.0000         0.5000    0.0417  - 0.0125    0
7.0000  - 1.0000       - 1.5000  - 0.6667  - 0.1417  - 0.0185

The interpolating polynomial in symbolic form is calculated as follows:

>> pretty(poly2sym(C))
    31     5  17   4   77   3   311    2   19601
- ----   x  + --  x  - --  x  + ---   x  - -----    x + 194/5
  1680        35       16       14          420

Observe that the results obtained by both interpolation methods are similar.

8.4 Numerical Derivation Methods

There are various different techniques available for numerical derivation. These are of great importance when developing algorithms to solve problems involving ordinary or partial differential equations.

Among the most common methods for numerical derivation are derivation using limits, derivation using extrapolation and derivation using interpolation on N-1 nodes.

8.4.1 Numerical Derivation via Limits

This method consists in building a sequence of numerical approximations to f' (x) via the generated sequence:

The iterations continue until |D_n+1−D_n|≥|D_n−D_n-1| or |D_n−D_n−1|< tolerance. This approach approximates f'(x) by D_n.

The algorithm to obtain the derivative D is easily implemented by the M-file shown in Figure 8-14.

As an example, we approximate the derivative of the function:

To begin we define the function f in an M-file named funcion (see Figure 8-15). (Note: we use funcion rather than function here since the latter is a protected term in MATLAB.)

The derivative is then given by the following MATLAB command:

>> [L, n] = derivedlim ('funcion', (1-sqrt (5)) / 2,0.01)

L =

1.0000 - 0.7448 0
0.1000 - 2.6045 1.8598
0.0100 - 2.6122 0.0077
0.0010 - 2.6122 0.0000
0.0001 - 2.6122 0.0000

n =
4

Thus we see that the approximate derivative is – 2.6122, which can be checked as follows:

>> f = diff ('sin (cos (x))')

f =

cos (cos (x)) * sin (x) / x ^ 2

>> subs (f, (1-sqrt (5)) / 2).

ans =

   -2.6122

8.4.2 Richardson’s Extrapolation Method

This method involves building numerical approximations to f'(x) via the construction of a table of values D(j, k) with k≤j that yield a final solution to the derivative f' (x) = D(n, n). The values D(j, k) form a lower triangular matrix, the first column of which is defined as:

and the remaining elements are defined by:

The corresponding algorithm for D is implemented by the M-file shown in Figure 8-16.

As an example, we approximate the derivative of the function:

As the M-file that defines the function f has already been defined in the previous section, we can find the approximate derivative using the MATLAB syntax:

>> [D, relativeerror, absoluteerror, n] = richardson ('funcion', (1-sqrt(5))/2,0.001,0.001)

D =

   -0.7448   0        0        0        0        0
   -1.1335 - 1.2631   0        0        0        0
   -2.3716 - 2.7843 - 2.8857   0        0        0
   -2.5947 - 2.6691 - 2.6614 - 2.6578   0        0
   -2.6107 - 2.6160 - 2.6125 - 2.6117 - 2.6115   0
   -2.6120 - 2.6124 - 2.6122 - 2.6122 - 2.6122 - 2.6122

relativeerror =

  6. 9003e-004

absoluteerror =

  2. 6419e-004

n =
6

Thus we get the same result as before when we used the limit method.

8.4.3 Derivation Using Interpolation (n + 1 Nodes)

This method consists in building the Newton interpolating polynomial of degree N:

and numerically approximating f'(x₀) by P'(x₀).

The algorithm for the derivative D is easily implemented by the M-file shown in Figure 8-17.

As an example, we approximate the derivative of the function:

As the M-file that defines the function f has already been constructed in the previous section, we can calculate the approximate derivative using the MATLAB command:

>> [A, df] = nodes([2 4 6 7 8 9],[3 5 5 6 8 7])

A =

3.0000  1.0000  - 0.2500  0.1167  - 0.0125  - 0.0185

df =
-1.4952

8.5 Numerical Integration Methods

Given the difficulty of obtaining an exact primitive for most functions, numerical integration methods are especially important. There are many different ways to numerically approximate definite integrals, among them the trapezium method, Simpson’s method and Romberg’s method (all implemented in MATLAB’s Basic module).

8.5.1 The Trapezium Method

The trapezium method for numerical integration has two variants: the trapezoidal rule and the recursive trapezoidal rule.

The trapezoidal rule approximates the definite integral of the function f(x) between a and b as follows:

calculating f(x) at equidistant points x_k = a+kh, k = 0,1,…, M where x₀= a and x_M = b.

The trapezoidal rule is implemented by the M-file shown in Figure 8-18.

The recursive trapezoidal rule considers the points x_k = a+kh, k = 0,1,…, M, where x₀ = a and x_M = b, dividing the interval [a, b] into 2J = M subintervals of the same size h =(b-a)/2J. We then consider the following recursive formula:

and the integral of the function f(x) between a and b can be calculated as:

using the trapezoidal rule as the number of sub-intervals [a, b] increases, taking at the J-th iteration a set of 2J+ 1 equally spaced points.

The recursive trapezoidal rule is implemented via the M-file shown in Figure 8-19.

As an example, we calculate the following integral using 100 iterations of the recursive trapezoidal rule:

We start by defining the integrand by means of the M-file integrand1.m shown in Figure 8-20.

We then calculate the requested integral as follows:

>> recursivetrapezoidal('integrand1',0,2,14)

ans =

Columns 1 through 4

10.24390243902439   6.03104212860310   4.65685845031979   4.47367657743630

Columns 5 through 8

4.47109102437123 4.47132194954670 4.47138003053334 4.47139455324593

Columns 9 through 12

4.47139818407829 4.47139909179602 4.47139931872606 4.47139937545860

Columns 13 through 15

4.47139938964175 4.47139939318754 4.47139939407398

This shows that after 14 iterations an accurate value for the integral is 4.47139939407398.

We calculate the same integral using the trapezoidal rule, using M = 14, using the following MATLAB command:

>> trapezoidalrule('integrand1',0,2,14)

ans =
4.47100414648074

The result is now the less accurate 4.47100414648074.

8.5.2 Simpson’s Method

Simpson’s method for numerical integration is generally considered in two variants: the simple Simpson’s rule and the composite Simpson's rule.

Simpson’s simple approximation of the definite integral of the function f(x) between the points a and b is the following:

This can be implemented using the M-file shown in Figure 8-21.

The composite Simpson's rule approximates the definite integral of the function f (x) between points a and b as follows:

calculating f(x) at equidistant points x_k = a+kh, k = 0, 1,…, 2_M, where x₀= a and x_2M = b.

The composite Simpson's rule is implemented using the M-file shown in Figure 8-22.

As an example, we calculate the following integral by the composite Simpson's rule taking M = 14:

We use the following syntax:

>> compositesimpson('integrand1',0,2,14)

ans =

   4.47139628125498

Next we calculate the same integral using the simple Simpson’s rule:

>> Z=simplesimpson('integrand2',0,2,0.0001)

Z =

Columns 1 through 4

0 2.00000000000000 4.62675535846268 4.62675535846268

Columns 5 through 6

0.00010000000000 0.00010000000000

As we see, the simple Simpson’s rule is less accurate than the composite rule.

In this case, we have previously defined the integrand in the M-file named integrand2.m (see Figure 8-23).

8.6 Ordinary Differential Equations

Obtaining exact solutions of ordinary differential equations is not a simple task. There are a number of different methods for obtaining approximate solutions of ordinary differential equations. These numerical methods include, among others, Euler’s method, Heun’s method, the Taylor series method, the Runge–Kutta method (implemented in MATLAB’s Basic module), the Adams–Bashforth–Moulton method, Milne’s method and Hamming’s method.

8.6.1 Euler’s Method

Suppose we want to solve the differential equation y' = f (t, y),  y(a)=y₀, on the interval [a, b]. We divide the interval [a, b] into M subintervals of the same size using the partition given by the points t_k = a+kh, k = 0,1,…, M, h = (b-a) /M. Euler’s method then finds the solution of the differential equation iteratively by calculating y_k+1 = y_k+hf(t_k, y_k),  k = 0,1, …, M-1.

Euler’s method is implemented using the M-file shown in Figure 8-24.

8.6.2 Heun’s Method

Suppose we want to solve the differential equation y' = f(t, y), y(a) = y₀, on the interval [a, b]. We divide the interval [a, b] into M subintervals of the same size using the partition given by the points t_k = a+kh, k = 0,1,…, M, h = (b-a) /M. Heun’s method then finds the solution of the differential equation iteratively by calculating y_{k + 1} = y_k+ h(f(t_k, y_k) + f(t_{k + 1}, y_k+ f(t_k, y_k))) / 2, k = 0,1,…, M-1.

Heun’s method is implemented using the M-file shown in Figure 8-25.

8.6.3 The Taylor Series Method

Suppose we want to solve the differential equation y' = f (t, y), y(a) = y₀, on the interval [a, b]. We divide the interval [a, b] into M subintervals of the same size using the partition given by the points t_k = a+kh, k = 0,1,…, M, h = (b-a) /M. The Taylor series method (let us consider here the method to order 4) finds a solution to the differential equation by evaluating y', y", y"' and y"" to give the 4th order Taylor series for y at each partition point.

The Taylor series method is implemented using the M-file shown in Figure 8-26.

As an example we solve the differential equation y'(t) = (t - y) / 2 on the interval [0,3], with y(0) = 1, using Euler’s method, Heun’s method and by the Taylor series method.

We will begin by defining the function f(t, y) via the M-file shown in Figure 8-27.

The solution of the equation using Euler’s method in 100 steps is calculated as follows:

>> E = euler('dif1',0,3,1,100)

E =

0 1.00000000000000
0.03000000000000 0.98500000000000
0.06000000000000 0.97067500000000
0.09000000000000 0.95701487500000
0.12000000000000 0.94400965187500
0.15000000000000 0.93164950709688
0.18000000000000 0.91992476449042
.
.
.
2.85000000000000 1.56377799005910
2.88000000000000 1.58307132020821
2.91000000000000 1.60252525040509
2.94000000000000 1.62213737164901
2.97000000000000 1.64190531107428
3.00000000000000 1.66182673140816

This solution can be graphed as follows (see Figure 8-28):

>> plot (E (:,2))

The solution of the equation by Heun’s method in 100 steps is calculated as follows:

>> H = heun('dif1',0,3,1,100)

H =

0 1.00000000000000
0.03000000000000 0.98533750000000
0.06000000000000 0.97133991296875
0.09000000000000 0.95799734001443
0.12000000000000 0.94530002961496
.
.
.
2.88000000000000 1.59082209379464
2.91000000000000 1.61023972987327
2.94000000000000 1.62981491089478
2.97000000000000 1.64954529140884
3.00000000000000 1.66942856088299

The solution using the Taylor series method requires the previously defined function df = [y' y'' y''' y''''] using the M-file shown in Figure 8-29.

The differential equation is solved by the Taylor series method via the command:

>> T = taylor('df',0,3,1,100)

T =
0 1.00000000000000
0.03000000000000 0.98533581882813
0.06000000000000 0.97133660068283
0.09000000000000 0.95799244555443
0.12000000000000 0.94529360082516
.
.
.
2.88000000000000 1.59078327648360
2.91000000000000 1.61020109213866
2.94000000000000 1.62977645599332
2.97000000000000 1.64950702246046
3.00000000000000 1.66939048087422