Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

prelims mathematics and computer science > MCS3: Continuous Mathematics > Flashcards

MCS3: Continuous Mathematics Flashcards

1
Q

Lemma

If g: ℝ → ℝ is a stricly increasing function, then

Optimization Tricks

A

arg min f(x) = arg min g(f(x)) for x ∈ F

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

Lemma

If g: ℝ → ℝ is a 1-1 function, then

Optimization Tricks

A

arg min f(x) = g(arg min f(g(x))) for x ∈ F

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

Knowledge

Midpoint Rule

2 points

A
  • Approximate f: [a, b] → ℝ by 0ᵗʰ-order Taylor polynomial at m
  • M₁[f, a, b] = (b - a)f(m)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Knowledge

Bounds for err(M₁)[f, a, b]

2 points

A
  • Lower bound: -((b - a)³/24)D̅₂
  • Upper bound: -((b - a)³/24)D̲₂
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Knowledge

Trapezium Rule

2 points

A
  • Approximate f: [a, b] → ℝ by its linear interpolation
  • T₁[f, a, b] = ((b - a)/2)(f(a) + f(b))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Knowledge

Bounds for err(T₁)[f, a, b]

2 points

A
  • Lower bound: ((b - a)³/12)D̲₂
  • Upper bound: ((b - a)³/12)D̅₂
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Knowledge

Simpson’s Rule

2 points

A
  • Approximate f: [a, b] → ℝ by quadratic interpolation
  • S₂[f, a, b] = ((b - a)/6)(f(a) + 4f(m) + f(b))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Knowledge

Bounds for err(S₂)[f, a, b]

2 points

A
  • Lower bound: ((b - a)⁵/2880)D̲₄
  • Upper bound: ((b - a)⁵/2880)D̅₄
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Formula

Composite Midpoint Rule

A

Mₙ[f, a, b] = ((b - a)/n)(f((x₀ + x₁)/2) + … + f((xₙ₋₁ + xₙ)/2))

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

Knowledge

Composite Midpoint Rule Error Bounds

2 points

A
  • O(n⁻²)
  • Depends on -f’’
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Formula

Composite Simpson’s Rule

A

Sₙ[f, a, b] = ((b - a)/(3n))(f(x₀) + 4f(x₁) + 2f(x₂) + 4f(x₃) + … + 4f(xₙ₋₁) + f(xₙ))

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

Knowledge

Composite Simpson’s Rule Error Bounds

2 points

A
  • O(n⁻⁴)
  • Depends on f’’’’
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Knowledge

Monte Carlo Integration

4 points

A
  • MCₙ[f, R] = A(R)(1/n)∑f(X̲ᵢ)
  • A(R) is the area or volume of R
  • X̲ᵢ are indpenedently uniformly random on R
  • Pdf is p(x̲) = 1/A if x̲ ∈ R otherwise p(x̲) = 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Lemma

MCₙ[f, r] is unbiased

A

E[MCₙ[f, r]] = ∫ᵣ f(x̲) dx̲

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

Lemma

Var[MCₙ[f, R]] = …

A

V / n for a constant V

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

Lemma

MCₙ[f, R] is consistent

A

P[|err(MCₙ)[f, R]| ≥ ε] → 0 as n → ∞ for any ε > 0

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

Lemma

For large n err(MCₙ)[f, R] approaches

A

N(0, V/n)

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

Knowledge

IEEE 754 Single Precision Standard

4 points

A
  • 23 bits for m
  • 8 bits for e
  • 1 bit for sign
  • ε = 2⁻²⁴ ≈ 6⋅10⁻⁸
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Knowledge

IEEE 254 Double Precision Standard

4 points

A
  • 52 bits for m
  • 11 bits for e
  • 1 bit for sign
  • ε = 2⁻⁵³ ≈ 10⁻¹⁶
20
Q

Knowledge

Truncation Error

A

Approximating an infinite process by a finite one

21
Q

Knowledge

Roundoff Error

A

Approximating a real number for example in floating point format

22
Q

Definition

Linear Convergence

2 points

A
  • εₙ → 0
  • |εₙ₊₁|/|εₙ| → a for 0 < a < 1
23
Q

Definition

Sublinear Convergence

2 points

A
  • εₙ → 0
  • |εₙ₊₁|/|εₙ| → 1
24
Q

Definition

Logarithmic Convergence

3 points

A
  • εₙ → 0
  • xₙ converges sublinearly
  • |εₙ₊₂ - εₙ₊₁|/|εₙ₊₁ - εₙ| → 1
25
Q

Definition

Superlinear Convergence

2 points

A
  • εₙ → 0
  • |εₙ₊₁|/|εₙ| → 0
26
Q

Definition

Order-k Convergence

2 points

A
  • εₙ → 0
  • |εₙ₊₁|/|εₙ|ᵏ → a for a > 0, k > 1
27
Q

Lemma

If xₙ converges with order q, then …

A

x₂ₙ converges with order q²

28
Q

Knowledge

Interval Bisection

4 points

A
  • Let xₙ = (aₙ + bₙ)/2
  • If f(aₙ)f(xₙ) < 0 then (aₙ, xₙ) is a bracket
  • If f(aₙ)f(xₙ) > 0 then (xₙ, bₙ) is a bracket
  • If f(xₙ) = 0 then we have found a root
29
Q

Knowledge

Interval Bisection Error Analysis

2 points

A
  • |εₙ| < (b₀ - a₀)/2ⁿ⁺¹
  • Linear convergence
30
Q

Knowledge

Newton’s Method (1 dimension)

2 points

A
  • Approximate f by its first-order Taylor polynomial
  • xₙ₊₁ = xₙ - f(xₙ)/f’(xₙ)
31
Q

Lemma

Error Analysis for Newton’s Method (1 dimension)

1st Lemma; 2 points

A

Assume f has two continuous derivatives and f(x*) = 0
Let A(c) = max|f’‘(β)|/min|f’(α)| where α, β ∈ I = (x* - c, x* + c)
1. If xₙ ∈ I then |εₙ₊₁| ≤ (A(c)/2)εₙ²
2. If x₀ ∈ I and c A(c)/2 < 1 then xₙ → x* at least quadratically

32
Q

Proof

Assume f has two continuous derivatives and f(x*) = 0
Let A(c) = max|f’‘(β)|/min|f’(α)| where α, β ∈ I = (x* - c, x* + c)
1. If xₙ ∈ I then |εₙ₊₁| ≤ (A(c)/2)εₙ²
2. If x₀ ∈ I and c A(c)/2 < 1 then xₙ → x* at least quadratically

4 points

A
  • Use definition of Newton’s method
  • Use 2nd order Taylor’s remainder term
  • Show |εₙ| ≤ ρⁿ|ε₀| where ρ = c A(c)/2 by induction
  • Apply 1 to inductive hypothesis
33
Q

Lemma

Error Analysis for Newton’s Method (1 dimension)

2nd Lemma; 2 points

A

Assume f has two continuous derivatives and f(x*) = 0
Let B(c) = max|f’‘(β)|/min|f’(α)| where I = (x₀ - 2c, x₀ + 2c)
1. If x* ∈ (x₀ - c, x₀ + c) and c B(c)/2 < 1 then xₙ → x* at least quadratically
2. Such an I exists if f’(x*) ≠ 0

34
Q

Proof

Assume f has two continuous derivatives and f(x*) = 0
Let B(c) = max|f’‘(β)|/min|f’(α)| where I = (x₀ - 2c, x₀ + 2c)
1. If x* ∈ (x₀ - c, x₀ + c) and c B(c)/2 < 1 then xₙ → x* at least quadratically
2. Such an I exists if f’(x*) ≠ 0

5 points

A
  • Deduce |ε₁| < ρc
  • xₙ ∈ (x₀ - 2c, x₀ + 2c)
  • Use induction to show |εₙ| ≤ ρⁿ|ε₀|
  • A(c) → |f’‘(x*)/f’(x*)| as c → 0
  • c A(c)/2 < 1 for sufficiently small c
35
Q

Knowledge

Secant Method (1 dimension)

2 points

A
  • Approximate f by its linear interpolation
  • xₙ₊₁ = xₙ - f(xₙ)(xₙ - xₙ₋₁)/(f(xₙ) - f(xₙ₋₁))
36
Q

Knowledge

Secant Method Error Analysis (1 dimension)

2 points

A
  • Converges under same conditions as Newton’s method
  • Order ~1.62 convergence
37
Q

Knowledge

Newton’s Method (d dimensions)

4 points

A
  • Approximate each component of f̲(x̲) by its first-order Taylor polynomial
  • x̲ₙ₊₁ = x̲ₙ - (J̲(f̲)(x̲ₙ))⁻¹f̲(x̲ₙ)
  • Solve J̲(f̲)(x̲ₙ) Δ̲x̲ = -f̲(x̲ₙ) then set x̲ₙ₊₁ = x̲ₙ + Δ̲x̲
  • Computational cost of evaluating the Jacobian is O(d²) and solving the system is O(d³)
38
Q

Knowledge

Golden Section Search

4 points

A
  • A bracket is an interval (a, b, c) with f(b) < f(a) ∧ f(b) < f(c)
  • If cₙ - bₙ > bₙ - aₙ then z = cₙ - ((√5 - 1)/2)(cₙ - bₙ)
  • If f(b) < f(z) then aₙ₊₁ = aₙ, bₙ₊₁ = bₙ, cₙ₊₁ = z
  • Symmetric for other cases
39
Q

Knowledge

Golden Section Search Error Analysis

2 points

A
  • |εₙ| < Φⁿ⁺¹|c₀ - a₀|
  • Linear convergence
40
Q

Knowledge

Line Search Methods

4 points

A
  • x̲ₙ₊₁ = x̲ₙ + αₙ d̲ₙ
  • d̲ₙ should be a descent direction d(x̲ₙ + α d̲ₙ)/dα (0) = d̲ₙᵀ g̲ₙ < 0
  • d̲ₙ, d̲ₙ₋₁, d̲ₙ₋₂ should not veer wildly in different directions
  • αₙ should loosely minimize f(x̲ₙ + α d̲ₙ)
41
Q

Knowledge

Coordinate Gradient Descent

A

d̲ₙ = ±e̲ᵢ

42
Q

Knowledge

Gradient Descent

3 points

A
  • d̲ₙ = -g̲ₙ
  • O(d) computation for 1 evaluation of df/dx̲
  • Global, linear convergence
43
Q

Knowledge

Newton’s Method

3 points

Gradient Descent

A
  • Approximate f by its second-order Taylor polynomial
  • d̲ₙ = -H̲(f)(x̲ₙ)⁻¹ g̲ₙ
  • αₙ = 1
44
Q

Knowledge

Newton’s Method Error Analysis

2 points

Gradient Descent

A
  • O(d²) derivatives in H̲(f) and O(d³) computation
  • Convergence not always guaranteed and only quadratic when H̲(f)(x̲ₙ) is positive definite near the minimum
45
Q

Knowledge

BFGS Method

3 points

A
  • Update an approximate Hessian Ĥ̲ₙ
  • d̲ₙ = -Ĥ̲ₙ⁻¹ g̲ₙ
  • Shermar-Morrison formula updates an approximate inverse Hessian Ĥ̲ₙ⁻¹
46
Q

Knowledge

BFGS Method Error Analysis

2 points

A
  • O(d³) computation or O(d²) using Shermar-Morrison formula
  • Global, superlinear convergence for well-behaved f

prelims mathematics and computer science (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions