Compilations of Algorithms

Piere Carlo I. Dimalig

Engr. Irismay Jumawan

 TABLE OF CONTENTS

 Gauss Elimination Method

 Jacobi Methods
 Gauss-Seidel Method
 Fixed Point Iteration
 Newton Rahpson Method
 Secant Method
 Bisection Method
 Regula Falsi Method
 Least Square
 Euler’s Method
 Trapezoidal Rule
 Simpson’s Rule
 Runge Kutta Method
GAUSS ELIMINATION
Gaussian elimination is the name of the method we use to perform the three types of matrix
row operations on an augmented matrix coming from a linear system of equations in order to
find the solutions for such system. This technique is also called row reduction and it consists
of two stages: Forward elimination and back substitution.
The Gaussian elimination rules are the same as the rules for the three elementary row
operations, in other words, you can algebraically operate on the rows of a matrix in the next
three ways (or combination of):
1. Interchanging two rows
2. Multiplying a row by a constant (any constant which is not zero)
3. Adding a row to another row

EXAMPLE 1

GAUSS ELIMINATION

x+y+z=9
2x + 5y + 7z = 52
2x + y – z = 0

X Y Z C
1 1 1 9
2 5 7 52
2 1 1 0
2(R1)-R2
1 1 1 9
0 -3 -5 -34
2 1 1 0

2(R1)-R3 1 1 1 9
0 -3 -5 -34
0 1 1 18
3(R3)+R
2
1 1 1 9
0 -3 -5 -34
0 0 -2 20
 x+y+z=9
-3y-5z = -34
-2z = 20

x+y+z=9 x+y+z=9 -9 x=-9

-3y-5(-10)= -34 28 y=28
z = -10 z = -10 z=-10

CHECK
9
CHECK
S

EXAMPLE 2

GAUSSIAN ELIMINATION

X Y Z C
1 3 3 2
3 9 3 3
3 6 6 4
R2-R3
1 3 3 2
0 3 -3 -1
3 6 6 4
R3/3
1 3 3 2
0 3 -3 -1
1 2 2 (4/3)
R1-R3
1 3 3 2
0 3 -3 -1
0 1 1 (2/3)
3(R3)
1 3 3 2
0 3 -3 -1
0 3 3 2
R3-R2
1 3 3 2
0 3 -3 -1
0 0 6 3

x+3y+3z=2
3y-3z=-1
6z=3 z=1/2

3y-3(1/2)=-1 y=1/6

x+3(1/6)+3(1/2)=2 x=0
JACOBI METHOD
Given a current approximation
x(k) = (x1(k), x2(k), x3(k), …, xn(k))
for x, the strategy of Jacobi's Method is to use the first equation and the current values of
x2(k), x3(k), …, xn(k) to find a new value x1(k+1), and similarly to find a new value xi(k) using
the i th equation and the old values of the other variables. That is, given current values x(k) =
(x1(k), x2(k), …, xn(k)),
EXAMPLE 1

Jacobi method

5x-2y+3z=-1
-3x+9y+z=2
2x-y-7z=3

x=-1/5+2y/5-3z/5
y=2/9+x/3-z/9
z=-3/7+2x/7-y/7

k x y z
0 0 0 0
1 -0.200 0.222 -0.429
2 0.146 0.203 -0.517
3 0.192 0.328 -0.416
4 0.181 0.332 -0.421
5 0.185 0.329 -0.424
6 0.186 0.331 -0.423
7 0.186 0.331 -0.423
8 0.186 0.331 -0.423
9 0.186 0.331 -0.423

iteration
It converges at the 6th itteration
EXAMPLE 2
Jacobi Method

-5x-y+2z=1
2x+6y-3z=2
2x+y+7z=32

x=-1/5-y/5+2z/5
y=1/3-x/3+z/2
z=32/7-2x/7-y/7

k x y z
0 0 0 0
1 -0.20 0.33 4.57
2 1.56 2.69 4.58
3 1.10 2.10 3.74
4 0.88 1.84 3.96
5 1.02 2.02 4.06
6 1.02 2.02 3.99
7 0.99 1.99 3.99
8 1.00 2.00 4.00
9 1.00 2.00 4.00
10 1.00 2.00 4.00
11 1.00 2.00 4.00

It converges at the 8th itteration

GAUSS-SEIDEL METHOD
Gauss–Seidel method is an improved form of Jacobi method, also known as the successive
displacement method. The difference between the Gauss–Seidel and Jacobi methods is that
the Jacobi method uses the values obtained from the previous step while the Gauss–Seidel
method always applies the latest updated values during the iterative procedures
EXAMPLE 1

Gauss-Seidel Method

5x-2y+3z=-1
-3x+9y+z=2
2x-y-7z=3

x=-1/5+2y/5-3z/5
y=2/9+x/3-z/9
z=-3/7+2x/7-y/7

k x y z
0 0 0 0
1 -0.200 0.156 -0.508
2 0.167 0.334 -0.429
3 0.191 0.333 -0.422
4 0.186 0.331 -0.423
5 0.186 0.331 -0.423
6 0.186 0.331 -0.423

It converges at the 4th itteration

EXAMPLE 2
Gauss-Seidel Method

-5x-y+2z=1
2x+6y-3z=2
2x+y+7z=32

x=-1/5-y/5+2z/5
y=1/3-x/3+z/2
z=32/7-2x/7-y/7

k x y z
0 0 0 0
1 -0.20 0.40 4.57
2 1.55 2.10 3.83
3 0.91 1.94 4.03
4 1.02 2.01 3.99
5 0.99 2.00 4.00
6 1.00 2.00 4.00
7 1.00 2.00 4.00
8 1.00 2.00 4.00

It converges at the 6th iteration

FIXED POINT ITERATION

Fixed point iteration method is open and simple method for finding real root of non-linear
equation by successive approximation. It requires only one initial guess to start. Since it is
open method its convergence is not guaranteed. This method is also known as Iterative
Method
EXAMPLE 1
Fixed point itteration Relative error

Xnew=g(x) e%=(Xnew- Xol d)/(Xnew)

po=1.5
x^3+4x^2-10=0 iteration x g(x) x-g(x) e%
0 1.50000000 1.28695377 0.21304623
1 1.28695377 1.40254080 -0.11558704 -0.16554303
2 1.40254080 1.34545837 0.05708243 0.08241260
g(x)=(1/2)*(10-x^3)^1/2 3 1.34545837 1.37517025 -0.02971188 -0.04242601
4 1.37517025 1.36009419 0.01507606 0.02160596
5 1.36009419 1.36784697 -0.00775277 -0.01108457
6 1.36784697 1.36388700 0.00395996 0.00566787
7 1.36388700 1.36591673 -0.00202973 -0.00290344
8 1.36591673 1.36487822 0.00103852 0.00148598
9 1.36487822 1.36541006 -0.00053184 -0.00076089
10 1.36541006 1.36513782 0.00027224 0.00038951
11 1.36513782 1.36527721 -0.00013939 -0.00019942
12 1.36527721 1.36520585 0.00007136 0.00010209
13 1.36520585 1.36524238 -0.00003653 -0.00005227
14 1.36524238 1.36522368 0.00001870 0.00002676
15 1.36522368 1.36523326 -0.00000958 -0.00001370
16 1.36523326 1.36522835 0.00000490 0.00000701
17 1.36522835 1.36523086 -0.00000251 -0.00000359
18 1.36523086 1.36522958 0.00000128 0.00000184
19 1.36522958 1.36523024 -0.00000066 -0.00000094
20 1.36523024 1.36522990 0.00000034 0.00000048
21 1.36522990 1.36523007 -0.00000017 -0.00000025
22 1.36523007 1.36522998 0.00000009 0.00000013
23 1.36522998 1.36523003 -0.00000005 -0.00000006
24 1.36523003 1.36523001 0.00000002 0.00000003
25 1.36523001 1.36523002 -0.00000001 -0.00000002
26 1.36523002 1.36523001 0.00000001 0.00000001
Converges after 27 iterations 27 1.36523001 1.36523001 0.00000000 0.00000000
28 1.36523001 1.36523001 0.00000000 0.00000000
EXAMPLE 2

Fixed point itteration Relative error

Xnew=g(x) e%=(Xnew- Xold )/(Xnew)

po=1.5
x^3+4x^2-10=0 iteration x g(x) x-g(x) e%
0 1.5 1.3483997 0.1516003
1 1.3483997 1.3673764 -0.0189766 -0.1124298
2 1.3673764 1.3649570 0.0024194 0.0138781
g(x)=√10/(4+x) 3 1.3649570 1.3652647 -0.0003077 -0.0017725
4 1.3652647 1.3652256 0.0000392 0.0002254
5 1.3652256 1.3652306 -0.0000050 -0.0000287
6 1.3652306 1.3652299 0.0000006 0.0000036
7 1.3652299 1.3652300 -0.0000001 -0.0000005
8 1.3652300 1.3652300 0.0000000 0.0000001
Converges after 9 iterations 9 1.3652300 1.3652300 0.0000000 0.0000000
10 1.3652300 1.3652300 0.0000000 0.0000000
11 1.3652300 1.3652300 0.0000000 0.0000000
12 1.3652300 1.3652300 0.0000000 0.0000000
13 1.3652300 1.3652300 0.0000000 0.0000000
14 1.3652300 1.3652300 0.0000000 0.0000000
15 1.3652300 1.3652300 0.0000000 0.0000000
16 1.3652300 1.3652300 0.0000000 0.0000000
NEWTON RAPHSON
The Newton-Raphson method begins with an initial estimate of the root, denoted x0≠xr, and
uses the tangent of f(x) at x0 to improve on the estimate of the root. In particular, the
improvement, denoted x1, is obtained from determining where the line tangent to f(x) at x0
crosses the x-axis.
EXAMPLE 1
NEWTON RAPHSON

f(x)=x^3+4x^2-10 NEWTON RAPHSON RELATIVE ERROR (e%)

f'(x)=3x^2+8x Xnew= Xold- f(Xold)/f'(Xold) e%=(Xnew- Xold)/(Xnew

i x f(x) f’(x) e% x-f(x)

0 1 -5 11 6
1 1.454545455 1.5401953 17.9834711 0.3125 -0.085649887
2 1.368900401 0.0607197 16.5728681 -0.062564854 1.308180712
3 1.3652366 0.0001088 16.5135057 -0.002683638 1.36512783
4 1.365230013 3.512E-10 16.5133991 -4.82466E-06 1.365230013
5 1.365230013 0 16.5133991 -1.55797E-11 1.365230013
6 1.365230013 0 16.5133991 0 1.365230013
7 1.365230013 0 16.5133991 0 1.365230013
8 1.365230013 0 16.5133991 0 1.365230013
9 1.365230013 0 16.5133991 0 1.365230013

Using Po=1 as a starting approximation, it converges on the 6th iteration.

EXAMPLE 2
NEWTON RAPHSON

f(x)=x^2-9x+4 NEWTON RAPHSON RELATIVE ERROR (e%)

f'(x)=2x-9 Xnew= Xold- f(Xold)/f'(Xold) e%=(Xnew- Xold)/(Xnew

i x f(x) f’(x) e% x-f(x)

0 1 -4 -7 5
1 0.428571429 0.3265306 -8.1428571 -1.333333333 0.102040816
2 0.468671679 0.001608 -8.0626566 0.085561497 0.467063649
3 0.468871121 3.978E-08 -8.0622578 0.000425366 0.468871081
4 0.468871126 0 -8.0622577 1.05226E-08 0.468871126
5 0.468871126 0 -8.0622577 0 0.468871126
6 0.468871126 0 -8.0622577 0 0.468871126
7 0.468871126 0 -8.0622577 0 0.468871126

Using Po=1 as a starting approximation, it converges on the 5th iteration.

 SECANT METHOD
Secant method is also a recursive method for finding the root for the polynomials by successive approximation.
It’s similar to the Regular-falsi method but here we don’t need to check f(x1)f(x2)<0 again and again after every
approximation. In this method, the neighbourhoods roots are approximated by secant line or chord to the
function f(x). It’s also advantageous of this method that we don’t need to differentiate the given function f(x), as
we do in Newton-raphson method

EXAMPLE 1

SECANT METHOD
Xnew= {Xa- [f(Xa)*(Xa-Xb)]}/(f(Xa)-f(Xb))

f(x)=x^3-x+3
f'(x)=3x-1 RELATIVE ERROR (e%)

e%=(Xnew- Xold)/(Xnew)

i xa xb f(xa) f(xb) e%
0 -2 -1 -3 3
1 -1.0000 -1.5000 3.0000 1.1250 0.3333
2 -1.5000 -1.8000 1.1250 -1.0320 0.1667
3 -1.8000 -1.6565 -1.0320 0.1113 -0.0866
4 -1.6565 -1.6704 0.1113 0.0093 0.0084
5 -1.6704 -1.6717 0.0093 -0.0001 0.0008
6 -1.6717 -1.6717 -0.0001 0.0000 0.0000

Us i ng Xa =-1 a nd Xb=-2, the root of the equa ti on i s -1.672 where i t converges at the 6th i terati o

EXAMPLE 2
SECANT METHOD
Xnew= {Xa- [f(Xa)*(Xa-Xb)]}/(f(Xa)-f(Xb))

f(x)=x^5-5x+3
f'(x)=5x^4-5 RELATIVE ERROR (e%)

e%=(Xnew- Xold)/(Xnew)

i xa xb f(xa) f(xb) e%
1 1 2 -1 25
2 2.000 1.038 25.000 -0.985 -0.926
3 1.038 1.075 -0.985 -0.940 0.034
4 1.075 1.834 -0.940 14.590 0.414
5 1.834 1.121 14.590 -0.835 -0.636
6 1.121 1.159 -0.835 -0.702 0.033
7 1.159 1.363 -0.702 0.885 0.149
8 1.363 1.249 0.885 -0.203 -0.091
9 1.249 1.270 -0.203 -0.042 0.017
10 1.270 1.276 -0.042 0.003 0.004
11 1.276 1.276 0.003 0.000 0.000
12 1.276 1.276 0.000 0.000 0.000

Us i ng Xa=-1 a nd Xb=-2, the root of the equati on i s -1.672 where i t converges at the 6th i terati on.
BISECTION METHOD
The bisection method is used to find the roots of a polynomial equation. It separates the
interval and subdivides the interval in which the root of the equation lies. The principle
behind this method is the intermediate theorem for continuous functions. It works by
narrowing the gap between the positive and negative intervals until it closes in on the correct
answer. This method narrows the gap by taking the average of the positive and negative
intervals. It is a simple method and it is relatively slow. The bisection method is also known as
interval halving method, root-finding method, binary search method or dichotomy method.
EXAMPLE 1
BISECTION METHOD

midpoint (ck)= (ak+bk)/2

f(x)=x^3-(7/x)+2
interval 1.4,1.5

k left endpoint (ak) midpoint (ck) right endpoint (bk) f(ak) f(ck) f(bk)
1 1.400 1.450 1.500 -0.256 0.221 0.708
2 1.400 1.425 1.450 -0.256 -0.019 0.221
3 1.425 1.438 1.450 -0.019 0.101 0.221
4 1.425 1.431 1.438 -0.019 0.041 0.101
5 1.425 1.428 1.431 -0.019 0.011 0.041
6 1.425 1.427 1.428 -0.019 -0.004 0.011
7 1.427 1.427 1.428 -0.004 0.004 0.011
8 1.427 1.427 1.427 -0.004 0.000 0.004

Therefore, x=1.427

EXAMPLE 2
BISECTION METHOD

midpoint (ck)= (ak+bk)/2

f(x)=x^2-3
interval 1,4

k left endpoint (ak) midpoint (ck) right endpoint (bk) f(ak) f(ck) f(bk)
1 1.00 2.50 4.00 -2.00 3.25 13.00
2 1.00 1.75 2.50 -2.00 0.06 3.25
3 1.00 1.38 1.75 -2.00 -1.11 0.06
4 1.38 1.56 1.75 -1.11 -0.56 0.06
5 1.56 1.66 1.75 -0.56 -0.26 0.06
6 1.66 1.70 1.75 -0.26 -0.10 0.06
7 1.70 1.73 1.75 -0.10 -0.02 0.06
8 1.73 1.74 1.75 -0.02 0.02 0.06
9 1.73 1.73 1.74 -0.02 0.00 0.02

Therefore, x=1.73
REGULA FALSI METHOD
Regula Falsi method or the method of false position is a numerical method for solving an
equation in one unknown. It is quite similar to bisection method algorithm and is one of the
oldest approaches. It was developed because the bisection method converges at a fairly slow
speed. In simple terms, the method is the trial and error technique of using test ("false")
values for the variable and then adjusting the test value according to the outcome.

EXAMPLE 1
REGULA FALSI METHOD

f(x)=x^3-(7/x)+2
ck=bk-((fbk*(bk-ak)/(fbk-fak)))
interval 1.4,1.5

k LOWER GUESS (ak) (ck) UPPER GUESS (bk) f(ak) f(ck) f(bk)
1 1.400000 1.426547 1.500000 -0.256000 -0.003880 0.708333
2 1.426547 1.426947 1.500000 -0.003880 -0.000060 0.708333
3 1.426947 1.426953 1.500000 -0.000060 -0.000001 0.708333
4 1.426953 1.426953 1.500000 -0.000001 0.000000 0.708333

Therefore,
x=1.426953

EXAMPLE 2
REGULA FALSI METHOD

f(x)=x^2-3 interval
ck=bk-((fbk*(bk-ak)/(fbk-fak)))
1,4

k LOWER GUESS (ak) (ck) UPPER GUESS (bk) f(ak) f(ck) f(bk)
1 1.000 1.400 4.000 -2.000 -1.040 13.000
2 1.400 1.593 4.000 -1.040 -0.464 13.000
3 1.593 1.675 4.000 -0.464 -0.193 13.000
4 1.675 1.709 4.000 -0.193 -0.078 13.000
5 1.709 1.723 4.000 -0.078 -0.031 13.000
6 1.723 1.728 4.000 -0.031 -0.012 13.000
7 1.728 1.731 4.000 -0.012 -0.005 13.000
8 1.731 1.731 4.000 -0.005 -0.002 13.000
9 1.731 1.732 4.000 -0.002 -0.001 13.000
10 1.732 1.732 4.000 -0.001 0.000 13.000

Therefore, x=1.732
LEAST SQUARE
The least square method is the process of finding the best-fitting curve or line of best fit for a set of data points
by reducing the sum of the squares of the offsets (residual part) of the points from the curve. During the process
of finding the relation between two variables, the trend of outcomes are estimated quantitatively. This process
is termed as regression analysis. The method of curve fitting is an approach to regression analysis. This method
of fitting equations which approximates the curves to given raw data is the least squares.

EXAMPLE 1
LEAST SQUARE

X Y (Xk)^2 Xk(Yk)
15 30 225 450
25 75 625 1875
35 380 1225 13300
45 550 2025 24750
55 610 3025 33550
65 1220 4225 79300
75 830 5625 62250 Y=A+Bx
85 1450 7225.000 123250.000 Y=-327.819+19.425x
95 1520 9025.000 144400.000
SUM 495 6665 33225 483125

N 9
A -327.819444
B 19.425

EXAMPLE 2
LEAST SQUARE

X Y (Xk)^2 Xk(Yk)
2 25 4 50
4 70 16 280
6 380 36 2280
8 550 64 4400
10 610 100 6100
12 1220 144 14640
14 830 196 11620 Y=A+Bx
16 1450 256.000 23200.000 Y=-234.722+97.416x
18 1520 324.000 27360.000
SUM 90 6655 1140 89930

N 9
A -234.722222
B 97.41666667
EULER’S METHOD
The simplest numerical method for solving Equation \ref{eq:3.1.1} is Euler’s method. This
method is so crude that it is seldom used in practice; however, its simplicity makes it useful
for illustrative purposes. Euler’s method is based on the assumption that the tangent line to
the integral curve of Equation.
EXAMPLE 1

EULER'S METHOD

x0 = 0 y0 = 2 h= 0.2
x(n) y(n) f(x(n),y(n))y(n+1)=y(n) + h*f(x(n),y(n))
0 2 0 2
0.2 2 0.8 2.16
0.4 2.16 1.728 2.5056
0.6 2.5056 3.00672 3.106944
0.8 3.106944 4.97111 4.101166
1 4.101166 8.202332 5.741633
1.2 5.741633 13.77992 8.497616
1.4 8.497616 23.79333 13.25628
1.6 13.25628 42.4201 21.7403
1.8 21.7403 78.26508 37.39332
2 37.39332 149.5733 67.30797
2.2 67.30797 296.1551 126.539
2.4 126.539 607.3871 248.0164
2.6 248.0164 1289.685 505.9535
2.8 505.9535 2833.34 1072.621
3 1072.621 6435.728 2359.767
3.2 2359.767 15102.51 5380.269
3.4 5380.269 36585.83 12697.43
3.6 12697.43 91421.53 30981.74
3.8 30981.74 235461.2 78073.99
4 78073.99 624591.9 202992.4
TRAPEZOIDAL RULE
In Calculus, “Trapezoidal Rule” is one of the important integration rules. The name
trapezoidal is because when the area under the curve is evaluated, then the total area is
divided into small trapezoids instead of rectangles. This rule is used for approximating the
definite integrals where it uses the linear approximations of the functions.

The trapezoidal rule is mostly used in the numerical analysis process. To evaluate the definite
integrals, we can also use Riemann Sums, where we use small rectangles to evaluate the area
under the curve.
EXAMPLE 1
TRAPEZOIDAL RULE

LIMITS 0 TO 1
NO. OF SEGMENTS 20
h 0.05

x^3-7x+2

x^3 x constant
1 -7 2

SEGMENT x f(x) (h/2)*(fx0+fx1)

0 2
1 0.05 1.650125 0.091253125
2 0.1 1.301 0.073778125
3 0.15 0.953375 0.056359375
4 0.2 0.608 0.039034375
5 0.25 0.265625 0.021840625
6 0.3 -0.073 0.004815625
7 0.35 -0.407125 -0.012003125
8 0.4 -0.736 -0.028578125
9 0.45 -1.058875 -0.044871875
10 0.5 -1.375 -0.060846875
11 0.55 -1.683625 -0.076465625
12 0.6 -1.984 -0.091690625
13 0.65 -2.275375 -0.106484375
14 0.7 -2.557 -0.120809375
15 0.75 -2.828125 -0.134628125
16 0.8 -3.088 -0.147903125
17 0.85 -3.335875 -0.160596875
18 0.9 -3.571 -0.172671875
19 0.95 -3.792625 -0.184090625
20 1 -4 -0.194815625

ANSWER -1.249375
SIMPSON’S RULE
Simpson’s rule is one of the numerical methods which is used to evaluate the definite
integral. Usually, to find the definite integral, we use the fundamental theorem of calculus,
where we have to apply the antiderivative techniques of integration.
EXAMPLE 1

SIMPSON'S RULE

x^3-7x+2
Simpson=(h/3)*(f1+4*f2+f3)
h = 0.2

x^3 x constant
1 -7 2

x f(x) Simpson
0 2
0.2 0.608
0.4 -0.736 0.2464
0.6 -1.984
0.8 -3.088
1 -4 -1.2224
1.2 -4.672
1.4 -5.056
1.6 -5.104 -2
1.8 -4.768
2 -4
2.2 -2.752 -1.568
2.4 -0.976
2.6 1.376
2.8 4.352 0.592

ANSWER -3.952
RUNGE KUTTA METHOD
Runge–Kutta method is an effective and widely used method for solving the initial-value
problems of differential equations. Runge–Kutta method can be used to construct high order
accurate numerical method by functions' self without needing the high order derivatives of
functions.
EXAMPLE 1
RUNGE KUTTA METHOD

y'=6xy h=0.1
y(1.5)=?

y x h k1 k2 k3 k4
1 1 0.1 6 8.19 8.87985 12.460701
1.87667335 1.1 0.1 12.38604411 17.22223133 18.89071592 27.11336359
3.73876172 1.2 0.1 26.91908439 38.13536955 42.34147648 62.18869307
7.906452879 1.3 0.1 61.67033245 89.01875296 100.0948633 150.4938893
17.74631045 1.4 0.1 149.0690078 219.2379193 249.7613958 384.5020503
42.27247192 1.5 0.1 380.4522473 570.0442838 658.2045808 1037.692128