Numerical methods are techniques used to solve mathematical problems numerically, i.e., using numbers and algorithms rather than symbolic manipulations. In this section, we will explore how to implement some basic numerical methods in ALGOL. This will include root-finding algorithms, numerical integration, and solving differential equations.
Key Concepts
- Root-Finding Algorithms: Methods to find the roots of equations.
- Numerical Integration: Techniques to approximate the integral of a function.
- Solving Differential Equations: Methods to find numerical solutions to differential equations.
Root-Finding Algorithms
Bisection Method
The Bisection Method is a simple and robust root-finding algorithm that works by repeatedly dividing an interval in half and selecting the subinterval in which a root must lie.
Algorithm Steps:
- Choose initial interval \([a, b]\) such that \(f(a) \cdot f(b) < 0\).
- Compute the midpoint \(c = \frac{a + b}{2}\).
- Check the sign of \(f(c)\):
- If \(f(c) = 0\), then \(c\) is the root.
- If \(f(a) \cdot f(c) < 0\), set \(b = c\).
- Otherwise, set \(a = c\).
- Repeat steps 2-3 until the interval is sufficiently small.
Example Code:
begin
real procedure f(x);
value x;
real x;
f := x * x - 2; ! Example function: f(x) = x^2 - 2
real procedure bisection(a, b, tol);
value a, b, tol;
real a, b, tol;
real c;
while abs(b - a) > tol do
begin
c := (a + b) / 2;
if f(c) = 0 then
return c;
else if f(a) * f(c) < 0 then
b := c;
else
a := c;
end;
return (a + b) / 2;
end;
real root;
root := bisection(1.0, 2.0, 0.0001);
print("Root: ", root);
end;Explanation:
- The function
f(x)defines the equation \(x^2 - 2 = 0\). - The
bisectionprocedure implements the Bisection Method. - The
whileloop continues until the interval \([a, b]\) is smaller than the tolerancetol. - The midpoint
cis calculated and checked if it is the root. - Depending on the sign of
f(c), the interval is updated. - Finally, the root is printed.
Numerical Integration
Trapezoidal Rule
The Trapezoidal Rule is a numerical integration method that approximates the integral of a function by dividing the area under the curve into trapezoids.
Algorithm Steps:
- Divide the interval \([a, b]\) into \(n\) subintervals of equal width \(h = \frac{b - a}{n}\).
- Compute the sum of the areas of the trapezoids.
Example Code:
begin
real procedure f(x);
value x;
real x;
f := x * x; ! Example function: f(x) = x^2
real procedure trapezoidal(a, b, n);
value a, b, n;
real a, b;
integer n;
real h, sum;
integer i;
h := (b - a) / n;
sum := (f(a) + f(b)) / 2;
for i := 1 step 1 until n - 1 do
sum := sum + f(a + i * h);
return h * sum;
end;
real integral;
integral := trapezoidal(0.0, 1.0, 100);
print("Integral: ", integral);
end;Explanation:
- The function
f(x)defines the equation \(x^2\). - The
trapezoidalprocedure implements the Trapezoidal Rule. - The interval \([a, b]\) is divided into
nsubintervals. - The sum of the areas of the trapezoids is calculated and returned.
- Finally, the integral is printed.
Solving Differential Equations
Euler's Method
Euler's Method is a simple numerical method for solving ordinary differential equations (ODEs) with a given initial value.
Algorithm Steps:
- Start with the initial value \((x_0, y_0)\).
- Compute the next value using \(y_{n+1} = y_n + h \cdot f(x_n, y_n)\).
- Repeat for the desired number of steps.
Example Code:
begin
real procedure f(x, y);
value x, y;
real x, y;
f := x + y; ! Example differential equation: dy/dx = x + y
real procedure euler(x0, y0, h, steps);
value x0, y0, h;
real x0, y0, h;
integer steps;
real x, y;
integer i;
x := x0;
y := y0;
for i := 1 step 1 until steps do
begin
y := y + h * f(x, y);
x := x + h;
end;
return y;
end;
real solution;
solution := euler(0.0, 1.0, 0.1, 10);
print("Solution: ", solution);
end;Explanation:
- The function
f(x, y)defines the differential equation \(\frac{dy}{dx} = x + y\). - The
eulerprocedure implements Euler's Method. - The initial values \((x_0, y_0)\) and step size
hare used to compute the solution. - The loop iterates for the given number of steps, updating
xandyat each step. - Finally, the solution is printed.
Practical Exercises
Exercise 1: Implement the Secant Method
The Secant Method is another root-finding algorithm that uses two initial approximations to find the root.
Steps:
- Choose two initial approximations \(x_0\) and \(x_1\).
- Compute the next approximation using \(x_{n+1} = x_n - \frac{f(x_n) \cdot (x_n - x_{n-1})}{f(x_n) - f(x_{n-1})}\).
- Repeat until the difference between successive approximations is smaller than a given tolerance.
Solution:
begin
real procedure f(x);
value x;
real x;
f := x * x - 2; ! Example function: f(x) = x^2 - 2
real procedure secant(x0, x1, tol);
value x0, x1, tol;
real x0, x1, tol;
real x2;
while abs(x1 - x0) > tol do
begin
x2 := x1 - f(x1) * (x1 - x0) / (f(x1) - f(x0));
x0 := x1;
x1 := x2;
end;
return x1;
end;
real root;
root := secant(1.0, 2.0, 0.0001);
print("Root: ", root);
end;Exercise 2: Implement Simpson's Rule for Numerical Integration
Simpson's Rule is a more accurate numerical integration method that approximates the integral using parabolic segments.
Steps:
- Divide the interval \([a, b]\) into an even number of subintervals \(n\).
- Compute the sum of the areas of the parabolic segments.
Solution:
begin
real procedure f(x);
value x;
real x;
f := x * x; ! Example function: f(x) = x^2
real procedure simpson(a, b, n);
value a, b, n;
real a, b;
integer n;
real h, sum;
integer i;
h := (b - a) / n;
sum := f(a) + f(b);
for i := 1 step 2 until n - 1 do
sum := sum + 4 * f(a + i * h);
for i := 2 step 2 until n - 2 do
sum := sum + 2 * f(a + i * h);
return h * sum / 3;
end;
real integral;
integral := simpson(0.0, 1.0, 100);
print("Integral: ", integral);
end;Conclusion
In this section, we have explored some fundamental numerical methods in ALGOL, including root-finding algorithms, numerical integration, and solving differential equations. These methods are essential tools for solving mathematical problems that cannot be addressed analytically. By practicing these techniques, you will gain a deeper understanding of numerical computation and its applications in programming.