# Chapter 7 notebook: Linear Algebra: Choose Stable Matrix Methods Before Computing

**Goal:** Choose a matrix method from verified structure and report what its residual actually certifies.

**Start with:** Rules 7.1.1, 7.2.4, 7.3.4. Use a calculator or the optional Python lab. Programming is optional for the workbook; the Jupyter version requires a Python 3 kernel. All lab numbers are constructed practice inputs, not observed data.

**Source:** [Finished Chapter 7](../skills/math-thumb-linear-algebra/references/chapter.md) from *Mathematical Rules of Thumb*. Numbered rules, classifications, and the decision path come from the book. The lab, exercises, answer key, and worksheet prompts are companion additions.

## 1. Frame your decision

Write a question in which an answer would change something you do. Gather: Matrix dimensions and structure; right-hand side; scale and conditioning; precision; memory limit; requested residual and forward accuracy.

- My question and intended decision:
- Known inputs and units:
- Required accuracy or threshold:
- What I expect before calculating:
- What I still need to find out:

Use the lab as a worked starting point if you do not yet have your own problem. For notation or prerequisites, ask the chapter skill to explain only the concept blocking the next step.

## 2. Choose a route

- **Start with sensitivity.** Estimate conditioning and the digit budget before setting solver tolerances.
- **Verify claimed structure.** Check relative symmetry, positive definiteness, sparsity pattern, block meaning, and scale before choosing a specialized factorization.
- **Choose the direct method by matrix type.** Use Cholesky for verified SPD systems, pivoted LU for general dense systems, and QR or SVD for least squares according to conditioning and rank.
- **Avoid unnecessary objects.** Solve for inverse actions, apply Schur complements through block solves, and keep orthogonal factors implicit when possible.
- **Budget memory as well as flops.** Consider matrix-free actions, cache blocking, and fill-reducing ordering before the matrix outgrows the machine.
- **Verify outputs.** Scale residuals, inspect orthogonality where relevant, and refine a solve only while backward error continues to improve.
- **For spectra and compression, inspect cheap evidence first.** Use Gershgorin, eigenvalue ratios, storage counts, and singular-value tails before escalating to shift-invert or large decompositions.
- **For Krylov methods, separate problem difficulty from solver design.** Check SPD requirements, conditioning, clustering, preconditioner cost, restart behavior, and true residuals.

**Chapter-specific stop check:** Residual and forward error are different quantities. A low-rank storage win, symmetry claim, or converged iteration must pass its own accuracy or structural check.

## 3. Work the lab

A calculation starts with 12 reliable decimal digits and has a condition estimate of 10^5. A first-pass budget is 12-log10(10^5)=7 digits. Separately, storing a 1,000 by 800 matrix uses 800,000 scalar entries; rank-20 factors use 20 × (1000+800)=36,000, or 4.5% of that storage, excluding overhead. Storage savings do not certify approximation accuracy; inspect the singular-value tail.

Predict the sign and scale before running the code. Then change one input and explain why the result moves. The code checks the constructed example; it does not prove the rule for every possible input. Code assertions may describe the example's chosen regime, so inspect them before changing that regime.

```python
import math
digits, condition = 12, 1e5
rows, columns, rank = 1000, 800, 20
assert condition >= 1 and 0 < rank <= min(rows, columns)
dense_entries = rows*columns
factor_entries = rank*(rows+columns)
print(f"Rough remaining digits: {digits-math.log10(condition):.1f}")
print(f"Dense entries: {dense_entries:,}; factors: {factor_entries:,}")
print(f"Storage fraction: {factor_entries/dense_entries:.3%}")
```

**My prediction, observed result, and explanation:**

_Record your work here._

## 4. Practise without the answers

### Exercise 1

A full-rank least-squares matrix has condition number 10^4. What happens to conditioning in its normal equations?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 2

A symmetric matrix is claimed suitable for Cholesky. Is symmetry alone enough?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 3

A solver has a tiny residual. Can it promise a tiny forward error for an ill-conditioned system?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

**Coaching prompt:** “Use the Chapter 7 skill to help me with Exercise 2. Ask for my attempt, give one useful hint if I need it, and help me check the assumptions before showing the answer.”

## 5. Answer key and reasoning

Read this after attempting the exercises, or use it immediately if you prefer a complete walkthrough. An answer is complete only when its assumptions and stopping point are clear.

### Answer 1

In the 2-norm, kappa(A^T A)=kappa(A)^2=10^8. QR avoids forming that squared-conditioning system; rank uncertainty may motivate SVD.

### Answer 2

No. Positive definiteness is also required. For example diag(1,-1) is symmetric and indefinite.

### Answer 3

No. Residual measures an equation defect; forward error also depends on conditioning and scaling. Report a scaled residual and a sensitivity estimate, or bound the quantity of interest.

## 6. Build the complete chapter toolkit

The new lab samples the chapter; the following checklist covers all 23 rules. Study one thematic group at a time. A large group can take several sessions.

- **Diagnose Accuracy and Structure Up Front:** work with rules 7.1.1, 7.1.2, 7.1.3, 7.1.4, 7.1.5.
- **Match the Algorithm to Matrix Structure:** work with rules 7.2.1, 7.2.2, 7.2.3, 7.2.4, 7.2.5, 7.2.6, 7.2.7, 7.2.8, 7.2.9.
- **Estimate Spectra, Compression, and Iterative Difficulty:** work with rules 7.3.1, 7.3.2, 7.3.3, 7.3.4, 7.3.5, 7.3.6, 7.3.7, 7.3.8, 7.3.9.

For each selected rule, read its equation, explanation, and worked use in the source. Reproduce that example; change one input; then change one assumption so the rule is no longer justified. Record the result and what check catches the failure. Historical examples remain labeled and qualified as in the source.

Read each complete numbered profile in the [chapter reference](../skills/math-thumb-linear-algebra/references/chapter.md) before applying it. The cues below abbreviate the graph metadata; they are not complete conditions. Change the status only after doing the practice described below.

| Rule | Book role | First assumptions to inspect | Practice status |
|---|---|---|---|
| 7.1.1: Estimate digits lost from the condition number | Independent | compatible matrix structure;  scale aware tolerance | new |
| 7.1.2: Check matrix symmetry relative to scale | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.1.3: Certify an eigenpair with its residual | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.1.4: Equilibrate rows and columns with wildly different scales | Workflow | large row or column scale disparity;  recoverable scaling factors | new |
| 7.1.5: Use iterative refinement to recover linear-solve accuracy | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.1: Solve systems instead of forming an explicit inverse | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.2: Use partial pivoting for general dense LU | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.3: Treat Schur complements as first-class operators | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.4: Prefer QR to normal equations for accurate least squares | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.5: Use Cholesky for symmetric positive-definite systems | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.6: Prefer orthogonal transformations for numerical stability | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.7: Go matrix-free when storage dominates arithmetic | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.2.8: Use blocked matrix algorithms to exploit fast BLAS-3 kernels | Workflow | large dense matrices;  level three blas available | new |
| 7.2.9: Reorder sparse factorizations to control fill | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.3.1: Use Gershgorin disks as a cheap eigenvalue screen | Independent | square matrix;  matrix entries known | new |
| 7.3.2: Power iteration speed is set by the eigenvalue ratio | Independent | compatible matrix structure;  scale aware tolerance | new |
| 7.3.3: Use shift-invert for interior or smallest eigenvalues | Specialized | compatible matrix structure;  scale aware tolerance | new |
| 7.3.4: Check low-rank storage before compressing a matrix | Independent | compatible matrix structure;  scale aware tolerance | new |
| 7.3.5: Use the next singular value to price a low-rank approximation | Independent | compatible matrix structure;  scale aware tolerance | new |
| 7.3.6: Define numerical rank relative to the largest singular value | Workflow | compatible matrix structure;  scale aware tolerance | new |
| 7.3.7: Expect conjugate-gradient work to scale with square-root conditioning | Independent | compatible matrix structure;  scale aware tolerance | new |
| 7.3.8: Judge a preconditioner by clustered eigenvalues and total time | Workflow | compatible iterative solver;  affordable preconditioner application | new |
| 7.3.9: Increase GMRES restart when convergence stalls | Specialized | compatible matrix structure;  scale aware tolerance | new |

For a completed row, record: **rule number / my new input / mathematical claim type / verified assumptions / calculation / check / valid use / rejected use / next step**. “Practised” means you worked an example. “Demonstrated” means you can explain a valid use, transfer it, and reject a misuse without the answer key.

## 7. Apply it to your own problem

Return to your opening question. Choose the smallest rule set that can settle it. Use the book's independent/workflow/specialized classification separately from the claim type (exact, approximate, bound, diagnostic, or heuristic).

- Selected rule number(s) and reason:
- Assumptions that hold, fail, or remain uncertain:
- Substitution with units:
- Result and error, uncertainty, or bound:
- Independent check or limiting case:
- Decision this supports:
- Stop here, do a named next calculation, or gather missing information:

## 8. Transfer and continue

Useful nearby chapters: Chapter 19: optimization; Chapter 20: numerical methods; Chapter 21: scientific computing. Bring the question, units, assumptions, result type, and uncertainty to the next chapter. Choose a bridge only when it supplies an operation you actually need.

**Completion check:** Explain this chapter's lab in your own words; solve one changed-input exercise; reject one invalid use; and produce a decision record for your own problem. If one check fails, revisit that part of the chapter rather than marking every rule complete.