Which statements about the Jacobi and Gauss–Seidel methods for Ax = b are true?

both converge for every starting vector if A is strictly diagonally dominant

the Jacobi method converges for every starting vector iff the spectral radius of its iteration matrix is less than 1

Gauss–Seidel converges for every symmetric positive definite A

both converge for every starting vector if A is strictly diagonally dominant

the Jacobi method converges for every starting vector iff the spectral radius of its iteration matrix is less than 1

Gauss–Seidel converges faster than Jacobi for every matrix A

Gauss–Seidel converges for every symmetric positive definite A

Which statements about orders of convergence are true?

Newton–Raphson converges quadratically to a simple root

Newton–Raphson converges only linearly to a double root

the secant method has order (1 + √5)/2 at a simple root

Newton–Raphson converges quadratically to a simple root

Newton–Raphson converges only linearly to a double root

the secant method has order (1 + √5)/2 at a simple root

the bisection method converges quadratically

Which statements about Newton–Cotes quadrature are true?

the trapezoidal rule is exact for every polynomial of degree at most 1

Simpson’s 1/3 rule is exact for every polynomial of degree at most 3

the composite trapezoidal rule has error O(h²)

the trapezoidal rule is exact for every polynomial of degree at most 1

Simpson’s 1/3 rule is exact for every polynomial of degree at most 3

the composite trapezoidal rule has error O(h²)

the composite Simpson rule has error O(h³)

Numerical Analysis: Linear Systems, Non-linear Equations, Interpolation, Quadrature and IVPs

Numerical Analysis is Section 8 of the GATE Mathematics (MA) paper and its most arithmetical: nearly every question is one or two steps of a named method, followed by a question about its error or its convergence. The section runs through five topics, and this chapter takes them in order: direct methods for linear systems (Gaussian elimination, LU and Cholesky), the iterative methods of Jacobi and Gauss–Seidel with their convergence for diagonally dominant matrices; the bisection, secant, Newton–Raphson and fixed-point methods for non-linear equations, with their orders of convergence; Lagrange and Newton interpolation with the interpolation error; numerical differentiation, the trapezoidal and Simpson rules, Newton–Cotes and composite rules and their errors; and Euler’s method and the second-order Runge–Kutta method for initial value problems. Two things decide most MSQs: the order of each method, and the degree of polynomial each rule integrates exactly.

1. Direct methods: Gaussian elimination, LU and Cholesky

Gaussian elimination reduces Ax = b to an upper triangular system in about 2n³/3 operations and back-substitutes in n². Recording the multipliers gives LU decomposition A = LU (Doolittle: L unit lower triangular), which exists without pivoting when all leading principal minors are non-zero; partial pivoting (largest pivot in the column) gives PA = LU for every invertible A and controls round-off. Cholesky: A = LLᵀ with L lower triangular and positive diagonal exists iff A is symmetric positive definite, at half the cost of LU.

Doolittle for [[2, 1, 1], [4, 3, 3], [8, 7, 9]]: multipliers l₂₁ = 2, l₃₁ = 4 give rows (0, 1, 1) and (0, 3, 5); then l₃₂ = 3 and u₃₃ = 5 − 3 = 2. So U = [[2, 1, 1], [0, 1, 1], [0, 0, 2]] and det A = 2 · 1 · 2 = 4.
Cholesky for [[4, 2], [2, 5]]: l₁₁ = √4 = 2, l₂₁ = 2/2 = 1, l₂₂ = √(5 − 1²) = 2.

2. Iterative methods: Jacobi and Gauss–Seidel

Split A = D + L + U (diagonal, strictly lower, strictly upper). Jacobi: x^(k+1) = D⁻¹(b − (L + U)x^(k)), iteration matrix T_J = −D⁻¹(L + U). Gauss–Seidel uses each new component at once: x^(k+1) = (D + L)⁻¹(b − Ux^(k)), T_GS = −(D + L)⁻¹U. A stationary iteration converges for every starting vector iff the spectral radius ρ(T) < 1, and the error shrinks roughly by ρ(T) per step.

If A is strictly diagonally dominant by rows (|aᵢᵢ| > Σ_j≠i |aᵢⱼ|), both Jacobi and Gauss–Seidel converge for every x⁽⁰⁾. If A is symmetric positive definite, Gauss–Seidel converges.
For A = [[4, 1], [2, 5]]: T_J = [[0, −1/4], [−2/5, 0]] has eigenvalues ±√(1/10), ρ ≈ 0.316; T_GS = [[0, −1/4], [0, 1/10]], ρ = 0.1 = ρ(T_J)². For 2 × 2 (and consistently ordered) matrices, Gauss–Seidel converges twice as fast.

⚠️ Gauss–Seidel is not always the faster one

There are matrices for which Jacobi converges and Gauss–Seidel diverges, and the reverse; diagonal dominance is a sufficient condition, not a necessary one. The statement “Gauss–Seidel always converges faster than Jacobi” is false in general and true only for special classes such as the 2 × 2 case above.

3. Non-linear equations

The four root-finders
Method	Step	Order of convergence
bisection	halve [a, b] keeping a sign change	linear; interval length (b − a)/2ⁿ after n steps
secant	xₙ₊₁ = xₙ − f(xₙ)(xₙ − xₙ₋₁)/(f(xₙ) − f(xₙ₋₁))	(1 + √5)/2 ≈ 1.618 at a simple root
Newton–Raphson	xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ)	2 at a simple root; linear with ratio (m − 1)/m at a root of multiplicity m
fixed point x = g(x)	xₙ₊₁ = g(xₙ)	linear with ratio \|g′(α)\| if 0 < \|g′(α)\| < 1; order p if g′ = … = g^(p−1) = 0 ≠ g^(p) at α

Newton on f = x³ − 2x − 5 from x₀ = 2: f(2) = −1, f′(2) = 10, so x₁ = 2.1. Newton on x² − 2 from 1: 1.5, 1.41667, 1.4142157, doubling the correct digits each step.
Secant on x² − 2 from x₀ = 1, x₁ = 2: x₂ = 2 − 2 · 1/(2 − (−1)) = 4/3.
For x² − x − 2 = 0 (root 2): g = √(x + 2) has g′(2) = 1/4 and g = 1 + 2/x has g′(2) = −1/2, both converge; g = x² − 2 (g′ = 4) and g = 2/(x − 1) (g′ = −2) repel. Newton itself is the fixed-point method g = x − f/f′, with g′(α) = 0 at a simple root.

4. Polynomial interpolation and its error

Through n + 1 points with distinct nodes x₀, …, xₙ there is exactly one polynomial pₙ of degree ≤ n. Lagrange form: pₙ = Σ yᵢℓᵢ(x), ℓᵢ = Π_j≠i (x − xⱼ)/(xᵢ − xⱼ). Newton form: pₙ = f[x₀] + f[x₀, x₁](x − x₀) + … + f[x₀, …, xₙ](x − x₀)⋯(x − xₙ₋₁), with divided differences f[x₀, …, xₖ] = (f[x₁, …, xₖ] − f[x₀, …, xₖ₋₁])/(xₖ − x₀); adding a node adds one term. For the data (0, 1), (1, 3), (2, 7): f[0, 1] = 2, f[1, 2] = 4, f[0, 1, 2] = 1, so p₂ = 1 + 2x + x(x − 1) = x² + x + 1 and p₂(3) = 13.

Interpolation error. If f ∈ Cⁿ⁺¹, then f(x) − pₙ(x) = f⁽ⁿ⁺¹⁾(ξ)/(n + 1)! · Π(x − xᵢ) for some ξ in the span of the nodes and x. Linear interpolation of ln x at 1 and 2 has error at 1.5 at most (max |f″|/2)·|0.5 · (−0.5)| = (1/2)(1/4) = 0.125. Also f[x₀, …, xₙ] = f⁽ⁿ⁾(ξ)/n!, so the n-th divided difference of a polynomial of degree n is its leading coefficient and all higher ones vanish.

5. Numerical differentiation and integration

Differentiation: the forward difference [f(x + h) − f(x)]/h has error −(h/2)f″(ξ), order h; the central difference [f(x + h) − f(x − h)]/(2h) has error −(h²/6)f‴(ξ), order h². Round-off grows like ε/h, so shrinking h indefinitely makes the estimate worse.

Closed Newton–Cotes rules on [a, b], h the spacing
Rule	Formula (one panel)	Error	Exact for degree ≤
trapezoidal	(h/2)[f₀ + f₁]	−(h³/12)f″(ξ); composite −((b − a)h²/12)f″(ξ)	1
Simpson 1/3	(h/3)[f₀ + 4f₁ + f₂]	−(h⁵/90)f⁗(ξ); composite −((b − a)h⁴/180)f⁗(ξ)	3
Simpson 3/8	(3h/8)[f₀ + 3f₁ + 3f₂ + f₃]	−(3h⁵/80)f⁗(ξ)	3

∫₀¹ x² dx with the trapezoidal rule, h = 0.5: (0.5/2)(0 + 2 · 0.25 + 1) = 0.375, against 1/3; the error 0.0417 = (1 · 0.25/12) · 2 matches the formula with f″ = 2.
∫₀¹ x⁴ dx with Simpson, h = 0.5: (0.5/3)(0 + 4 · 0.0625 + 1) = 0.20833, against 0.2; the error 1/120 = (1 · 0.0625/180) · 24 matches with f⁗ = 24. Simpson is exact for x³ even though it was built from a quadratic, because the odd error term cancels by symmetry.

6. Initial value problems: Euler and second-order Runge–Kutta

For y′ = f(x, y), y(x₀) = y₀ with step h: Euler yₙ₊₁ = yₙ + h f(xₙ, yₙ) has local error O(h²) and global error O(h). Second-order Runge–Kutta in Heun’s form (the improved Euler method): k₁ = f(xₙ, yₙ), k₂ = f(xₙ + h, yₙ + hk₁), yₙ₊₁ = yₙ + (h/2)(k₁ + k₂); the midpoint form uses k₂ = f(xₙ + h/2, yₙ + hk₁/2) and yₙ₊₁ = yₙ + hk₂. Both have global error O(h²).

y′ = x + y, y(0) = 1, h = 0.1: Euler gives y₁ = 1 + 0.1 · 1 = 1.1; Heun gives k₁ = 1, k₂ = f(0.1, 1.1) = 1.2, y₁ = 1 + 0.05 · 2.2 = 1.11; the exact y = 2eˣ − x − 1 gives 1.11034.
Stability: on y′ = λy with λ < 0, Euler gives yₙ = (1 + hλ)ⁿy₀, which decays only if |1 + hλ| ≤ 1, i.e. h ≤ 2/|λ|. For y′ = −20y that is h ≤ 0.1; a larger step produces growing oscillations even though the exact solution decays.

Key takeaways

LU needs non-zero leading minors (or pivoting); Cholesky A = LLᵀ exists exactly for symmetric positive definite A.
Jacobi and Gauss–Seidel converge iff ρ(T) < 1, always for strictly diagonally dominant A; for 2 × 2 matrices ρ(T_GS) = ρ(T_J)².
Orders: bisection 1, secant 1.618, Newton 2 at simple roots and linear at multiple roots; fixed-point iteration converges when |g′(α)| < 1.
Interpolation error is f⁽ⁿ⁺¹⁾(ξ)Π(x − xᵢ)/(n + 1)!; the interpolating polynomial is unique and Newton’s form grows one term per node.
Trapezoidal is exact to degree 1 with O(h²) composite error; Simpson to degree 3 with O(h⁴); Euler is first order and RK2 second order.

Practice questions (18)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A real square matrix A has a Cholesky factorisation A = LLᵀ with L lower triangular with positive diagonal if and only if A is
1. symmetric positive definite
2. symmetric
3. invertible
4. diagonally dominant
Show answer
Answer: A — symmetric positive definite
LLᵀ is symmetric, and xᵀLLᵀx = ‖Lᵀx‖² > 0 for x ≠ 0 because L is invertible, so SPD is necessary; conversely the algorithm succeeds exactly when every pivot is positive, which SPD guarantees. [[1, 2], [2, 1]] is symmetric and invertible but indefinite, and has no Cholesky factor.
In the Cholesky factorisation [[4, 2], [2, 5]] = LLᵀ, the entry l₂₂ of L is ____.
Numerical answer — type the value.
Show answer
Answer: 2
l₁₁ = √4 = 2; l₂₁ = a₂₁/l₁₁ = 2/2 = 1; l₂₂ = √(a₂₂ − l₂₁²) = √(5 − 1) = 2. Check: LLᵀ = [[2, 0], [1, 2]][[2, 1], [0, 2]] = [[4, 2], [2, 5]].
In the Doolittle factorisation A = LU (L unit lower triangular) of A = [[2, 1, 1], [4, 3, 3], [8, 7, 9]], the entry u₃₃ of U is ____.
Numerical answer — type the value.
Show answer
Answer: 2
R₂ − 2R₁ = (0, 1, 1) and R₃ − 4R₁ = (0, 3, 5); then R₃ − 3R₂ = (0, 0, 2). So l₂₁ = 2, l₃₁ = 4, l₃₂ = 3 and u₃₃ = 2. Check: det A = u₁₁u₂₂u₃₃ = 2 · 1 · 2 = 4.
Which statements about the Jacobi and Gauss–Seidel methods for Ax = b are true?
1. both converge for every starting vector if A is strictly diagonally dominant
2. the Jacobi method converges for every starting vector iff the spectral radius of its iteration matrix is less than 1
3. Gauss–Seidel converges faster than Jacobi for every matrix A
4. Gauss–Seidel converges for every symmetric positive definite A
Show answer
Answer: A — both converge for every starting vector if A is strictly diagonally dominant; B — the Jacobi method converges for every starting vector iff the spectral radius of its iteration matrix is less than 1; D — Gauss–Seidel converges for every symmetric positive definite A
(1) Diagonal dominance makes ‖T_J‖_∞ < 1 and similarly bounds T_GS. (2) A linear stationary iteration eₖ = Tᵏe₀ tends to 0 for all e₀ iff ρ(T) < 1. (4) is the Ostrowski–Reich theorem. (3) is false: there are matrices where Jacobi converges and Gauss–Seidel diverges.
For A = [[4, 1], [2, 5]], the spectral radius of the Gauss–Seidel iteration matrix −(D + L)⁻¹U is ____.
Numerical answer — type the value.
Show answer
Answer: 0.1
D + L = [[4, 0], [2, 5]] with inverse [[1/4, 0], [−1/10, 1/5]], and U = [[0, 1], [0, 0]], so −(D + L)⁻¹U = [[0, −1/4], [0, 1/10]], an upper triangular matrix with eigenvalues 0 and 0.1. The Jacobi matrix has ρ = √(1/10) ≈ 0.316, and indeed 0.1 = 0.316².
One Gauss–Seidel iteration for 4x + y = 9, x + 3y = 7 from (x, y) = (0, 0), updating x first, gives y₁ = ____ (correct to two decimal places).
Numerical answer — type the value.
Show answer
Answer: 1.58
x₁ = (9 − y₀)/4 = 2.25, and Gauss–Seidel uses it immediately: y₁ = (7 − x₁)/3 = 4.75/3 = 1.583, i.e. 1.58. Jacobi would use x₀ = 0 and give y₁ = 7/3 = 2.33. The exact solution is (20/11, 19/11) ≈ (1.82, 1.73).
Bisection starts on [0, 1]. After n steps the bracketing interval has length 2⁻ⁿ. The least n for which this length is at most 10⁻³ is ____.
Numerical answer — type the value.
Show answer
Answer: 10
2⁻ⁿ ≤ 10⁻³ ⟺ 2ⁿ ≥ 1000. 2⁹ = 512 is too small and 2¹⁰ = 1024 suffices, so n = 10. Bisection gains one binary digit per step whatever the function, which is why its count needs no derivative.
One Newton–Raphson step for f(x) = x³ − 2x − 5 from x₀ = 2 gives x₁ = ____.
Numerical answer — type the value.
Show answer
Answer: 2.1
f(2) = 8 − 4 − 5 = −1 and f′(x) = 3x² − 2 gives f′(2) = 10, so x₁ = 2 − (−1)/10 = 2.1. The root is 2.0946, so one step already has two correct digits.
One secant step for f(x) = x² − 2 with x₀ = 1 and x₁ = 2 gives x₂ = ____ (correct to two decimal places).
Numerical answer — type the value.
Show answer
Answer: 1.33
x₂ = x₁ − f(x₁)(x₁ − x₀)/(f(x₁) − f(x₀)) = 2 − 2 · 1/(2 − (−1)) = 2 − 2/3 = 4/3 = 1.33. Newton from 2 would give 1.5.
Which statements about orders of convergence are true?
1. Newton–Raphson converges quadratically to a simple root
2. Newton–Raphson converges only linearly to a double root
3. the secant method has order (1 + √5)/2 at a simple root
4. the bisection method converges quadratically
Show answer
Answer: A — Newton–Raphson converges quadratically to a simple root; B — Newton–Raphson converges only linearly to a double root; C — the secant method has order (1 + √5)/2 at a simple root
(1) With g = x − f/f′, g′(α) = f(α)f″(α)/f′(α)² = 0 at a simple root. (2) At a root of multiplicity m, g′(α) = 1 − 1/m = 1/2 for m = 2, so the error halves each step; m f/f′ restores order 2. (3) The secant error satisfies eₙ₊₁ ≈ Ceₙeₙ₋₁, giving order the golden ratio. (4) Bisection is linear with ratio 1/2.
Which fixed-point iterations xₙ₊₁ = g(xₙ) converge to the root x = 2 of x² − x − 2 = 0 for every x₀ close enough to 2?
1. g(x) = √(x + 2)
2. g(x) = x² − 2
3. g(x) = 1 + 2/x
4. g(x) = 2/(x − 1)
Show answer
Answer: A — g(x) = √(x + 2); C — g(x) = 1 + 2/x
Each g has 2 as a fixed point; local convergence needs |g′(2)| < 1. (1) g′ = 1/(2√(x + 2)) = 1/4. (2) g′ = 2x = 4. (3) g′ = −2/x² = −1/2. (4) g′ = −2/(x − 1)² = −2. So (1) and (3) converge, (3) with oscillation because g′ < 0.
The polynomial of least degree through (0, 1), (1, 3) and (2, 7) takes the value ____ at x = 3.
Numerical answer — type the value.
Show answer
Answer: 13
Divided differences: f[0, 1] = 2, f[1, 2] = 4, f[0, 1, 2] = (4 − 2)/2 = 1. Newton form: p = 1 + 2x + 1 · x(x − 1) = x² + x + 1, so p(3) = 9 + 3 + 1 = 13. Linear extrapolation from the last two points would give 11.
f(x) = ln x is interpolated linearly at x = 1 and x = 2. The bound max_ξ∈[1,2] |f″(ξ)|/2 · |(x − 1)(x − 2)| on the error at x = 1.5 equals ____.
Numerical answer — type the value.
Show answer
Answer: 0.125
f″ = −1/x², so max |f″| on [1, 2] is 1 at x = 1. |(1.5 − 1)(1.5 − 2)| = 0.25. The bound is (1/2)(0.25) = 0.125. The actual error is ln 1.5 − (ln 2)/2 = 0.4055 − 0.3466 = 0.059, inside the bound.
The composite trapezoidal rule with h = 0.5 applied to ∫₀¹ x² dx gives ____.
Numerical answer — type the value.
Show answer
Answer: 0.375
(h/2)[f(0) + 2f(0.5) + f(1)] = 0.25 × (0 + 0.5 + 1) = 0.375. The exact value is 1/3, and the error 0.0417 equals (b − a)h²f″/12 = 1 × 0.25 × 2/12; the rule overestimates because x² is convex.
Simpson’s 1/3 rule with h = 0.5 applied to ∫₀¹ x⁴ dx gives ____ (correct to four decimal places).
Numerical answer — type the value.
Show answer
Answer: 0.2083
(h/3)[f(0) + 4f(0.5) + f(1)] = (0.5/3)(0 + 4 × 0.0625 + 1) = 1.25/6 = 0.20833, i.e. 0.2083. The exact value is 0.2; the error 1/120 = (b − a)h⁴f⁗/180 = 0.0625 × 24/180, the first power Simpson does not integrate exactly.
Which statements about Newton–Cotes quadrature are true?
1. the trapezoidal rule is exact for every polynomial of degree at most 1
2. Simpson’s 1/3 rule is exact for every polynomial of degree at most 3
3. the composite trapezoidal rule has error O(h²)
4. the composite Simpson rule has error O(h³)
Show answer
Answer: A — the trapezoidal rule is exact for every polynomial of degree at most 1; B — Simpson’s 1/3 rule is exact for every polynomial of degree at most 3; C — the composite trapezoidal rule has error O(h²)
(1) The error term involves f″, which vanishes for linear f. (2) The error involves f⁗, so cubics are integrated exactly; e.g. ∫₀¹ x³ = (1/6)(0 + 4/8 + 1) = 1/4. (3) −(b − a)h²f″/12. (4) is false: the composite Simpson error is −(b − a)h⁴f⁗/180, order h⁴.
For y′ = x + y, y(0) = 1, one step of the second-order Runge–Kutta method in Heun’s form (improved Euler) with h = 0.1 gives y(0.1) ≈ ____.
Numerical answer — type the value.
Show answer
Answer: 1.11
k₁ = f(0, 1) = 1; the Euler predictor is 1 + 0.1 × 1 = 1.1, and k₂ = f(0.1, 1.1) = 1.2; y₁ = 1 + (0.1/2)(1 + 1.2) = 1.11. Euler alone gives 1.1; the exact 2e^0.1 − 1.1 = 1.11034.
Euler’s method is applied to y′ = −20y, y(0) = 1, with a constant step h > 0. The largest h for which the numerical solution does not grow in magnitude is ____.
Numerical answer — type the value.
Show answer
Answer: 0.1
Euler gives yₙ₊₁ = (1 − 20h)yₙ, so |yₙ| does not grow iff |1 − 20h| ≤ 1, i.e. 0 ≤ h ≤ 2/20 = 0.1. At h = 0.1 the iterates alternate ±1; for h > 0.1 they oscillate with growing amplitude, although the exact solution e^−20x decays.