OutlineDiscrete ApproximationsFinite Memory ProblemFinite Precision ProblemSlide 5Slide 6Numerical AnalysisSlide 8Numerical Linear AlgebraSlide 10Solving Linear SystemsSlide 12Gaussian EliminationSlide 14A Problem with GEODE/PDESlide 17Slide 18Principal ComponentsSlide 20Slide 21Slide 22OutlineOutline•Announcements–Add/drop today!–HWI due Friday•Discrete Approximations•Numerical Linear Algebra•Solving ODE’s•Solving PDE’sDiscrete ApproximationsDiscrete Approximations•The defining principle of numerical computing:Computers are finite•This has several consequences:–Computers can only hold a finite amount of data (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 of data, continuous curves or surfaces must be approximated by storing values at a finite number of points•This leads to discretization errors•Can improve the approximation by–adding more points–tracking higher-order properties (e.g. splines)Finite Precision ProblemFinite Precision Problem•Computers only work with integers•To represent a real number, we use two integers:–±m*bp•m=“mantissa”•b=base, set by the system•p=exponent–Limited precision in both mantissa and exponent–Leads to roundoff errorsFinite Precision ProblemFinite Precision Problem•Suppose we are working with base 10 numbers, and mantissa and exponent have 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 ProblemPrecision Bytes m(bits) eps p(bits) rangeSingle 4 24 1e-7 8 10 ±38Double 8 53 1e-16 11 10 ±308Numerical AnalysisNumerical Analysis•The study of algorithms for mathematical 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.Numerical Linear AlgebraNumerical Linear Algebra•Linear Systems•Matrix Factorizations•EigenproblemsSolving Linear SystemsSolving Linear SystemsSolving Linear SystemsSolving Linear SystemsGaussian EliminationGaussian Elimination•This procedure is known as “Gaussian Elimination”•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 is upper 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 GE•Bigger ∆t means we can get solution in fewer steps, but•If ∆t is too big, then solution will be inaccurateODE/PDEODE/PDEEitherODE/PDEODE/PDEODE/PDEODE/PDE•Solutions involve a trade-off between –simple computation/small ∆t –expensive computation/big ∆t•includes implicit methods, which involve solving linear systemsPrincipal ComponentsPrincipal Components•Example: Temperature in NW AtlanticPrincipal ComponentsPrincipal ComponentsPrincipal ComponentsPrincipal ComponentsRgn 1 Rgn 2 … Rgn 8C =Cov=1/(m-1)*CT*CPrincipal ComponentsPrincipal