1OutlineOutline• Announcements– Add/drop today!– HWI due Friday• Discrete Approximations• Numerical Linear Algebra• Solving ODE’s• Solving PDE’sDiscrete ApproximationsDiscrete Approximations• The defining principle of numericalcomputing:Computers are finite• This has several consequences:– Computers can only hold a finite amount ofdata (limited by memory)– Computers can represent integers exactly,but only over a finite rangeFinite Memory ProblemFinite Memory ProblemxC(x)• Because we can only store a finite amount ofdata, continuous curves or surfaces must beapproximated by storing values at a finitenumber of points• This leads to discretization errors• Can improve the approximation by– adding more points– tracking higher-order properties (e.g. splines)2Finite Precision ProblemFinite Precision Problem• Computers only work with integers• To represent a real number, we use twointegers:– ±m*bp• m=“mantissa”• b=base, set by the system• p=exponent– Limited precision in both mantissa andexponent– Leads to roundoff errorsFinite Precision ProblemFinite Precision Problem• Suppose we are working with base 10numbers, and mantissa and exponenthave 2 digits:– ± xx 10yy– smallest number: 1*10-99• 0.5* 1*10-99 = ??? --Underflow– largest number: 99*1099• 2* 99*1099 = ??? --Overflow– Only 99 numbers in each decade– Only 200*99-1=19,799 numbers!Finite Precision ProblemFinite Precision Problem10 ±308111e-16538Double10 ±3881e-7244Singlerangep(bits)epsm(bits)BytesPrecision3Numerical AnalysisNumerical Analysis• The study of algorithms formathematical problems• concerned with– accuracy– stability– performanceNumerical AnalysisNumerical Analysis• Three big areas (i.e. physics)– Linear algebra– ODE’s/PDE’s– Optimization problems• Other topics– Computational geometry– Numerical integrationNumerical Linear AlgebraNumerical Linear AlgebraLinearAlgebraODEOptimCompGeom.Num.Integr.4Numerical Linear AlgebraNumerical Linear Algebra• Linear Systems• Matrix Factorizations• EigenproblemsSolving Linear SystemsSolving Linear SystemsSolving Linear SystemsSolving Linear Systems5Gaussian EliminationGaussian Elimination• This procedure is known as “GaussianElimination”• for j=1:m-11. Divide row j by its jth entry2. Subtract row j from rows j+1 through mGaussian EliminationGaussian Elimination• GE is also known as “LU factorization”– A=LU where L is lower triangular, U isupper triangular– Ax=b– LUx=b– Solve Ly=b for y, then Ux=y for x• 1-1020--Big number-small number– difference is less then EPS– round to -1020– could lead to large errors• Solution: pivot rowsA Problem with GEA Problem with GE6• Bigger ∆t means we can get solution infewer steps, but• If ∆t is too big, then solution will beinaccurateODE/PDEODE/PDEEither ODE/PDEODE/PDEODE/PDEODE/PDE• Solutions involve a trade-off between– simple computation/small ∆t– expensive computation/big ∆t• includes implicit methods, which involve solvinglinear systems7Principal ComponentsPrincipal Components• Example: Temperature in NW AtlanticPrincipal ComponentsPrincipal ComponentsPrincipal ComponentsPrincipal Components=CRgn 8…Rgn 2Rgn 1Cov=1/(m-1)*CT*C8Principal ComponentsPrincipal