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)