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

Fourth-Order Runge-Kutta (RK4) Method

The RK4 method solves the initial value problem $\dfrac{dy}{dx}=f(x,y),\ y(x_0)=y_0$ by advancing the solution one step $h$ at a time using a weighted average of four slope estimates. It achieves accuracy equivalent to a 4th-order Taylor expansion without needing higher derivatives.

For each step from $(x_n, y_n)$:

Here $k_1$ is the slope at the start, $k_2,k_3$ are slopes at the midpoint, and $k_4$ is the slope at the end of the interval. The local truncation error is $O(h^5)$ and the global error is $O(h^4)$.

Solving $\dfrac{dy}{dx}=x+y,\ y(0)=1,\ h=0.1$ for $y(0.2)$

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

Step 1: from $x_0=0,\ y_0=1$ to $x_1=0.1$

Step 2: from $x_1=0.1,\ y_1=1.110342$ to $x_2=0.2$

(The exact value $y=2e^{x}-x-1$ gives $y(0.2)=1.242806$, confirming the result.)

Derivation of the Newton-Raphson Method

To solve $f(x)=0$, expand $f$ in a Taylor series about an approximate root $x_n$ and retain linear terms:

Setting $f(x_{n+1})=0$ and solving for $x_{n+1}$ gives the iteration formula:

Geometrically, the tangent to the curve at $(x_n, f(x_n))$ is drawn, and its x-intercept becomes the next approximation.

Convergence

Newton-Raphson has quadratic convergence near a simple root: if $\varepsilon_n$ is the error at step $n$, then

so the number of correct digits roughly doubles each iteration. Limitations: it requires $f'(x)$; it may diverge or oscillate if the initial guess is poor or $f'(x_n)\approx 0$; convergence drops to linear at a multiple root.

Root of $f(x)=x^3 - 2x - 5 = 0$

Since $f(2)=-1<0$ and $f(3)=16>0$, take $x_0 = 2$.

Successive values agree to four decimals:

Curve Fitting

Curve fitting is the process of constructing a mathematical function (curve) that best approximates a given set of discrete data points $(x_i, y_i),\ i=1,2,\dots,n$. Unlike interpolation, the fitted curve need not pass through every point; instead it captures the overall trend while minimizing the deviation from the data. It is used for prediction, smoothing noisy data, and modelling relationships.

Least Squares Method for a Straight Line $y = a + bx$

For each data point the residual (error) is $e_i = y_i - (a + bx_i)$. The least squares principle chooses $a$ and $b$ that minimize the sum of squared residuals:

Setting the partial derivatives to zero:

These give the normal equations:

Solving simultaneously:

where $\bar{x},\bar{y}$ are the means. The required sums $\sum x_i,\ \sum y_i,\ \sum x_i y_i,\ \sum x_i^2$ are computed in a table; substituting them gives $a$ and $b$, and hence the best-fit line $y = a + bx$.

Numerical Differentiation Using Finite Differences

Given tabulated values $y_i = f(x_i)$ at equally spaced points with step $h$, derivatives are approximated by finite difference formulas obtained from Taylor expansions.

Forward difference (uses points ahead, best near the start of a table):

Derived from $f(x_i+h) = f(x_i) + h f'(x_i) + O(h^2)$. Truncation error is $O(h)$.

Backward difference (uses points behind, best near the end of a table):

Derived from $f(x_i-h) = f(x_i) - h f'(x_i) + O(h^2)$. Truncation error is also $O(h)$.

Second derivative (central form, error $O(h^2)$):

Example: For $y = x^2$ tabulated at $x=1,2,3$ giving $y=1,4,9$ with $h=1$, the forward difference at $x=1$ is $f'(1)\approx(4-1)/1 = 3$, and the backward difference at $x=3$ is $f'(3)\approx(9-4)/1 = 5$ (compare exact $f'(x)=2x$ giving 2 and 6 — accuracy improves as $h\to0$).

Euler's Method

Euler's method is the simplest numerical technique for the initial value problem $\dfrac{dy}{dx}=f(x,y),\ y(x_0)=y_0$. It approximates the solution curve by short straight-line segments, using the slope at the current point to step forward:

where $h$ is the step size. It is a first-order method with global error $O(h)$, so accuracy improves as $h$ is reduced.

Example

Solve $\dfrac{dy}{dx} = x + y,\ y(0)=1$ for $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 $1.2428$; the gap reflects Euler's $O(h)$ error, which a smaller $h$ would reduce.)

Gauss Elimination vs Gauss-Jordan Method

Both are direct methods for solving a linear system $AX = B$ by row operations, but they differ in how far the elimination is carried.

Summary: Gauss elimination triangularizes the augmented matrix then back-substitutes, whereas Gauss-Jordan continues eliminating until the coefficient matrix becomes the identity, giving the solution directly. Gauss elimination needs fewer operations, while Gauss-Jordan is preferred for finding the inverse of a matrix.

Newton's Divided Difference Interpolation

For unequally spaced data points $(x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)$, Newton's divided difference formula constructs an interpolating polynomial.

Divided differences are defined recursively:

Interpolating polynomial:

Advantages: It works for unequal spacing (unlike Newton's forward/backward formulas), and new data points can be added easily by appending one more term without recomputing existing coefficients. The leading coefficients are obtained from a divided-difference table.

Power Method (Largest Eigenvalue)

The power method is an iterative technique to find the dominant eigenvalue (largest in magnitude) of a square matrix $A$ and its corresponding eigenvector. It assumes $A$ has a single dominant eigenvalue $|\lambda_1| > |\lambda_2| \ge \cdots$.

Algorithm:

1. Choose an arbitrary non-zero initial vector $X_0$ (e.g. $[1,1,\dots,1]^T$).
2. Compute $X_{k+1} = A X_k$.
3. Normalize by factoring out the largest-magnitude component: $X_{k+1} = \lambda^{(k+1)} \bar{X}_{k+1}$, where $\lambda^{(k+1)}$ is that largest component.
4. Repeat until $\lambda^{(k+1)}$ and the vector $\bar{X}_{k+1}$ converge.

At convergence, $\lambda^{(k+1)} \to \lambda_1$ (largest eigenvalue) and $\bar{X} \to$ its eigenvector.

Why it works: Writing $X_0$ as a combination of eigenvectors $X_0 = \sum c_i V_i$, then $A^k X_0 = \sum c_i \lambda_i^k V_i = \lambda_1^k\left(c_1 V_1 + \sum_{i\ge2} c_i (\lambda_i/\lambda_1)^k V_i\right)$. Since $|\lambda_i/\lambda_1| < 1$, all terms except $V_1$ vanish, so $A^k X_0$ aligns with $V_1$ and the scaling factor tends to $\lambda_1$.

Convergence is linear, governed by the ratio $|\lambda_2/\lambda_1|$; a small ratio gives fast convergence.

Fitting a Second-Degree Parabola $y = a + bx + cx^2$

By the least squares principle, the constants $a,b,c$ minimize the sum of squared residuals:

Setting $\dfrac{\partial S}{\partial a}=\dfrac{\partial S}{\partial b}=\dfrac{\partial S}{\partial c}=0$ gives the three normal equations:

Procedure:

1. From the data, compute the column sums $\sum x,\ \sum x^2,\ \sum x^3,\ \sum x^4,\ \sum y,\ \sum xy,\ \sum x^2 y$ (and use $n$ = number of points) in a tabular form.
2. Substitute these into the three normal equations.
3. Solve the resulting $3\times3$ linear system (e.g. by Gauss elimination) for $a,b,c$.
4. The best-fit parabola is $y = a + bx + cx^2$.

This least-squares parabola gives the curve of best fit minimizing the total squared vertical deviation from the data.

Absolute, Relative and Percentage Errors

If $x$ is the true value and $\tilde{x}$ its approximation:

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

Sources of Errors in Numerical Computation

1. Inherent (input/data) errors — errors already present in the input data due to measurement limitations or imprecise constants.
2. Round-off errors — caused by representing numbers with a finite number of digits/bits in a computer (e.g. storing $1/3$). They accumulate over many operations.
3. Truncation errors — caused by approximating an infinite process by a finite one, e.g. cutting off a Taylor/infinite series after a few terms or using a finite step size $h$.
4. Modelling/formulation errors — from simplifying assumptions made when forming the mathematical model.
5. Human/blunder errors — mistakes in problem setup, programming, or data entry.

Total error is essentially the combination of round-off and truncation errors, and good numerical methods aim to keep both small.

Secant Method

The secant method finds a root of $f(x)=0$ using two previous approximations $x_{n-1}$ and $x_n$. The function is approximated by the straight line (secant) through $(x_{n-1}, f(x_{n-1}))$ and $(x_n, f(x_n))$, and the next estimate is its x-intercept:

It is essentially Newton-Raphson with the derivative $f'(x_n)$ replaced by the difference quotient $\dfrac{f(x_n)-f(x_{n-1})}{x_n - x_{n-1}}$. It needs two starting values but, unlike false position, does not require them to bracket the root.

Comparison with Newton-Raphson

Conclusion: Newton-Raphson converges faster (quadratically) but needs the derivative; the secant method converges a little slower yet avoids derivative evaluation, making it useful when $f'(x)$ is hard or expensive to compute.

False Position (Regula Falsi) Method

The false position method is a bracketing method to find a root of $f(x)=0$. Starting with two points $a$ and $b$ such that $f(a)\,f(b) < 0$ (so a root lies between them, by the intermediate value theorem), it approximates the root by the x-intercept of the straight line (chord) joining $(a, f(a))$ and $(b, f(b))$:

Iteration steps:

1. Compute $x$ from the formula above.
2. Evaluate $f(x)$. If $f(x)=0$ (or $|f(x)|<\varepsilon$), $x$ is the root.
3. Otherwise, retain the bracket: if $f(a)\,f(x)<0$ replace $b$ by $x$; else replace $a$ by $x$.
4. Repeat until the root is found to the desired accuracy.

Geometric Interpretation

The curve $y=f(x)$ crosses the x-axis between $a$ and $b$. A straight chord is drawn joining the points $(a,f(a))$ (above the axis) and $(b,f(b))$ (below the axis). The point where this chord cuts the x-axis is taken as the new approximation $x$ to the root. The interval is then narrowed to the sub-interval that still brackets the root, and a new chord is drawn — successive chords converge onto the true root.

The method always converges (since the root stays bracketed) but only linearly, and can be one-sided (slow) if the curve is strongly concave/convex on the interval.