BE Civil Engineering (IOE, TU) Numerical Methods (IOE, SH 553) Question Paper 2078 Nepal

Definition. A root of $f(x)=0$ is a value $x=\xi$ for which $f(\xi)=0$. Bracketing methods rely on the Intermediate Value Theorem: if $f$ is continuous and $f(a)\,f(b)<0$, a root lies in $(a,b)$.

(a) Bisection method

Check the bracket:

$$f(1)=1-1-2=-2<0,\qquad f(2)=8-2-2=4>0.$$

Since $f(1)\,f(2)<0$, a root lies in $[1,2]$.

Iteration rule: $c=(a+b)/2$; if $f(a)f(c)<0$ keep $[a,c]$, else keep $[c,b]$.

Approximate root after 6 iterations: $c \approx (1.51562+1.53125)/2 = \mathbf{1.52344}$.

Error bound: $|\xi - c| \le \dfrac{b-a}{2^{n}} = \dfrac{2-1}{2^{6}} = \dfrac{1}{64} \approx \mathbf{0.0156}.$

(b) Newton-Raphson method

$f'(x)=3x^2-1$. Iteration: $x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)} = x_n - \dfrac{x_n^3-x_n-2}{3x_n^2-1}.$

• $x_0=2$: $f=4,\ f'=11 \Rightarrow x_1 = 2 - 4/11 = \mathbf{1.636364}$
• $x_1=1.636364$: $f=(4.38082)-1.636364-2=0.744452,\ f'=3(2.677686)-1=7.033058 \Rightarrow x_2 = 1.636364-0.105849 = \mathbf{1.530515}$
• $x_2=1.530515$: $f=(3.585158)-1.530515-2=0.054643,\ f'=3(2.342476)-1=6.027428 \Rightarrow x_3 = 1.530515-0.009066 = \mathbf{1.521449}$

Converged root $\approx \mathbf{1.52138}$.

Comment. Newton-Raphson reaches ~5 significant figures in 3 steps (quadratic convergence: the number of correct digits roughly doubles each step), whereas bisection (linear convergence, error halved per step) needs many more iterations for the same accuracy. The trade-off is that Newton-Raphson requires $f'(x)$ and may diverge for a poor initial guess, while bisection always converges once a sign change is bracketed.

(a) Lagrange interpolation

For nodes $x_0=5, x_1=6, x_2=9, x_3=11$ with values $12,13,14,16$, the polynomial is

$$P(x)=\sum_{i=0}^{3} y_i \, L_i(x),\quad L_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}.$$

At $x=10$:

• $L_0=\dfrac{(10-6)(10-9)(10-11)}{(5-6)(5-9)(5-11)}=\dfrac{(4)(1)(-1)}{(-1)(-4)(-6)}=\dfrac{-4}{-24}=0.166667$
• $L_1=\dfrac{(10-5)(10-9)(10-11)}{(6-5)(6-9)(6-11)}=\dfrac{(5)(1)(-1)}{(1)(-3)(-5)}=\dfrac{-5}{15}=-0.333333$
• $L_2=\dfrac{(10-5)(10-6)(10-11)}{(9-5)(9-6)(9-11)}=\dfrac{(5)(4)(-1)}{(4)(3)(-2)}=\dfrac{-20}{-24}=0.833333$
• $L_3=\dfrac{(10-5)(10-6)(10-9)}{(11-5)(11-6)(11-9)}=\dfrac{(5)(4)(1)}{(6)(5)(2)}=\dfrac{20}{60}=0.333333$

$$P(10)=12(0.166667)+13(-0.333333)+14(0.833333)+16(0.333333)$$ $$=2.0-4.333333+11.666667+5.333333=\mathbf{14.6667\ m}.$$

(b) Newton's forward-difference interpolation

Forward difference table ($h=1$):

With $x_0=0$, $p=\dfrac{x-x_0}{h}=\dfrac{0.5-0}{1}=0.5$,

$$y(x)=y_0+p\,\Delta y_0+\frac{p(p-1)}{2!}\Delta^2 y_0+\frac{p(p-1)(p-2)}{3!}\Delta^3 y_0.$$ $$y(0.5)=1+0.5(1)+\frac{(0.5)(-0.5)}{2}(6)+\frac{(0.5)(-0.5)(-1.5)}{6}(6)$$ $$=1+0.5+(-0.125)(6)+(0.0625)(6)=1+0.5-0.75+0.375=\mathbf{1.125\ mm}.$$

(a) Numerical integration of $\int_0^1 e^x\,dx$

Step size $h=(1-0)/4=0.25$. Nodes and values:

(i) Trapezoidal rule

$$I_T=\frac{h}{2}\Big[y_0+y_4+2(y_1+y_2+y_3)\Big]$$ $$=\frac{0.25}{2}\big[1.000000+2.718282+2(1.284025+1.648721+2.117000)\big]$$ $$=0.125\big[3.718282+2(5.049746)\big]=0.125(13.817774)=\mathbf{1.727222}.$$

(ii) Simpson's 1/3 rule

$$I_S=\frac{h}{3}\Big[y_0+y_4+4(y_1+y_3)+2y_2\Big]$$ $$=\frac{0.25}{3}\big[1.000000+2.718282+4(1.284025+2.117000)+2(1.648721)\big]$$ $$=0.083333\big[3.718282+4(3.401025)+3.297442\big]=0.083333(20.619824)=\mathbf{1.718319}.$$

Exact value: $\int_0^1 e^x\,dx = e-1 = 1.718282$.

Percentage errors:

• Trapezoidal: $\dfrac{|1.727222-1.718282|}{1.718282}\times100 = \mathbf{0.520\%}$.
• Simpson 1/3: $\dfrac{|1.718319-1.718282|}{1.718282}\times100 = \mathbf{0.0022\%}$.

Simpson's rule is far more accurate (error $\propto h^4$ versus $h^2$ for trapezoidal).

(b) Volume of earthwork (Simpson's 1/3 rule)

With $h=20$ m and 5 ordinates (even number of intervals = 4, so the rule applies directly):

$$V=\frac{h}{3}\Big[A_0+A_4+4(A_1+A_3)+2A_2\Big]$$ $$=\frac{20}{3}\big[12+20+4(18+25)+2(22)\big]=\frac{20}{3}\big[32+172+44\big]=\frac{20}{3}(248)$$ $$=\mathbf{1653.33\ m^3}.$$

(a) Gauss elimination with partial pivoting

Augmented matrix:

$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right]$$

Partial pivoting (column 1): largest magnitude in column 1 is $|-3|=3$ (row 2). Swap R1 and R2:

$$\left[\begin{array}{ccc|c} -3 & -1 & 2 & -11 \\ 2 & 1 & -1 & 8 \\ -2 & 1 & 2 & -3 \end{array}\right]$$

Eliminate column 1: $R2 \leftarrow R2+\tfrac{2}{3}R1$, $R3 \leftarrow R3-\tfrac{2}{3}R1$:

• $R2: (0,\ 1-\tfrac{2}{3}=0.33333,\ -1+\tfrac{4}{3}=0.33333\ |\ 8-\tfrac{22}{3}=0.66667)$
• $R3: (0,\ 1+\tfrac{2}{3}=1.66667,\ 2-\tfrac{4}{3}=0.66667\ |\ -3+\tfrac{22}{3}=4.33333)$

$$\left[\begin{array}{ccc|c} -3 & -1 & 2 & -11 \\ 0 & 0.33333 & 0.33333 & 0.66667 \\ 0 & 1.66667 & 0.66667 & 4.33333 \end{array}\right]$$

Partial pivoting (column 2): $|1.66667|>|0.33333|$, swap R2 and R3:

$$\left[\begin{array}{ccc|c} -3 & -1 & 2 & -11 \\ 0 & 1.66667 & 0.66667 & 4.33333 \\ 0 & 0.33333 & 0.33333 & 0.66667 \end{array}\right]$$

Eliminate column 2: $R3 \leftarrow R3 - \tfrac{0.33333}{1.66667}R2 = R3 - 0.2\,R2$:

• $R3: (0,\ 0,\ 0.33333-0.2(0.66667)=0.2\ |\ 0.66667-0.2(4.33333)=-0.2)$

Upper-triangular system:

$$-3x_1 - x_2 + 2x_3 = -11,\quad 1.66667x_2 + 0.66667x_3 = 4.33333,\quad 0.2x_3 = -0.2.$$

Back-substitution:

• $x_3 = -0.2/0.2 = \mathbf{-1}$
• $x_2 = (4.33333 - 0.66667(-1))/1.66667 = 5.0/1.66667 = \mathbf{3}$
• $x_1 = (-11 + x_2 - 2x_3)/(-3) = (-11+3+2)/(-3) = -6/-3 = \mathbf{2}$

Solution: $x_1=2,\ x_2=3,\ x_3=-1$.

(b) Gauss-Seidel iteration

Rearranged for the dominant diagonal:

$$x=\frac{7+y-z}{4},\quad y=\frac{21+4x+z}{8},\quad z=\frac{15+2x-y}{5}.$$

Start $(0,0,0)$, using latest available values:

After 3 iterations: $\mathbf{x \approx 1.99375,\ y \approx 3.99219,\ z \approx 2.99906}$, converging to the exact solution $(2,4,3)$.

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

(a) Euler's method ($h=0.1$): $y_{n+1}=y_n+h\,f(x_n,y_n)$.

Euler estimate: $y(0.4) \approx 1.528200$.

(b) RK4 method ($h=0.2$). Per step:

$$k_1=f(x,y),\ k_2=f(x+\tfrac{h}{2},y+\tfrac{h}{2}k_1),\ k_3=f(x+\tfrac{h}{2},y+\tfrac{h}{2}k_2),\ k_4=f(x+h,y+hk_3),$$ $$y_{n+1}=y_n+\frac{h}{6}(k_1+2k_2+2k_3+k_4).$$

Step 1 ($x_0=0,\ y_0=1$, $h/2=0.1$):

• $k_1=0+1=1.000000$
• $k_2=(0.1)+(1+0.1\cdot1)=0.1+1.1=1.200000$
• $k_3=(0.1)+(1+0.1\cdot1.2)=0.1+1.12=1.220000$
• $k_4=(0.2)+(1+0.2\cdot1.22)=0.2+1.244=1.444000$
• $y_1=1+\frac{0.2}{6}(1+2(1.2)+2(1.22)+1.444)=1+0.033333(7.284)=\mathbf{1.242800}$ at $x=0.2$.

Step 2 ($x_1=0.2,\ y_1=1.242800$):

• $k_1=0.2+1.2428=1.442800$
• $k_2=0.3+(1.2428+0.1\cdot1.4428)=0.3+1.387080=1.687080$
• $k_3=0.3+(1.2428+0.1\cdot1.687080)=0.3+1.411508=1.711508$
• $k_4=0.4+(1.2428+0.2\cdot1.711508)=0.4+1.585102=1.985102$
• $y_2=1.2428+\frac{0.2}{6}\big(1.442800+2(1.687080)+2(1.711508)+1.985102\big)$
• $=1.2428+0.033333(10.225078)=1.2428+0.340836=\mathbf{1.583636}$ at $x=0.4$.

RK4 estimate: $y(0.4) \approx 1.583636$.

(c) Exact and error comparison

$y(0.4)=2e^{0.4}-0.4-1 = 2(1.491825)-1.4 = 2.983649-1.4 = \mathbf{1.583649}$.

Conclusion. RK4 is dramatically more accurate (local error $O(h^5)$, global $O(h^4)$) than Euler (global error $O(h)$), even using a larger step size.

Secant iteration: $x_{n+1}=x_n-f(x_n)\dfrac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$, with $f(x)=x^2-5$.

Initial: $f(x_0)=f(2)=4-5=-1$, $f(x_1)=f(3)=9-5=4$.

Iteration 1 ($x_0=2, x_1=3$):

$$x_2=3-4\cdot\frac{3-2}{4-(-1)}=3-4\cdot\frac{1}{5}=3-0.8=\mathbf{2.200000}$$

$f(x_2)=2.2^2-5=4.84-5=-0.16$.

Iteration 2 ($x_1=3, x_2=2.2$):

$$x_3=2.2-(-0.16)\cdot\frac{2.2-3}{-0.16-4}=2.2-(-0.16)\cdot\frac{-0.8}{-4.16}=2.2-(-0.16)(0.192308)$$ $$=2.2+0.030769=\mathbf{2.230769}$$

$f(x_3)=2.230769^2-5=4.976331-5=-0.023669$.

Iteration 3 ($x_2=2.2, x_3=2.230769$):

$$x_4=2.230769-(-0.023669)\cdot\frac{2.230769-2.2}{-0.023669-(-0.16)}=2.230769-(-0.023669)\cdot\frac{0.030769}{0.136331}$$ $$=2.230769+0.005343=\mathbf{2.236112}$$

Approximate root $\approx 2.23611$ (true value $\sqrt5 = 2.23607$).

Normal equations for $y=a+bx$ ($n=5$):

$$\sum y = na + b\sum x,\qquad \sum xy = a\sum x + b\sum x^2.$$

Sums:

$$b=\frac{n\sum xy-\sum x\sum y}{n\sum x^2-(\sum x)^2}=\frac{5(62.1)-15(18.2)}{5(55)-15^2}=\frac{310.5-273}{275-225}=\frac{37.5}{50}=\mathbf{0.75}.$$ $$a=\frac{\sum y-b\sum x}{n}=\frac{18.2-0.75(15)}{5}=\frac{18.2-11.25}{5}=\frac{6.95}{5}=\mathbf{1.39}.$$

Fitted line: $y = 1.39 + 0.75x$.

At $x=6$: $y = 1.39 + 0.75(6) = 1.39 + 4.50 = \mathbf{5.89}.$

Classification. For $A u_{xx}+B u_{xy}+C u_{yy}+\dots=0$, the discriminant is $D=B^2-4AC$:

• $D<0$ : elliptic (e.g. Laplace/Poisson, steady-state problems);
• $D=0$ : parabolic (e.g. heat/diffusion equation);
• $D>0$ : hyperbolic (e.g. wave equation).

For Laplace's equation $u_{xx}+u_{yy}=0$: $A=1,\ B=0,\ C=1\Rightarrow D=0-4(1)(1)=-4<0$, hence elliptic.

Five-point formula. Using central differences with mesh spacing $h$,

$$u_{xx}+u_{yy}\approx\frac{u_{i+1,j}+u_{i-1,j}+u_{i,j+1}+u_{i,j-1}-4u_{i,j}}{h^2}=0,$$

so

$$\boxed{\,u_{i,j}=\frac{1}{4}\big(u_{i+1,j}+u_{i-1,j}+u_{i,j+1}+u_{i,j-1}\big)\,}$$

i.e. each interior value is the average of its four neighbours.

        u_top = 100
          |
u_left -- P -- u_right
  80      |      60
        u_bot = 40

Estimate.

$$u_P=\frac{1}{4}(100+60+40+80)=\frac{280}{4}=\mathbf{70\,^{\circ}C}.$$

Spacing $h_{\text{step}}=0.5$. Forward difference table:

At the leading node ($p=0$), the derivative formula is

$$\left.\frac{dQ}{dh}\right|_{h_0}=\frac{1}{h_{\text{step}}}\Big[\Delta Q_0-\frac{1}{2}\Delta^2 Q_0+\frac{1}{3}\Delta^3 Q_0-\dots\Big].$$

Substituting $\Delta Q_0=2.5,\ \Delta^2 Q_0=1.0,\ \Delta^3 Q_0=0.0$:

$$\left.\frac{dQ}{dh}\right|_{h=1.0}=\frac{1}{0.5}\Big[2.5-\frac{1}{2}(1.0)+\frac{1}{3}(0)\Big]=\frac{1}{0.5}(2.0)=\mathbf{4.0\ m^3/s\ per\ m}.$$

Definitions. If $x_t$ is the true value and $x_a$ the approximation:

• Absolute error: $E_a=|x_t-x_a|$.
• Relative error: $E_r=\dfrac{|x_t-x_a|}{|x_t|}$.
• Percentage error: $E_p=E_r\times100\%$.

Computation. $x_t=\pi=3.14159265$, $x_a=\dfrac{22}{7}=3.14285714$.

• Absolute error: $E_a=|3.14159265-3.14285714|=\mathbf{0.00126449}$.
• Relative error: $E_r=\dfrac{0.00126449}{3.14159265}=\mathbf{0.00040250}$.
• Percentage error: $E_p=0.00040250\times100=\mathbf{0.0402\%}$.

Thus $22/7$ overestimates $\pi$ by about $0.04\%$, accurate to roughly three significant figures.

The cross-sectional area is $A=\int_0^{20} d(x)\,dx$, approximated by the Trapezoidal rule with $h=5$ m.

$$A=\frac{h}{2}\Big[d_0+d_n+2\big(d_1+d_2+d_3\big)\Big]$$ $$=\frac{5}{2}\Big[0+0+2(2.5+4.0+3.0)\Big]=\frac{5}{2}\big[2(9.5)\big]=\frac{5}{2}(19.0)=\mathbf{47.5\ m^2}.$$

Cross-sectional area of flow $\approx 47.5\ \mathrm{m}^2$. (This area, multiplied by the mean velocity, gives the river discharge $Q=A\bar v$.)