Numerical Analysis / Midterm

🧭 CPSC $302$ Midterm Comprehensive Study Guide

🔹 1. Floating-Point Representation & Error Analysis

1.1 Definition

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

β $equals$ base (commonly $2$ or $10$ )
t $equals$ precision (# of digits in mantissa)
p $is a member of$ [L, U] $equals$ exponent range

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

1.2 Key Properties

Machine epsilon (εₘ):
[
εₘ $equals$ \frac{ $1$ }{ $2$ } β^{ $1$ -t} \quad \text{(for rounding to nearest)}
]
Smallest value such that ( $1$ $plus$ εₘ > $1$ ).
Relative error: $is less than or equal to$ εₘ
Spacing: constant in relative sense, not in absolute sense.
i.e., distance between consecutive representable numbers grows with magnitude.

1.3 Rounding and Chopping

Method	Description	Max Relative Error
Round to nearest	Rounds to closest representable	$is less than or equal to$ ½ ULP $equals$ εₘ
Chop (truncate)	Truncates digits beyond precision	$is less than or equal to$ β^{ $1 minus$ t}

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

1.4 Floating-Point Arithmetic Pitfalls

Cancellation error: subtraction of nearly equal numbers $right double arrow$ significant digits lost.
Exampe:( $1 plus$ ε) $negative 1$ $equals$ ε ) may vanish if ε < machine epsilon.
$right arrow$ 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 $right arrow$ small Δoutput.
- Ill-conditioned ⇢ small Δinput $right arrow$ 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

Type	Description	Example
Roundoff error	due to finite precision	computing $1$ / $3$ in binary
Truncation error	from discretization/approximation	finite difference
Convergence error	stopping iteration early	iteration tolerance not met

Total error $almost equals$ truncation $plus$ roundoff.

2.1 Discretization Example

Using the forward difference formula:
[
f'(x_0) $almost equals$ \frac{f(x_0 $plus$ h) - f(x_0)}{h}
]
Error: ( O(h) $plus$ O(εₘ/h) ).
Optimal h: ( h_{opt} $almost equals$ \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| $equals$ \frac{|b_0 - a_0|}{ $2$ ^n}
]
Convergence: linear with rate ½.
Always convergent if f(a)f(b) < $0 period$

Example (from practice):
After $6$ iterations starting with interval $1$ $right arrow$ length $equals$ $1$ / $2$ ⁶ $equals$ $1$ / $64$ $almost equals$ $0.0156$ .

3.2 Fixed-Point Itraion

Given f(x) $equals 0$ , rewrite as x $equals$ g(x)
Ieraion ( x_{k $positive 1$ } $equals$ g(x_k) ).

Fixed-Point Theorem:
If:

g continuous on [a, b],
g([a, b]) $subset of$ [a, b],
|g′(x)| $is less than or equal to$ k < $1$ on [a, b],

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

If |g′(r)| $is greater than or equal to$ $1$ , divergence may occur.

Common mistake: Using g(x) $equals$ x $minus$ f(x) may violate |g′|< $1 period$
Better: scale or choose g with smaller derivative.

3.3 Neto’s etho

[
_{k $positive 1$ } $equals$ x_k - \frac{f(x_k)}{f'(x_k)}
]

Quadratic convergence if start sufficinty cose nd f′r) $is not equal to 0 period$
If f′ $almost equals$ $0$ near root, may diverge.
Requires evaluating derivative each iteration.

Modified version (constant ervatve d:
[
x{k $positive 1$ } $equals$ x_k -\frac{f(x_k)}{d}
]
$right arrow$ convergent if $0$ < | $1$ $minus$ f′(r)/d| < $1$ $right arrow$ linear.

3. Scan Metod

[x_{k $positive 1$ } $equals$ x_k -f(x_k)\frac{x_k - x_{k- $1$ }}{f(x_k)-f(x_{k- $1$ })}
]

Uses finite-difference approximation of f′.
Sueriner covergece ( $tilde 1.618$ )
Twostartingguessesrequired.

3.5 Comparison

Method	Order	Requires derivative	Guaranteed convergence?
Bisection	$1$ (linear)	No	Ys
ixed-oint	$is less than or equal to 1$	ossibly	If
Secant	$1.618$	No	No
Newton	$2$	Yes	If close enough

3.6 Newton’s Failure Example

For ( f(x) $equals$ x^{ $1$ / $3$ } ):
[
f'(x) $equals$ \frc $1$ }{x^{/ $3$ }},\quad _{k $positive 1$ } $equals$ _k - 3x_ $equals$ -2x_k]
$right arrow$ oscilates, noconvergence to root $0 period$

🔹 4. Numerical Conditioning & Reformulation

4.1 Well vs Ill-conditioned

role: (f) $equals$ ex $1$ ) neax $equals 0 period$
$right arrow$ ( f $0$ ) $equals 0$ ), bt sall chnes in x ie large rative errr $right double arrow$ ill-condtioned.

Reformulate:
[
\frac{e^x- $1$ }{x} $almost equals$ $1$ $plus$ \frac{x}{ $2$ } $plus$ \frac{x^ $2$ }{ $6$ } $plus$ $dot dot dot$
]
Better numerically stable for small x.

4.2 Catastrophic Cancellation

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

�5. Lie lgebaRefreh(for shor nwrs)

51OrtoonalMtrices

( ^Q $equals$ I ).
oumns (and row)orthonormal.
Properties:
- ( ||Qx||₂ $equals$ ||x||₂ )
- ( \det()
- osnuar ivese $equals$ Qᵀ.

52 Diagonlizabiliy

A is iagonalizale if $there exists$ P: (P^{- $1$ }AP $equals$ D ).
Sufficien conditions:
- n distinct eignvalues.
- A symetric (real ase).

5.3 Norm and Trace

Frobenius norm:
[
||A||F $equals$ \sqrt{\sum{ij} |a_{ij}|^ $2$ } $equals$ \sqrt{tr(A^TA)} $equals$ \sqrt{\sum σ_i^ $2$ }
]
Trace identity: tr(AB) $equals$ tr(BA).

5.4 Permutation Matrices

Obtained by permuting rows/cols of identity.
Orthogonal: ( P^T P $equals$ I ).
( ||PA||_F $equals$ ||A||_F ).

5.5 Skew-Symmetric Matrices

Aᵀ $equals$ $minus$ A $right double arrow$ eigenvalues purely imaginary ( $plus or minus$ iλ).
Singular values $equals$ |λ|.

🔹 6. Numerical Integration Recurrence Example (Assignment 1)

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

Stable sice | $minus$ ¼|< $1$ $right double arrow$ eror decays.

🔹 7. MATLAB Vectorization eview

7.1 Vecto Operations

Gal	MATLAB Cmmand
Element-wise product	`x .* y`
Inner product	`dot(x,y)` or `x'*y`
Diagonal matrix from vector	`diag(x)`
Outer product	`x*y'`
(

7.2 Control & Plotting

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

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

7.3 Symbolic & VPA

digits( $100$ ) $right arrow$ 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

Method	Error Reduction per Iteration	Notes
Bisection	½	guaranteed, slow
Fixed Point	$is less than or equal to$ k (< $1$ )	depends on
Secant	$tilde 1.618$ owr	uelner
Neton	$almost equals$ uadatic	fst, eeds drivatve
Modifie Newton const d)	linear	slower but smpler

� 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

Can I classify the type of error (roundoff, truncation, convergence)?
Can I justify whether an algorithm is stable and/or convergent?
Do I know conditions on derivatives that ensure convergence?
Can I apply floating-point rules to predict overflow, underflow, or NaN?
Do I know orthogonality, trace, Frobenius norm, and SVD relations?
Can I recognize or derive U-shaped error vs h plots?
Can I vectorize any MATLAB expression without loops?