Math 3607 Topic 2 Review
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Math 3607 Topic 2 Review
Preliminaries
Two Types of Errors
● absolute error
● relative error
Floating-Point Numbers
● binary scientific notation:
士 ╱ f ≠礻(b1) ≠礻(b)2(2) ≠ . . . ≠礻(b)d(d) 、礻E ,
where bi is 0 or 1 and E is an integer.
- d determines the resolution
- the range of E determines the scope or extent
● IEEE Standard (double-precision; 64 bits)
- d ≥ 扌礻 and _fà礻礻 < E < fà礻&
- ≥ 礻-52 ≈ 礻 × fà - 16
- realmin, realmax
Floating-Point Numbers
● Key features
- On any interval of the form「礻E , 礻E+1(, there are 礻d evenly-spaced f-p numbers.
- The spacing between two adjacent f-p numbers in「礻E , 礻E+1( is 礻E -d ≥ 礻E .
- The gap between 1 and the next f-p number is , the machine epsilon.
- Representation error (in relative sense) is bounded by 1 .
Conditioning (of a problem)
● The condition number measures the ratio of error in the result (or output) to error in the data (or input).
● Recall the definition of condition number κf.x(
● A large condition number implies that the error in a result may be much greater than the round-off error used to compute it.
● Catastrophic cancellation is one of the most common sources of loss of precision.
Stability (of an algorithm)
● When an algorithm produces much more error than can be explained by the condition number, the algorithm is unstable.
Square Linear Systems
Polynomial Interpolation
● Polynomial interpolation leads to a square linear system of equations with a Vandermonde matrix.
Gaussian Elimination and (P)LU Factorization
● A triangular linear system is solved by backward substitution or forward elimination.
● A general linear system is solved by Gaussian elimination.
● Gaussian elimination (with partial pivoting) is equivalent to (P)LU factorization.
● Solving a triangular linear system of size n × n takes ~ n2 flops.
● PLU factorization takes ~ n2 flops.
Norms
● A norm generalizes the notion of length for vectors and matrices.
● Vector norm
|v|p ≥ ╱ i1 |bi |p \1/p , p ∈「f , &(
and
|v|| ≥ hi(á){ |vi |
● Matrix norm (induced)
|A|p ≥ lxl(h)áp1 |Ax|p , p ∈「f , &ì
● Frobenius norm (matrix)
╱ 、1/2
● MATLAB: norm can calculate both vector and matrix norms
Row and Column Operations
Various row and column operations can be emulated by matrix multiplications. ("Left-multiplication for row actions, right-multiplication for column actions")
● row/column extraction (unit vector)
● row/column swap (elementary permutation matrix)
● row/column rearrangement (permutation matrix)
● row replacement Ri → Ri ≠ cRj (Gaussian transformation matrix)
Conditioning/Stability
● Partial pivoting is needed for numerical stability.
● The matrix condition number is equal to the condition number of solving a linear system of equations.
Programming Notes
● Built-in functionalities
- backslash (\)
- lu
- norm
- cond condest linsolve
● Demonstration/Instructional codes
- backsub and forelim
- GEnp and GEpp
- mylu and myplu
Overdetermined Linear Systems
Polynomial Approximation
● The most common solution to overdetermined systems is obtained by least squares, which minimizes the 2-norm of the residual vector.
● Least squares is used to find fitting functions that depend linearly on the unknown parameters.
● Equivalence of the LLS problem and the normal equation
- linear algebra proof
- calculus proof
QR Factorization
● Orthogonal sets of vectors are preferred to nonorthogonal ones in computing. (no catastrophic cancellation)
● Matrices with orthonormal columns and orthogonal matrices enjoy many nice analytical properties.
● QR factorization plays a role in LLS similar to the of LU factorization for square linear systems.
Two Types of QR Factorization
For A ∈ Rm ×n , m ≥ n:
● Thick QR factorization: A ≥ QR
- Q ∈ Rm ×m orthogonal
- R ∈ Rm ×n upper triangular
- obtained by using successive Householder transformation matrices for triangularization
● Thin: A ≥
- ∈ Rm ×n orthonormal columns
- ∈ Rn ×n upper triangular
- obtained by Gram-Schmidt orthonormalization procedure
Householder Transformation Matrices
● A Householder transformation matrix H (associated with a vector z) is a reflection matrix which is
- symmetric,
- orthogonal, and
- transforms z to |z|2 e1 .
Programming Notes
● Built-in functionalities
- backslash (\)
- qr
● Demonstration/Instructional codes
- lsqrfact: solving least squares using QR
- gs: Gram-Schmidt (for homework)
2022-03-09