3. Numerical Analysis I - University Of Alabama

2y ago
38 Views
3 Downloads
1.15 MB
41 Pages
Last View : 13d ago
Last Download : 2m ago
Upload by : Anton Mixon
Transcription

3. Numerical analysis I1.2.3.4.5.6.Root finding: Bisection methodRoot finding: Newton‐Raphson methodInterpolationCurve fitting: Least square methodCurve fitting in MATLABSummaryTextA. Gilat, MATLAB: An Introduction with Applications, 4th ed., WileyME 349, Engineering Analysis, Alexey Volkov1

3.1. Root finding: Bisection method Formulation of the problemIdea of the bisection methodMATLAB code of the bisection methodRoot finding with build‐in MATLAB function fzeroReading assignmentGilat 7.9, 9.1http://en.wikipedia.org/wiki/Bisection methodME 349, Engineering Analysis, Alexey Volkov2

3.1. Root finding: Bisection methodProblem statementWe need to find real roots ,of an equation (3.1.1)0in the interval, whereis the continuous function.Root of Eq. (3.1.1) is the (real) number that turns this equation into identity.In general, a non‐linear equation can have arbitrary number of roots in a fixed interval ,. Examples: Linear equation – .,Only one root / . Quadratic equation0, Transcendental equation sin. ,ME 349, Engineering Analysis, Alexey Volkovsin – .Can have 0, 1, or 2 real roots.Multiple roots, Can not be solved algebraically.3

3.1. Root finding: Bisection methodExample: Roots finding in thermo‐physical calculations The temperature dependence of the material properties is given by empirical equations.The specific heat (J/kg/K) as a function of temperature (K) of some material:Then the specific internal (thermal) energy(J/kg) at temperature23is4Let's assume that1. We consider some body of that material of mass (kg)with initial temperature . Then the thermal energy ofthat body is equal toHeating2. We heat the body by a laser and add energy (J). 3. What is the body temperature after heating?In order to answer this question we must find a rootof the equation: ME 349, Engineering Analysis, Alexey Volkov? 4

3.1. Root finding: Bisection methodAlgebraic solution is: An equation (formula) that defines the root of the equation0. An accurate solution.Numerical solution : A numerical value which turns equation An approximate solution. It means that 0, but Iterations 0 into identity. is small.0 The numerical methods for root finding of non‐linear equations usually use iterations forsuccessive approach to the root:We find , , , . such that , i.e. ε 0.After finite number of iterations, we will be able to find the root with finite numerical error .ME 349, Engineering Analysis, Alexey Volkov5

3.1. Root finding: Bisection methodBisection method Let's assume that we localize a single root in an interval ,andchanges sign in theroot. If the interval , contains one root of the equation, then0. Let's iteratively shorten the interval by bisections until the root will be localized in thesufficiently short interval. For every bisection at the central point/2 , we replaceeither or by providing0 after the replacement.0Bisection point:/2One iteration of the bisection method:1. Assume the root is localized in the interval.2. Calculate middle point/2. This is the th approximation to the root3. If, then stop iterations. The root is found with tolerance .4. If0 then,or,otherwise.ME 349, Engineering Analysis, Alexey Volkov .6

3.1. Root finding: Bisection methodMATLAB code for the bisection methodExample: Solving equation sin1/2.function [ x, N ] Bisection ( a, b, Tol )N 0;fa Equation ( a ) ;while b – a Tolc 0.5 * ( a b ) ;fc Equation ( c ) ;if fa * fc 0a c;elseb c;endN N 1;endx c;endfunction f Equation ( x )f sin ( x ) – 0.5;endME 349, Engineering Analysis, Alexey VolkovNotes:1. Calculation ofis the most computationally"expensive" part of the algorithm. It is important tocalculateonly once per pass of the loop.2. Advantage of the bisection method: If we areable to localize a single root, the method allows usto find the root of an equation with any continuousthat changes its sign in the root. No any otherrestrictions applied.3. Disadvantage of the bisection method: It is aslow method. Finding the root with small tolerancerequires a large number of bisections. Example:Let's assume 1,10 . Then thecan be found from equation /2 :log /log 2log 10log 227 .7

3.1. Root finding: Bisection methodSummary on root finding with build‐in MATLAB function fzeroThe MATLAB build‐in function fzero allows one to find a root of a nonlinear equation:LHS of equationx fzero ( @fun, x0 )Initial approximationExample:sin12 sin120function [ f ] fun ( x )f sin ( x ) – 0.5 ;endx fzero ( @fun, 0.01 )ME 349, Engineering Analysis, Alexey Volkov8

3.1. Root finding: Bisection method The MATLAB build‐in function fzero allows one to find a root of a nonlinear equation: x fzero ( @fun, x0 ). fun is the (user‐defined) function that calculates the LHSof the equation. x0 can be either a single real value or a vector of two values. If x0 is a single real number, then it is used as the initial approximation to the root. In thiscase the fzero function automatically finds another boundary of the interval x1 such thatf(x1) * f(x0) 0 and then iteratively shrinks that interval. If x0 is a vector of two numbers, then x0(1) and x0(1) are used as the boundaries of theinterval, where the root is localized, such that f( x0(1) ) * f ( x0(2) ) 0. The function works only ifchanges its sign in the root (not applicable for). The function utilizes a complex algorithm based on a combination of the bisection, secant,and inverse quadratic interpolation methods. Example: Roots of equation sinfunction [ f ] SinEq ( x )f sin ( x ) – 0.5 ;endx fzero ( @SinEq, [ 0, pi / 2 ] )x fzero ( @SinEq, 0.01 )ME 349, Engineering Analysis, Alexey Volkov9

3.2. Root finding: Newton‐Raphson method Idea of Newton‐Raphson method: LinearizationGraphical form of the root finding with Newton‐Raphson methodExamples: When Newton‐Raphson method does not workMATLAB code for Newton‐Raphson methodMATLAB function functionReading assignmenthttp://en.wikipedia.org/wiki/Newton's methodGilat 7.9, 9.1ME 349, Engineering Analysis, Alexey Volkov10

3.2. Root finding: Newton‐Raphson methodProblem statementWe need to find a real root(3.2.1) of a non‐linear equation Differentiable function0in aninterval, whereis the differentiablefunction with continuous derivative ′ .Newton‐Raphson method In the framework of Newton‐Raphson (Newton's)method we start calculations from some initialapproximation for the root, , and then iterativelyincrease the accuracy of this approximation, i.e.successively calculatesuch that , , . and ε 0. In order to find the next approximation to the root,, we , based on the previous approximation, use the idea of linearization: For one iteration, wereplace non‐linear Eq. (3.2.1) by a linear equation that isas close to Eq. (3.2.1) as possible.ME 349, Engineering Analysis, Alexey VolkovAll other functions in thisexample are not differentiableif , includes point11

3.2. Root finding: Newton‐Raphson method Linearization is based on the Taylor series. The Taylor series is the approximation ofvicinity of pointby a polynomial:1 2 Let's apply the Taylor series in order to find based on , i.e. representand(3.2.1) in the form of the Taylor series at Iteration in Eq.Linearization(we retained onlylinear terms)0 in a 12 0 then drop all non‐linear terms 0(3.2.2) and use this equation to find the next approximation to the root: ME 349, Engineering Analysis, Alexey Volkov (3.2.3) 12

3.2. Root finding: Newton‐Raphson methodGraphical representation of the Newton‐Raphson method The plot of the function tangent to the plot of the function is the straight line that is in the point . When we find the root of Eq. (3.2.2), we find a point, where the tangent crosses the axis. The iterative process of Newton‐Raphson method can be graphically represented as follows: ′ Advantages of Newton‐Raphson method: It is the fast method. Usually only a few iterations are required to obtain the root. It can be generalized for systems of non‐linear equations.ME 349, Engineering Analysis, Alexey Volkov13

3.2. Root finding: Newton‐Raphson method Disadvantage of the Newton‐Raphson method: There are lot of situations, when the methoddoes not work. Conditions that guarantee the convergence of , , . to , i.e. 0 , are complicated. Roughly, the Newton‐Raphson method converges if In some interval around the root ,derivative is continuous), ′0, ′′Example:of equationhas the first and second derivatives (firstis finite.is the function that does not satisfy these properties and the root0 can not be find with the Newton‐Raphson method. Initial approximation, , is chosen to be "sufficiently close" to the root .Examples: Newton‐Raphson method does not work when theinitial point is too "far" from the root or enters a cycle ME 349, Engineering Analysis, Alexey Volkov20214

3.2. Root finding: Newton‐Raphson methodMATLAB code for Newton‐Raphson methodExample: Solving equation sin1/2.function [ x, N ] NewtonMethod ( a, Tol )N 0;x a;[ f, dfdx ] Equation ( x ) ;while abs ( f ) Tolx x ‐ f / dfdx ;[ f, dfdx ] Equation ( x ) ;N N 1;endendfunction [ f, dfdx ] Equation ( x )f sin ( x ) – 0.5 ;dfdx cos ( x ) ;endNotes:1. Calculation ofand ′is the mostcomputationally "expensive" part of the algorithm.It is important to calculateand ′onlyonce per pass of the loop.2. Disadvantage of the current version of the code:For solving different equations we need to preparedifferent versions of the NewtonMethod function.They will be different only by the name of thefunction (Equation) that calculatesand ′ .We can make NewtonMethod universal (capable ofsolving different equations) by programming theMATLAB function function. Only 3 iterations is necessary to get the root with toleranceME 349, Engineering Analysis, Alexey Volkov10 .15

3.2. Root finding: Newton‐Raphson methodMATLAB function function Function function is a function that accepts the name of another function as an inputargument. Definition of the function function:function [ . ] Function1 ( Fun, . ) : Here Fun the name of input function argument Use of the function function :[ . ] Function1 ( @Fun1, . ) : Here Fun1 is the name of a MATLAB functionMATLAB code for the Newton‐Raphson method based on function functionFile SinEq.mfunction [ f, dfdx ] SinEq ( x )f sin ( x ) – 0.5 ;function [ x, N ] NewtonMethodFF ( Eq, a, Tol )dfdx cos ( x ) ;N 0;endx a;[ f, dfdx ] Eq ( x ) ;while abs ( f ) TolIn the MATLAB command window:x x ‐ f / dfdx ;[ x, N ] NewtonMethodFF ( @SinEq, 0.01, 1e‐08 )[ f, dfdx ] Eq ( x ) ;N N 1;endendFile NewtonMethodFF.mME 349, Engineering Analysis, Alexey Volkov16

3.3. Interpolation Interpolation problemReduction of the interpolation problem to the solution of a SLEPolynomial interpolationExample: Interpolations of smooth and non‐smooth dataReading assignmentME 349, Engineering Analysis, Alexey Volkov17

3.3. InterpolationInterpolation problemLet's assume that a functional dependence between two variables and is given in thetabulated form: We know values of the function,, for some discrete values of theargument ,1, , .Arg.Fun.(3.3.1)Such tabulated data can be produced in experiments. Example:is time andtemperature, in the experiment we measure the temperature at a discrete times .We are interested in the question : How can we predict the values of the functionderivatives, etc.) at arbitrary which does not coincide with any of ?There are two major of approaches to introduce(3.3.1). We will consider two major methods:is(and itsbased on tabulated data in the form1. Interpolation.2. Fitting (will be considered later).Interpolation implies that we introduce a continuous interpolation function,1, , .This means that the interpolation function goes through every pointME 349, Engineering Analysis, Alexey Volkov,such that(3.3.2)on the plane,.18

3.3. InterpolationInterpolation functionInterpolation inInterpolation interval , We assume that allExtrapolation inare given in ascending order: Interpolation is the process of constructing of new data pointswithin theobservation interval::is the interpolated value of the function Extrapolation is the process of constructing of new data points beyond the observationinterval:or:is the extrapolated value of the function Both interpolation and extrapolation can be performed only approximately, but extrapolationis subject to greater uncertainty and higher risk of producing meaningless results.ME 349, Engineering Analysis, Alexey Volkov19

3.3. InterpolationSolution of the interpolation problem Let's introduce a system ofknown functions,,,, .Usually these functions are assumed to be smooth(have continuous derivatives of any order). Now, let's look for the interpolation function in the following form: (3.3.3)whereare unknown coefficients. In order to be an interpolation function,satisfy conditions (3.3.2), i.e. should(3.3.4). Eqs. (3.3.4) is the linear system of equations with respect torewritten in the matrix form as follows: coefficients. It can be(3.3.5)Thus solution of the interpolation problem reduces to solution of a SLE.ME 349, Engineering Analysis, Alexey Volkov20

3.3. InterpolationThe interpolation function in the form (3.3.6)is called the interpolation polynomial. In order to find the interpolation polynomial one needs to solve the SLE given by Eqs. (3.3.5):,Eq. 3.3.5, Elements of the matrix of coefficients If the interpolation data includespolynomial of degree1. , , 1 1 .1.(3.3.7)(3.3.8)are equal topoints,, then we can find the interpolation The chosen order of functions in Eqs. (3.3.7) and (3.3.8) ( is the coefficient at the highestdegree of ) allows us to use the MATLAB polyval function in order to calculate value of theinterpolation polynomial.ME 349, Engineering Analysis, Alexey Volkov21

3.3. Interpolation: General approachProblem 3.3.1: Interpolation of various functionsThese functions can be usedto generate data points:File InterpolationProblem.mfunction [ C ] InterpolationProblem ( x i, y i )N length ( x i );A zeros ( N, N );for i 1 : N % i is the row indexfor j 1 : N % j is the column indexA(i,j) x i(i) (N‐j);endendC inv ( A ) * y i';end File Interpolation.mfunction [ C ] Interpolation ( Fun, a, b, N, NN )% Preparation of tabulated datax i linspace ( a, b, N );y i arrayfun ( Fun, x i );% Solving the interpolation problemC InterpolationProblem ( x i, y i );% Now we plot the function, interpolation polynomial, and data pointsx linspace ( a, b, NN );f polyval ( C, x ); % Interpolation polynomialy arrayfun ( Fun, x ); % Original functionplot ( x, y, 'r', x i, y i, 'bx', x, f, 'g' )endFile Problem 3 3 1C Interpolation ( @TriangleFun, ‐1, 3, 5, 101 )ME 349, Engineering Analysis, Alexey Volkov1 1File PolyFun.mfunction [ y ] PolyFun ( x )Coeff [ 1 2 3 ];y polyval ( Coeff, x ) ;endFile SinFun.mfunction [ y ] SinFun ( x )y sin ( pi * x / 2 ) ;endFile TriangleFun.mfunction [ y ] TriangleFun ( x )if x 0y 0;elseif x 1y x;elseif x 2y 2 ‐ x;elsey 0;endend22

3.3. InterpolationExample 1: Smooth datasin/2 ,is the number of interpolation pointsA. Symmetric interpolation interval (‐1,1)31020InterpolationpolynomialOriginal functionB. Non‐symmetric interpolation interval (0.5, 1)31015 In general, it is difficult to build and calculate interpolation polynomials at largedue to strong enhancement of round‐off errors. We are limited by small !ME 349, Engineering Analysis, Alexey Volkov( 10‐20)23

3.3. InterpolationExample 2: Non‐smooth data in the form of a triangle pulseSymmetric interpolation interval (‐1,3)51015 For non‐smooth data, an increasein the number of data points(and degree of the polynomial)can deteriorate the accuracy. The values of the interpolationpolynomial for non‐smooth dataare subject to "oscillations."ME 349, Engineering Analysis, Alexey Volkov24

3.4. Curve fitting: Least square method Fitting problemWhen is interpolation not a viable approach?Least square method: General approachLeast square method: Polynomial fittingReading assignmentGilat 8.2, 8.4, 8.5ME 349, Engineering Analysis, Alexey Volkov25

3.4. Curve fitting: Least square methodCurve fitting is the process of constructing a curve, or mathematical function, that has the bestfit to a series of discrete data points.Fitting functionData interval,,,Curve fitting implies that, ,)1. We choose a form of the fitting function (e.g. linear fitting function,. In general, the choice of the fittingwith some number of unknown coefficientsfunction is arbitrary and the number of unknown coefficients is much smaller than thenumber of data points.2. We introduce a measure of difference, , between the data points,and the fittingfunction.3. We find such unknown coefficients,that allow us to minimize the value of .ME 349, Engineering Analysis, Alexey Volkov26

3.4. Curve fitting: Least square methodData pointFitting functionData interval,,,Interpolation functionCurve fitting is an alternative to interpolation.Difference between interpolation and fitting functions: Interpolation function passes precisely through every data point.Fitting function goes closely to data points and follows the general trend in data behavior. Interpolation function has coefficients, where is the number of data points.Fitting function has coefficients, usually .ME 349, Engineering Analysis, Alexey Volkov27

3.4. Curve fitting: Least square method Curve fitting can (and must!) be used instead of interpolation if There are too many data points in order to build an interpolating function ( 10). Input data are noisy. We are interested in revealing general trends in the data behavior (Curve fitting canbe used as a tool for data analysis).Example: Fitting vs. interpolation of noisy data (see solution in FittingVsInterpolation.m)Data points are given by the law1 2 random noiseFitting function1.18 1.931015Interpolationpolynomial of degreeME 349, Engineering Analysis, Alexey Volkov28

3.4. Curve fitting: Least square methodLeast square method: General ideaLeast square method for finding coefficients of fitting functions is based on the generalconditions that allow one to find a minimum of a functionMinimum of a function,Minimum of a function0,0,0In the least square method, the same conditions of a minimum are applied to the mean‐squaredifference between the fitting function and tabulated data.Fitting function,,Example: Fitting function with two coefficients:1,Conditions of minimum of0,,,,:0These are two equations with respect toME 349, Engineering Analysis, Alexey Volkovand29

3.4. Curve fitting: Least square methodLeast square method: Polynomial fitting Assume that we have data points,,1, . . , . Consider the fitting function in the form of a polynomial of degree,,,.,( (3.4.1) Introduce the mean square difference,,., Apply conditions of a minimum of0 Eq. (3.4.1) 2 1,,.,:0,1, . . ,,(3.4.2),ME 349, Engineering Analysis, Alexey Volkov30

3.5. Curve fitting: Least square method,1, . . , Eq. (3.4.3) is the SLE with respect to coefficientsand the RHS are,,,., (3.4.3), where the matrix of coefficients.(3.4.4)Solution of the polynomial fitting problem reduces to a SLE given by Eq. (3.4.3) with respect to1, . . , ) of the fitting polynomial.unknown coefficients (Once coefficients are found, values of the fitting polynomial can be calculated with the MATLABpolyval function.ME 349, Engineering Analysis, Alexey Volkov31

3.5. Curve fitting in MATLAB Polynomial curve fitting with the MATLAB build‐in functionsOther fitting functionsData analysis based on the curve fittingMATLAB basic fitting interfaceReading assignmentGilat 8.2, 8.4, 8.5ME 349, Engineering Analysis, Alexey Volkov32

3.5. Curve fitting in MATLABLeast square method: Polynomial fitting in the MATLAB Assume that we havedata points,,1, . . , .1 (

Summary on root finding with build‐in MATLAB function fzero The MATLAB build‐in function fzero allows one tofind a rootofa nonlinear equation: x fzero ( @fun, x0 ) Example: sin T L 1 2 T Lsin T F 1 2 0 function[f] fun(x) f sin ( x ) –0.5 ; end x fzero (@fun, 0.01) ME 349, Engineering Analysis, Alexey Volkov 8 LHS of equation

Related Documents:

Texts of Wow Rosh Hashana II 5780 - Congregation Shearith Israel, Atlanta Georgia Wow ׳ג ׳א:׳א תישארב (א) ׃ץרֶָֽאָּהָּ תאֵֵ֥וְּ םִימִַׁ֖שַָּה תאֵֵ֥ םיקִִ֑לֹאֱ ארָָּ֣ Îָּ תישִִׁ֖ארֵ Îְּ(ב) חַורְָּ֣ו ם

“numerical analysis” title in a later edition [171]. The origins of the part of mathematics we now call analysis were all numerical, so for millennia the name “numerical analysis” would have been redundant. But analysis later developed conceptual (non-numerical) paradigms, and it became useful to specify the different areas by names.

the numerical solution of second-order optimization methods. Next step development of Numerical Multilinear Algebra for the statistical analysis of multi-way data, the numerical solution of partial di erential equations arising from tensor elds, the numerical solution of higher-order optimization methods.

numerical solutions. Emphasis will be placed on standing the under basic concepts behind the various numerical methods studied, implementing basic numerical methods using the MATLAB structured programming environment, and utilizing more sophisticated numerical methods provided as built-in

Fractions and Numerical Fluency 7-3 specifically on identifying the Number, Operation, and Quantitative Reasoning as well as the Patterns, Relationships, and Algebraic Thinking TEKS that directly affects numerical fluency. Materials: Fractions and Numerical Fluency Slides 76-96, Numerical Fluency PowerPoint Handout 1-Graphic Organizer (page 7-14)

2. Numerical approximation of PDEs. Both the mathematical analysis of the PDEs and the numerical analysis of methods rely heavily on the strong tools of functional analysis. Numerical approximation of PDEs is a cornerstone of the mathematical modeling since almost all modeled real world problems fail to have analytic solutions or they are not

continuum can be attributed for no numerical approximation. With the introduction of numerical analysis in the field of mechanics, a huge window for scientists and engineers has opened up. In numerical analysis, the algorithmic model is an approximation to the continuum model in the sense

Preface to the First Edition The book is designed for use in a graduate program in Numerical Analysis that is structured so as to include a basic introductory course and subsequent more specialized courses. The latter are envisaged to cover such topics as numerical linear algebra, the numerical solution of ordinary and partial differential .