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

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

Lemma

A symmetric 2x2 matrix A is…

5 points

A
  • positive definite iff |A| > 0 and a > 0
  • positive semidefinite, not definite iff |A| = 0 and a + c ≥ 0
  • negative definite iff |A| > 0 and a < 0
  • negative semidefinite, not definite iff |A| = 0 and a + c ≤ 0
  • indefinite iff |A| = 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
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
3
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
4
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
5
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
6
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
7
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
8
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
9
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
10
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
11
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
12
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
13
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
14
Q

Knowledge

d-dimensional Midpoint Rule Error Bounds

2 points

A
  • N = nᵈ
  • O(N^(-2/d))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Knowledge

d-dimensional Simpson’s Rule Error Bounds

2 points

A
  • N = nᵈ
  • O(N^(-4/d))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
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(R) if x ∈ R otherwise p(x) = 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
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
18
Q

Lemma

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

2 points

A
  • V / n for a constant V
  • V can be estimated by ∑ᵢ f(Xᵢ) + ∑ᵢ f²(Xᵢ)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
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
20
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
21
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
22
Q

Knowledge

IEEE 254 Double Precision Standard

4 points

A
  • 52 bits for m
  • 11 bits for e
  • 1 bit for sign
  • ε = 2⁻⁵³ ≈ 10⁻¹⁶
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Knowledge

Truncation Error

A

Approximating an infinite process by a finite one

24
Q

Knowledge

Roundoff Error

A

Approximating a real number for example in floating point format

25
Q

Definition

Linear Convergence

2 points

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

Definition

Sublinear Convergence

2 points

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

Definition

Logarithmic Convergence

3 points

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

Definition

Superlinear Convergence

2 points

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

Definition

Order-k Convergence

2 points

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

Lemma

If xₙ converges with order q, then …

A

x₂ₙ converges with order q²

31
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
32
Q

Knowledge

Interval Bisection Error Analysis

2 points

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

Knowledge

Newton’s Method (1 dimension)

2 points

A
  • Approximate f by its first-order Taylor polynomial
  • xₙ₊₁ = xₙ - f(xₙ)/f’(xₙ)
34
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

35
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
36
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

37
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
38
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ₙ₋₁))
39
Q

Knowledge

Secant Method Error Analysis (1 dimension)

2 points

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

Knowledge

Halley’s Method

4 points

A
  • Second-order Taylor approximation
  • Cubic convergence under certain conditions
  • Second-order polynomial may have zero or two roots
  • Solving second-order polynomials requires the slow square-root function
41
Q

Knowledge

Muller’s Method

5 points

A
  • Tracks three points on the function, interpolating them by a parabola
  • Second-order polynomial may have zero or two roots
  • Solving second-order polynomials requires the slow square-root function
  • Allows complex roots so may converge to a complex number
  • Order of convergence ~1.84
42
Q

Knowledge

Inverse Quadratic Interpolation

3 points

A
  • Fit x = ay² + by + c
  • Always has exactly one real solution to y = 0
  • Order of convergence ~1.84
43
Q

Knowledge

Brent’s Method

3 points

A
  • Global convergence
  • Linear convergence for badly-behaved functions and order ~1.84 for well-behaved
  • Keeps track of three values, using IQI, but then Secant method if IQI tries to go outside the bracket and then interval bisection if neither provide sufficient reduction in the bracket size
44
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³)
45
Q

Knowledge

Broyden’s Method

6 points

A
  • Track the Jacobian by an approximation
  • xₙ₊₁ = xₙ + ∆x, ĵₙ∆x = -f(xₙ)
  • Computational cost of solving the system is O(d³)
  • Can track ĵₙ⁻¹ for O(d²) computation
  • Converges if started close to an isolated root slower than Newton’s method
  • Limited memory methods reduce space requirement to O(d)
46
Q

Knowledge

f(x) and f(x*) may be indistinguishable when…

A

|x - x*|/|x*| < O(√ε)

47
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
48
Q

Knowledge

Golden Section Search Error Analysis

2 points

A
  • |εₙ| < Φⁿ⁺¹|c₀ - a₀|
  • Linear convergence
49
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ₙ)
50
Q

Knowledge

Backtracking

3 points

A
  • Start with αₙ = α’
  • Repeatedly multiply through by a factor of 0 < ρ < 1 (usually ρ = 1/2) until the step length obeys the Armijo Rule
  • Choose α’ = αₙ₋₁ (gₙ₋₁ᵀdₙ₋₁)/(gₙᵀdₙ)
51
Q

Knowledge

Armijo Rule

2 points

A
  • f(xₙ + αₙdₙ) < f(xₙ) + σαₙgₙᵀdₙ
  • σ in the range 10⁻⁴ to 10⁻¹
52
Q

Knowledge

Coordinate Gradient Descent

A

dₙ = ±eᵢ

53
Q

Knowledge

Gradient Descent

3 points

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

Knowledge

Newton’s Method

3 points

Gradient Descent

A
  • Approximate f by its second-order Taylor polynomial
  • d̲ₙ = -H̲(f)(x̲ₙ)⁻¹ g̲ₙ
  • αₙ = 1
55
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
56
Q

Knowledge

BFGS Method

3 points

A
  • Update an approximate Hessian Ĥₙ
  • dₙ = -Ĥₙ⁻¹ gₙ
  • Shermar-Morrison formula updates an approximate inverse Hessian Ĥₙ⁻¹
57
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 (7 decks)

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