GATE Mathematics Numerical Analysis Syllabus

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$.

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$.

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.

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$.

State the classic convergence guarantee for Jacobi and Gauss-Seidel in terms of diagonal dominance.

If $A$ is strictly diagonally dominant, then both the Jacobi and the Gauss-Seidel iterations converge to the solution of $A\vec{x}=\vec{b}$ for any initial guess $\vec{x}^{(0)}$.

Besides strict diagonal dominance, name another standard sufficient condition guaranteeing convergence of the Gauss-Seidel method.

If $A$ is symmetric positive definite, then the Gauss-Seidel iteration converges for any starting vector. (This condition guarantees Gauss-Seidel convergence but not Jacobi convergence in general.)

Is convergence of Jacobi/Gauss-Seidel guaranteed for every system? What governs the actual speed of convergence?

No — convergence is not guaranteed in general; it requires $\rho(T)<1$. The smaller the spectral radius $\rho(T)$ of the iteration matrix, the faster the convergence; the asymptotic error reduction per step is approximately the factor $\rho(T)$.

Why are iterative methods like Gauss-Seidel often preferred over direct methods for very large sparse linear systems?

Iterative methods preserve sparsity (they only need matrix-vector products and never store fill-in), have low memory use, and can reach acceptable accuracy in far fewer than $O(n^{3})$ operations, whereas direct elimination introduces fill-in and costs $O(n^{3})$.

What is the relaxation (SOR) extension of Gauss-Seidel, and what is its purpose?

Successive Over-Relaxation forms $x_i^{(k+1)}=(1-\omega)x_i^{(k)}+\omega\,x_i^{GS}$ with relaxation factor $\omega$. Choosing $1<\omega<2$ can accelerate convergence beyond Gauss-Seidel ($\omega=1$); convergence requires $0<\omega<2$.

Classify the methods Bisection, Newton-Raphson, Secant, and Fixed-Point iteration as either *bracketing* or *open* methods.

Bracketing method: Bisection (needs an interval enclosing the root). Open methods: Newton-Raphson, Secant, and Fixed-Point iteration (they use one or more starting points and do not require a bracket).

State the intermediate value theorem condition that lets the bisection method find a root in $[a,b]$.

If $f$ is continuous on $[a,b]$ and $f(a)\cdot f(b)<0$ (opposite signs at the endpoints), then there exists at least one root $c\in(a,b)$ with $f(c)=0$.

Describe one step of the bisection method.

Compute the midpoint $c=\dfrac{a+b}{2}$ and evaluate $f(c)$. If $f(a)f(c)<0$ the root lies in $[a,c]$, so set $b=c$; otherwise it lies in $[c,b]$, so set $a=c$. Repeat on the halved interval.

What is the order of convergence of the bisection method, and how does the error behave per iteration?

Bisection converges linearly (order $1$) with rate $\frac{1}{2}$: the interval width — and hence the error bound — is exactly halved each step, $\,|e_{n+1}|\leq\frac{1}{2}|e_{n}|$.

How many bisection iterations $n$ are needed to guarantee an error less than a tolerance $\varepsilon$ on an initial interval $[a,b]$?

The error after $n$ steps is at most $\dfrac{b-a}{2^{n}}$, so we need $\dfrac{b-a}{2^{n}}<\varepsilon$, giving $$n>\frac{\ln\!\left(\frac{b-a}{\varepsilon}\right)}{\ln 2}=\log_{2}\!\frac{b-a}{\varepsilon}.$$

List one key advantage and one disadvantage of the bisection method.

Advantage: it is guaranteed to converge (always brackets a root) and is very robust. Disadvantage: it converges slowly (only linearly) and requires an initial sign-change bracket; it cannot find roots of even multiplicity where $f$ does not change sign.

State the Newton-Raphson iteration formula for finding a root of $f(x)=0$.

$$x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})},\qquad f'(x_n)\neq 0.$$

What is the geometric interpretation of the Newton-Raphson method?

Each iterate $x_{n+1}$ is the $x$-intercept of the tangent line to $y=f(x)$ at the point $(x_n,f(x_n))$. The method repeatedly replaces the curve by its tangent and follows it to the axis.

State the order of convergence of the Newton-Raphson method for a simple root.

It converges quadratically (order $2$) near a simple root: the error satisfies $|e_{n+1}|\approx C|e_{n}|^{2}$ with $C=\left|\dfrac{f''(\alpha)}{2f'(\alpha)}\right|$, so the number of correct digits roughly doubles each step.

What is the asymptotic error constant for Newton-Raphson, and what does it depend on?

For a simple root $\alpha$, $\displaystyle\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^{2}}=\left|\frac{f''(\alpha)}{2f'(\alpha)}\right|.$ It depends on the second derivative and first derivative of $f$ at the root.

List two common situations in which the Newton-Raphson method may fail or behave poorly.

(1) If $f'(x_n)=0$ or is very small, the iteration diverges or overshoots. (2) A poor initial guess far from the root can cause divergence, cycling, or convergence to a different root. Also, convergence drops to linear at multiple roots.

How does Newton-Raphson convergence change at a root of multiplicity $m>1$, and how can quadratic convergence be restored?

At a root of multiplicity $m$, ordinary Newton-Raphson converges only linearly with rate $\frac{m-1}{m}$. Using the modified iteration $x_{n+1}=x_n-m\dfrac{f(x_n)}{f'(x_n)}$ restores quadratic convergence.

State the secant method iteration formula for solving $f(x)=0$.

$$x_{n+1}=x_{n}-f(x_{n})\,\frac{x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}.$$ It needs two initial approximations $x_0,x_1$.

How is the secant method derived from Newton-Raphson?

It replaces the derivative $f'(x_n)$ in Newton's formula by the finite-difference (slope of the secant line) approximation $f'(x_n)\approx\dfrac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$, avoiding analytic derivatives.

State the order of convergence of the secant method.

The secant method has superlinear convergence of order $p=\dfrac{1+\sqrt{5}}{2}\approx 1.618$ (the golden ratio): $|e_{n+1}|\approx C|e_n|^{1.618}$.

Compare the secant method and Newton-Raphson in terms of derivatives, function evaluations, and convergence order.

Newton needs $f'$ (two evaluations $f,f'$ per step) and converges with order $2$. The secant method needs no derivative (one new $f$ evaluation per step, reusing the previous value) and converges with order $\approx 1.618$ — slower per step but often cheaper per evaluation.

How does the secant method differ from the *regula falsi* (false position) method, which uses the same formula?

Both use the secant/false-position interpolation formula, but regula falsi keeps the two points bracketing the root (retaining a sign change), guaranteeing convergence. The secant method always uses the two most recent iterates, so it may lose the bracket and even diverge, but converges faster when it does converge.

To solve $f(x)=0$ by fixed-point iteration, how is the problem rewritten, and what is the iteration?

Rewrite $f(x)=0$ as $x=g(x)$ for some iteration function $g$. Then iterate $x_{n+1}=g(x_n)$ starting from $x_0$; a fixed point $\alpha=g(\alpha)$ is a root of the original equation.

State the sufficient condition for convergence of the fixed-point iteration $x_{n+1}=g(x_n)$ near a fixed point $\alpha$.

If $g$ is continuously differentiable near $\alpha$ and $|g'(x)|\leq k<1$ on an interval containing $\alpha$ and $x_0$, then the iteration converges to the unique fixed point $\alpha$ (Contraction Mapping condition). In particular $|g'(\alpha)|<1$ is required for local convergence.

What is the order of convergence of a fixed-point iteration when $g'(\alpha)\neq 0$, and what is the asymptotic error relation?

It converges linearly (order $1$): $\displaystyle\lim_{n\to\infty}\frac{e_{n+1}}{e_n}=g'(\alpha)$, so $|e_{n+1}|\approx|g'(\alpha)|\,|e_n|$. The smaller $|g'(\alpha)|$, the faster the linear convergence.

Under what condition does a fixed-point iteration achieve at least quadratic convergence?

If $g'(\alpha)=0$ (and $g''$ exists), the iteration is at least second-order. Newton-Raphson is exactly the fixed-point scheme with $g(x)=x-\dfrac{f(x)}{f'(x)}$, for which $g'(\alpha)=0$ at a simple root, explaining its quadratic convergence.

How does the sign of $g'(\alpha)$ affect the qualitative behavior of a convergent fixed-point iteration?

If $0<g'(\alpha)<1$, the iterates approach $\alpha$ monotonically (from one side). If $-1<g'(\alpha)<0$, the iterates converge in an oscillating (alternating) manner, spiraling around $\alpha$.