[PDF] LECTURE NOTES on ELEMENTARY NUMERICAL METHODS PDF slides.pdf

LECTURE NOTES on Numerical Methods for Initial Value Problems 341 In later analysis we shall need a quantity (called vector norm) that measures

ultimately, all numerical computation has to be reduced to these) 2 they are also easy to integrate and differentiate - we may thus substitute our fitted polynomial

[PDF] Numerical Analysis II – Lecture Notes - Department of Mathematical

12 mar 2018 · Iterative methods are the only option for the majority of problems in numerical analysis, and may actually be quicker even when a direct method

[PDF] MATH 435 Lecture Notes on Numerical Analysis - NIU Math

In this lecture, we will discuss numerical methods for the Root-Finding Problem Notes: 1 From the statement of the Bisection algorithm, it is clear that the

[PDF] Lecture Notes on Numerical Methods - Department of Mathematics

Preface What follows were my lecture notes for Math 3311: Introduction to Numerical Meth- ods, taught at the Hong Kong University of Science and Technology

[PDF] NOTES FOR NUMERICAL METHODS - MathCityorg

As analytic solutions are often either too tiresome or simply do not exist, we need to find an approximate method of solution This is where numerical analysis

[PDF] Numerical Analysis Notes - Unhaggle

Notes(PDF) Numerical Methods - Lecture Notes 2019 – 2020 Najm Numerical Analysis Handwritten Notes PDF for BSc Download S Baskar A short summary

[PDF] Introduction to Numerical Analysis - IITB Math - IIT Bombay

course is designed to meet this goal A first course in Calculus is indispensable for numerical analysis The first chapter of these lecture notes quickly reviews all

[PDF] Lecture Notes on Numerical Methods for Engineering (?) Pedro

Matlab: I shall try to make all the code in this notes runnable on Octave but this than geometric ideas because numerical analysis deals with formal methods of

[PDF] LECTURE NOTES on ELEMENTARY NUMERICAL METHODS

LECTURE NOTES on Numerical Methods for Initial Value Problems 341 In later analysis we shall need a quantity (called vector norm) that measures

LECTURE NOTES

ELEMENTARY NUMERICAL METHODSEusebius Doedel

Vector and Matrix Norms

Banach Lemma20

The Numerical Solution of Linear Systems

Gauss Elimination25

Operation Count29

Using the LU-decomposition for multiple right hand sides 34

Tridiagonal Systems37

Inverses40

Practical Considerations47

Gauss Elimination with Pivoting53

Error Analysis56

The Numerical Solution of Nonlinear Equations

Some Methods for Scalar Nonlinear Equations77

Bisection78

Regula Falsi80

Newton"s Method83

The Chord Method87

Newton"s Method for Systems of Nonlinear Equations 92

Residual Correction99

Convergence Analysis for Scalar Equations102

Convergence Analysis for Systems145

The Approximation of Functions

158

Function Norms158

Lagrange Interpolation Polynomial166

Lagrange Interpolation Theorem176

Chebyshev Polynomials185

Chebyshev Theorem191

Taylor Polynomial207

Taylor Theorem211

Local Polynomial Interpolation216

Numerical Differentiation

231

Best Approximation in the? · ?2

240

Best Approximation inR3240

Best Approximation in General247

Gram-Schmidt Orthogonalization256

Best Approximation in Function Space259

Numerical Integration

268

Trapezoidal Rule270

Simpson"s Rule273

Gauss Quadrature287

Discrete Least Squares Approximation

296

Linear Least Squares298

General Least Squares306

Smooth Interpolation by Piecewise Polynomials

326

Cubic Spline Interpolation330

Numerical Methods for Initial Value Problems

341

Numerical Methods347

Stability of Numerical Approximations355

Stiff Differential Equations365

Boundary Value Problems in ODE

384

A Nonlinear Boundary Value Problem400

Diffusion Problems

404

Nonlinear Diffusion Equations417

VECTOR AND MATRIX NORMS

In later analysis we shall need a quantity (called vector norm ) that measures the magnitude of a vector.

Letx≡(x1,x2,···,xn)T?Rn.

EXAMPLES

(of norms) : ?x?1≡n? k=1|xk|,(the " one-norm ?x?2≡(n? k=1x k2)1

2,(the "

two-norm ", or Euclidean length) infinity-norm ", or "max-norm") 1 ?x?1and?x?2are special cases of ?x?p≡(n? k=1|xk|p)1 p,(wherepis a positive integer), while for any fixed vectorxwe have ?x?∞is the limit of?x?pasp→ ∞.(

Check!

EXAMPLE

: Ifx= (1,-2,4)Tthen ?x?1= 7,?x?2=⎷

21,?x?∞= 4.

Vector norms are required to satisfy

(i) ?x? ≥0,?x?Rnand?x?= 0 only ifx=0, (ii) ?αx?=|α| ?x?,?x?Rn,?α?R, (iii)

Triangle inequality

All of the examples of norms given above satisfy

(i) and (ii)

Check !

To check condition

(iii) let x= (x1,x2,···,xn)T,y= (y1,y2,···,yn)T. Then ?nk=1|xk|+?nk=1|yk|=?x?1+?y?1. =?x?∞+?y?∞. 4

EXERCISES

Letx= (1,-2,3)T. Compute?x?1,?x?2, and?x?∞.Graphically indicate all pointsx= (x1,x2)TinR2for which?x?2= 1.

Do the same for?x?1and?x?∞.Graphically indicate all pointsx= (x1,x2,x3)T?R3with?x?2= 1. n?x?∞. 5 We also need a measure of the magnitude of a square matrix ( matrix norm

This is defined

in terms of a given vector norm , namely, ?A? ≡maxx?=0?Ax? ?x?.

Thus?A?measures the

maximum relative stretching in a given vector norm that occurs when multiplying all non-zero vectorsx?RnbyA. From this definition it follows that for arbitraryy?Rn,y?=0, we have ?Ay? i.e., 6 For specific choices of vector norm it is convenient to express the induced matrix norm directly in terms of the elements of the matrix :

For the case of the? · ?∞let

A≡((((a

11a12···a1n

21a22···a2n

a n1an2···ann)))) ,and letR≡maxin j=1|aij|.

ThusRis the "

maximum absolute row sum ". Forx?Rn,x?=0, we have ?Ax?∞ ?x?∞=maxi|?nj=1aijxj| ?x?∞ maxi?nj=1|aij||xj|?x?∞ maxi{?nj=1|aij| ?x?∞} ?x?∞=R . 7 Next we show that for any matrixAthere always is a vectoryfor which ?Ay?∞ ?y?∞=R . Letkbe the row ofAfor which?nj=1|akj|is a maximum,i.e., n j=1|akj|=R .

Takey= (y1,y2,···,yn)Tsuch that

y j=???1 ifakj≥0, -1 ifakj<0. Then ?Ay?∞ ?y?∞=?Ay?∞= maxi|n? j=1a ijyj|=n? j=1|akj|=R . 8

Thus we have shown that

?A?∞is equal to the maximum absolute row sum.

EXAMPLE

: If A=(( 1 2-3 1 0 4 -1 5 1)) then ?A?∞= max{6,5,7}= 7. NOTE : In this example the vectoryis given byy= (-1,1,1)T.

For this vector we have

?Ay?∞ ?y?∞= 7 = maximum absolute row sum. 9

Similarly one can show that

?A?1≡maxx?=0?Ax?1 ?x?1= maxjn i=1|aij| the maximum absolute column sum. (Check !

EXAMPLE

: For the matrix A=(( 1 2-3 1 0 4 -1 5 1)) we have ?A?1= max{3,7,8}= 8. 10

One can also show that

?A?2≡maxx?=0?Ax?2 ?x?2= maxiκi(A), where theκi(A) are defined to be the square roots of the eigenvalues of the matrixATA. (These eigenvalues are indeed nonnegative).

The quantities{κi(A)}ni=1are called the

singular values of the matrixA. 11

EXAMPLE

: If

A=?1 10 1?

then A

TA=?1 01 1? ?

1 1 0 1? =?1 11 2?

The eigenvaluesλofATAare obtained from

det(ATA-λI) = det?1-λ1

1 2-λ?

= (1-λ)(2-λ)-1 =λ2-3λ+1 = 0, from which

1=3 +⎷

2andλ2=3-⎷

5 2.

Thus we have

?A?2=? (3 +⎷

5)/2≂=1.618.

IfAis invertible then we also have

?A-1?2=1 miniκi(A). Thus if we order the square roots of the eigenvalues ofATAas

1≥κ2≥ ···κn≥0,

then ?A?2=κ1,and?A-1?2=1

κn.

Thus in the previous example we have

?A-1?2=1 ?(3-⎷

5)/2≂

=1.618 (!) 13

EXERCISES

LetA=?0 20 0?

. Compute?A?2.LetA=(( 1 0 0 0 0 1

0-1 0))

.Compute?A?2. n?A?∞. Prove that?A?1is equal to the maximum absolute column sum. 14

EXERCISES

LetAbe anynbynmatrix. For each of the following state whether it is true or false. If false then give a counter example. there is a vectorx?=0such that ?Ax?∞=?A?∞?x?∞.Give aconstructive proofthat for any square matrixA there is a vectorx?=0such that ?Ax?1=?A?1?x?1.Is there a vectorxsuch that ?Ax?1>?A?1?x?1? 15 All matrix norms defined in terms of (induced by) a given vector norm as ?A?= maxx?=0?Ax? ?x? automatically satisfy (i) ?A? ≥0,and?A?= 0 only ifA=O(zero matrix), (ii) ?αA?=|α| ?A?,?α?R, (iii) Check : Properties ( i) and ( ii) ! 16 PROOF of (iii) ?A+B?= maxx?=0?(A+B)x? ?x? = max x?=0?Ax+Bx??x? ?x?+ maxx?=0?Bx? ?x?quotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] LECTURE NOTES on ELEMENTARY NUMERICAL METHODS

LECTURE NOTES

ELEMENTARY NUMERICAL METHODSEusebius Doedel

TABLE OF CONTENTS

Vector and Matrix Norms

Banach Lemma20

The Numerical Solution of Linear Systems

Gauss Elimination25

Operation Count29

Tridiagonal Systems37

Inverses40

Practical Considerations47

Gauss Elimination with Pivoting53

Error Analysis56

The Numerical Solution of Nonlinear Equations

Some Methods for Scalar Nonlinear Equations77

Bisection78

Regula Falsi80

Newton"s Method83

The Chord Method87

Residual Correction99

Convergence Analysis for Scalar Equations102

Convergence Analysis for Systems145

The Approximation of Functions

Function Norms158

Lagrange Interpolation Polynomial166

Lagrange Interpolation Theorem176

Chebyshev Polynomials185

Chebyshev Theorem191

Taylor Polynomial207

Taylor Theorem211

Local Polynomial Interpolation216

Numerical Differentiation

Best Approximation in the? · ?2

Best Approximation inR3240

Best Approximation in General247

Gram-Schmidt Orthogonalization256

Best Approximation in Function Space259

Numerical Integration

Trapezoidal Rule270

Simpson"s Rule273

Gauss Quadrature287

Discrete Least Squares Approximation

Linear Least Squares298

General Least Squares306

Smooth Interpolation by Piecewise Polynomials

Cubic Spline Interpolation330

Numerical Methods for Initial Value Problems

Numerical Methods347

Stability of Numerical Approximations355

Stiff Differential Equations365

Boundary Value Problems in ODE

A Nonlinear Boundary Value Problem400

Diffusion Problems

Nonlinear Diffusion Equations417

VECTOR AND MATRIX NORMS

Letx≡(x1,x2,···,xn)T?Rn.

EXAMPLES

2,(the "

Check!

EXAMPLE

21,?x?∞= 4.

Vector norms are required to satisfy

Triangle inequality

All of the examples of norms given above satisfy

Check !

To check condition

EXERCISES

This is defined

Thus?A?measures the

For the case of the? · ?∞let

A≡((((a

11a12···a1n

21a22···a2n

ThusRis the "

Takey= (y1,y2,···,yn)Tsuch that

Thus we have shown that

EXAMPLE

For this vector we have

Similarly one can show that

LetA=?0 20 0?