Numerical Analysis / Midterm

🧭 CPSC Midterm Comprehensive Study Guide

🔹 1. Floating-Point Representation & Error Analysis

1.1 Definition

A floating-point number has the form
[
x \pm (d_0.d_1 d_2 d_{t-})_\beta \times \beta^p
]
where:

• β base (commonly or )

• t precision (# of digits in mantissa)

• p [L, U] exponent range

The set of representable numbers is
( F(β, t, L, U) { \pm m \times \beta^p : m \in [β^{t-}, β^t-], p \in [L, U] } ).

1.2 Key Properties

• Machine epsilon (εₘ):
  [
  εₘ \frac{}{} β^{-t} \quad \text{(for rounding to nearest)}
  ]
  Smallest value such that ( εₘ > ).

• Relative error: εₘ

• Spacing: constant in relative sense, not in absolute sense.
  i.e., distance between consecutive representable numbers grows with magnitude.

1.3 Rounding and Chopping

Round-to-nearest always yields smaller average relative error.

1.4 Floating-Point Arithmetic Pitfalls

• Cancellation error: subtraction of nearly equal numbers significant digits lost.
  Exampe:( ε) ε ) may vanish if ε < machine epsilon.
  Use algebraic reformulation (e.g., trigonometric identities or rationalized forms).

• Overflow: |x| > largest representable.

• Underflow: |x| < smallest normalized number.

1.5 Stability vs Conditioning

• Conditioning: property of the problem

  • Well-conditioned ⇢ small Δinput small Δoutput.

  • Ill-conditioned ⇢ small Δinput large Δoutput.

• Stability: property of the algorithm

  • Stable ⇢ behaves as if solving a slightly perturbed problem.

A stable algorithm can still yield poor results if the problem itself is ill-conditioned.

1.6 Typical NaN & Inf Behavior (MATLAB)

Examples:

0/0      % → NaN
Inf - Inf % → NaN
0*Inf     % → NaN
1/0       % → Inf

🔹 2. Error Types and Convergence

Total error truncation roundoff.

2.1 Discretization Example

Using the forward difference formula:
[
f'(x_0) \frac{f(x_0 h) - f(x_0)}{h}
]
Error: ( O(h) O(εₘ/h) ).
Optimal h: ( h_{opt} \sqrt{εₘ} ).
Central difference improves to O(h²).

🔹 3. Root-Finding Methods

3.1 Bisection Method

• Requires sign change over [a, b].

• Each iteration halves interval length:
  [
  |b_n - a_n| \frac{|b_0 - a_0|}{^n}
  ]

• Convergence: linear with rate ½.

• Always convergent if f(a)f(b) <

Example (from practice):
After iterations starting with interval length / ⁶ / .

3.2 Fixed-Point Itraion

Given f(x), rewrite as xg(x)
Ieraion ( x_{k}g(x_k) ).

Fixed-Point Theorem:
If:

1. g continuous on [a, b],

2. g([a, b]) [a, b],

3. |g′(x)| k < on [a, b],

Then unique fixed point exists, convergence is linear with rate k.

If |g′(r)| , divergence may occur.

Common mistake: Using g(x)xf(x) may violate |g′|<
Better: scale or choose g with smaller derivative.

3.3 Neto’s etho

[
_{k} x_k - \frac{f(x_k)}{f'(x_k)}
]

• Quadratic convergence if start sufficinty cose nd f′r)

• If f′ near root, may diverge.

• Requires evaluating derivative each iteration.

Modified version (constant ervatve d:
[
x{k} x_k -\frac{f(x_k)}{d}
]
convergent if < | f′(r)/d| < linear.

3. Scan Metod

[x_{k} x_k -f(x_k)\frac{x_k - x_{k-}}{f(x_k)-f(x_{k-})}
]

• Uses finite-difference approximation of f′.

• Sueriner covergece ()

• Twostartingguessesrequired.

3.5 Comparison

3.6 Newton’s Failure Example

For ( f(x)x^{/} ):
[
f'(x)\frc}{x^{/}},\quad _{k}_k - 3x_ -2x_k]
oscilates, noconvergence to root

🔹 4. Numerical Conditioning & Reformulation

4.1 Well vs Ill-conditioned

role: (f)ex) neax
( f)), bt sall chnes in x ie large rative errr ill-condtioned.

Reformulate:
[
\frac{e^x-}{x} \frac{x}{} \frac{x^}{}
]
Better numerically stable for small x.

4.2 Catastrophic Cancellation

A xrssos lk ( }x ).
eormult using ojugate{te we x le

�5. Lie lgebaRefreh(for shor nwrs)

51OrtoonalMtrices

• ( ^Q I ).

• oumns (and row)orthonormal.

• Properties:

  • ( ||Qx||₂ ||x||₂ )

  • ( \det()

  • osnuar ivese Qᵀ.

52 Diagonlizabiliy

• A is iagonalizale if P: (P^{-}APD ).

• Sufficien conditions:

  • n distinct eignvalues.

  • A symetric (real ase).

5.3 Norm and Trace

• Frobenius norm:
  [
  ||A||F \sqrt{\sum{ij} |a_{ij}|^} \sqrt{tr(A^TA)} \sqrt{\sum σ_i^}
  ]

• Trace identity: tr(AB)tr(BA).

5.4 Permutation Matrices

• Obtained by permuting rows/cols of identity.

• Orthogonal: ( P^T P I ).

• ( ||PA||_F ||A||_F ).

5.5 Skew-Symmetric Matrices

• Aᵀ A eigenvalues purely imaginary (iλ).

• Singular values |λ|.

🔹 6. Numerical Integration Recurrence Example (Assignment 1)

Given:
[
u_n \int_0^ \frac{x^n}{x}derrne:[
_n frc{}n} \fac{}}u_n-}, quad u_ \ln - \ln

Stable sice |¼|< eror decays.

🔹 7. MATLAB Vectorization eview

7.1 Vecto Operations

7.2 Control & Plotting

loglog(h,err,'-*')
semilogy(iter, abs(x - xstar))
legend('Bisection','Newton','Secant')

Use loglog for power-law error scaling (slope order).

7.3 Symbolic & VPA

• digits() set variable precision arithmetic.

• Useful to analyze roundoff vs true error.

• Compare double vs single vs vpa precision.

7.4 Common Numerical Checks

if abs(x_k - x_{k-1}) < tol
    disp('Converged')
end

Use unique() to remove duplicates (for minima problems).
Always confirm algorithm stops when |Δx| < tolerance.

🔹 8. Convergence Speed Summary

� 9. Typical onceptual Quesions

• Differece between stable algorithm and well-conditioned problem.

• Identify which formula causes cancellation and how to fix it.

• Compute number of bisection iterations needed for desired tolerance.

• Explain why Newton’s method may fail for flat derivatives.

• Describe relationship between trace and Frobenius norm.

• State conditions for convergence of fixed-point iteration.

• Evaluate effect of chopping vs rounding on floating-point representation.

• Determine condition number interpretation (sensitivity).

✅ Key Mental Checklist for Exam

1. Can I classify the type of error (roundoff, truncation, convergence)?

2. Can I justify whether an algorithm is stable and/or convergent?

3. Do I know conditions on derivatives that ensure convergence?

4. Can I apply floating-point rules to predict overflow, underflow, or NaN?

5. Do I know orthogonality, trace, Frobenius norm, and SVD relations?

6. Can I recognize or derive U-shaped error vs h plots?

7. Can I vectorize any MATLAB expression without loops?