Final

Question 1

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

Answer 1

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

Question 2

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

Answer 2

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)

Question 3

Pseudo random numbers

Answer 3

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

Question 4

Monte Carlo Methods

Answer 4

• 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

Question 5

Relative error bound

Answer 5

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

Question 6

Taylor Series approximation x0 of degree n

Answer 6

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

Question 7

Taylor error of degree n

Answer 7

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}

Question 8

Normalized floating point numbers representation

Answer 8

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

Question 9

UFL, OFL, ϵm

Answer 9

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

Question 10

Subnormal floating point numbers representation

Answer 10

m = L, leading digit = 0

Hence smallest = 2^-n.2^L

Question 11

Roundoff error

Answer 11

erel = |fl(x)-x|/|x| ≤ ϵm
abs = |fl(x)-x| ≤  ϵm.|x|

Question 12

Single/double precision ϵm

Answer 12

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

Question 13

Loss of significance

Answer 13

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!

Question 14

Vector norm properties

Answer 14

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

Question 15

Matrix norm properties

Answer 15

||A|| > 0 iff A ≠ 0
||aA|| = |a| ||A|| for all scalars a
||A+B|| ≤ ||A|| + ||B||
\+ submultiplicativity:
||Ax|| ≤ ||A|| ||x||
||AB|| ≤ ||A|| ||B||

Question 16

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

Answer 16

||v||_p = (|v1|^p + ... + |vn|^p)^{1/p}
||v||_1 = |v1| + ... + |vn|
||v||_2 = √(v1^2 + ... vn^2)
||v||_∞ = max(i) |vi|

Question 17

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

Answer 17

||A|| = max(||x||=1) ||Ax||
||A|| = max(||x||) ||Ax||/||x||
||A||_1 = max |column sum|
||A||_∞ = max |row sum|
||A||_2 = max σi

Question 18

Linear system of equations LU solve?

Answer 18

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

Question 19

Linear system of equations partial pivoting?

Answer 19

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

Question 20

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)?

Answer 20

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

Question 21

Condition number

Answer 21

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

Question 22

Condition number relative residual

Answer 22

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

Question 23

Rule of the thumb accuracy cond(A)

Answer 23

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

Question 24

LU partial pivoting guarantee?

Answer 24

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

Question 25

Markov chain

Answer 25

xn = A x_{n-1}

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

Question 26

COO format

Answer 26

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

Question 27

CSR format

Answer 27

rowptr = [i0 i1 ... nnz] (nrow+1 int)
col = [i0 i1 ... ] (nzz int)
data = [# # ...] (nzz double)

Question 28

CSR example
  0  0 1.3
-1.5 .2 0
  5  0  0
  0  0  0
  0 0.3 3

Answer 28

rowptr = [0 1 3 4 4 6]
col = [2 0 1 0 1 2]
data = [1.3 -1.5 .2 5 .3 3]

Question 29

Eigenvalue

Answer 29

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

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

Question 30

Power iteration

Answer 30

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)

Question 31

Power iteration convergence

Answer 31

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

Faster when λ2/λ1 is small

Question 32

Rayleigh coefficient

Answer 32

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

Question 33

Inverse power iteration

Answer 33

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

Question 34

Inverse power iteration convergence

Answer 34

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

Faster when λn/λn-1 is small

Question 35

Shifted Inverse power iteration

Answer 35

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

Question 36

Shifted Inverse power iteration convergence

Answer 36

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

Question 37

Rayleigh Quotient Iteration

Answer 37

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

Question 38

SVD

Answer 38

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

Question 39

Reduced SVD

Answer 39

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

Question 40

Low-rank approximation / error

Answer 40

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

Question 41

Linear least squares pb

Answer 41

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

Question 42

Linear least squares system

Answer 42

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...)

Question 43

Linear least squares normal equations

Answer 43

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

Question 44

Linear least squares SVD

Answer 44

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

Question 45

Interpolation

Answer 45

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)]

Question 46

Interpolation monomials

Answer 46

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

Question 47

Interpolation monomials error

Answer 47

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})

Question 48

Nonlinear equation 1D solve f(x)=0

Answer 48

• 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)

Question 49

System nonlinear equations solve f(x)=0

Answer 49

• 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)

Question 50

Optimization 1D

Answer 50

• 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…)

Question 51

Optimization ND

Answer 51

• 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)