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

Bisection Method

The bisection method is a bracketing method for finding a real root of a continuous function $f(x)$. It is based on the Intermediate Value Theorem: if $f(x)$ 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, b$ such that $f(a)\cdot f(b) < 0$.
2. Compute the midpoint $c = \dfrac{a+b}{2}$.
3. If $f(c)=0$, then $c$ is the root. Otherwise:
   • if $f(a)\cdot f(c) < 0$, the root lies in $[a,c]$, so set $b=c$;
   • else the root lies in $[c,b]$, so set $a=c$.
4. Repeat until $|b-a|$ (or $|f(c)|$) is less than the required tolerance.

The method always converges (linearly), halving the interval each step. After $n$ steps the error $\le \dfrac{b-a}{2^{n}}$.

Solving $x^3 - x - 1 = 0$

Let $f(x)=x^3-x-1$. Then $f(1)=-1<0$ and $f(2)=5>0$, so a root lies in $[1,2]$.

The interval has narrowed to $[1.3245, 1.3247]$, and the values stabilise at

correct to three decimal places (the exact root of the cubic is $1.32472\ldots$).

Interpolation

Interpolation is the process of estimating the value of a function $y=f(x)$ for an intermediate value of $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 fitting a polynomial that passes through all the given points. (Estimating outside the range is extrapolation.)

For equally spaced data with step $h$ (so $x_i = x_0 + ih$), we use Newton's difference formulae.

Forward Differences

Newton's Forward Difference Formula (derivation)

Let $p=\dfrac{x-x_0}{h}$. Using the shift operator $E$ where $Ey_0=y_1$ and $E=1+\Delta$, the interpolating polynomial is

Expanding by the binomial series,

with $p=\dfrac{x-x_0}{h}$.

Newton's Backward Difference Formula (derivation)

With backward differences $\nabla y_i = y_i - y_{i-1}$, let $p=\dfrac{x-x_n}{h}$. Since $E^{-1}=1-\nabla$,

Expanding,

with $p=\dfrac{x-x_n}{h}$.

When to use each

• Forward formula is used to interpolate values near the beginning of the table (small $x$), since it builds on the leading entries.
• Backward formula is used to interpolate values near the end of the table (large $x$), since it builds on the trailing entries.

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

Gauss Elimination with Partial Pivoting

Gauss elimination solves $A\mathbf{x}=\mathbf{b}$ by reducing the augmented matrix $[A\,|\,\mathbf{b}]$ to upper-triangular form through elementary row operations, then solving by back-substitution.

Partial pivoting: before eliminating column $k$, the row with the largest absolute value in that column (on or below the diagonal) is swapped into the pivot position. This avoids division by a small/zero pivot and controls round-off error growth.

Solve the system

Augmented matrix:

Step 1 (column 1): Largest |entry| 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 (column 2): $|\tfrac{10}{3}|>|\tfrac{1}{3}|$, 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:

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$ be the true value and $\tilde{x}$ its approximation.

• Absolute error: $E_a = |x-\tilde{x}|$ — the magnitude of the difference between true and approximate values (same units as $x$).
• Relative error: $E_r = \dfrac{|x-\tilde{x}|}{|x|}$ — the absolute error per unit of the true value (dimensionless); a better measure of accuracy.
• Percentage error: $E_p = E_r \times 100\% = \dfrac{|x-\tilde{x}|}{|x|}\times 100\%$.

Sources of error

1. Inherent (input) errors — uncertainty already present in the data, due to measurement limitations or because the data are themselves approximate.
2. Round-off error — caused by representing numbers with a finite number of digits/finite machine precision (e.g. $\tfrac{1}{3}=0.3333$).
3. Truncation error — caused by truncating an infinite process to a finite one, e.g. cutting off a Taylor/series expansion after a few terms or using a finite step size $h$.
4. Modelling / formulation errors — from simplifying assumptions in the mathematical model.
5. Human / blunder errors — mistakes in programming, data entry, or calculation.

Secant Method

The secant method finds a root of $f(x)=0$ by approximating the curve with the secant line through the two most recent points $(x_{n-1},f(x_{n-1}))$ and $(x_n,f(x_n))$, and taking the next estimate as where that line crosses the $x$-axis.

Iteration formula

It requires two initial guesses $x_0, x_1$ (which need not bracket the root). It is essentially the Newton–Raphson method with the derivative replaced by a divided difference:

Comparison with Newton–Raphson

Newton–Raphson converges faster but requires the derivative; the secant method is preferred when $f'(x)$ is hard or expensive to evaluate.

False Position (Regula Falsi) Method

The false position method is a bracketing method that, like bisection, starts from $a,b$ with $f(a)\cdot f(b)<0$. Instead of taking the midpoint, it joins the points $(a,f(a))$ and $(b,f(b))$ by a straight chord and takes the point where this chord cuts the $x$-axis as the next approximation.

Formula

The chord meets the $x$-axis at

Then, exactly as in bisection, keep whichever sub-interval still brackets the root:

• if $f(a)\cdot f(x)<0$, set $b=x$;
• else set $a=x$. Repeat until $|f(x)|$ is sufficiently small.

Geometric interpretation

Geometrically, the curve $y=f(x)$ is replaced locally by the straight line (chord) joining the two end-points of the bracket. The intersection of this chord with the $x$-axis gives the new estimate of the root. Because $f(a)$ and $f(b)$ have opposite signs, the chord must cross the axis between $a$ and $b$, so the new point always lies inside the bracket — the method always converges (linearly, often faster than bisection, though one endpoint may stay fixed, slowing convergence near the root).

Lagrange's Interpolation Formula

Lagrange's formula interpolates a polynomial through $n+1$ data points $(x_0,y_0),\dots,(x_n,y_n)$ whose arguments may be unequally spaced.

Each Lagrange basis polynomial $L_i(x)$ equals $1$ at $x=x_i$ and $0$ at every other node, so the sum passes exactly through all points. For two points (linear) and three points (quadratic):

Example

Given $(1,1),(2,4),(3,9)$ (i.e. $y=x^2$), estimate $y$ at $x=2.5$:

which matches $2.5^2=6.25$, confirming the formula.

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 strip $[x_0,x_1]$, approximate $f(x)$ by a straight line (Newton's forward formula to first order). The area of that strip is the area of a trapezium:

Adding the areas of all $n$ trapezia gives the composite trapezoidal rule:

i.e. $\dfrac{h}{2}[\text{(first + last)} + 2(\text{sum of interior ordinates})]$.

Error term

For a single interval the error is

For the composite rule over $[a,b]$,

The error is $O(h^2)$, so the rule is exact for polynomials of degree $\le 1$.

Gauss–Seidel Iterative Method

The Gauss–Seidel method is an iterative technique for solving a system $A\mathbf{x}=\mathbf{b}$. It rearranges each equation to make one variable the subject and refines the solution iteratively, immediately using updated values within the same iteration (unlike Jacobi, which uses only old values).

Procedure

For a $3\times3$ system

solve each equation for its diagonal variable:

Steps

1. Start with an initial guess (usually $x=y=z=0$).
2. Compute $x^{(k+1)}$, then use it immediately to compute $y^{(k+1)}$, then use both for $z^{(k+1)}$.
3. Repeat until $|x^{(k+1)}-x^{(k)}|,\dots$ are all below the tolerance.

Convergence condition

The method converges if the coefficient matrix is diagonally dominant, i.e. $|a_{ii}|\ge\sum_{j\neq i}|a_{ij}|$ for every row (with strict inequality in at least one). Reordering equations to achieve diagonal dominance improves convergence. Gauss–Seidel generally converges faster than Jacobi because it uses the most recent values.

Numerical Differentiation (Forward & Backward Differences)

Numerical differentiation estimates derivatives $f'(x), f''(x),\dots$ from a table of values at equally spaced points $x_i=x_0+ih$, $y_i=f(x_i)$, by differentiating an interpolating polynomial.

Forward difference formulae (used near the start of the table)

From Newton's forward formula with $p=\dfrac{x-x_0}{h}$:

At the tabular point $x=x_0$ ($p=0$):

The simplest first-order approximation is $f'(x_0)\approx\dfrac{y_1-y_0}{h}$.

Backward difference formulae (used near the end of the table)

From Newton's backward formula with $p=\dfrac{x-x_n}{h}$:

At $x=x_n$ ($p=0$):

The simplest approximation is $f'(x_n)\approx\dfrac{y_n-y_{n-1}}{h}$.

Use: forward formulae near the beginning of the table, backward formulae near the end. Both are most accurate close to the tabular point used.

Euler's Method

Euler's method is the simplest numerical method for solving a first-order initial-value problem

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

It is a first-order method with local truncation error $O(h^2)$ and global error $O(h)$, so it requires small $h$ for accuracy.

Example

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

Here $f(x,y)=x+y$.

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

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

(The exact value is $y=2e^{x}-x-1\Rightarrow y(0.2)=1.2428$; the difference reflects Euler's truncation error.)

Gauss Elimination vs Gauss–Jordan

Both are direct methods for solving $A\mathbf{x}=\mathbf{b}$ using elementary row operations on the augmented matrix, but they differ in how far the reduction is carried.

Summary: Gauss elimination reduces $A$ to upper-triangular form and then back-substitutes, whereas Gauss–Jordan continues the elimination to a diagonal/identity form so the unknowns are obtained directly. Gauss elimination needs fewer operations; Gauss–Jordan is preferred when the matrix inverse is also required.