Shared Flashcard Set

Details

Kaushik Qual Questions
Kaushik's Questions from Quals
39
Computer Science
Graduate
03/05/2014

Additional Computer Science Flashcards

 


 

Cards

Term
Define Well-Posedness
Definition
A solution exists, is unique, and depends continuously on problem data
Term

Give an example of a problem that is not well-posed

What condition does it violate

Definition

And ODE (say y'=λy) with no initial value

The solution is not unique

Term
What condition of
Definition
Term

Give examples of ill posed problems that violate conditions:

1. exist

2. depends continuously on problem data

Definition

1. Ax = b when A is singular and b is not in the span of A

2. Differentiation... small change to input can cause large change in solution

Term
Give an example of a problem that is well posed but ill conditioned
Definition
Vandermonde System
Term
Are well-posed and well-conditioned guaranteed to produce and accurate solution
Definition
No, you need well-conditioned problem and a stable algorithm
Term
Does MATLAB backslash produce minimum residual or minimum error
Definition
Assuming this is a direct method, minimum residual
Term
Derive error bound for perturbantion to A in Ax=b
Definition
[image][image]
Term
How can you solve Ax = b?
Definition

Direct Methods: LU, QR

Iterative Methods: Jacobi, Gauss-Seidel

Term
With direct methods, is solution guaranteed to exist for Ax=b?
Definition

If A is nonsingular yes.

If A is singular and b is in the span of A, yes.

Term
If Ax = b is not square, which method would you use?
Definition
QR
Term
For QR, what assumptions do you have for there to be a solution?
Definition
b must be in the span of A
Term
For QR, if b is not in the span of A, what do you do?
Definition
You minimize the residual.
Term
If A is not well conditioned or is rank deficient, which method would you use and why?
Definition
Use the SVD because it always exists
Term
What is numerical quadrature
Definition
Numerical approximation of a definite integral
Term
Suppose you can only do one function evaluation (numerical quadrature), what is the best you can do?
Definition
Midpoint
Term
Why does midpoint work exactly for 1, x?
Definition
[image]
Term
What is Gaussian Quadrature?
Definition
Both the nodes and the weights are optimally chosen to maximize the degree of the resulting quadrature rule.
Term
What is an orthogonal polynomial?
Definition
Two polynomials p and g are orthogonal if [image]
Term
What are Legendre Polynomials
Definition
The first n form an orthogonal basis for Pn-1.  Get them from applying Gram-Schmidt to the monomials and scale so that Pk(1) = 1.
Term
Give some methods for solving nonlinear equations
Definition
Bisection, Newton, Secant
Term
Is Bisection always guaranteed to find a root?
Definition
Yes
Term
Why don't we generally use bisection?
Definition
Only linear convergence
Term
What would you use to solve a system of nonlinear equations
Definition
Newton's method
Term
What is the convergence rate of Newton's method?
Definition
Quadratic if there are no multiple roots
Term
What is a multiple root (in 1D)
Definition
If f(m-1) (x) = 0 and f(m) (x) = 0.
Term
What is a multiple root in n-dimensions?
Definition
At a root x, f(x) = 0, the Jacobian of f(x) is singular, the Hessian of f(x) is singular, and so on.
Term
Good Properties of Newton's method
Definition
  1. Quadratic Convergence
  2. Will definitely converge if it is started close enough to a root

 

Term
Bad Properties of Newton's method
Definition
  • Multiple root -- not quadratic convergence
  • Expensive to find Jacobian, Hessian
  • Expensive to solve (solve system of equations each iteration)
Term
How would you reduce computational complexity of Newton's Method?
Definition
Approximate the derivatives (Jacobian, Hessian)
Term
What would be a disadvantage of a fixed Jacobian in Newton's Method?
Definition
Slower convergence
Term
Suppose the Jacobian is sparse.  Would you still be able to reduce computational cost by fixing the computation?
Definition
No, if it is sparse you can you an iterative method to solve the system
Term
If sparse Jacobian in Newton's method, would you need to iterate for a large number of steps to solve it?
Definition
No, a few iterations will obtain an approximate solution that is good enough
Term
How would you guarantee a solution with Newton's method?
Definition
Damped Newton or Trust Region Methods
Term
What if you are far away from a root with Newton's Method?
Definition
damped Newton will not take full steps when far away from a root, but will be able to take full steps when closer
Term
Given y' = f(y), f(0) = c, how would you solve it?
Definition
Euler's Method
Term
Can you always use central difference over, say, backward difference?
Definition
Compare stencils of PDE that works with Backward Difference, and the Central Difference Formula's stencil.  It should work.
Supporting users have an ad free experience!