《Lecture 1-Introduction to numerical analysis.ppt》由会员分享，可在线阅读，更多相关《Lecture 1-Introduction to numerical analysis.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Lecture 1 - Introduction to numerical analysis& Textbook (not necessarily to have) Numerical Analysis (Eighth Edition) Richard L. Burden & J. Douglas Faires. & References(参考书目参考书目) Numerical Method in Scientific Computing Germund Dahlquist, Ake Bjorck Numerical Methods in Engineering with MATLAB Jaa
2、n Kiusalaas Numerical Analysis: Mathematics of Scientific Computing (Third Edition) 数值分析数值分析 （英文版（英文版 第第3版版 ） David Kincaid & Ward Cheney（机械工业出版社机械工业出版社) Numerical Analysis (Seventh Edition) 数值分析数值分析 （第七版（第七版 影印版）影印版） Richard L. Burden & J. Douglas Faires （高等教育出版社）高等教育出版社） http:/ Reminder: You will
3、need to secure access to a PC for this semester A PC with Matlab installed, preferably.Grading (Tentative) Homework: 30% Final Exam: 30%Term Project: 30%In-Class Presentation: 10%EvaluationHomework: Simply copying another students answers to homework problems is strongly discouraged. No late homewor
4、k or assignment.Tests: Final exam will be closed-book and closed-note. One A4 sized cheet sheet will be allowed, if necessary. Another reminder: You are professionals in training, your work should reflect this fact. Classroom Behavior: Remember that you are graduate students. Critical thinking are h
5、ighly encouraged. Speak yourself out ( if possible, in English) whenever you have relevant questions or commentsAttendance: Students will be responsible for any announcements made in class, whether or not they are present.What is Numerical AnalysisIntroductionA Small Example computation of , 4 , 3,2
6、112222212 nPPPnnnnn=2n=3n=4 2 2.828427124746190 3 3.061467458920719 4 3.121445152258053 5 3.136548490545941 6 3.140331156954739 7 3.141277250932757 8 3.141513801144145 9 3.141572940367883 10 3.141587725279961 11 3.141591421504635 12 3.141592345611077 13 3.141592576545004 14 3.141592633463248 15 3.14
7、1592654807589 16 3.141592645321215 17 3.141592607375720 18 3.141592910939673 19 3.141594125195191 20 3.141596553704820 21 3.141596553704820 22 3.141674265021758 23 3.141829681889202 24 3.142451272494134 25 3.142451272494134 26 3.162277660168380 27 3.162277660168380 28 3.464101615137754 29 4.00000000
8、0000000 30 0.000000000000000 31 0.000000000000000 Result of 15 digit computationRed digits are correctBlack and green digits are incorrect = 0 ?Wheres the problem?, 4 , 3,2112221 nPPnnnnsmall 11is calculated as zeroLets replacewith the algebraically identical expressionLets replacewith the algebraic
9、ally identical expression small 11smallsmall 11, 4 , 3,211222212 nPPPPnnnnand redo the computation 2 2.828427124746190 3 3.061467458920719 4 3.121445152258053 5 3.136548490545941 6 3.140331156954739 7 3.141277250932757 8 3.141513801144145 9 3.141572940367883 10 3.141587725279961 11 3.141591421504635
10、 12 3.141592345611077 13 3.141592576545004 14 3.141592633463248 15 3.141592654807589 16 3.141592645321215 17 3.141592607375720 18 3.141592910939673 19 3.141594125195191 20 3.141596553704820 21 3.141596553704820 22 3.141674265021758 23 3.141829681889202 24 3.142451272494134 25 3.142451272494134 26 3.
11、162277660168380 27 3.162277660168380 28 3.464101615137754 29 4.000000000000000 30 0.000000000000000 31 0.000000000000000 2 2.828427124746190 3 3.061467458920719 4 3.121445152258053 5 3.136548490545940 6 3.140331156954753 7 3.141277250932773 8 3.141513801144301 9 3.141572940367091 10 3.14158772527716
12、0 11 3.141591421511200 12 3.141592345570118 13 3.141592576584872 14 3.141592634338563 15 3.141592648776985 16 3.141592652386591 17 3.141592653288992 18 3.141592653514593 19 3.141592653570993 20 3.141592653585093 21 3.141592653588618 22 3.141592653589499 23 3.141592653589719 24 3.141592653589774 25 3
13、.141592653589788 26 3.141592653589792 27 3.141592653589793 28 3.141592653589793 29 3.141592653589793 30 3.141592653589793 31 3.141592653589793 correct to all digits correct to all digits listBoringIs that all there isto numerical analysis?Not so boring if the result of this computation affects The a
14、bility of the next plane you fly to stay in the air The integrity of the next bridge you cross The state of the economy on which you live The path of a missile that isnt intended to strike youSo what are the common problems of numerical analysis?Algorithm areas: Linear Equations Nonlinear Equations
15、Single and Systems Data Fitting Interpolation and Approximation Integration Differential Equations Ordinary and Partial OptimizationDidnt we study that stuff in math classes?Yes, but as the Pi Example shows, math classes are just the beginningExamples of Applications for Numerical AnalysisGrowth of
16、a PopulationAn Exponential Model: )(d)(dtNttNWhose solution is )1()(0 tteeNtN Suppose a certain Population contains 1,000,000 individualsinitially, that 435,000 immigrate into the community in the first year, and that 1,564,000 individuals are present at theend of the one year. To determine the birt
17、h rate of this population, we must solve in the equation )1(000,435000,000, 1000,564, 1 ee of which the exact solution cannot be obtained by algebraic methods This problem is equivalent to finding a solution of an equation of the form 0)( xfat least 6 satellites are always within Line of sight from
18、almost everywhere on the Earths surface.Global Positioning System, GPS(全球定位系统全球定位系统) denotes the coordinates of the GPS denotes the coordinates of the GPS receiver position at time treceiver position at time t， denotes the coordinates of each satellite Sdenotes the coordinates of each satellite Si i
19、 at the time the message was sent. We solve at the time the message was sent. We solve the following nonlinear equation systemthe following nonlinear equation system),(tzyx),(iiiitzyx 0)()()()(0)()()()(0)()()()(0)()()()(0)()()()(0)()()()(626262652525254242424323232322222221212121cttzzyyxxcttzzyyxxct
20、tzzyyxxcttzzyyxxcttzzyyxxcttzzyyxx 0),( 0),(0),(21212211nnnnxxxfxxxfxxxf0)( xF Written as: Where TnnnxxxxRRDF),(,:21 Chapter 10: Numerical Solutions of Nonlinear Systems of Equations (非线性方程组的数值解非线性方程组的数值解)Chapter 2: Solutions of Equations in One Variable (非线性方程的数值解法非线性方程的数值解法)Suppose we have obtaine
21、d the following datawhich represent the temperature at differentdepths of a certain ocean area： Depth（M） 466 741 950 1422 1634 Temp（oC） 7.04 4.28 3.40 2.54 2.13 What are the temperatures at the depth of, e.g. 500m，600m,1000mCan we provide a reasonable estimate ofthe population size in the year of 19
22、65, or 2010?19505519619606620719708299219809870519901143332000126743432231 ttty30/ )1979( ts432231 sssyA cencus of the population of China is taken every 10 years.The following table lists the population, in thousands of ppl, from 1950 to 1990. Chapter 3: Interpolation and Polynomial Approximation (
23、插值法与多项式逼近插值法与多项式逼近) Chapter 8: Approximation Theory (逼近理论逼近理论)A sheet of corrugated roofing is constructed by pressing a flat sheet of aluminum into one whose cross section has the form of a sine wave A corrugated sheet 4 feet long is needed, the hight of each wave is 1in, each wave has a period of
24、. Question: Find the length of flat sheet needed. 2An example from biochemistry From Calculus we know that the problem is to find the length of the curve given by dxxdxxfL 48024802)(cos1)(1This is an elliptic integral of the second kind, which cannot be evaluated by ordinary methods.Chapter 4: Numer
25、ical Differentiation and IntegrationAn example from biochemistry A，B，C are three type of proteins，the reactions that can occur among them are：123aaaABBBCBBCAC This biochemical process can be modelled as follows Chapter 5: Initial Value Problems for Ordinary Differential Equations (ODEs) （常微分方程的初值问题）
26、（常微分方程的初值问题）0)0(,:0)0(,:1)0(,:3222322223231121323111 yyayCyyayyayayByyyayayAAn example from civil engineering A common problem concerns the deflection of a beam of rectangular cross section subject to uniform loading while the ends of the beam are supported so that they undergo no deflection)( xw )(
27、2)()(22lxEIqxxwEISxdxwd The differential equation approximating this physical situation is of the formWhere w(x) is the deflection a distance x from theleft end of the beam. Since no deflection occurs atThe ends of the beam, we have two boundary conditions 0)()0( lwwChapter 11: Boundary Value Proble
28、ms for Ordinary Differential Equations (ODEs) （常微分方程的边值问题）（常微分方程的边值问题）An example from electrical engineering1i5i5i1i2i3i3i4iV volts 2 3 5 2 2 1 4 3Suppose that a potential of V volts is applied between the points A and G in the circuit and that , , and represent current flow as shown in the above di
29、agram.AG1i2i,43ii5iKirchhoffs laws of electrical Circuits imply that the currents satisfy the following system of linear equations 00003200011100027501100100055:form matrix the in Written032 0 0275 0 55 543215454343254121ViiiiiiiiiiiiiiiiViiChapter 6: Direct Methods for Solving Linear Systems （求解线性方
30、程组的直接方法）（求解线性方程组的直接方法）Chapter 7: Iterative Techniques in Matrix Algebra （矩阵代数的迭代解法）（矩阵代数的迭代解法）Linear systems of equations are associated with many problems in engineering and science as well as the social science and quantitative study of business and economic problems.xxGT 1 exTG: Google Matrix, “t
31、he worlds largest matrix computation”. 8.1 billion rows and 8.1 billions columns growing everyday as the number of web pages grows everyday. x: PageRank vector向量向量 “The $25,000,000,000 Eigenvector本征向量本征向量”Google Search EngineGoogle Search EngineLondon, London, England: England: Millennium Millennium
32、 (Wobbly) (Wobbly) Bridge (1998-Bridge (1998-2002,2002, Norman Norman Foster and Foster and Partners and Partners and Arup Arup Associates) Associates) the natural modes and frequencies of a structure are the solution of an eigenvalue problem that is quadratic when damping effects are included in th
33、e model. (F. Tisseur, K. Meerbergen, The quadratic Eigenvalue Problem, SiREV 43, 2000, pp.235-286)Vibration Analysis of Mechanical StructuresEigenfaces in Image ProcessingIn image In image processing, the processing, the eigenvectors of the eigenvectors of the covariance matrix covariance matrix ass
34、ociated with a associated with a large set of large set of normalized normalized pictures of faces pictures of faces are called are called eigenfaces; this is eigenfaces; this is an example of an example of principal principal components components analysis. analysis. They are very useful for expres
35、sing any face image as a linear combination of some of them. In the facial recognition branch of biometrics, eigenfaces provide a means of applying data compression to faces for identification purposes. xAx Chapter 9: Approximating Eigenvalues 特征值的计算特征值的计算 Analysis: Solve a problem using equations A
36、lgebra, Calculus, Differential Equations, Partial Differential Equations, etc. Numerical Analysis: Similar but using only Arithmetic! Addition, Subtraction, Multiplication, DivisionAnalysis vs. Numerical Analysis Numerical methods require tedious and repetitive arithmetic operations. Not practical t
37、o be carry out by humans. They need a detailed and complete set of instructions for every single step to perform. (program) Numerical Analysis and Computers The specific computer language used is not important! The methods can be implemented in Basic, C, Matlab, etc. Even in spreadsheets like Excel.
38、 Some calculator have enough capabilities, e.g. TI-89 or HP-48g.Numerical Analysis and ComputersContinued No necessary a computer algebra system, e.g. Matlab, Maple or Mathematica. They are good to do graphs. Fortran and C are preferred due to their speed. It might be easier to start with Matlab.Num
39、erical Analysis and ComputersContinuedCourse Objectives Students will be able to analyze mathematical problems and determine the errors involved in obtaining a numerical solution to the problem. Students will become familiar with the limits that various numerical techniques operate under. Students w
40、ill be able to use computers to generate numerical solutions to various categories of mathematical problems.Section 1.2 Round off Errors and Computer Arithmetic The arithmatic performed by a calculator or computer is different from the arithmetic in our algebra and calculus courses. In our tradition
41、al math world, we permit numbers with an infinite number of digits. 3332844222 Computers use floating point numbers which have 3 parts:l Signl Characteristicl Mantissa Size: IEEE: Single 32 bits, Double 64 bitsFloating Points For the 64-bit (binary digit) representation A machine number looks like 0
42、 10000000011 1011100100010000000000000000 The first bit is a sign indicator, denoted s. Followed by an 11-bit component, c, called the characteristic And a 52-bit binary fraction, f, called the mantissa Using this system gives a floating-point number of the form )1(2)1(1023fcs 0 10000000011 10111001
43、0001000000000000000056640625.27)1(2)1(102310270 f4096156212311618121 2112112112112112111027121024 212120202101285431012910 fcsAs a consequence, this machine number precisely represents the decimal number The next largest machine number is 0 10000000011 1011100100010000000000000001307102310102225.0)0
44、1(2)1( The smallest positive number that can be represented has 27.566406250,1,0 fcsNumbers occuring in calculations that have a magnitude less than this value results underflow and are generally set to zero.309521023101017977.0)211(2)1( The largest positive number that can be represented has 5221,1
45、,0 fcsNumbers occuring in calculations that have a magnitude greater than this value results overflow and typically cause the computation to stop.Note that there are two representations for the number zero0, 0, 10, 0, 0 fcsfcsAs we have seen, In the computational world, each representable number has
46、 only a fixed and finite number of digits. This means only rational numbers and not even all the rational numbers can be represented exactly. Since is not rational, it is given an approximate representation, one whose square will not be precisely 3. Although it will likely be sufficiently close to 3
47、 and be acceptable in most situations At times problems arise because of this discrepancy 3Round-off Errors The error produced when a calculator or computer is used to perform real-number calculations k-digit decimal machine numbers: machine numbers that are in the following normalized decimal float
48、ing point form., 3 , 290 91,10. 0121kidddddink ， Any positive real number within the numerical range of the machine can be normalized to the formThe floating-point form of y, denoted fl(y), is obtained by terminating the mantissa of y at k decimal digits.10. 02121nkkkdddddy .10. 0)(fl21nkdddy There
49、are two ways of performing this termination. Chopping (example of pi) RoundingIf is an approximation to , then The absolute error is The relative error is provided that *pp.*pp ,/*ppp . 0 pExample: 103100. 0,103000. 0)c103100. 0,103000. 0)b is error relative is error absolute103100. 0,103000. 0)a4*4
50、3*31*1 pppppp The example shows that the same relative error occurs for widely varying absolute errors. As a measure of accuracy, the absolute error can be misleading and the relative error more meaningful since the relative error takes into consideration the size of the value.,103333. 01 Significan