BSc CSIT (TU) Science Numerical Method (BSc CSIT, CSC207) Question Paper 2081 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 of size $h$ using a weighted average of four slope estimates. It matches the Taylor series up to $h^4$, giving local truncation error $O(h^5)$ without needing derivatives of $f$.

The working formulas are:

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

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

Step 1: from $x_0=0,\ y_0=1$ to $y_1=y(0.1)$

• $k_1 = 0.1(0+1)=0.1$
• $k_2 = 0.1\,(0.05 + 1.05)=0.1(1.1)=0.11$
• $k_3 = 0.1\,(0.05 + (1+0.055))=0.1(0.05+1.055)=0.1(1.105)=0.1105$
• $k_4 = 0.1\,(0.1 + (1+0.1105))=0.1(1.2105)=0.12105$

Step 2: from $x_1=0.1,\ y_1=1.110342$ to $y_2=y(0.2)$

• $k_1 = 0.1(0.1 + 1.110342)=0.1(1.210342)=0.121034$
• $k_2 = 0.1\,(0.15 + (1.110342+0.060517))=0.1(0.15+1.170859)=0.1(1.320859)=0.132086$
• $k_3 = 0.1\,(0.15 + (1.110342+0.066043))=0.1(0.15+1.176385)=0.1(1.326385)=0.132639$
• $k_4 = 0.1\,(0.2 + (1.110342+0.132639))=0.1(0.2+1.242981)=0.1(1.442981)=0.144298$

Result

This agrees closely with the exact solution $y=2e^x-x-1$, which gives $y(0.2)=2e^{0.2}-1.2=1.242806$.

Derivation of the Newton-Raphson Method

Let $f(x)=0$ have a root near an initial guess $x_n$. Expanding $f$ by Taylor series about $x_n$ and retaining only the linear term:

Setting $f(x)=0$ for the next, improved estimate $x=x_{n+1}$:

Solving for $x_{n+1}$ gives the Newton-Raphson iteration:

Geometrically, $x_{n+1}$ is the x-intercept of the tangent to $y=f(x)$ at $x_n$.

Convergence

The method has quadratic convergence near a simple root: if $\alpha$ is the root and $e_n=x_n-\alpha$, then

so the number of correct digits roughly doubles each iteration. Conditions: $f'(x)\neq 0$ near the root and a sufficiently close initial guess. Drawbacks: it may diverge or oscillate if $f'$ is near zero or the start is poor, convergence drops to linear at multiple roots, and it requires the derivative $f'(x)$.

Root of $x^3 - 2x - 5 = 0$

Here $f(x)=x^3-2x-5$, $f'(x)=3x^2-2$. Since $f(2)=-1<0$ and $f(3)=16>0$, the root lies in $(2,3)$; take $x_0=2$.

Since consecutive values agree to four decimals:

Curve Fitting

Curve fitting is the process of constructing a smooth curve (a mathematical function) that best represents the trend of a given set of discrete data points $(x_i,y_i)$. Unlike interpolation, the fitted curve need not pass through every point; it captures the overall relationship and is used for smoothing data, prediction, and approximating an underlying law. The most widely used technique is the method of least squares.

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

Given $n$ data points $(x_i,y_i)$, we seek constants $a$ and $b$ so the line $y=a+bx$ fits best. The error (residual) at each point is $e_i=y_i-(a+bx_i)$. The least squares principle minimizes the sum of squared residuals:

For a minimum, set the partial derivatives to zero:

These give the normal equations:

Solving the two simultaneous equations gives:

Procedure

1. Tabulate $x_i,\ y_i,\ x_i^2,\ x_i y_i$ and compute the column sums.
2. Substitute $\sum x_i,\ \sum y_i,\ \sum x_i^2,\ \sum x_i y_i$ into the formulas for $a$ and $b$.
3. Write the fitted line $y=a+bx$.

The resulting line is the best-fit line in the least squares sense, minimizing the total squared vertical distance between the data points and the line.

Numerical Differentiation

Numerical differentiation estimates the derivative of a function known only at tabulated points $x_0,x_1,\dots$ with equal spacing $h$, using finite differences derived from Newton's interpolation formulas. Let $y_i=f(x_i)$.

Forward Difference Formula

Used near the beginning of the table. With $p=\dfrac{x-x_0}{h}$ and Newton's forward formula, differentiating gives, at $x=x_0$:

where $\Delta y_0=y_1-y_0$ is the forward difference. The simple two-point form is $f'(x_0)\approx\dfrac{y_1-y_0}{h}$ with error $O(h)$.

Backward Difference Formula

Used near the end of the table. With Newton's backward formula and $\nabla y_n=y_n-y_{n-1}$, at $x=x_n$:

The simple two-point form is $f'(x_n)\approx\dfrac{y_n-y_{n-1}}{h}$.

Summary: forward differences use tabulated values ahead of the point and suit the start of the table; backward differences use values behind the point and suit the end. Both are first-order accurate in their two-point forms; including higher difference terms improves accuracy.

Euler's Method

Euler's method is the simplest single-step numerical technique for solving the initial value problem

It approximates the solution curve by short straight-line segments using the slope at the current point. Over a step of size $h$:

Geometrically, from $(x_n,y_n)$ we move along the tangent line of slope $f(x_n,y_n)$ to reach the next point. It is a first-order method with local truncation error $O(h^2)$ and global error $O(h)$, so accuracy improves as $h$ decreases.

Example

Solve $\dfrac{dy}{dx}=x+y,\ y(0)=1$; find $y(0.2)$ with $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 $1.2428$; the gap reflects Euler's first-order error, which shrinks for smaller $h$.)

Gauss Elimination vs Gauss-Jordan Method

Both are direct methods for solving a system of linear equations $AX=B$ by row operations on the augmented matrix $[A\,|\,B]$, but they differ in how far the reduction is carried.

Summary: Gauss elimination converts the system to an upper-triangular set and then solves it by back substitution, whereas Gauss-Jordan continues the reduction until the coefficient matrix becomes the identity, giving the solution directly without back substitution. Gauss elimination needs fewer operations and is preferred for solving systems, while Gauss-Jordan is convenient for computing matrix inverses.

Newton's Divided Difference Interpolation

This formula constructs an interpolating polynomial through data points $(x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)$ with unequally spaced $x$-values (it also works for equal spacing).

Divided Differences

The divided differences are defined recursively:

and in general

Interpolation Formula

Procedure

1. Build a divided-difference table, computing successive columns from the data.
2. Use the top diagonal entries $f[x_0],f[x_0,x_1],\dots$ as the coefficients.
3. Substitute the required $x$ and evaluate $P(x)$.

Advantages: it handles unequal spacing, is symmetric in the data, and new points can be added easily by appending one more term without recomputing earlier coefficients.

Power Method

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

Principle

Any starting vector $x^{(0)}$ can be written as a combination of eigenvectors $x^{(0)}=c_1 v_1+c_2 v_2+\cdots+c_n v_n$. Repeatedly multiplying by $A$ gives

Since $|\lambda_i/\lambda_1|<1$ for $i>1$, all terms except the first vanish as $k\to\infty$, so $A^k x^{(0)}$ aligns with the dominant eigenvector $v_1$.

Algorithm

1. Choose an initial non-zero vector $x^{(0)}$ (e.g. $[1,1,\dots,1]^T$).
2. Compute $y^{(k+1)}=A\,x^{(k)}$.
3. Let $\lambda^{(k+1)}=$ the largest-magnitude component of $y^{(k+1)}$.
4. Normalize: $x^{(k+1)}=\dfrac{y^{(k+1)}}{\lambda^{(k+1)}}$.
5. Repeat until $\lambda^{(k+1)}$ and $x^{(k+1)}$ converge to the desired accuracy.

At convergence, $\lambda^{(k+1)}$ is the largest eigenvalue and $x^{(k+1)}$ is the corresponding eigenvector.

Notes: convergence is linear and is faster when $|\lambda_2/\lambda_1|$ is small; it fails if $|\lambda_1|=|\lambda_2|$. The smallest eigenvalue can be found by applying the method to $A^{-1}$ (inverse power method).

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

Given $n$ data points $(x_i,y_i)$, we determine $a,b,c$ so that the parabola best fits the data. The residual at each point is $e_i=y_i-(a+bx_i+cx_i^2)$. The least squares principle minimizes

Normal Equations

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

Procedure

1. Form a table of $x,\ y,\ x^2,\ x^3,\ x^4,\ xy,\ x^2y$ and compute their column sums.
2. Substitute the sums $\sum x,\sum x^2,\sum x^3,\sum x^4,\sum y,\sum xy,\sum x^2y$ into the three normal equations.
3. Solve the $3\times3$ system (e.g. by Gauss elimination) for $a,b,c$.
4. Write the fitted parabola $y=a+bx+cx^2$.

This curve minimizes the total squared vertical deviation of the data from the parabola and is the best-fit quadratic in the least squares sense.

Absolute, Relative and Percentage Errors

Let $x_t$ be the true value and $x_a$ the approximate (computed) value.

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

• Relative error: the absolute error per unit of the true value (dimensionless).

• Percentage error: the relative error expressed as a percentage.

Sources of Errors in Numerical Computation

1. Inherent (input/data) errors — errors already present in the input data due to measurement limitations or because the data are themselves approximate.
2. Round-off errors — caused by representing numbers with a finite number of digits; figures beyond the machine precision are dropped or rounded (e.g. storing $\pi$ or $1/3$).
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 replacing a derivative by a finite difference.
4. Modelling errors — arise when the mathematical model only approximates the real physical problem.
5. Blunders / human errors — mistakes in formulation, coding, or transcription.

The total error in a result is the combined effect of these, mainly round-off and truncation errors, which often work against each other when choosing step sizes.

Secant Method

The secant method finds a root of $f(x)=0$ using two approximations $x_{n-1}$ and $x_n$, replacing the curve by the secant line through $(x_{n-1},f(x_{n-1}))$ and $(x_n,f(x_n))$. The next estimate is where this line crosses the x-axis:

It can be seen as the Newton-Raphson method with the derivative $f'(x_n)$ replaced by the difference quotient $\dfrac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$. Two starting values are needed, but they need not bracket the root.

Algorithm

1. Take two initial guesses $x_0,x_1$.
2. Compute $x_{n+1}$ from the formula above.
3. Repeat until $|x_{n+1}-x_n|$ (or $|f(x_{n+1})|$) is within tolerance.

Comparison with Newton-Raphson

The secant method converges more slowly than Newton-Raphson per iteration but avoids computing the derivative, often making it cheaper overall when $f'(x)$ is costly or unavailable. Both may diverge with poor initial guesses.

False Position (Regula Falsi) Method

The false position method is a bracketing method to find a root of $f(x)=0$. It starts with two points $a$ and $b$ such that $f(a)$ and $f(b)$ have opposite signs, i.e. $f(a)\cdot f(b)<0$, guaranteeing (by the Intermediate Value Theorem) a root in $(a,b)$.

Instead of taking the midpoint (as in bisection), it joins the points $(a,f(a))$ and $(b,f(b))$ by a straight chord and takes the point $x_1$ where this chord cuts the x-axis as the next approximation:

Algorithm

1. Choose $a,b$ with $f(a)f(b)<0$.
2. Compute $x_1$ using the formula above.
3. If $f(a)\cdot f(x_1)<0$, the root lies in $(a,x_1)$, so set $b=x_1$; otherwise set $a=x_1$.
4. Repeat until $|f(x_1)|$ (or the interval) is within the required tolerance.

Geometric Interpretation

Geometrically, the curve $y=f(x)$ between $x=a$ and $x=b$ is approximated by the secant (chord) line joining $(a,f(a))$ and $(b,f(b))$. The x-intercept of this chord is taken as the estimate of the root. Because the chord usually crosses the axis closer to the true root than the midpoint does, false position generally converges faster than bisection, though one endpoint may stay fixed (stagnation), giving only linear convergence.