Final Flashcards

1
Q

Function? x,y:
n: 1,2,3…
time: e1,e2,e3…
linear-log plot straight line

A

Complexity, exponential
y = a.b^{x} - O(a.b^{x})
log y = log(a) + x.log(b)
^y = ^a + ^b.x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Function? x,y:
h: e1,e2,e3…
error: e1,e2,e3…
log-log plot straight line

A
Error, power function
y = ax^b - O(ax^b)
log y = log(a) b.log(x)
^y = ^a + b.^x
Algebraic convergence (n^-a) / growth (n^a)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Pseudo random numbers

A

o Random pattern o Long period
o Efficiency
o Repeatability
o Portability

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Monte Carlo Methods

A
  • Approximation based on repeated randomized sampling
  • Nondeterministic problems / complicated or high dimensions)
  • Slow convergence of error O(n^{-.5}), but efficiency does not degrade with dimension of pb
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Relative error bound

A

|x-^x|/|x| ≤ 10^{-n+1} if n significant digits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Taylor Series approximation x0 of degree n

A

^f(x) = sum(i=0:n) f^(i)(x0)/i! (x-x0)^i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Taylor error of degree n

A

O(h^{n+1}) where h=(x-x0)

Indeed R = f(x)-^f(x) = sum(i=n+1:∞) f^(i)(x0)/i! (x-x0)^i ≤ f^(n+1)(ξ)/(n+1)! h^{n+1}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Normalized floating point numbers representation

A

x = ± 1.b1b2…bn ⨉ 2^m
m in [L,U]
precision p = n+1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

UFL, OFL, ϵm

A

UFL 2^L
OFL 2^{U+1}(1-2^{-p})
ϵm = distance 1/next = 2^-n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Subnormal floating point numbers representation

A

m = L, leading digit = 0

Hence smallest = 2^-n.2^L

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Roundoff error

A
erel = |fl(x)-x|/|x| ≤ ϵm
abs = |fl(x)-x| ≤  ϵm.|x|
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Single/double precision ϵm

A

Single: ϵm = 2^{-23} ≈ 1e-7
Double: ϵm = 2^{-52} ≈ 1e-16

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Loss of significance

A

Substraction/rounding errors, leads to loss of significant digits.

1.000001000 - 1.000000000
with 10 sig digits gives
= 1.000000000
with 4 sig digits
Divisions work better!
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Vector norm properties

A

||x|| > 0 iff x ≠ 0
||ax|| = |a| ||x|| for all scalars a
||x+y|| ≤ ||x|| + ||y||

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Matrix norm properties

A
||A|| > 0 iff A ≠ 0
||aA|| = |a| ||A|| for all scalars a
||A+B|| ≤ ||A|| + ||B||
\+ submultiplicativity:
||Ax|| ≤ ||A|| ||x||
||AB|| ≤ ||A|| ||B||
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

||v||_p, ||v||_1, ||v||2, ||v||

A
||v||_p = (|v1|^p + ... + |vn|^p)^{1/p}
||v||_1 = |v1| + ... + |vn|
||v||_2 = √(v1^2 + ... vn^2)
||v||_∞ = max(i) |vi|
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

||A||, ||A||1, ||A||∞, ||A||_2

A
||A|| = max(||x||=1) ||Ax||
||A|| = max(||x||) ||Ax||/||x||
||A||_1 = max |column sum|
||A||_∞ = max |row sum|
||A||_2 = max σi
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Linear system of equations LU solve?

A

Factorize A = LU O(n^3)
LUx = b (forward sub Ly=b O(n^2))
Ux = y (backward sub O(n^2))
L with ones diagonal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Linear system of equations partial pivoting?

A

Avoids division by zero: find largest |entry| in the column and swap it with top row. If not possible anyway, singular matrix.

A = PLU
PLUx = b
Solve y: Ly=P^Tb
Solve x: Ux = y

(a11 a12
a21 A22)
= 
( u11   u12
u11.l21  l21.u12+L22U22)
l21 = a21/u11
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q
Solving KU=F
when K(100,100), LU factorization ≈ 1 sec and each solve (forward + backward substitution) ≈ 0.01 sec
How long find 10 different U when (1000,1000)?
A

factorisation x=(1000/100)^3 = 1e3 sec
solve y=(1000/100)^2 0.01 = 1 sec
total = 1e3 + 10 ≈ 1e3 sec

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Condition number

A

Characterizes error amplification.
cond(A) = ||A^-1||.||A||
||Δx||/||x|| ≤ cond(A) ||Δb||/||b||
||Δx||/||x|| ≤ cond(A) ||E||/||A||

22
Q

Condition number relative residual

A

r = b-A^x
For well-conditioned matrices, small r implies small relative error
||Δx||/||x|| ≤ cond(A) ||r||/(||A||.||x||)

23
Q

Rule of the thumb accuracy cond(A)

A

A and b accurate to S decimal digits, cond(A)=10^W, solution will have (S-W) accurate digits (IEEE double = 16 digits)

24
Q

LU partial pivoting guarantee?

A

||r||/(||A||.||x||) ≤ c.ϵm (small relative residual, NOT relative error) regardless of conditioning of the system

25
Q

Markov chain

A

xn = A x_{n-1}

A transition matrix, each entry non-negative probability, columns sum to 1, “from” top “to” left.

26
Q

COO format

A
row = [i0 i1 ... ] (nnz int)
col = [i0 i1 ... ] (nnz int)
data = [ # # ... ] (nnz double)
27
Q

CSR format

A
rowptr = [i0 i1 ... nnz] (nrow+1 int)
col = [i0 i1 ... ] (nzz int)
data = [# # ...] (nzz double)
28
Q
CSR example
  0  0 1.3
-1.5 .2 0
  5  0  0
  0  0  0
  0 0.3 3
A
rowptr = [0 1 3 4 4 6]
col = [2 0 1 0 1 2]
data = [1.3 -1.5 .2 5 .3 3]
29
Q

Eigenvalue

A

A nxn, x≠0 eigenvector, λ eigenvalue: Ax = λx

A = UDU^{-1} diagonalizable, n linearly independent eigenvectors (U = [u1 u2 … ])

30
Q

Power iteration

A
finds the largest λ1
xk+1 = A xk (normalize xk)
xk = λ1^k [⍺1.u1 + ⍺2(λ2/λ1)^k.u2 + ... + ⍺n(λn/λ1)^k.un]
xk converges to ⍺1.u1
cost per iteration O(n^2)
31
Q

Power iteration convergence

A

ek+1/ek ≈ |λ2|/|λ1| (linear)

Faster when λ2/λ1 is small

32
Q

Rayleigh coefficient

A

λ = x.T@A@x / x.T@x

33
Q

Inverse power iteration

A
finds the smallest λn
xk+1 = A^-1 xk
Factorize LUxk+1 = Pxk
solve Ly = Pxk
solve Uxk+1 = y
O(n^2) per iteration
34
Q

Inverse power iteration convergence

A

ek+1/ek ≈ |λn|/|λn-1| (linear)

Faster when λn/λn-1 is small

35
Q

Shifted Inverse power iteration

A
finds λ close to σ
xk+1 = (A-σI)^{-1} xk
B = A - σI
Factorize LUxk+1 = Pxk
Solve Ly = Pxk
Solve Uxk+1 = y
O(n^2) per iteration
36
Q

Shifted Inverse power iteration convergence

A
ek+1/ek ≈ |λc1-σ|/|λc2-σ| (linear) where λc1 closest to σ, λc2 2nd closest to σ
Faster when (λc1-σ)/(λc2-σ) is small
37
Q

Rayleigh Quotient Iteration

A

Shifted Inverse power iteration + update of σ.
Bk = A - σk@I
Compute xk+1…
Update σk = xk+1.T@A@xk+1 / xk+1.T@xk+1
At least quadratic convergence, cost O(n^3) per iteration

38
Q

SVD

A
A = UΣV.T O(n^3)
- col V eigenvec of A.T@A
- col U eigenvec of A@A.T
- σi^2 eigenval A.T@A (sing val)
Singular values are always positive! (A.T@A positive definite)
mxn = mxm mxn nxn
39
Q

Reduced SVD

A
mxn = mxk kxk kxn
k = min(m,n)
40
Q

Low-rank approximation / error

A
A = Σ(i=1:k) σk@uk@vk.T
error = ||A - Ak||_2 = σk+1
41
Q

Linear least squares pb

A

Given m data points, find n coeff (n < m) of the function f(t) that best fits the data (overdetermined system)

42
Q

Linear least squares system

A
Ax ≈ b, min_x ||Ax-b||_2^2
A vandermonde matrix e.g.
f(t) = x0+x1t+x2t^2:
(1 t1 t1^2
1 t2 t2^2...)
43
Q

Linear least squares normal equations

A

A.T@A@x = A.T@b
factorization n^3, solving n^2
can be ill-conditioned, solution only if rank(A)=n

44
Q

Linear least squares SVD

A
x = V@Σ^+@U.T@b
factorization n^3, solving mn
Always solution (unique with Σ^-1 if rank(A)=n)
45
Q

Interpolation

A
m data points, find
f(t) = Σ(j=0:n-1) xj.ɸj(t), n linearly Independent basis functions
Ax = b
Generalized vandermonde matrix mxn:
[ɸ0(t0) ɸ1(t0) ... ɸn-1(t0)
ɸ0(t1) ... ɸn-1(tm-1)]
46
Q

Interpolation monomials

A

p{n-1}(t) = Σ(j=0:n-1) xj.t^j (degree n-1)

47
Q

Interpolation monomials error

A

Points equally spaced on interval length h, function sufficiently smooth, error of the interpolant of degree n-1 is O(h^n) = O(h^{degree+1})

48
Q

Nonlinear equation 1D solve f(x)=0

A
  • Bisection method (no derivatives, one eval per it, linear convergence hk+1 = .5hk)
  • Newton’s method (xk+1 = xk - f(xk)/f’(xk), 2 eval per it, quadratic convergence)
  • Secant method (2 initial guesses, ^f’(xk) = (f(xk)-f(x{k-1}))/(xk-x{k-1}), no need for derivatives, one eval per it, superlinear convergence)
49
Q

System nonlinear equations solve f(x)=0

A
  • Newton’s method (solve J(xk)sk = -f(xk) where J(xk)ij = ∂fi/∂xj, xk+1 = xk + sk, typically quadratic local convergence, costly)
  • Secant method (Broyden) approximate jacobian s.t. ^J(xk+1 - xk) = f(xk+1) - f(xk)
  • Finite difference method (approximate partial derivatives)
50
Q

Optimization 1D

A
  • 1st ord necess cdt: f’(x)=0
  • 2nd ord suff cdt: f’‘(x) > 0
  • Golden section search (guaranteed to converge to global min for unimodal fct, no derivative, 1 eval per it, hk+1 = 0.618 hk linear convergence)
  • Newton’s method (xk+1 = xk-f’(xk)/f’‘(xk), typically quadratic local convergence, 2 eval per it, may fail to converge/or max/saddle…)
51
Q

Optimization ND

A
  • 1st ord necess cdt: ∇f(x)=0
  • 2nd ord suff cdt: Hf(x) pd (nd max, indefinite saddle…)
  • Steepest descent (sk = -∇f(xk), ⍺k=argmin_⍺(f(xk+⍺.sk)), xk+1 = xk + ⍺k.sk, linear convergence)
  • Newton’s method (solve Hf(xk)@sk = -∇f(xk), xk+1 = xk + sk, typically quadratic local conv, need Hessian, high comp cost)