[PDF] MATH 2P20 NUMERICAL ANALYSIS I Lecture Notes - Brock University

View - Download MATH 2P20 NUMERICAL ANALYSIS I Lecture Notes - Brock University

Previous PDF

Next PDF

MATH 2P20

NUMERICAL ANALYSIS I

Lecture Notes

c°Jan Vrbik 2 3

Contents

1PREVIEW 5

Fittingpolynomialsto:............................ 5

Discretedata .............................. 5

Morecomplicatedmathematicalfunctions .............. 5 Numerical Integration and Dierentiation ................. 5

Integration................................ 5

Dierentiation.............................. 6

Relatedissues.............................. 6

MatrixAlgebra................................ 6

Eigenvaluesandeigenvectors...................... 6

Remaining Topics............................... 7

2USINGMAPLE 9

Basics ..................................... 9

ListsandLoops................................ 10

VariablesandPolynomials.......................... 11

Procedures .................................. 12

MatrixAlgebra................................ 12

Otherusefulcommands: ........................ 13

Plots...................................... 13

3 INTERPOLATING POLYNOMIALS 15

Newton'sInterpolation............................ 15 Lagrangeinterpolation............................ 16

4CUBICSPLINE 19

Step-by-step Solution............................. 20

Tri-diagonal Systems (LU Decomposition)

................. 23

Example.................................... 25

5 LEAST-SQUARES FIT (MATRIX ALGEBRA

)27

Normal Equations.............................. 27

Gaussian Elimination

............................ 29

SymmetricData ............................... 31

WeightedFit ................................. 32

LinearModels................................. 33

Pivoting

................................... 34

Matrix Inverse

................................ 36 4 Incorporatingpivoting ......................... 38

6 APPROXIMATING FUNCTIONS 41

Orthogonal(Legendgre)Polynomials .................... 43 ChebyshevPolynomials ........................... 45 LaguerreandHermitePolynomials ..................... 49

Laguerre................................. 49

Hermite ................................. 50

7 NUMERICAL INTEGRATION 53

Trapezoidal rule................................ 53

Compositerule ............................. 54

Rombergintegration .......................... 55

SimpsonRule................................. 56

Erroranalysis.............................. 58

Compositerule ............................. 58

OtherRules.................................. 59

Singularandimproperintegrals.................... 61 Gaussian Integration............................. 64

8 NUMERICAL DIFFERENTIATION 71

RichardsonExtrapolation .......................... 72 Higher-DegreeFormulas ........................... 73

Nonsymmetricspacing ......................... 74

Higherderivatives............................ 75

9NONLINEAREQUATIONS 77

Newton'sMethod............................... 77

Several Unknowns.............................. 80

10 ODE, BOUNDARY-VALUE PROBLEM 83

Linear

DierentialEquation ........................ 83

NonlinearCase ................................ 86

11 MATRIX' EIGENVALUES 89

Householder'sMethod ............................ 90 QR

Decomposition.............................. 92

5

Chapter 1 PREVIEW

The course topics will concentrate on the following three areas:

Fitting polynomials to:

Discrete data

(either computed or empirical, and collected in a tableofandvalues). Thismaybedoneforseveraldierent reasons. We may want to

1. accurately

interpolate(computeusing a value ofnot found in the table itself).

2. draw a smooth picture connecting all data points,

3.fit a simple curve (linear, quadratic) to empirical (not so accurate) data. The

curve be 'as close as possible' to the individual data points - we will have to agree on some overall criterion.

More complicated mathematical functions

over a specific range ofvalues. Similarly to the previous case. we cannot do this exactly, but have to minimize (in some well defined sense) the error of thefit.

There are several reasons for doing this:

1. Polynomials are easy to evaluate (we just add/subtract and multiply - and

ultimately, all numerical computation has to be reduced to these)

2. they are also easy to integrate and dierentiate - we may thus substitute our

fitted polynomial for the actual function (which may be very hard or even impossible to integrate). To facilitate the procedure (offitting polynomials to a function), several sets of orthogonal polynomials are introduced (e.g. Legendre, Chebyshev, Hermite, etc.).

Numerical Integration and Dierentiation

Here the objective is clear; we know that many functions are impossible to integrate analytically,sowewanttohaveanaccuratewayofdoingthisnumerically. We would also like to have some idea and control over the accuracy of the results.

Integration

Thewayhowwecannumericallyevaluate

R ()is to choose a set ofvalues (so called nodes)inthe[ ]interval, for each (say =012 )of these compute the corresponding )We then have to develop a formula for combining these values to accurately estimate the integral (the area between the ()function and theaxis). ways of approaching it: 6

1. A sensible (but in a sense arbitrary) choice ofequidistant values (eectively

subdividing [ ]intoequal-length subintervals, leading to two basic 'rules' of integration, trapezoidalandSimpson, to be studied in detail.

2. A choice of

points which is, in a certain sense,optimal(we can define 'optimal' only when we have a better understanding of the issues).

Dierentiation

similarly involves estimating the value of 0 00 ()etc. at= 0

This can be

done by computing ()at 0 and a few extra values ofin the neighborhood of 0 (this time, we will almost always choose them equidistant), and plugging them into the corresponding formula (which, of course, will be our task to develop). The major problem facing us here will the round-off error.

Related issues

The formulas for numerical dierentiation can also be used (this is in fact their major application) to solve, numerically, various types of ordinaryand partial differential equations . We will deal with some examples of the ODE variety only ( boundary-valueproblem). In this context, we will also have to learn solving nonlinear(regular) equations.

Matrix Algebra

The basic problem is to solvelinear equations forunknowns, i.e.Ax=r where Ais anby(square) matrix,xis the (column) vector of theunknowns, and ris similarly a vector of the right hand side values. The simplest technique uses the so called

Gaussian eliminationandbackward substitution.One

can reduce the round-oerror by adding an extra step (row interchange) called pivoting In some (important) special cases (related to our treatment of dierential equa- tions) Ais tridiagonal (only the elements on or adjacent to the main-diagonal are non-zero). It then becomes more ecient to use a dierent approach, namely a so called

LUdecompositionof matrixA

We will then employ some of these techniques to learn how to solve, itera- tively ,non-linear equations forunknowns, byNewton's method(we will start with a single equation for one unknown).

Eigenvalues and eigenvectors

of square matrices are defined by Ax=x where x(non-zero) is an eigenvector andan eigenvalue.

To simplify the issue, we will assume that

Aissymmetric(a fairly important

class of matrices), which implies that both eigenvalues and eigenvectors must be real (they could becomplexin general). We will then learn how tofind them, one by one (there is of them in general), byfirst utilizingHousholder's method to reduce Ato a tridiagonal matrix, and then the applying, repeatedly, the so called QLalgorithm to extract the smallest eigenvalue. The resulting matrix is then deflatedand the process repeated till all eigenvalues are found. 7

Remaining Topics

There is a number of important topics which we will not have time to discuss in this brief course, namely:

1. Solving ordinary dierential equations (initial-valueproblem).

2. Solving partial dierential equations.

3. Optimizing a function of several variables (finding its largest or smallest

value). 8 9

Chapter 2 USING MAPLE

Basics

Typing anexpression(following Maple'sprompt) results in evaluating it. When the expression contains only integers (no decimal point), one gets the exact (rational) answer, as soon as at least one number in the expression is real (with a decimal point), the result is real (rounded oto 10 significant digits). The symbols andˆfacilitate multiplication, division and exponentiation, respectively. Note that each line of your input has to end with a semicolon:

453(5 + 2) + 2ˆ(3);

1103
56
The result of any computation can be stored under a name (which you make up, rather arbitrarily), and used in any subsequent expression. Maple then remembers the value, until the end of your session, or till you deliberately replace it with a new value. Note that this (giving a name to a result) is achieved by typing the name, followed by a colon and the equal sign (a group of two symbols, representing a single operation), followed by the actual expression to be stored: := (30+4)(26) + 2345; :=2813333333 7+9;

498095238

:= 146; 7 3 7+9; 28
3 (from now on, we will omit the prompt from our examples, showing only what wehave to type).

Maple can also handle the usual functions such as

sin, cos, tan, arcsin, arccos, arctan, exp, ln, sqrt , etc. All angles are always measured in radians. sin(3);sqrt(8);

1411200081

2 2

We can also

defineour own functions by: :=ˆ2; 10 2 (3); 9 where is an arbitrary name.

Lists and Loops

Maple can store, under a single name, a wholelistof values, thus: := [325sqrt(3)7]; 3 2 537]
The individual elements of a list can be referenced by indexing (and used in computing another expression): [2]4; 20

One can add elements of a list by the following

command(as Maple calls them): sum ('[]',''=14); 27
2 +3 One can convert the last answer to its decimal form by: evalf(%);

1523205081

Note that the

%symbol always refers to the previous expression.

Similarly to

sum, one can also computeproductof elements of a list.

To subtract say

3from each element of the listredefiningcorrespondingly,

canbeachievedby: forfrom1to4do[]:=[]3end do:

Note that terminating a statement by

:instead of the usual;will prevent Maple from printing the four results computed in the process (we may not need to see them individually). Also note that, upon completion of this statement, will have the value of

5(any informationhad contained previously will have been

destroyed)! We can easily verify that the individual elements of our list have been updated accordingly: [2]; 2 We may also create a list using the following approach: := [seq(2ˆ=16)]; := [248163264]; 11

Variables and Polynomials

If a symbol, such as for examplehas not been assigned a specificvalue,Maple considers it a variable. We may then defineto be apolynomialinthus: := 32+4ˆ2; := 32+4 2

A polynomial can be dierentiated

di( ); 2+8 integrated from, say, 0to3 int (=03); 36
or plotted, for a certain range of values plot (=03); We can also evaluate it, substituting a specificnumberfor(there are actually two ways of doing this): subs (=3);eval( =3); 33
33
We can also multiply two polynomials (in our example, we will multiply by itself), but to convert to a regular polynomial form, we nee to expandthe answer: ;expand(%); (3quotesdbs_dbs5.pdfusesText_9

[PDF] numerical analysis pdf download

[PDF] numerical analysis pdf for computer science

[PDF] numerical analysis pdf s.s sastry

[PDF] numerical analysis pdf sauer

[PDF] numerical analysis pdf solutions

[PDF] numerical analysis questions and answers pdf

[PDF] numerical mathematical analysis pdf

[PDF] numerical methods for computer science pdf

[PDF] numerical methods for engineering and science by saumyen guha pdf

[PDF] numerical methods for scientific and engineering computation 4th edition pdf

[PDF] numerical methods for solving system of nonlinear equations

[PDF] numerical methods in civil engineering book pdf

[PDF] numerical methods journal pdf

[PDF] numerical methods practical applications

[PDF] numerical methods problems and solutions pdf