# MT238: Mathematical Analysis for Computer Science Engineering ## Unit 1: Differential Equations ### 1. Algebraic and Transcendental Equations #### 1.1. Bisection Method * **Concept:** A bracketing method that repeatedly bisects an interval and then selects a subinterval in which the root must lie. * **Requirement:** A continuous function $f(x)$ such that $f(a)$ and $f(b)$ have opposite signs ($f(a) \cdot f(b) < 0$) on an interval $[a, b]$. * **Algorithm:** 1. Choose an interval $[a, b]$ such that $f(a) \cdot f(b) < 0$. 2. Calculate the midpoint: $c = (a+b)/2$. 3. If $f(c) = 0$, then $c$ is the root. 4. If $f(a) \cdot f(c) < 0$, the root lies in $[a, c]$. Set $b = c$. 5. If $f(c) \cdot f(b) < 0$, the root lies in $[c, b]$. Set $a = c$. 6. Repeat steps 2-5 until the interval width $(b-a)$ is sufficiently small. * **Rate of Convergence:** Linear. The error is halved in each iteration. Error bound after $n$ iterations is $\frac{b_0 - a_0}{2^n}$. * **Exam Point:** Simple, guaranteed to converge if initial interval is correct, but slow. #### 1.2. Iteration Method (Fixed-Point Iteration) * **Concept:** Rewrites $f(x) = 0$ into the form $x = g(x)$ and then iteratively applies $x_{n+1} = g(x_n)$. * **Requirement:** The function $g(x)$ must be continuous in the interval of interest. For convergence, $|g'(x)| < 1$ in the vicinity of the root. * **Algorithm:** 1. Rewrite $f(x)=0$ as $x = g(x)$. 2. Choose an initial guess $x_0$. 3. Iterate using $x_{n+1} = g(x_n)$. 4. Stop when $|x_{n+1} - x_n|$ is sufficiently small. * **Rate of Convergence:** Linear, if $|g'(x_0)| \neq 0$. It is first-order convergence. * **Exam Point:** Easy to implement, but convergence is not guaranteed and depends heavily on the choice of $g(x)$ and initial guess. #### 1.3. False Position Method (Regula Falsi) * **Concept:** Similar to Bisection, but uses a secant line to approximate the root. * **Requirement:** A continuous function $f(x)$ such that $f(a)$ and $f(b)$ have opposite signs ($f(a) \cdot f(b) < 0$) on an interval $[a, b]$. * **Algorithm:** 1. Choose an interval $[a, b]$ such that $f(a) \cdot f(b) < 0$. 2. Calculate the next approximation using the formula: $c = \frac{a f(b) - b f(a)}{f(b) - f(a)}$ 3. If $f(c) = 0$, then $c$ is the root. 4. If $f(a) \cdot f(c) < 0$, the root lies in $[a, c]$. Set $b = c$. 5. If $f(c) \cdot f(b) < 0$, the root lies in $[c, b]$. Set $a = c$. 6. Repeat steps 2-5 until the interval width $(b-a)$ or $|f(c)|$ is sufficiently small. * **Rate of Convergence:** Linear, but generally faster than Bisection. * **Exam Point:** Combines the bracketing guarantee of Bisection with a potentially faster convergence by using more information about the function's slope. #### 1.4. Newton-Raphson Method * **Concept:** Uses the tangent line at the current approximation to find the next approximation. * **Requirement:** The function $f(x)$ and its derivative $f'(x)$ must be continuous near the root. $f'(x)$ should not be zero near the root. * **Algorithm:** 1. Choose an initial guess $x_0$. 2. Iterate using the formula: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ 3. Stop when $|x_{n+1} - x_n|$ or $|f(x_n)|$ is sufficiently small. * **Rate of Convergence:** Quadratic, if $f'(x) \neq 0$ at the root. This means the number of correct decimal places roughly doubles with each iteration. * **Exam Point:** Fastest convergence among the discussed methods if conditions are met. High risk of divergence if the initial guess is poor or $f'(x) \approx 0$. * **[Figure: Newton-Raphson Geometric Interpretation]** This figure visually demonstrates how the Newton-Raphson method uses the tangent line to approximate the root. It's important for understanding the iterative step and the concept of quadratic convergence. #### 1.5. Rate of Convergence of Methods * **Linear Convergence:** Error decreases by a constant factor in each step. $e_{n+1} \approx C |e_n|$, where $0 < C < 1$. * **Bisection Method:** $C=1/2$. * **Iteration Method (if $|g'(x)| \neq 0$):** $C = |g'(x^*)|$. * **False Position Method:** Linear, but generally faster than Bisection. * **Quadratic Convergence:** The error in the next step is proportional to the square of the error in the current step. $e_{n+1} \approx C |e_n|^2$. * **Newton-Raphson Method:** $C = |\frac{f''(x^*)}{2 f'(x^*)}|$. * **Exam Point:** Understanding the order of convergence is crucial for comparing method efficiency and predicting the number of iterations required for a desired accuracy. Quadratic convergence is highly desirable. ### 2. Solution of System of Linear Equations #### 2.1. LU Decomposition Method * **Concept:** Decomposes a square matrix $A$ into a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $A = LU$. * **Application:** Solves $Ax = b$ by solving two simpler systems: 1. $Ly = b$ (forward substitution) 2. $Ux = y$ (backward substitution) * **Requirements:** The matrix $A$ must be square. For unique LU decomposition without pivoting, the leading principal minors must be non-zero. Pivoting (row/column interchanges) might be necessary. * **Algorithm (Doolittle's Method - typically $L$ has 1s on diagonal):** For $A = LU$, where $A = [a_{ij}]$, $L = [l_{ij}]$, $U = [u_{ij}]$: * $u_{ii} = 1$ for all $i$. * For $k = 1, \dots, n$: * For $j = k, \dots, n$: $u_{kj} = a_{kj} - \sum_{p=1}^{k-1} l_{kp} u_{pj}$ * For $i = k+1, \dots, n$: $l_{ik} = (a_{ik} - \sum_{p=1}^{k-1} l_{ip} u_{pk}) / u_{kk}$ * **Solving $Ly = b$:** $y_i = b_i - \sum_{j=1}^{i-1} l_{ij} y_j$ * **Solving $Ux = y$:** $x_i = (y_i - \sum_{j=i+1}^{n} u_{ij} x_j) / u_{ii}$ * **Exam Point:** Efficient for solving multiple systems with the same matrix $A$ but different vectors $b$. Avoids explicit matrix inversion. Requires careful implementation, especially with pivoting. * **[Figure: LU Decomposition Matrix Structure]** This figure would show the block structure of $L$ and $U$ matrices, emphasizing the lower and upper triangular forms. It's important for visualizing the decomposition process and the subsequent forward/backward substitution steps.