L2b: Basic concepts in numerical computations, continued

Question 1

What should you never write on your own?

Answer 1

People spend their whole life doing this

Question 2

What is A monte Carlo simulation, and what is the use of random numbers for it?

Answer 2

Question 3

What is a simple linear congruential generator?

Is it truely random?

Answer 3

The u’s become more and more uniformly distributed over a large enough sample.

• For specific values of a and n, you can plot u_n against n and see correlation and repeated patterns,
• If I start with a specific seed, I will always get the same sequence of random numbers –> hence the game pseudorandom numbers

Question 4

What is a mapping distribution and how does it allow use to generate a random distribution from a more complex distribution from a sequence of random variables that draw from the uniform distribution?

Answer 4

• Basically if you take any random variable an map its realisations to its cumulative distribution function the resulting random variable generated from here is always uniform –> So we want to invert this

Question 5

Generally what is computational complexity and what notation do we use?

Answer 5

Question 6

What is the computation complexity of the following process?

1. n
2. nlog(n)
   3.exp(n)
3. n²
4. n³

How does this change between 0<-n<=1000 and larger values of n?

Answer 6

Question 7

What are the two main types of computation complexity?

Answer 7

Time Complexity –> measures how the number of computational steps ( operations, comparisons, iterations) grwos with the size of the input n –> about speed and is expressed in Big-O notation.

• Space Complexity –> measure how much memory (RAM, storage etc.) an algorithm needs as the input size n grow –> its about capacity - how much data you need to store during the computation
• Sometimes there is a trade off between the two –> you can use extra memory to make something faster, or use less but it makes it slower –> called the time-space trade-off.

Question 8

What are the concepts “condition number” and “stability” that arise in numerical work?

Answer 8

Question 9

How do we run into a “condition number” problem when solving a system of linear equations Ax=b when A is invertible but very close to being singular but is not?

Answer 9

Question 10

what happens the κ(A) the gets large?

Answer 10

Every time you solve the problem, you will run into this issue (it is independent from the algorithm) –> you would have to reformulate (if you can) the problem to make it go away

• Need to understand that there are problems that just fundamentally amplify errors

Question 11

How is the numerical solution to an ODE a problem with stability?

Answer 11

• there are conditions when it does compute the correct solution (the blue line) but under other conditions the numerical solution “blows up” –> need to know under what conditions you algorithm/numerical method would do this