Solving big systems by approximation

Mathematics · Linear Algebra · ages 23-24

Name ______________________ Date ____________

For 3x + y = 8 and x + 2y = 5, a solver gives the guess (2,1). What is the first component of the residual r = b - Ax?
Answer: ______________
For 4x + y = 10 and x + 5y = 11, take one Jacobi step from (0,0). What is the new x?
Answer: ______________
The system 4x + y = 10, x + 5y = 11 is strictly row diagonally dominant, so Jacobi converges from every starting guess.
Circle one: True False
For 4x + y = 10 and x + 5y = 11, take one Jacobi step from (1,2). What is the new y?
Answer: ______________
A nonsingular system lacks strict row diagonal dominance. Its Jacobi iteration matrix has eigenvalues 0.4 and -0.4. Jacobi must fail to converge to the solution from some starting guesses.
Circle one: True False
Why do symmetry and positive definiteness support the standard CG guarantee for a real system Ax = b?
- Symmetry alone gives strict convexity and a unique energy minimum.
- Positive diagonal entries make the energy strictly convex, so symmetry need not be checked.
- They give the energy gradient Ax - b and a unique minimum at the solution.
For 6x + 2y = 30 and x + 4y = 12, the first Jacobi guess from (0,0) is (5,3). What is x after the second step?
- 5.00
- 4.00
- 3.00
Use one Gauss-Seidel step on 6x + y = 12, x + 4y = 8, starting at (0,0). Update x first, then y. What is the new pair?
- (2,2)
- (1.5,2)
- (2,1.5)
- (1.5,1.5)
For an SPD system, which claim about an SPD preconditioner used with preconditioned CG is accurate?
- If it reduces the eigenvalue ratio, fewer iterations must outweigh the added cost of solving with M.
- It can improve the spectrum and convergence, but a faster solve is not guaranteed.
- It changes the exact solution, so the last iterate needs a correction.
A has rows (3,-1) and (-1,3), and eigenvalues 2 and 4. Which statement correctly checks the standard CG assumptions?
- The negative off-diagonal entries make A indefinite.
- A is symmetric and both eigenvalues are positive, so it is positive definite.
- The positive diagonal entries alone prove that A is symmetric positive definite.
- The positive eigenvalues prove the CG assumptions without needing to check whether A equals its transpose.

Answer key

For grown-ups. Fold this page away before handing over the rest.

Solving big systems by approximation W1-mt_FKkxKYVGYJ-s1

1 · The first row gives 3 times 2 + 1 = 7. Subtract from its right-hand side: 8 - 7 = 1.
2.5 · Use old y = 0 in x_new = (10 - y_old)/4. This gives 2.5.
True · In both rows, the absolute diagonal entry exceeds the sum of the absolute off-diagonal entries.
2 · Jacobi uses old x = 1, so y_new = (11 - 1)/5 = 2.
False · The spectral radius is 0.4 < 1, so Jacobi converges from every start. Strict row diagonal dominance is sufficient, not necessary.
They give the energy gradient Ax - b and a unique minimum at the solution. · Symmetry gives the gradient Ax - b. Positive definiteness makes the quadratic energy strictly convex, with a unique minimum solving Ax = b.
4.00 · Use the previous guess's y value 3: x_new = (30 - 2 times 3)/6 = 4.
(2,1.5) · First x_new = 12/6 = 2. Then use that fresh x: y_new = (8 - 2)/4 = 1.5.
It can improve the spectrum and convergence, but a faster solve is not guaranteed. · Useful preconditioning can improve spectral properties and convergence. Improvement is not automatic, and preconditioner solves also cost work.
A is symmetric and both eigenvalues are positive, so it is positive definite. · The matching off-diagonal entries establish symmetry. Both eigenvalues are positive, so this symmetric matrix is positive definite.