BSc CSIT (TU) Science Numerical Method (BSc CSIT, CSC207) Question Paper 2079 Nepal

Bisection Method

The bisection method is a bracketing method to find a real root of a continuous nonlinear equation $f(x)=0$. It is based on the Intermediate Value Theorem: if $f$ is continuous on $[a,b]$ and $f(a)\cdot f(b)<0$, then at least one root lies in $(a,b)$.

Procedure

1. Choose $a$ and $b$ such that $f(a)\cdot f(b)<0$.
2. Compute the midpoint $c=\dfrac{a+b}{2}$.
3. If $f(c)=0$ (or $|f(c)|<\varepsilon$), then $c$ is the root.
4. If $f(a)\cdot f(c)<0$, the root lies in $[a,c]$, so set $b=c$; otherwise the root lies in $[c,b]$, so set $a=c$.
5. Repeat until $|b-a|$ is smaller than the required tolerance.

The method always converges (it is unconditionally convergent) but linearly, since the interval halves each step.

Solving $f(x)=x^3-x-1=0$

$f(1)=1-1-1=-1<0$ and $f(2)=8-2-1=5>0$, so a root lies in $[1,2]$.

Continuing until the third decimal place stabilises, the root is

Correct to three decimal places, the root is $x \approx 1.325$.

Interpolation

Interpolation is the process of estimating the value of a function $f(x)$ at an intermediate point $x$ lying within the range of a given set of tabulated data points $(x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)$, by constructing a polynomial that passes through all the given points.

For equally spaced data with step size $h$ ($x_i = x_0 + ih$), Newton's difference formulae are used.

Newton's Forward Difference Formula

Let $p=\dfrac{x-x_0}{h}$. Using the forward difference operator $\Delta y_i = y_{i+1}-y_i$:

Derivation (outline): Express the interpolating polynomial as a Newton series $y = a_0 + a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots$. Substituting $x=x_0,x_1,\dots$ gives $a_0=y_0$, $a_1=\Delta y_0/h$, $a_2=\Delta^2 y_0/(2!h^2)$, etc. Writing $x-x_0=ph$ yields the formula above.

Newton's Backward Difference Formula

Let $p=\dfrac{x-x_n}{h}$. Using the backward difference operator $\nabla y_i = y_i-y_{i-1}$:

It is derived analogously by building the Newton series from the last point backward.

When Each is Used

• Forward formula is used to interpolate near the beginning of the table (when $x$ is close to $x_0$), since it uses the leading differences.
• Backward formula is used to interpolate near the end of the table (when $x$ is close to $x_n$), since it uses the trailing differences.

Both require equally spaced data; for unequal spacing, Lagrange's or Newton's divided difference formula is used.

Gauss Elimination with Partial Pivoting

Gauss elimination solves $Ax=b$ by transforming the augmented matrix $[A\,|\,b]$ into upper-triangular form using elementary row operations (forward elimination), then solving by back substitution.

Partial pivoting: before eliminating column $k$, the row below (or at) the pivot having the largest absolute value in that column is swapped into the pivot position. This avoids division by small/zero pivots and improves numerical stability.

Solving the System

Augmented matrix:

Step 1 – pivot in column 1. Largest magnitude is $3$ (row 2). Swap $R_1\leftrightarrow R_2$:

Eliminate: $R_2\to R_2-\tfrac{2}{3}R_1$, $R_3\to R_3-\tfrac{1}{3}R_1$:

Step 2 – pivot in column 2. $|\tfrac{10}{3}|>|\tfrac13|$, so swap $R_2\leftrightarrow R_3$:

Eliminate: $R_3\to R_3-\dfrac{-1/3}{10/3}R_2 = R_3+\tfrac{1}{10}R_2$:

Back substitution:

Solution: $\boxed{x=7,\; y=-9,\; z=5}$

Check: $2(7)+(-9)+5=10$ ✓, $3(7)+2(-9)+3(5)=18$ ✓, $7+4(-9)+9(5)=16$ ✓.

Errors in Numerical Computation

Let $x_T$ be the true value and $x_A$ the approximate value.

• Absolute error: the magnitude of the difference between true and approximate values,

• Relative error: absolute error per unit of the true value,

• Percentage error: relative error expressed as a percentage,

Sources of Errors

1. Round-off error – caused by representing numbers with a finite number of digits in a computer (finite precision).
2. Truncation error – caused by approximating an infinite process by a finite one (e.g. truncating a Taylor/infinite series).
3. Inherent (input/data) error – present in the original data due to measurement limitations or initial assumptions.
4. Modelling/formulation error – arises from simplifying a real problem into a mathematical model.
5. Human/blunder errors – mistakes in writing programs, copying numbers, or in formulae.

Secant Method

The secant method finds a root of $f(x)=0$ by replacing the tangent used in Newton–Raphson with a secant line through two recent points. Given two approximations $x_{n-1}$ and $x_n$, the next approximation is

Geometrically, $x_{n+1}$ is the point where the secant line joining $(x_{n-1},f(x_{n-1}))$ and $(x_n,f(x_n))$ crosses the $x$-axis.

Comparison with Newton–Raphson

The secant method is preferred when the derivative is hard or expensive to compute, at the cost of slightly slower convergence than Newton–Raphson.

False Position (Regula Falsi) Method

The false position method is a bracketing method to solve $f(x)=0$. Like bisection it needs an interval $[a,b]$ with $f(a)\cdot f(b)<0$, but instead of the midpoint it uses the point where the chord (straight line) joining $(a,f(a))$ and $(b,f(b))$ cuts the $x$-axis:

Procedure

1. Find $a,b$ with $f(a)f(b)<0$.
2. Compute $x$ from the formula above.
3. If $f(a)\cdot f(x)<0$, set $b=x$; else set $a=x$.
4. Repeat until $|f(x)|<\varepsilon$ or the interval is sufficiently small.

Geometric Interpretation

The curve $y=f(x)$ is approximated by the straight chord joining the two end-points of the bracket. The intersection of this chord with the $x$-axis gives the next estimate of the root. Successive chords approach the true root. The method always keeps the root bracketed (so it always converges), generally faster than bisection because it uses the function's slope, though one endpoint may remain fixed, slowing convergence for highly curved functions.

Lagrange's Interpolation Formula

For $n+1$ data points $(x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)$ with arbitrary (unequal) spacing, the interpolating polynomial is

Each Lagrange basis polynomial $L_i(x)$ equals $1$ at $x=x_i$ and $0$ at every other node, so $y(x)$ passes through all the given points. Its main advantage is that the data need not be equally spaced.

Example

Find $y$ at $x=2$ given $(1,1),(3,27),(4,64)$ (i.e. $y=x^3$).

So $y(2)\approx 6$, close to the exact $2^3=8$ (the cubic is not recovered exactly because only three points are used).

Trapezoidal Rule

Derivation

To evaluate $I=\int_{a}^{b} f(x)\,dx$, divide $[a,b]$ into $n$ equal sub-intervals of width $h=\dfrac{b-a}{n}$, with nodes $x_i=a+ih$ and ordinates $y_i=f(x_i)$.

Over a single sub-interval $[x_i,x_{i+1}]$, approximate $f(x)$ by the straight line through $(x_i,y_i)$ and $(x_{i+1},y_{i+1})$. The area under this line is a trapezium:

Summing over all sub-intervals gives the composite trapezoidal rule:

(For a single interval, $I=\frac{b-a}{2}[f(a)+f(b)]$.)

Error Term

The error of the composite trapezoidal rule is

Thus the rule is exact for linear functions, has error $O(h^2)$, and underestimates/overestimates depending on the sign of $f''$ (concavity).

Gauss–Seidel Iterative Method

The Gauss–Seidel method is an iterative technique for solving a system $Ax=b$. The $i$-th equation is solved for the $i$-th unknown:

Its key feature is that newly computed values are used immediately within the same iteration (unlike Jacobi, which uses only previous-iteration values), so it usually converges faster.

Procedure (for a 3×3 system)

Given

rewrite as

1. Start with an initial guess (commonly $x=y=z=0$).
2. Update each unknown using the latest available values.
3. Repeat until $|x_i^{(k+1)}-x_i^{(k)}|<\varepsilon$ for all $i$.

Convergence Condition

Convergence is guaranteed if the coefficient matrix is diagonally dominant, i.e. $|a_{ii}|\ge\sum_{j\neq i}|a_{ij}|$ for each row (rearrange equations if needed).

Numerical Differentiation (Forward & Backward Differences)

Given a function tabulated at equally spaced points $x_i=x_0+ih$ with step $h$ and values $y_i$, the derivative is estimated from finite differences.

Forward Difference Formula

Used near the beginning of the table. From Newton's forward formula, differentiating with respect to $x$:

and more accurately

The simple first form has error $O(h)$.

Backward Difference Formula

Used near the end of the table. From Newton's backward formula:

and more accurately

Second Derivative

Forward/backward first-difference formulae are first-order accurate ($O(h)$); smaller $h$ improves accuracy but excessively small $h$ amplifies round-off error.

Euler's Method

Euler's method is the simplest numerical method to solve a first-order ODE

It advances the solution in steps of size $h$ using the tangent (slope) at the current point:

Geometrically, the curve is approximated by a series of short straight-line segments along the local slope. It is a first-order method with local truncation error $O(h^2)$ and global error $O(h)$.

Example

Solve $\dfrac{dy}{dx}=x+y$, $y(0)=1$, find $y(0.2)$ with $h=0.1$.

Step 1 ($x_0=0,\;y_0=1$):

Step 2 ($x_1=0.1,\;y_1=1.1$):

So $y(0.2)\approx 1.22$. (The exact value is $2e^{0.2}-0.2-1\approx 1.2428$; the gap reflects Euler's first-order accuracy, which improves as $h$ decreases.)

Gauss Elimination vs Gauss–Jordan

Summary: Gauss elimination reduces the augmented matrix to upper-triangular form and then uses back substitution, whereas Gauss–Jordan continues the elimination to make the coefficient matrix the identity so the solution appears directly. Gauss–Jordan needs more arithmetic but is convenient for computing inverses.