### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Numerical Methods I COSC 3361

UH

GPA 3.94

### View Full Document

## 66

## 0

## Popular in Course

## Popular in Chemistry

This 64 page Class Notes was uploaded by Lowell Harris on Saturday September 19, 2015. The Class Notes belongs to COSC 3361 at University of Houston taught by Staff in Fall. Since its upload, it has received 66 views. For similar materials see /class/208183/cosc-3361-university-of-houston in Chemistry at University of Houston.

## Reviews for Numerical Methods I

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15

IIll COSC 3361 Numerical Analysis Ordinary Differential Equations VI Boundary value problem EdgarGab m Fall 2005 0080 3361 Numerical Analysis Edgar Gabriel CSUH Initial value vs boundary value problems Initial value problem y fty aStSb ya yo Boundary value problem y ftyy aStSb ya ya W yb 0080 3361 Numerical Analysis Edgar Gabriel 2 C J UH Existence and uniqueness of the solution of initial value Problems Existence theorem for initialvalue Problems If fis continuous in a rectangle R centered around then the initial value problem lt tol s a y yol s y f by ya yo a solution yt for lt tol smina M with M maxlftyl on R Uniqueness theorem for initialvalue problems If f and g are continuous on the rectangle R defined previously then the initial value problem has a unique solution in the interval lttol SminW M 0080 3361 Numerical Analysis Edgar Gabriel 3 C J UH Existence Theorem for boundary value problems The boundary value problem y fty y0 O y1 o a has a unique solution If E7 IS continuous nonnegative and bounded in the infinite strip defined by O S t 1 oltgt S y S 00 0080 3361 Numerical Analysis Edgar Gabriel 4 C J UH Example Check whether the following two points boundaryvalue has a unique solution y 5y sin 3ye y0 0 N 0 Solution 81 53cos 3ye By By is continuous in the strip 031 SvS sis is bounded above by 8e gt Problem has a unique solution 0080 3361 Numerical Analysis Edgar Gabriel 5 Theorems on boundary value problems ll One can show that the problem y fty ya a W can be transformed into 5 gtz 210 a z1 gtz b a2fa b atz through a change of variables yt Zt a b 61 or Zt ya b at 0080 3361 Numerical Analysis Edgar Gabriel 6 Theorems on boundary value problems Ill One can show that the problem y ay y0 a y1 can be transformed into Z 80 z0 0 z1 0 gtzftza at through a change of variables yo zt a at or zt W a 0m 0080 3361 Numerical Analysis Edgar Gabriel 7 Shooting Methods I Given the boundary value problem y ftay aStSb 81 yaa W Solution of 81 can be obtained by guessing an appropriate second initial valuey a z and solve the initial value problem Resulting value 3219 Objective select y a z such that 3 0080 3361 Numerical Analysis Edgar Gabriel Shooting Methods ll For that we define the nonlinear function 19z z and find the zero of that function Any of the methods discussed in the section Solution of nonlinear equations can be used to solve the problem Bisection Newton Secant Note calculating 3z is very expensive since it involves the solution of an initial value problem eg using a RungeKutta or a multistep method 0080 3361 Numerical Analysis Edgar Gabriel 9 C J UH Shooting Methods Ill Secant Method X X xn1 xn fxn n x fan 1 Applied to the boundary value problem leads to n l Z Z Z Zng Znn n1 1 eon mu 0080 3361 Numerical Analysis Edgar Gabriel 10 C J Algorithm input f a b 20 21 alpha beta epsilon f 2nd order ODE ab interval alpha beta boundary value of the ODE at a resp b 2021 two initial guesses for the second initial value epsilong desired accuracy myrungegatgb solves f in the interval ab and returns the function value at b Since f describes a 2nd order ODE we need o0 o0 two initial values PhiO myrungeatb f a b alpha zO beta Phil myrungeatb f a b alpha zl beta for k l MAX 2 21 Phil zl zOPhil Phi0 PhiO Phil Phil myrungeatb f a b alpha 2 beta if Phi lt epsilon break 20 21 21 2 end Interpolation Since calculating 62 is very expensive polynomial interpolation is often used to estimate 2 such that 6z0 Note the inverse notation 0a 9a lac Z0 Z1 Zn p9ZnZn Calculating pO 0080 3361 Numerical Analysis Edgar Gabriel 12 0080 3361 Numerical Analysis Numerical Integration and Differentiation Ill Gauss Quadrature and Adaptive Quadrature Edgar Gabriel Fall 2005 I111 0080 3361 Numerical Analysis Edgar Gabriel CSUH Summary of the last lecture I For approximating an integral value one can determine the approximating polynomial of degree n The according integral is then I fxdx z j pxdx j fxilixdx ziAi xi 21 a a 0 i0 i0 For equally spaced pointsx0x1xnthe formula 21 is called the NewtonCotes formula The NewtonCotes formula produce exact results for f being a polynomial of degree at most n 0080 3361 Numerical Analysis Edgar Gabriel C J UH Summary of the last lecture ll Two ways of calculating the coefficients A in the NewtonCotes formula have been presented Using the Lagrange form of the interpolating polynomial Using the method of undetermined coefficients k A Name 1 1 l Trapezoid rule 2 2 2 1 g 1 Simpsons rule 6 6 6 3 t g g 1 38th rule 8 8 s s 4 l 32 g g 7 Milne 90 90 90 90 90 0080 3361 Numerical Analysis Edgar Gabriel Change of intervals I A formula derived for a certain interval can easily be adapted to any other interval by making a change of variable eg using the substitution xabat jfomub mjfoH4b mnm and for the approximation foyub mjfoH b mnm zw miAJmw mm 0080 3361 Numerical Analysis Edgar Gabriel C J UH Change of intervals ll Even more generally b ad d C fltdt If 206126 with 1 b a ad bc t xix d C d C 0080 3361 Numerical Analysis Edgar Gabriel C Quadrature Formulas General quadrature formulas are described by b n l fxdx zZaim a i0 Basic steps to solve an integral using a quadrature formula Determinethe knots ti Construct the interpolating polynomial Determinethe coefficients at 0080 3361 Numerical Analysis Edgar Gabriel Composite Formulas I Applying a integration formula onto multiple intervals For equidistant points xi aih with h xi xi l ifxdx 2k Tfxdx i1 XH ince Ifoodx xi xi 1Zajfxi 1 xi xi 1tj ajfxi 1 htj Thus MHZ foodx thiajfxl1htj i1 jO 0080 3361 Numerical Analysis Edgar Gabriel C J UH Error estimates I Truncation error for the composite Formula b k rt emlthgt i fltxgtdx hZZajfltxil 11 i1 jO Assuming that instead of the exact values fxi1htjwe can only calculate f with fOCH m1 1111quot 3 8f 0080 3361 Numerical Analysis Edgar Gabriel C J UH Error estimates ll The error is then 3 6h ajfi Lj J Zajfxi1mj M ffxdx h i 3 II S i f xdx hi i1 k n etrunc k n h 2 ajfx1 mi 12 Z ajfi Lz39 i1 jO i1 i0 eroundo 0080 3361 Numerical Analysis Edgar Gabriel C J UH Error estimates Ill Since a NewtonCotes formula is exact for all polynomials of degree at most n all methods of order gt 1 have to integrate pt c exactly Thus 1 k k IptdtCZajC Zaj1 101 0 i0 i0 Using 91 we can rewrite the roundoff error a k n k n ZZaijcH mj hZZaj Lj i1 3 hgfiioiaji 102 1 0080 3361 Numerical Analysis Edgar Gabriel C J UH groundo S h Error estimates IV If all values for a are positive k k Zlajl2aj1 111 jO jO and emndo S hnef b a8f If not all values of ai are positive equation 111 is not correct Roundoff error is magnified by the process Calculation is not stable 0080 3361 Numerical Analysis Edgar Gabriel C J UH Conclusions All NewtonCotes formulas with purely positive coefficients a are numerically stable This is only the case for the algorithms of degree k 7 and k 9 Algorithms fork 8 or k 210 have some negative coefficients a and are therefore not stable 0080 3361 Numerical Analysis Edgar Gabriel C J UH Generalized quadrature formulas NewtonCotes For the formula of degree n we had n coefficients which had to be determined The choice of nodes t were done a priori The equations to determine the coefficients were set up such that the formula produces exact results for all polynomials of degree at most 17 Other definitions for the coefficients might be useful as well eg Cbhebyshev s quadrature formulas lfltxgtdxziorltm aft 0080 3361 Numerical Analysis Edgar Gabriel C J UH Gaussian quadrature formulas I Gaussian quadrature Determine the knots such that the resulting formulas of degree n is exact for all polynomials of degree 2n1 Introduce a weight function wx such that b n l fxwxdx z Zeami 141 a i0 Furthermore let q be a nonzero polynomial of degree n1 that is worthogonal to H Thus for any polynomial of degree n we have lqxpxwxdx 0 0080 3361 Numerical Analysis Edgar Gabriel C J UH Gaussian quadrature formulas ll Using the zeros of qx formula 141 will be exact for all polynomials of degree 2n1 The polynomials qx with the desired behaviour are called Legendre polynomials All zeros are simple roots Zeros of these functions are well documented for many degrees n After determining the zeros of the Legendre Polynomials of degree n determine the coefficients a using eg the method of undetermined coefficients 0080 3361 Numerical Analysis Edgar Gabriel C J UH Example Determine the Gaussian quadrature rule when ab1 1 WX1 and n2 The orthogonal polynomials are 3 qox1 41xx c12xxz l 613Xx3 x The roots of c1306 are on Thus ifmdwaof06f0azf Using the method of undetermined coefficients one obtains 8 5 0080 3361 Numerical Analysis Edgar Gabriel C J UH Coefficients of the Gaussian Quadrature fornu as All coefficients and zeros are transformed to the interval 01 k ai ti Degree 1 2 1 l 2 2 1 1 LE 1 4 2 2 2 6 2 6 3 3 3 3 LE 1 15 6 18 18 18 2 10 2 0080 3361 Numerical Analysis Edgar Gabriel C O UH Adaptive Quadrature Given a function f interval ab required accuracy 5 If a given method will not be sufficiently accurate on the given interval divide the interval into two equal parts Repeat this procedure until desired accuracy has been reached Problem how to estimate the error of the quadrature algorithm used 0080 3361 Numerical Analysis Edgar Gabriel C J UH Adaptive Quadrature ll Example Simpson s rule b a ab 6 fa4f 2 Sab l fxdx gtfltbgtEltaJagt with the error term being Ema itltb agt215flt4gtltcfgt 90 or slightly rewritten jfxdxSuvvu25f4 191 0080 3361 Numerical Analysis Edgar Gabriel C J UH Adaptive Quadrature III When subdividing into two subdomains jfxdx jfxdxjfxdx u 14 iw 5 4 Suw 90W u2f 52 i 5 4 SWv 90W W2f 53 5 Mjf 4gt f 4gt i 201 1 SuwSwv 22 0080 3361 Numerical Analysis Edgar Gabriel C J UH Adaptive Quadrature IV With WW f4 2 flt4 3 equation 201 becomes Ifxdx SuwSwv v u5f4gt 211 Note each subdomain has to fulfill the local error term given by 380 xi 1Vu 212 6139 Note WW usually not available Assumption over a small interval f 4gt c Thus 1mg fmgl 213 0080 3361 Numerical Analysis Edgar Gabriel C J UH Adaptive Quadrature V Using 21 3 the term WW can be eliminated by IIll multiplying 211 by 1615 multiplying 191 by 115 gt subtracting 222 from 221 This leads to Ifxdx a Su w Swv Suw Swv Suv 223 Error estimate 0080 3361 Numerical Analysis Edgar Gabriel Adaptive Quadrature Algorithm 39 Given f a b s hb a2 lh2 Calculate fafalfahfahlfb Calculate Sab Saah Sahb Calculate error term ell5SaahSahb Sltab Compare e with the local error term as defined in 212 If accuracy not satisfactory start the same procedure twice by setting aa bah aah bb 0080 3361 Numerical Analysis Edgar Gabriel C O UH IIll COSC 3361 Numerical Analysis Ordinary Differential Equations VII Finite Differences EdgarGab m Fall 2005 0080 3361 Numerical Analysis Edgar Gabriel CSUH Initial value vs boundary value problems Initial value problem y fty aStSb ya yo Boundary value problem y ftyy aStSb yaa yb 0080 3361 Numerical Analysis Edgar Gabriel 2 C J UH Finite Differences Approach Idea replace the derivatives in the ODE by an according approximation formula Typically central differences 1 h yt 2hyt yt 11 t yth2ytyt hl Let the interval ab be partitioned into tO t19vtnatn1 with t0 61 and tn1 17 0080 3361 Numerical Analysis Edgar Gabriel 3 C J UH Finite Differences Approach ll For simplicity lets assume the points are equally spaced b tiaih OSiSn1 mil 6 A two point boundary value problem becomes then yo a 1 2 1 b in YiYi 1 ftaya2 h i1yi 1 41 yn1 Equation 41 leads to a system of equations Solving the system of linear equations gives the solution of the ODE at the distinct points t0t1tntn1 0080 3361 Numerical Analysis Edgar Gabriel 4 C J UH IIll Example Solve the following two point boundary value problem using the finite difference method with h12 y 2y 10t 0 y0 1 D2 Since h12 the mesh points are to 0 Thus yo NO 1 y2 W2 2 y1 unknown Discrete version of the ODE 12 t21 1 1 Wltyi12yiyi 1Z yi1yi 11Oti 0 531 0080 3361 Numerical Analysis Edgar Gabriel 5 Example ll For i1 and h12 this becomes 43 2 2y1yo2y2 y010t1 O 42 2y1122 11OO 8 8y14250 gt y1 0080 3361 Numerical Analysis Edgar Gabriel 6 C J UH The Linear Case Assuming the ODE is linear the according system of equations will also be linear f t y y W vty wty Equation 41 becomes 1 1 Wltyi12yiyi 1 i Viyiwi2 hyi1yi l or regrouped 1 1 2 1 w v 12 y 1 I12 3 1 wz yil zui 731 0080 3361 Numerical Analysis Edgar Gabriel 7 C J UH The Linear Case ll Multiplying 71 with h2 leads to ai d 0 bi l l 1 hwiyi1 2 112129321 1lhwiyi1 h2u or aiyi 1diyiciyi1 bi 0080 3361 Numerical Analysis Edgar Gabriel 8 C J UH The Linear Case III d1 61 3 1 a1 d2 62 3 2 a2 d3 C3 ya art 3 dn Z Cn Z yn Z art 2 dn l Cn l yn l art 1 dn y n 0080 3361 Numerical Analysis Edgar Gabriel 9 Thomas Algorithm for tridiagonal matrices I Writing out the first equation of 91 leads to d1y1cly2 b1aoa Multiply this equation by ald and subtracting it from the second equation leads to 1 dgy2czy3 17 101 Multiply with a2 and subtract it from the third equation of 91 leads 0 a similar equation 0080 3361 Numerical Analysis Edgar Gabriel 10 C J Thomas Algorithm for tridiagonal matrices ll Thus we end up with the following set of equations d1yl C1y2 71 at dgyz Czy3 17 dz lyn l Cn lyn 71 1 n Through backwards substitutions one can calculate all values yi Note algorithm only requires 2n divisions and 3n multiplications algorithm only works if the according denominators are not zero 0080 3361 Numerical Analysis Edgar Gabriel 0080 3361 Numerical Analysis Numerical Integration and Differentiation ll Numerical Integration of Polynomials Edgar Gabriel Fall 2005 I111 0080 3361 Numerical Analysis Edgar Gabriel CSUH Basic concepts of integration I Antidifferentiation Given a function fX find a function FX with the property that F x f x 1 Example fx ax gt Fx acquot1 C n1 fxex gt Fxex Calculating the Integral of a function from a to b l fxdx Fltbgt Flta 0080 3361 Numerical Analysis Edgar Gabriel C J UH Basic concepts of integration ll Graphical Interpretation 0080 3361 Numerical Analysis Edgar Gabriel C Basic concepts of integration III Some rules i6 fxdx ijxdx jgx f xdx f f 206126 j gxdx jfxdx jfxdx f fxdx jfxdx j fxdx 0080 3361 Numerical Analysis Edgar Gabriel C J UH Basic concepts of integration III Some rules 2 g 1ltbgt I fxdx I fgtg tdt g 1ltagt Ig xfxdx gxfxZ I gxf xdx 0080 3361 Numerical Analysis Edgar Gabriel CSUH Problems Some antiderivatives can not be determined easily eg 2 Do x2k1 F x d 00 I6 x gamma some can not be determined at all FxI dx In these situations numerical approximations for the integrals are required 0080 3361 Numerical Analysis Edgar Gabriel C J UH Numerical integration 15t solution use a polynomial to approximate the function in the integration domain b b fixedlepomu Using the Lagrange Form of the interpolation function b b n rt jpxdx IZfxilixdx with lix H x x a i0 jOj i xi Xj xnllmdx 71 0080 3361 Numerical Analysis Edgar Gabriel C J UH Numerical integration ll Equation 71 is often expressed as b n b j fxdx z 2 Aifxi with A139 j lixdx 81 a i0 a If the nodes in equation 81 are equally spaced it is called the NewtonCotes formula 0080 3361 Numerical Analysis Edgar Gabriel C J UH Trapezoid Rule I Applying the NewtonCotes formula for n1 assuming that x0 a and x1 19 the cardinal functions are b X x a lo 1 Thus 6 ba and lx ba AO Iloxdxb a A1Illxdxb a and b a b a lfltxgtdxz afafb Please note the trapezoid rule produces exact results for all polynomials of degree at most 1 0080 3361 Numerical Analysis Edgar Gabriel C J UH Trapezoid Rule ll 1 The error term can be expressed as e Eba3f 5 If the interval ab is partitioned into several pieces eg ax0 ltx1ltltxn 17 the trapezoid rule can be applied to each subinterval l fxdx i fxdx z gim x1fX1fxi 101 1 1 xi 101 is also called the composite trapezoid rule Can also be applied for spline functions 0080 3361 Numerical Analysis Edgar Gabriel C J UH Trapezoid Rule Ill Graphical interpretation Y 0080 3361 Numerical Analysis Edgar Gabriel C J UH NewtonCotes example For n2 and ab0 1 apply the NewtonCotes formula For equally spaced points x0 ox1lx2 1 The according cardinal functions are 10x 2x x 1 11x 4xx 1 12x 2xx A0j10xdxl A1j11xdxE A2j12xdxl Thus 0 6 o 3 o 6 from z Area lflt03fltlgtlflt1gt 0 i0 1 l 6 3 2 6 121 Note the NewtonCotes formula is exact for polynomials of degree at most n 0080 3361 Numerical Analysis Edgar Gabriel C J UH Method of undetermined coefficients Equation 121 can also be derived differently b 1 l fxdx z Aof0A1f A2f1 If the polynomial is of degree 2 use trial functions to determine 140241242 The trial functions for n2 would be foo 1xx2 0080 3361 Numerical Analysis Edgar Gabriel C J UH Method of undetermined coefficients ll Applying the trial function one obtains 1 J dxxg1 1AOA1A2 141 0 1 1 1 1 xdxax2g5 gt EEA1A2 142 1 1 1 1 1 2d 2 31gt A x x 3xO 3 3 4 1142 143 Solving 141142 and 143 leads to 1 2 1 A 2 6 1 3 A1 6 0080 3361 Numerical Analysis Edgar Gabriel C J UH Example 1 For fx3x21 determine Ifxdx Using antiderivative O Fx x3 x C andthus 1 jfxdx2 O Using NewtonCotes for n2 1 1 2 1 1 1 27 1 1 42 fmdx 6f03f26f 6346 0080 3361 Numerical Analysis Edgar Gabriel C J UH Simpson s Rule NewtonCotes of order 2 for an arbitrary interval ab b a ab 6 fa4f 2 i fxdx z fb Error term i 5 4 gt 5 6 90K a2f 5 001 0080 3361 Numerical Analysis Edgar Gabriel C J UH Composite Simpson s rule For an even number of subintervals and even spacing hb an xiaih Ogign Then ifxdx TfxdxTfxdx Tfxdx E Tfxdx i1 x214 Applying the Simpson Rule to each subinterval leads to b nZ Ifxdx zZfx2i 24fx2i 1fx2i 0 i1 Error term e iltb agth4f 4gtlt gt 0014 0080 3361 Numerical Analysis Edgar Gabriel C J UH Exercises I Derive the NewtonCotes formula for n3 based on the nodes O13231 using the method of undetermined coefficients Solution AO A1 A2 A3 l Use the formula obtained from the previous exercise to calculate ln2 using 1 1 O x1 Solution ln2z069765625 errorz00045 00 0080 3361 Numerical Analysis Edgar Gabriel C J UH

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.