TWiki> Rob Web>InternalNotes>ClassCs450NumericalAnalysis (24 Apr 2008, RobBlake)EditAttach
Class Webpage: https://femto.cs.uiuc.edu/courses/2006F_CS450/

Download lecture notes here: http://www.cse.uiuc.edu/heath/scicomp/notes/

Chapter 1:

  1. What does it mean for an algorithm to be stable?
  2. What does it mean for a problem to be well conditioned?
  3. What does it mean for a problem to be well posed?
  4. Are well posed problems always well conditioned?
  5. Are well conditioned problems always well posed?
  6. If you apply a stable algorithm to a well conditioned problem will you get a relatively accurate solution?
  7. What is the absolute forward error? backward error?
  8. What is the relative forward error? backward error?
  9. What is the relative backward error of approximating cos(x) with 1 + 0.5*x2 at x = π/8 ?
  10. What is the difference between data error and computational error?
  11. What is the difference between truncation error and rounding error?
12. What is the condition number of a problem? 13. How does conditioning relate to forward and backward error? 14. What is machine precision? Underflow? Overflow? 15. When does 1 + a = 1 in floating point? Does this mean a = 0 in floating point? 16. What limits the accuracy of addition, subtraction, multiplication, division of machine numbers? 17. Which operations can result in overflow? underflow? 18. What is cancellation? 19. Which is most accurate: 1/x - 1/(x+1) or 1/(x(x+1)) ? When x =~ 0 or x =~ -1 ? How about for |x| larger than 1 / epsmach ?

Chapter 2

  1. When does A x = b have a solution? a unique solution?
  2. What does it mean for a matrix A to be singular?
  3. If A x = 0 for all x = 0?
  4. If A has rank n, and A is n by n?
  5. There exists B such that A B = B A?
  6. There exists B such that A B = B A = I ?
  7. What is the 1-norm, 2-norm, infinity-norm of a vector?
  8. What is the norm of a matrix in the 1-norm, 2-norm, infinity-norm?
  9. What is the condition number of a matrix? 10. What is the norm and condition number of a diagonal matrix? 11. When does cond(AB) = cond(B)? When A is a scalar? Matrix? 12. How does cond(A) relate to cond(A-1)? 13. How sensitive is the solution to A x = b to changes in A and b? 14. Does a relatively small residual indicate a relatively accurate solution? 15. What is the complexity of computing the LU factorization of A? 16. What is the complexity of forward and back substitution? 17. Does the LU factorization always exist? with row-pivoting? with row and column pivoting? 18. How do we decide when to pivot for partial (row) pivoting? full (row and column) pivoting? 19. Which is more expensive: (1) Computing the LU factorization (with pivoting) of A and solving with forward and back substitution or (2) Computing the inverse of A and multiplying times b? 20. What is the advantage of solving symmetric systems? symmetric positive definite systems? 21. What is the Cholesky factorization? When can it be computed? 22. What is the complexity of computing the LU factorization for a banded system if no pivoting is required?

Chapter 3

  1. When does a linear system of equations have a least-squares solution?
  2. When is the least-squares solution unique?
  3. Suppose a matrix A has more rows than columns, does A x = b have a least-squares solution? Is it unique? If A has more columns than rows?
  4. How does the rank of A relate to the existence and uniqueness of a least-squares solution?
  5. What happens when b is in the span of the columns of A?
  6. How does the conditioning of the least squares problem relate to A and the angle between b and the span of the columns of A?
  7. What are the normal equations?
  8. What do the normal equations tell us about the least-squares residual and the columns of A?
  9. What is the pseudo-inverse of a matrix? If A is full rank? If A is not full rank? 10. How does the conditioning of the normal equations relate to the condition number of A? 11. What is the QR factorization of a matrix? 12. Why don't we use the LU factorization for solving the least-squares problem? 13. What does it mean for a matrix to be orthogonal? 14. What is a Householder reflection? How is it used to compute the QR factorization? 15. What is a Givens rotation? How is it used to compute the QR factorization? 16. How many Householder reflections (or Givens rotations) are required to reduce a matrix to upper triangular? 17. What is the singular value decomposition of a matrix? 18. Which method is most expensive, normal equations, householder, SVD? 19. Which method is most accurate, normal equations, householder, SVD? 20. What is the 2-norm and 2-norm condition number of a matrix? 21. Given several data points, what is the least-squares fit of a polynomial of the form p(t) = x1 t + x2 t2? 22. What is the first column of a matrix after the first Householder reflection? 23. What is the (1,1) entry of a matrix after the first Givens rotation?

Chapter 4

  1. What is an eigenvalue (eigenvector) of a square matrix?
  2. What is the characteristic polynomial?
  3. For every polynomial, p, is there a matrix with p as its characteristic polynomial?
  4. What is the conditioning of the eigenvalue problem?
  5. What matrices always have well conditioned eigenvalues?
  6. What does it mean for a matrix to be normal?
  7. What does it mean for a matrix to be defective?
  8. Can a normal matrix be defective? Can a defective matrix be normal?
  9. Can a matrix be both non-normal and non-defective? 10. Are symmetric matrices always normal? Always non-defective? 11. What is a similarity transformation? 12. What is a unitary matrix? Similarity transformation by a unitary matrix? 13. For real matrices, how close can we get to diagonal using orthogonal similarity transformations? 14. What about with unitary similarity transformations? And with a general similarity transformation? 15. What is the real schur form of a matrix? 16. What is the general schur form of a matrix? 17. What is the power method? Inverse iteration? 18. To which eigenvector does the power method converge? 19. To which eigenvector does the inverse iteration converge? 20. Perform one step of the normalized power iteration with a small matrix. 21. Why do we normalize the power iteration with the infinity-norm? 22. Perform one step of the normalized inverse iteration with a small matrix. 23. What is the Rayleigh quotient? Compute the Rayleigh quotient for a small matrix and approximate eigenvector 24. Why do we use shifts with power and inverse iterations? 25. What is the Rayleigh quotient iteration? 26. What is the purpose of preliminary reduction to Hessenberg or Tridiagonal form? 27. Why can't we just reduce to diagonal or upper triangular directly? 28. What does Lanczos and Arnoldi produce? 29. What is the QR iteration? To what form does the QR iteration converge?

Chapter 5

  1. When does a function, f(x), have a root?
  2. When is the root of a function well-conditioned?
  3. How does the absolute conditioning of evaluating, f(x), at a root relate to the conditioning of that root?
  4. What is a multiple root of a function?
  5. What is the derivative (at a root) of a function with a multiple root?
  6. What is a fixed point iteration?
  7. What is the convergence rate of a fixed-point iteration?
  8. What is linear, superlinear, and quadratic convergence rates?
  9. How does the number of correct digits in the solution increase with a linear convergence rate? quadratic convergence rate? 10. What is the bisection method? Does it always converge? What is its rate of convergence? 11. Given a fixed point method, xn+1 = xn - 0.5 (xn)2 + 0.5, will it converge to x = 1 if the initial guess is sufficiently close? How about for x = -1 ? 12. What if g'(x) is zero at the fixed point? What about if g'(x) < -1 ? 13. What is Newton's method? What is the rate of convergence for Newton's method? 14. What happens when Newton's method is applied to a function with a multiple root? 15. What is the secant method? What is the advantage of secant method over Newton's method? Disadvantages? 16. What is general idea of Broyden's method? What is the advantage of Broyden's method over Newton? Disadvantage? 17. Perform one step of Newton's method for a small system of equations. 18. What is a trust region? 19. What is damped Newton?

Chapter 6

  1. What is a local minimum of a function? global minimum?
  2. Is the derivative always zero at a local minimum? Is the second derivative always positive?
  3. If the second derivative is positive and the first derivative is zero, is it always a local minimum?
  4. If the second derivative is negative what can we say? What about if the second derivative is zero?
  5. How does the first and second derivative test work in higher dimensions?
  6. What does it mean for a function to be coercive? How about convex?
  7. What does it mean for a set to be convex? What do we know about convex functions on convex sets?
  8. What is the first derivative test for a constrained system?
  9. What is the conditioning of the local minimization problem? How does this relate to the conditioning of the root finding problem for f'(x) = 0 ? 10. What is the steepest descent method? 11. What is the general idea behind the conjugate gradient method? 12. Which methods use a one-dimensional line search? 13. What is Newton's method for the minimization problem? 14. Does Newton's method only converge to local minima in this context? 15. What is general idea of the BFGS method? How is BFGS related to Broyden's method? 16. For what is Gauss-Newton used? 17. Which methods explicitly require solving a linear system of equations at each step? 18. What is the penalty method? How does it work? 19. What is the purpose of a trust-region in an optimization algorithm?

Chapter 7

  1. How many points can we interpolate with an nth degree polynomial?
  2. What is the difference between interpolation and least-squares? When do we use one versus the other?
  3. What is the advantage of using the Monomial vs. Newton vs. Lagrange basis?
  4. What is the disadvantage of using each of these basis representations?
  5. Do all three of these basis representations generate the same polynomial?
  6. What does it mean for a basis representation to allow for the interpolating polynomial to be built incrementally? Which representation allows for incremental construction?
  7. What is the problem with using equally spaced points for polynomial interpolation?
  8. What are the Chebyshev points?
  9. What is Hermite interpolation? Spline interpolation? 10. Which is smoother, Hermite or Spline? 11. How many free parameters does a cubic spline have? 12. What can we enforce with these free parameters? 13. What is a natural cubic spline? periodic cubic spline?

Chapter 8

  1. What is the conditioning of integration? How about differentiation?
  2. Is it a good idea to integrate noisy data? How about differentiate?
  3. What does it mean for a set of quadrature rules to be progressive?
  4. Which classes of quadrature rules have progressive subsets?
  5. What is Newton-Cotes quadrature? How are the nodes and weights determined?
  6. What is Gauss quadrature? How are the nodes and weights determined?
  7. What does it mean for a quadrature rule to be open? How about closed?
  8. Which quadrature rules are open? Which are closed?
  9. What is an advantage of using an open rule? 10. What is a composite quadrature rule? 11. Apply the composite midpoint (or trapezoid) rule to some tabulated data (or to a given function. 12. What is the degree of a quadrature rule? 13. What is the degree of an n-point Newton-Cotes rule? How about a Gauss rule? 14. What is the forward difference approximation to the first-derivative? How about backward difference? And centered difference? 15. What is the centered difference approximation to the second-derivative? 16. Apply the forward/backward/centered difference formula to tabulated data (or to a given function). 17. What is Richardson extrapolation? Why is it useful? 18. Apply Richardson extrapolation to some function of order hp with given results for two different values of h.

Chapter 9

  1. What does it mean for a system of initial value problem (IVP) ordinary differential equations (ODEs) to have stable solutions?
  2. Consider the coupled system du/dt = c w and dw/dt = u, where c is a constant. For what values of c is this system stable?
  3. Consider the coupled system du/dt = a u + b w and dw/dt = c w, where a, b, and c are constants. For what values of a,b,c is this system stable?
  4. Given a linear system of ODEs, dx/dt = A x, where A is a matrix and x(t) is a vector for each value of t. When is this stable?
  5. Consider the linear system of ODEs above, what is the condition for forward Euler to be stable? How about backward Euler?
  6. Apply one step (or two steps) of forward or backward Euler to any of the ODEs given above.
  7. What is the trapezoid rule? When is the trapezoid rule stable for linear systems?
  8. Given a higher-order ODE, how do you convert it into first-order form and find the stability?
  9. What is the difference between stable and asymptotically stable? 10. How do we determine stability for nonlinear systems? 11. What is a Runge-Kutta method? What is a multistep method? 12. What is the advantage of using an implicit method? Cost per step? Stability? Accuracy? 13. What is a stiff differential equation?

Chapter 10

  1. What is a boundary value problem?
  2. How is the conditioning of the boundary value problem (BVP) related to growing and decaying modes?
  3. Describe the steps involved in applying a shooting method. What is the dimension of the system of equations that must be solved?
  4. Describe the steps involved in applying a finite difference method. What is the dimension of the system of equations that must be solved?
  5. Describe the steps involved in applying a collocation method. What is the dimension of the system of equations that must be solved?
  6. What does it mean for a BVP to be linear? Have separated boundary conditions?
  7. Approximate the solution to a BVP using a three-point finite difference approximation (i.e., one interior point).
  8. Approximate the solution to a BVP using collocation with a quadratic polynomial (i.e., three unknown coefficients).

Chapter 11

  1. What is the advection equation? What is the solution to the advection equation?
  2. What is the heat equation? Is the heat equation parabolic, elliptic, or hyperbolic?
  3. What is the wave equation? Is the wave equation parabolic, elliptic, or hyperbolic?
  4. What is the laplace equation? Is the laplace equation parabolic, elliptic, or hyperbolic?
  5. What class of PDEs have solutions which are evolving toward a steady state solution: parabolic, elliptic, or hyperbolic?
  6. What class of PDEs have solutions which are not evolving toward any steady state: parabolic, elliptic, or hyperbolic?
  7. What class of PDEs has as its solution the steady state solution: parabolic, elliptic, or hyperbolic?
  8. What are characteristics of a PDE? What are the characteristics for the advection equation?
  9. How do characteristics help to determine if boundary conditions are properly specified? 10. How does semi-discretization work in the method of lines? 11. Approximate the solution to a simple 2D PDE using centered differences and only one unknown interior point. 12. Compute the solution to an advection equation at some point in time and space given the initial conditions.

2006-12-08

  • exam in 144 Loomis, 8:00 AM on te 12th.

chapter 1:

  • stable algo + well-posed = =good solution?
  • truncation error - error using exact arithmetic
  • conditioning = (forward error)/(backwards error)
  • add/sub can result in underflow: 1e-20 - 1.01e-20, so can mul/div

chapter 2:

  • AB = BA does not imply non singular. B=zero matrix
  • cond(A) == cond(inv(A))
  • LU fct alwasy exists with row pivoting, not sure otherwise.
  • When does cond(AB) = cond(B)? When A is a scalar? Matrix?
    • A is scalar * I. Use matrix norm properties, |AB| <= |A| |B|
  • What is the complexity of computing the LU factorization for a banded system if no pivoting is required?
    • both with and without pivoting, O(beta^2*n). Makes sense when Beta == n.
  • Does the LU factorization always exist? with row-pivoting? with row and column pivoting?
    • not without pivoting of some sort.
  • How do we decide when to pivot for partial (row) pivoting? full (row and column) pivoting?
    • partial row: search the column for the max value, pivot rows to move it to the diagonal
    • complete row+col: search n^2 entries, look for max, pivot row and col to move it to the diagonal.
  • What is the advantage of solving symmetric systems? symmetric positive definite systems?
    • symmetric indefinate becomes LDL^T == Jordan form, D has 1x1 or 2x2 blocks. n^3/6 to factorize
    • symmetric pos def becomes LL^T, n^3/6 to factorize.
  • What is the Cholesky factorization? When can it be computed?
    • LL^T, only for sym pos def

chapter 3:

  • existance + uniqueness for least squares soln:
    • always exists
    • only unique if rank(A) = # cols of a.
  • conditioning:
    • b : cond(A)*1/cos
    • E : cond(A)^2*tan + cond(A)
  • psuedoinverse: (A^T*A)^-1*A
  • normal eqns conditioning: cond(A)^2, without the tan. Unstable for stable problems.
  • Why don't we use the LU factorization for solving the least-squares problem?
    • Use QR instead of LU. LU for this problem doesn't minimize in span of A.
  • lookup givens/normal/blah tradeoffs at the bottom of this page. Givens is more expensive if done naively and A is dense.

chapter 4:

  • every matrix has a characteristic polynomial, and every polynomial is the characteristic polynomial for some matrix.
    • Companion metricies.
  • normal => non-defective.
  • Why do we normalize the power iteration with the infinity-norm?

Review session

2006-11-03

Useful matlab commands for the homework

  • polyfit / polyval
  • spline / ppval

Quiz 6 review

golden search linear, C=0.618 direct
successive parabolic interp superlinear, r-1.342 direct
steepest descent linear, with C just less than 1 worst case gradients, line serach
newton quadreatic hessian, line search if far
BFGS superlineaar gradient, line search if far
conjugate gradient ??? gradient, no storage for hessian

Exam Review

  • might have to do one step of OR factorization
  • condition number for functions
  • eigenvalue problem, conditioning (condition bad when eigenvectors ill conditioned.)
  • root problems, bad conditioning when the derivative is 0
  • fl(x+y) can underflow?
  • forward/backward error
  • cancellation

Linear systems

  • conditioning (almost all based on conditioning of A)
  • forward/back substitution.
  • expense costs - inversion > gaussian elimination > infinity norm
  • complexity of solving modified systems
  • norms+conditioning for small problems
  • pivoting, allows you to solve any matis ysstem with gauss elimination
  • why is cholesky better than LU
    • h alf the operations
    • no pivoting

technique cost
Cholesky n^3^/6
LU n^3^/3
Gauss-jordan n^3^/2
inversion n^3^
inverse solve n^2^
LU solve n^2^
Modified problem n^2^
banded decomp b^2^n
Gauss Jordan solve n

Least squares

see pg 144

  • always has a soln
    • only unique when A has full rank.
  • if rhs is nearly orthogonal to span of A, ill conditioned.
  • residual always normal to span(A)
  • know how ot find the residual for triangluar systems
    • qual question - what happens when you do least squares with the one norm?
    • residual ends up not being orthogonal
  • be able to perform a givens rotation
    • what is the 1,1 entry after a householder rotation
      • perserves length
      • need to remember rule about sign
  • homework representative of householder questions
  • don't need to perform SVD or gram schmidt
  • should be ale to calculate psuedo inverse of a matrix with SVD
  • should be ableto perform elimination with given rotations.
  • expense for m ~= n: SVD > givens > householder > normal
  • expense for m >> n: SVD > normal> givens > householder
  • stable: SVD > householder, givens > normal
  • storage cost: svd > givens > householder > normal
  • givens 50% more than householder, 2x storage
  • should be able to solve a 3x2 least squares soln via the normal equations
  • given svd, norms and condition number

eigevalues

1 0
0 1
algebraeic 2, geometric 2
1 1
0 1
algebraeic 2, geometric 1
0 0
0 0
singular, algebareic 2, geometric 2
0 1
0 0
singular, algebraeic 2, geometric 1
  • raleigh quotient
  • know properties of lanczos, arnoldi
  • why do we shift matricies? to accelerate convergence
  • know what QR converges to
A T B
Real symmetric orthogonal Real diagonal
Complex Hermitan Unitary Real diagonal
normal (both real and complex) unitary diagonal
distinct eigenvalues (both real and complex) non-singular diagonal
anything real orthogonal real block triangular
anything unitary Schur (triangular)
anything nonsingular Jordan (almost diagonal)

  • |d_lambda| < 1/cos(theta) * norm_2(E), theta is angle b/w left, right eigenvalues
  • |d_lambda| < cond(eigenvectors)*norm_2(E)

root finding

  • know how fast bisection method
  • know rate of convergences
  • now newton's method
  • jacobian
  • condition number for root finding (1/deriv)
  • one step of
    • newton's method
    • fixed point iteration
    • secant
  • know fixed point iterations and how the derivative of them effects cocvergence

2006-08-30

http://www.cse.uiuc.edu/eot/ Look up floating point systems.

2006-08-23

First class in intro to Numerical Analysis!

Class Webpage: https://femto.cs.uiuc.edu/courses/2006F_CS450/

First homework due sept 6.

Download lecture notes here: http://www.cse.uiuc.edu/heath/scicomp/notes/

Edit | Attach | Print version | History: r8 < r7 < r6 < r5 < r4 | Backlinks | Raw View | Wysiwyg edit | More topic actions
Topic revision: r8 - 24 Apr 2008 - 16:46:08 - RobBlake
 
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback