淡江大学数值方法课件

1Copyright 2011 by yshong2Numerical Methods(Aspect in Engineering Applications with Computers)YUNG-SHAN HONG,Ph.D.,PE.Office:E723Tel:26215656 ext.3260Instructor:Copyright 2015 by yshong3Objective:This course covers a variety of numerical methods and their applications in various engineering problems.Emphasis is placed on the solution of solving nonlinear equation,matrix analysis of linear and nonlinear equations,eigen-value problems,curve fitting,numerical integration and differentiations as well as interpolation methods.Pre-knowledge of Engineering Mathematics and programming skills with computer language(s)are strongly required.Copyright 2006 by yshong4Outline and Schedule:u Introduction(2 hrs)u Mathematical modeling and engineering problem solving(2hrs)u Error and definition(2hrs)u Roots of equations(1)-bracketing methods(2hrs)u Roots of equations(2)-open methods(2hr)u Systems of nonlinear equations(2hrs)u Linear algebraic equations-mathematical and numerical method(3hrs)u Eigenvalue problems(3hrs)Copyright 2006 by yshong5Outline and Schedule:u Least squares regression(2hrs)u Interpolation-Lagrange and Newton approach(2hr)u Interpolation-spline function(2hrs)u Numerical integration general,double integral(2hrs)u Numerical integration Gauss integral(2hrs)u Numerical solution of ordinary differential equations(2hrs)u Numerical solution of partial differential equations(2hrs)Copyright 2007 by yshong6Grading:u Ordinarily expression 40%u Homework(67 times)u Mid term exam 30%u Final term exam 30%Copyright 2006 by yshong7Textbook:Chapra,S.C.and Canale,R.P.(2010),“Numerical methods for engineers”,Sixth Edition,McGRAW-Hill.Reference:u Gerad,C.F.and Wheatley,P.O.(1999),“Applied numerical analysis”,Sixth Edition,Addison-Wesley.u Schilling,R.J.and Harris,S.L.(1999),“Applied numerical methods for engineers using Matlab and C”,Brooks/Cole.u 林聰悟、林佳慧(1997),“數值方法與程式”,圖文技術服務。Copyright 2009 by yshong8About the authors:Steve Chapra teaches in the Civil and Environmental Engineering Department at Tufts University.Dr.Chapra received engineering degrees from Manhattan College and the University of Michigan.Before joining the faculty at Tufts,he worked for the Environmental Protection Agency and the National Oceanic and Atmospheric Administration,and taught at Texas A&M University and the University of Colorado.His general research interests focus on surface water-quality modeling and advanced computer applications in environmental engineering.Copyright 2006 by yshong9About the co-authors:Raymond P.Canale is an emeritus professor at the University of Michigan.During his over 20-year career at the university,he taught numerous courses in the area of computers,numerical methods,and environmental engineering.He also directed extensive research programs in the area of mathematical and computer modeling of aquatic ecosystems.He has authored or coauthored several books and has published over 100 scientific papers and reports.Copyright 2006 by yshong10Why you should study numerical methods?uNumerical methods are extremely powerful problem-solving tools.They are capable of handling large systems of equations,nonlinearities,and complicated geometries that are not uncommon in engineering practice and often impossible to solve analytically.uDuring your careers,you may often have occasion to use commercially available prepackaged that involve numerical methods.The intelligent use these programs is often predicated on knowledge of the basic theory underlying the methods.Copyright 2006 by yshong11uMany problems cannot be approached using prepackaged programs.If you are conversant with numerical methods and are adept at computer programming,you can design your own programs to solve problems without having to buy expensive software.uNumerical methods are an efficient vehicle for learning to use computers.Because numerical methods are for the most part designed for implementation on computers,they are ideal for this purpose.You will also learn to control the errors of approximation that are part of large-scale numerical calculations.uNumerical methods provide a vehicle for you to reinforce your understanding of mathematics.Because one function of numerical methods is to reduce higher mathematics to basic arithmetic operations.Copyright 2006 by yshong12Solutions of the problem in engineering:INTRODUCTIONuAnalytical solution:(closed form solution)Ex.Determine at x=0 let x=0 900 x(o)sinxEx.Determine dP1?Copyright 2006 by yshong13uNumerical solution:(approximation solution)Ex.Determine at x=10 let xf(x)101?Copyright 2006 by yshong14Numerical method:Data+Mathematical theory+computer program Approximation Copyright 2006 by yshong15Types of the problem:(a)Solution of nonlinear equation(roots of equation)let xf(x)Ex.Copyright 2006 by yshong16(b)Matrix analysis(solution of linear algebratic eqs.)Ex.u1u2Ex.Copyright 2006 by yshong17(c)System of nonlinear eqs.Ex.x1x2Copyright 2006 by yshong18(d)Curve fittingu Regression Least squares regressionu Interpolation&ExtrapolationxyyxRegressionInterpolation&ExtrapolationCopyright 2006 by yshong19(e)Integration techniquexf(x)abIf(x)p(w)spaceCopyright 2006 by yshong20(f)Ordinary differential equation(ODE)Because many physical laws are couched in terms of the rate of change of a quantity rather than the magnitude of the quantity itself.Ex.Difference scheme viewpointSolve y as a function of tytf(t,y)yi+1yiyRi+1titi+1tCopyright 2006 by yshong21(f)Ordinary differential equation(ODE)Additional data must be given:u Initial value problemu Boundary value problemx1f(x1)x?x1f(x1)x?x2f(x2)Copyright 2006 by yshong22(g)Partial differential equation(PDE)The behavior of a physical quantity is couched in terms of its rate of change with respect to two or more independent variables.u Elliptic solid mech.,flow mech.potentialLaplace eqs.(seepage eq.)Copyright 2006 by yshong23(g)Partial differential equation(PDE)u Parabolic consolidation,heatAnalytical sol.u Hyperbolic wave eqs.Copyright 2006 by yshong24Motivation:Numerical methods are techniques by which mathematical problems are formulated so that they can be solved with arithmetic operations.Although there are many kinds of numerical methods,they have one common characteristic:they invariably involve large numbers of tedious arithmetic calculations.It is little wonder that with the development of fast,efficient digital computers,the role of numerical methods in engineering problem solving has increased dramatically in recent years.Copyright 2006 by yshong25Non-computer methods:(1)Solutions were derived for some problems using analytical,or exact method.Ex.Exact sol.Ex.?Exact sol.Copyright 2006 by yshong26(2)Graphical solutions were used to characterize the behavior of systems.Ex.12xyx.y.x.y.The results are not very precise.Graphical techniques are often limited to problems that can be described using three or fewer dimensions.(3)Calculators and slide rules were used to implement numerical method manually.The method used to simple engineering problems.Copyright 2006 by yshong27Numerical method:Data+Mathematical theory+computer program Approximation Complex engineering problems:Copyright 2006 by yshong28The engineering problem-solving process:Problem definitionMathematical modelNumeric or graphic resultsImplementationDataTheoryProblem-solving tools:Computers,statistics,Numerical methods,graphics,etc.Societal interfaces:Scheduling,optimization,communication,public interaction,etc.Copyright 2006 by yshong29CHAPTER 1 A SIMPLE MATHEMATICAL MODELA mathematical model can be broadly defined as a formulation or equation that expresses the essential features of a physical system or process in mathematical terms.In a very general sense,it can be represented as a functional relationship of the form:Dependent variable=f(independent variables,parameters,forcing functions).(1.1)Copyright 2006 by yshong30Dependent variable=f(independent variables,parameters,forcing functions).(1.1)Where the dependent variable is a characteristic that usually reflects the behavior or state of the system;the independent variables are usually dimensions,such as time and space,along which the systems behavior is being determined;the parameters are reflective of the systems properties or composition;and the forcing functions are external influences acting upon it.d:dependent variableP:forcing functionsA,E,L:parametersCopyright 2006 by yshong31The following illustrates a physical problem how to represent by a mathematical model.According Newton second law,Where F=net force acting on the body(N or kg-m/sec2)m=mass of object(kg)a=its acceleration(m/sec2)(1.2)Copyright 2006 by yshong32(1.2):Where a=the dependent variable reflecting the systems behaviorF=the forcing function(net froce)m=a parameter represent a property of the system(1.3)Note:this simple case there is no independent variable because we are not yet predicting how acceleration varies in time or space.Copyright 2006 by yshong33To illustrate a more complex model of this kind,Newtons second law can be used to determine the terminal velocity of a free-falling body near the earths surface.The falling body will be a parachutist.(Fig.1.2).(1.4)FuFdF:net force+:the object will accelerate-:the object will decelerate0:the object will remain at a constant levelCopyright 2006 by yshong34.(1.5)FD:the downward pull of gravityFU:the upward force of air resistance.(1.6).(1.7)g:the gravitational constant 9.8 m/s2c:drag coefficient=f(shape,surface roughness,.)Copyright 2006 by yshong35From eqs.(1.4)through(1.7)combined:or.(1.9).(1.8)Type of eq.?ODEEq.(1.9)is a differential equation that relates the acceleration of a falling object to the forces acting on it.If the parachutist is initially at rest(v=0 at t=0),that is a initial value problem.Solve eq.(1.9)forWhat type of problem?Copyright 2006 by yshong36.(1.10)Note:v(t):the dependent variablet=the independent variablec,m=parametersg=the forcing function The following will illustrate the analytical solution and the numerical solution,respectively.Copyright 2006 by yshong37Ex 1.1 analytical solutionKnown:mass=68.1 kg,c=12.5 kg/sEq.(1.10)thenterminal velocity53.39exact sol.t(s)v(m/s)Eq.(1.10)is called an analytical,or exact solution because it exactly satisfies the original differential equation.Unfortunately,there are many mathematical models that cannot be solved exactly.In many of these cases,the only alternative is to develop a numerical solution that approximates the exact solution.Copyright 2006 by yshong38Ex 1.2 numerical solution.(1.11).(1.9)So eq.(1.9):Copyright 2006 by yshong39When t=0,v=0,if step size(time step)=2 i=0i=1m/sm/sv(t=6),v(t=8),.Copyright 2006 by yshong40v(m/s)t(s)terminal velocityexact sol.numerical sol.24860Copyright 2006 by yshong41Homework:Problems 1.1,1.2 and 1.3(p.21)Due:One weekCopyright 2010 by yshong42CHAPTER 2 PROGRAMMING AND SOFTWAREpp.25-51Copyright 2006 by yshong43CHAPTER 3 APPROXIMATIONS AND ROUND-OFF ERRORSHow much error is present in our calculations and is it tolerable?Two major forms of numerical error:Round-off errorTruncation errorInherent errorCopyright 2006 by yshong44The concept of a significant figure.See Fig.3.1(p.53)Accuracy and precisionAccuracy refers to how closely a computed or measured value agrees with the true value.True value=2.83Precision refers to how closely individual computed or measured values agree with each other.Copyright 2006 by yshong45Fig.3.2Increasing accuracyIncreasing precision(a)(b)(c)(d)Copyright 2006 by yshong46Numerical methods should be sufficiently accurate or unbiased to meet the requirements of particular engineering problem.They also should be precise enough for adequate engineering design.Copyright 2006 by yshong47Error definitions(1)True error Et(absolute error)Et=true value-approximationEx.Two approaches to measure length of the two objects.Approach(a):Object(a)true length=1m,measured error=1cm Approach(b):Object(b)true length=0.1m,measured error=1cmWhat is better approach?Copyright 2006 by yshong48(2)Relative error et Ex.Two approaches to measure length of the two objects.Approach(a):Object(a)true length=1m,measured error=1cm Approach(b):Object(b)true length=0.1m,measured error=1cmApproach(a):e et=1%Approach(b):e et=10%Copyright 2006 by yshong49(3)The approximation percent relative error ea.(3.5)m:iteration numberi:point,positionIterative approach characteristicvalueCal.numberCopyright 2006 by yshong50Truncation error(Chapter 4)Truncation errors are those that result from using an approximation in place of an exact mathematical procedure.For example,in Chap.1 we approximated the derivative of velocity of a falling parachutist by a finite-divided-difference eq.of the form.(4.1)Copyright 2006 by yshong51A truncation error was introduced into the numerical solution because the difference eq.only approximates the true value of the derivative.In order to gain insight into the properties of such errors,we now turn to a mathematical formulation that is used widely in numerical methods to express functions in an approximate fashion the Taylor series.Copyright 2006 by yshong52Taylor seriesc is between a,b,nth-order derivatives are existence for f(x),then f(x)at c can be to express following eq.using Taylor series.Rn(x)=remainder termCopyright 2006 by yshong53If c=0,f(x)series expressing to call Maclaurins series,If(n-1)th-order approximate,then Rn(x)refers to truncation errorCopyright 2006 by yshong54Ex.Use fourth-order Maclaurin series expansions to approximate the functionPredict the functions value at x=1.Sol:let f(x)=ex,f(x)=f(x)=f(x)=f(4)(x)=ex,f(0)=1,f(x)=f(x)=f(x)=f(4)(x)=1Maclaurin expansion series:Copyright 2006 by yshong55Expressing to fourth-order But truncation error=2.71828-2.70833=0.00995Copyright 2006 by yshong56In a similar manner,the complete Taylor series expansion:.(4.5)If we simplify the Taylor series,Refer to first-order approximationRefer to second-order approximationxi+1-xi=h refer to step sizeCopyright 2006 by yshong57Ex.4.1 Use zero fourth-order Taylor series expansions to approximate the function:from xi=0 with h=1.That is,predict the functions value at xi+1=1Sol:true value f(1)=0.2zero-order:Truncation error=0.2-1.2=-1first-order:Truncation error=0.2-0.95=-0.75Copyright 2006 by yshong58second-order:Truncation error=0.2-0.45=-0.25f(x)xZero orderfirst ordersecond orderxi=0 xi+1=11.20.950.45f(xi+1)f(xi)How order Taylor series expansion can be no truncation error?Copyright 2006 by yshong59In general,the nth-order Taylor series expansion will be exact for an nth-order polynomial.For other differentiable and continuous functions,such as exponentials and sinusoids,a finite number of terms will not yield an exact estimate.Each additional term will contribute some improvement,to the approximation.Only if an infinite number of terms are added will the series yield an exact result.EX.4.2Copyright 2010 by yshongProblems:4.2,4.4 and 4.560Round-off error(Chapter 3)Round-off errors originate from the fact that computers retain only a fixed number of significant figures during a calculation.Number such as p,e,or cannot be expressed by a fixed number of significant figures.Therefore,they cannot represented exactly by the computer.In addition,because computers use a base-2 representation,they cannot precisely represent certain exact base-10 numbers.The discrepancy introduced by this omission of significant figures is called round-off error.Copyright 2006 by yshong61Base-2:00 01 10 11 100 101 110 111 1000 1001Base-10:0 1 2 3 4 5 6 7 8 9Ex.3253 is represented base-10:Ex.110.11 is represented base-2:Copyright 2006 by yshong62But,ex.(0.2)10 8 numbers represented:To get a decimal point at sixth numberRound-off error=0.2-0.199219=0.000781Copyright 2010 by yshongRef.Figure 3.6(p.63)63ROOTS OF EQUATIONS(Part 2,p.113)Ex.Such as f(x)cannot be solved analytically.In such instance,the only alternative is an approximate solution technique.One method to obtain an approximate solution is to plot the function and determine where it crosses the x axis.This point,which represents the x value for which f(x)=0,is the root.f(x)xrootCopyright 2006 by yshong64Although graphical method are useful for obtaining rough estimates of roots,they are limited because of their lack of precision.An alternative approach is to use trial and error.This“technique”consists of guessing a value of x and evaluating whether f(x)is zero.Such this methods are obviously inefficient and inadequate for the requirements of engineering practice.Copyright 2006 by yshong65Ex.Such computations can be performed directly because v is expressed explicitly as a function of time.However,suppose we had to determine the drag coefficient for a parachutist of a given mass to attain a prescribed velocity in a set time period.Ex.There is no way to rearrange the equation so that c is isolated on one side of the equal sign.In such cases,c is said to be implicit.Copyright 2006 by yshong66Approach of Nonlinear equation solution:Bracketing method(chap.5)bisection,false positionOpen method(chap.6)one-point iteration,Newton-Raphson,secant methodRoots of polynomials(chap.7)Mllers methos,Bairstows methodCopyright 2006 by yshong67Roots within the intervalAssumption a nonlinear equation f(x)=0 is a continue function.Two points are“a”and“b”on x-axis,then f(x)is whether solutions between a and b.According to follow as,(1)If f(a)*f(b)=0,then f(x)has a solution.(2)If f(a)*f(b)0,then?Ref.pp.122123.fig.5.2 fig.5.4.Copyright 2010 by yshong68CHAPTER 5 BRACKETING METHODSBi-section methodabf(a)f(b)x1x2x3Copyright 2006 by yshong69Ex.Use bisection to solve the following equation in 1,2.The equation is X3+2x2-5x+1=0 (ea1%)Sol:let f(x)=X3+2x2-5x+1;and f(1)=-1,f(2)=7,f(1)*f(2)0,It has a solution.(1)x1=(1+2)/2=1.5,f(1.5)=1.375;and f(1)*f(1.5)0,new section is 1,1.5.ea1=abs(1.5-1)/1.5)*100%=33%(2)x2=(1+1.5)/2=1.25,f(1.25)=-0.17188;and f(1.25)*f(1.5)0,new section is 1.25,1.5.ea2=abs(1.25-1.5)/1.25)*100%=20%(3)Repeat until the result is accurate enough to satisfy your needs.Copyright 2006 by yshong70False position method(linear interpolation method)abf(a)f(b)x1x2x3Copyright 2006 by yshong71abf(a)f(b)x1x2x3f(x)(x1,f(x1)(1)Determine the straight line to join(a,f(a)and(b,f(b).Suppose it has one solution in a,b for equation f(x)=0.Let y=mx+k,and x=a,x=bCopyright 2006 by yshong72(1)-(2):f(a)-f(b)=m(a-b),substitute(1)thenSo,straight line(2)The x-value of straight line at x-axial.So,let y=0,x=x1.Copyright 2006 by yshong73(3)Substitute x1 to f(x),if f(x1)=0,then x1 is the solution.If f(x1)0,(a)If f(a)*f(x1)0,new section is x1,b(4)so,the general form:;i=1,2,(a)If f(a)*f(xi)0,then a=xi(5)Repeat until the result is accurate enough to satisfy your needs.(ex.ea1%or 0.1%)Copyright 2006 by yshong74Ex.Use false position to solve the following equation in-1,0.The equation is 3X3+4x2-8x-1=0 (ea1%)Sol:let f(x)=3X3+4x2-8x-1;and f(-1)=8,f(0)=-1,f(-1)*f(0)0,It has a solution in-1,0.(1)substitute a=-1,b=0,f(-1)=8,f(0)=-1 to general formi=1,Copyright 2006 by yshong75and f(-0.11111)=-0.065843,f(-1)*f(-0.11111)0 new section-1,-0.11111(2)substitute a=-1,b=-0.11111,f(-1)=8,f(-0.11111)=-0.065843 to general formi=2,and f(-0.118367)=-0.001993,f(-1)*f(-0.118367)0 new section-1,-0.118367(3)Repeat until the result is ea1%.Ref.ex.5.5,5.6Copyright 2006 by yshong76Problem:5.2,5.3,5.10,5.13Copyright 2006 by yshong77CHAPTER 6 OPEN METHODSFor the bracketing methods in the previous chapter,the root is located within an interval prescribed by a lower and an upper bound.Repeated application of these methods always results in closer estimates of the true value of the root.Such methods are said to be convergent because they move closer to the truth as the computation progresses.In contrast,the open methods described in this chapter are based on formulas that require only a single starting value of x or two starting values that do not necessarily bracket the root.As such,they sometimes diverge or move away from the true root as the computation progresses.However,when the open methods converge,