DS310 Exam 1

Compare and contrast truncation error and rounding error in the context of numerical calculations.

• Truncation error happens when an algorithm simplifies or truncates a mathematical process to make it solvable (e.g., approximating sin x ≈ x for small x).

• Rounding error happens when a computer cannot exactly represent a real number in its finite-precision system and must round it (e.g., storing π ≈ 3.141593).

Describe how a floating-point number system is structured.

• A floating-point number is stored as:

  (−1)sign×(1.mantissa)×2exponent(−1)sign×(1.mantissa)×2exponent

• The IEEE single-precision format uses:

  • 1 sign bit

  • 8 exponent bits

  • 23 mantissa (fraction) bits.

• This gives a finite range of representable numbers, spaced unevenly across the real line.

Provide disadvantages to using a floating-point number system for numerical calculations, including underflow, overflow, and roundoff error.

• Overflow: when a result exceeds the largest representable number.

• Underflow: when a result is too small to distinguish from 0.

• Round-off error: when a number cannot be represented exactly and must be rounded.
  These errors can cause instability or incorrect results in numerical algorithms.

Explain what machine precision is and its utility in numerical mathematics.

• Machine precision (εₘₐcₕ) is the smallest number that, when added to 1, produces a number distinguishably greater than 1.

• It measures the granularity of a computer’s number line and helps estimate rounding error accumulation and stability of algorithms.

 Describe what time and space (memory) costs are and how they are measured.

• Time cost: number of computational steps or floating-point operations (flops) needed to complete an algorithm.

• Space cost: amount of memory (number of stored values) required to run the algorithm.

Discuss the tradeoffs between lowering an algorithm’s time cost and lowering its space (memory) cost.

• Reducing time cost often requires storing intermediate results (higher memory).

• Reducing space cost may require recomputation (higher time).
  Efficient algorithms balance these two resources depending on hardware limits.

Describe what the Taylor series states and why it is so useful for function approximation.

• The Taylor series expresses a smooth function as an infinite polynomial expansion around a point a:

  f(x)=f(a)+f′(a)(x−a)+f′′(a)2!(x−a)2+…f(x)=f(a)+f′(a)(x−a)+2!f′′(a)​(x−a)2+…

• Truncating this series gives a Taylor approximation, which allows us to estimate complicated functions using only polynomials—fast and easy for computers to evaluate.

• Describe strategies for converting a difficult problem into one that is more easily solved.

• Use the problem-conversion mantra: “If you can’t solve it, change it into one you can.”

• Break a large or complex problem into simpler parts (e.g., decompose A into L and U).

• Transform nonlinear or dense systems into structured, easier subproblems.

Describe how vectors and matrices are used to represent and describe data in data science and statistics.

• Vectors: represent observations (e.g., [height, weight]) or variables.

• Matrices: organize entire datasets—each row = observation, each column = variable.
  They are the foundation for statistical models, regressions, and distance computations.

List the four requirements of a distance metric.

• Non-negativity: d(x,y) ≥ 0

• Identity: d(x,y)=0 iff x=y

• Symmetry: d(x,y)=d(y,x)

• Triangle inequality: d(x,z) ≤ d(x,y)+d(y,z)

List the defining properties of orthogonal matrices and positive-definite matrices.

• Orthogonal: AᵀA = I → columns are orthonormal; preserves vector lengths.

• Positive-definite: xᵀA x > 0 for all non-zero x.

Explain what a coefficient matrix’s condition number tells us about its corresponding linear system, including its applications in error analysis.

• Condition number: κ(A) = ‖A‖ ‖A⁻¹‖

• Measures sensitivity of Ax = b to input changes.

  • Small κ ≈ well-conditioned → stable, small error amplification.

  • Large κ ≈ ill-conditioned → tiny input errors → large output errors.

Discuss what properties of a coefficient matrix lead to an ill-conditioned problem.

• Nearly singular (determinant ≈ 0).

• Columns are almost linearly dependent.

• Very large differences in magnitude between elements (poor scaling).

Describe what a matrix decomposition is.

• Expressing one matrix as the product of two or more simpler matrices (e.g., A = L U).

• Simplifies solving, inverting, or analyzing A.

Discuss the rationale behind least-squares strategies for solving overdetermined linear systems.

• Overdetermined systems (more equations than unknowns) rarely have exact solutions.

• Least-squares finds the x that minimizes the total squared residuals ‖A x − b‖², giving the best fit line or model.

Explain how a QR decomposition can be used to find a least-squares solution to an overdetermined linear system, including fitting a linear regression model.

• Decompose A = Q R (Q orthogonal, R upper triangular).

• Multiply both sides by Qᵀ: R x = Qᵀ b.

• Solve R x = Qᵀ b by back substitution.

• Produces x that minimizes ‖A x − b‖² and fits a linear regression model.

List key properties of a Householder transform.

• Formula: H = I − 2 vvᵀ / (vᵀv).

• Always symmetric (Hᵀ = H).

• Always orthogonal (HᵀH = I).

• Used to “annihilate” entries below a pivot element while preserving vector norms.

Describe the computational advantages of using a Householder transform to generate an orthogonal matrix.

• Builds Q using fewer flops and less rounding error than Gram-Schmidt.

• Numerically stable and efficient for large n since each reflection eliminates many elements at once.

Define stability in the context of numerical algorithms, including how it differs from conditioning.

• Define stability in the context of numerical algorithms, including how it differs from conditioning.

• Stability: An algorithm is stable if small input or rounding errors produce proportionally small output errors (the algorithm doesn’t amplify noise).

• Conditioning: a property of the problem; stability: a property of the algorithm used to solve it.

Describe how partial pivoting leads to more stable algorithms for an LU decomposition.

• Partial pivoting swaps rows so the pivot (diagonal element) is the largest available in magnitude.

• Prevents division by small numbers and limits propagation of rounding errors, improving numerical stability.

Truncation Error

Error introduced when an algorithm approximates or simplifies a function or calculation in order to obtain a solution more easily.(Example: small-angle approximation)

Rounding Error

Error introduced when a computer approximates a value while performing an algorithm because of finite precision. (Example: rounding π ≈ 3.141593)