Term
|
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
|
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
|
|
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
|
|
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
|
|
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
|
|
Term
| Why does midpoint work exactly for 1, x? |
|
Definition
|
|
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
|
|
Term
| Why don't we generally use bisection? |
|
Definition
|
|
Term
| What would you use to solve a system of nonlinear equations |
|
Definition
|
|
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
- Quadratic Convergence
- 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
|
|
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
|
|
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. |
|
|
