GATE Mathematics Numerical Analysis Flashcards

24 sample cards from the Numerical Analysis deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. 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})$.

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

3. 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

What this deck covers

Numerical Analysis flashcards FAQ