GATE Mathematics Numerical Analysis Syllabus

Numerical Analysis syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Numerical Analysis in GATE Mathematics, not a summary of it.

1. 1

   Systems of linear equations

   3 topics

   • Direct methods
     • Gaussian elimination
     • LU decomposition
     • Cholesky factorization
   • Iterative methods
     • Gauss-Seidel
     • Jacobi
   • Convergence for diagonally dominant coefficient matrices
2. 2

   Numerical solutions of nonlinear equations

   4 topics

   • Bisection method
   • Secant method
   • Newton-Raphson method
   • Fixed point iteration

Numerical Analysis flashcards for GATE Mathematics

24 of 51 cards from the Numerical Analysis deck — real questions with worked answers.

1. In numerical linear algebra, what is the defining characteristic of a *direct method* for solving a linear system $A\vec{x}=\vec{b}$?

   A direct method computes the exact solution (up to rounding error) in a finite, predetermined number of arithmetic operations, with no iteration or convergence requirement. Examples include Gaussian elimination, LU decomposition, and Cholesky factorization.

2. Contrast direct methods with iterative methods for solving $A\vec{x}=\vec{b}$.

   Direct methods (e.g. Gaussian elimination) terminate after a finite number of steps and give the exact answer barring roundoff. Iterative methods (e.g. Jacobi, Gauss-Seidel) generate a sequence $\vec{x}^{(k)}$ that converges to the solution, requiring a stopping criterion; they are preferred for large sparse systems.

3. State the asymptotic operation count (number of multiplications/divisions) for solving a dense $n\times n$ system by Gaussian elimination.

   It requires approximately $\frac{n^{3}}{3}$ floating-point operations (the $O(n^{3})$ cost dominated by the forward elimination phase), plus $O(n^{2})$ for back substitution.

4. Describe the two phases of Gaussian elimination for solving $A\vec{x}=\vec{b}$.

   (1) Forward elimination: use elementary row operations to reduce $A$ to an upper-triangular matrix $U$ (eliminating entries below each pivot). (2) Back substitution: solve the resulting triangular system $U\vec{x}=\vec{c}$ from the last equation upward.

5. In Gaussian elimination, what is the multiplier used to eliminate entry $a_{ik}$ using pivot row $k$, and how is row $i$ updated?

   The multiplier is $m_{ik}=\dfrac{a_{ik}}{a_{kk}}$ (where $a_{kk}$ is the pivot). Then row $i$ is updated by $R_{i}\leftarrow R_{i}-m_{ik}R_{k}$, which zeroes the entry in column $k$.

6. Why is *partial pivoting* used in Gaussian elimination?

   Partial pivoting swaps rows so the largest-magnitude available entry in the current column becomes the pivot. This avoids division by zero (or by very small pivots), reducing roundoff-error growth and improving numerical stability.

7. What does LU decomposition factor a matrix $A$ into, and what property do the factors have?

   It writes $A=LU$, where $L$ is lower-triangular and $U$ is upper-triangular. In Doolittle's form $L$ has unit diagonal ($l_{ii}=1$); in Crout's form $U$ has unit diagonal.

8. Given the factorization $A=LU$, describe how the system $A\vec{x}=\vec{b}$ is solved.

   Substitute to get $LU\vec{x}=\vec{b}$. First solve $L\vec{y}=\vec{b}$ by forward substitution, then solve $U\vec{x}=\vec{y}$ by back substitution.

9. What is a key advantage of LU decomposition over plain Gaussian elimination when solving $A\vec{x}=\vec{b}_i$ for many right-hand sides?

   The factorization $A=LU$ is computed once at $O(n^{3})$ cost; each new right-hand side then costs only $O(n^{2})$ via forward/back substitution. Plain Gaussian elimination would redo the $O(n^{3})$ work for every right-hand side.

10. State a sufficient condition guaranteeing that a matrix $A$ has an LU decomposition without row interchanges.

    $A$ has an LU factorization (no pivoting needed) if all its leading principal minors are nonzero, i.e. $\det(A_k)\neq 0$ for $k=1,\dots,n$. This is guaranteed, for instance, when $A$ is strictly diagonally dominant or symmetric positive definite.

11. How can the determinant of $A$ be obtained from its LU factorization $A=LU$ (Doolittle form)?

    Since $\det(L)=1$ (unit diagonal), $\det(A)=\det(U)=\prod_{i=1}^{n}u_{ii}$, the product of the diagonal entries of $U$.

12. What is the Cholesky factorization of a symmetric positive definite matrix $A$?

    It is the factorization $A=LL^{T}$, where $L$ is a lower-triangular matrix with positive diagonal entries. Equivalently $A=R^{T}R$ with $R$ upper-triangular.

13. What conditions must a matrix $A$ satisfy to admit a (real) Cholesky factorization?

    $A$ must be symmetric ($A=A^{T}$) and positive definite ($\vec{x}^{T}A\vec{x}>0$ for all $\vec{x}\neq\vec{0}$). Under these conditions the Cholesky factor exists and is unique.

14. How does the cost of Cholesky factorization compare to general LU decomposition for an $n\times n$ system?

    Cholesky requires about $\frac{n^{3}}{6}$ operations — roughly half the cost of LU/Gaussian elimination ($\frac{n^{3}}{3}$) — because it exploits symmetry by computing only one triangular factor.

15. Give the Cholesky formulas for the diagonal entry $l_{jj}$ and off-diagonal entry $l_{ij}$ ($i>j$) of $L$ where $A=LL^{T}$.

    $$l_{jj}=\sqrt{a_{jj}-\sum_{k=1}^{j-1}l_{jk}^{2}},\qquad l_{ij}=\frac{1}{l_{jj}}\left(a_{ij}-\sum_{k=1}^{j-1}l_{ik}l_{jk}\right).$$

16. In Cholesky factorization, what happens numerically if you attempt it on a symmetric matrix that is NOT positive definite?

    The algorithm requires computing $\sqrt{a_{jj}-\sum_{k<j}l_{jk}^{2}}$; for a non-positive-definite matrix this radicand becomes zero or negative, so the square root fails. (This breakdown is itself a numerical test for positive definiteness.)

17. What is the general form of a stationary iterative method based on the splitting $A=M-N$?

    Writing $A=M-N$, the iteration is $M\vec{x}^{(k+1)}=N\vec{x}^{(k)}+\vec{b}$, i.e. $\vec{x}^{(k+1)}=M^{-1}N\vec{x}^{(k)}+M^{-1}\vec{b}$. The matrix $T=M^{-1}N$ is the iteration matrix.

18. State the necessary and sufficient condition for convergence of a stationary iteration $\vec{x}^{(k+1)}=T\vec{x}^{(k)}+\vec{c}$ for any initial guess.

    The iteration converges for every starting vector if and only if the spectral radius satisfies $\rho(T)<1$, where $\rho(T)=\max_i|\lambda_i|$ is the largest absolute eigenvalue of the iteration matrix $T$.

19. For the splitting $A=D+L+U$ (diagonal, strict lower, strict upper parts), write the Jacobi iteration in matrix form.

    $$\vec{x}^{(k+1)}=D^{-1}\left(\vec{b}-(L+U)\vec{x}^{(k)}\right),$$ with iteration matrix $T_J=-D^{-1}(L+U)$.

20. Write the component (scalar) form of the Jacobi iteration for the $i$-th unknown.

    $$x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\neq i}a_{ij}x_j^{(k)}\right).$$ All updates use only old values $x_j^{(k)}$.

21. For the splitting $A=D+L+U$, write the Gauss-Seidel iteration in matrix form.

    $$\vec{x}^{(k+1)}=(D+L)^{-1}\left(\vec{b}-U\vec{x}^{(k)}\right),$$ with iteration matrix $T_{GS}=-(D+L)^{-1}U$.

22. Write the component (scalar) form of the Gauss-Seidel iteration for the $i$-th unknown.

    $$x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\right).$$ It uses already-updated values $x_j^{(k+1)}$ for $j<i$.

23. What is the essential difference between the Jacobi and Gauss-Seidel methods?

    Jacobi computes all new components using only the previous iterate's values (it stores the whole old vector). Gauss-Seidel immediately uses each newly computed component within the same sweep, so it needs only one storage vector and typically converges faster.

24. Define a *diagonally dominant* matrix and a *strictly diagonally dominant* matrix.

    $A$ is (weakly) diagonally dominant if $|a_{ii}|\geq\sum_{j\neq i}|a_{ij}|$ for all $i$. It is strictly diagonally dominant if the inequality is strict, $|a_{ii}|>\sum_{j\neq i}|a_{ij}|$, for every row $i$.

See more Numerical Analysis flashcards →

Planning Numerical Analysis for GATE Mathematics

Numerical Analysis (GATE Mathematics) FAQ