Lectures on Numerical Analysis - Penn Math

1 Lectures on Numerical AnalysisDennis Deturck and Herbert S. WilfDepartment of MathematicsUniversity of PennsylvaniaPhiladelphia, PA 19104-6395 Copyright 2002, Dennis Deturck and Herbert WilfApril 30, 20022 Contents1 Di erential and Di erence Linearequationswithconstantcoe Di erenceequations .. Computingwithdi Stability theory .. Stability theory of di erence equations .. 192 The Numerical Solution of Di erential Euler'smethod .. Softwarenotes .. Systemsandequationsofhigherorder .. Howtodocumentaprogram.

2 Comparisonofthemethods .. Predictor-corrector methods .. Controlling the step size .. :Rockettothemoon .. Example:Computingthecosinefunction .. Example:Themoonrocketinonedimension .. 744 CONTENTS3 Numerical linear Vector spaces and linear Linearsystems .. Buildingblocksforthelinearequationsolver .. Howbigiszero? .. Operationcount .. Tounscrambletheeggs .. Eigenvalues and eigenvectors of matrices .. The orthogonal matrices of ConvergenceoftheJacobimethod .. Corbat o's idea and the implementation of the Jacobi algorithm.

3 Getting it together .. 124 Chapter 1Di erential and Di IntroductionIn this chapter we are going to study di erential equations, with particular emphasis on howto solve them with computers. We assume that the reader has previously met di erentialequations, so we're going to review the most basic facts about them rather erential equationis an equation in an unknown function, sayy(x), where theequation contains various derivatives ofyand various known functions ofx. The problemis to \ nd" the unknown function. Theorderof a di erential equation is the order of thehighest derivative that appears in 's an easy equation of rst order:y0(x)=0:( )The unknown function isy(x) = constant, so we have solved the given equation ( ).

4 The next one is a little harder:y0(x)=2y(x):( )A solution will, now doubt, arrive after a bit of thought, namelyy(x)= ,ify(x)is a solution of ( ), then so is 10y(x), or 49:6y(x), or in factcy(x) for any a solution of ( ). Are there any other solutions? No there aren't,because ifyis any function that satis es ( ) then(ye 2x)0=e 2x(y0 2y)=0;( )and soye 2xmust be a constant, general, we can expect that if a di erential equation is of the rst order, then themost general solution will involve one arbitrary constantC. This is not always the case,6Di erential and Di erence Equationssince we can write down di erential equations that have no solutions at all.

5 We would have,for instance, a fairly hard time (why?) nding a real functiony(x)forwhich(y0)2= y2 2:( )There are certain special kinds of di erential equations that can always be solved, andit's often important to be able to recognize them. Among there are the \ rst-order linear"equationsy0(x)+a(x)y(x)=0;( )wherea(x) is a given function we describe the solution of these equations, let's discuss the an equation is linear is to say that if we have any two solutionsy1(x)andy2(x)oftheequation, thenc1y1(x)+c2y2(x) is also a solution of the equation, wherec1andc2are anytwo constants (in other words, the set of solutions forms a vector space).

6 Equation ( ) is linear, in fact,y1(x)=7andy2(x) = 23 are both solutions, and sois 7c1+23c2. Less trivially, the equationy00(x)+y(x) = 0( )is linear. The linearity of ( ) can be checked right from the equation itself, withoutknowing what the solutions are (do it!). For an example, though, we might note thaty=sinxis a solution of ( ), thaty=cosxis another solution of ( ), and nally,by linearity, that the functiony=c1sinx+c2cosxis a solution, whatever the constantsc1andc2. Now let's consider an instance of the rst order linear equation ( ):y0(x)+xy(x)=0:( )So we're looking for a function whose derivative is xtimes the function.

7 Evidentlyy=e x2=2will do, and the general solution isy(x)=ce x2= instead of ( ) we hady0(x)+x2y(x)=0;then we would have found the general solutionce x3= a last example, takey0(x) (cosx)y(x)=0:( )The right medicine is nowy(x)=esinx. In the next paragraph we'll give the general ruleof which the above are three examples. The reader might like to put down the book at thispoint and try to formulate the rule for solving ( ) before going on to read about What we need is to choose some antiderivativeA(x)ofa(x), and then thesolution isy(x)=ce A(x).Since that was so easy, next let's put a more interesting right hand side into ( ), byconsidering the equationy0(x)+a(x)y(x)=b(x)( ) Introduction7where nowb(x) is also a given function ofx(Is ( ) a linear equation?)

8 Are you sure?).To solve ( ), once again choose some antiderivativeA(x)ofa(x),andthennotethat we can rewrite ( ) in the equivalent forme A(x)ddx eA(x)y(x) =b(x):Now if we multiply through byeA(x)we see thatddx eA(x)y(x) =b(x)eA(x)( )so , if we integrate both sides,eA(x)y(x)=Zxb(t)eA(t)dt+const.;( )where on the right side, we mean any antiderivative of the function under the integral (x)=e A(x) Zxb(t)eA(t)dt+const. :( )As an example, consider the equationy0+yx=x+1:( )We nd thatA(x)=logx, then from ( ) we gety(x)=1x Zx(t+1)tdt+C =x23+x2+Cx:( )We may be doing a disservice to the reader by beginning with this discussion of certaintypes of di erential equations that can be solved analytically, because it would be erroneousto assume that most, or even many, such equations can be dealt with by these , the reason for the importance of the Numerical methods that are the main subjectof this chapter is precisely that most equations that arise in \real" problems are quiteintractable by analytical means, so the computer is the only the above disclaimer.

9 In the next section we will study yet another importantfamily of di erential equations that can be handled analytically, namely linear equationswith constant coe Find the general solution of each of the following equations:(a)y0=2cosx8Di erential and Di erence Equations(b)y0+2xy=0(c)y0+xy=3(d)y0+1xy= x+5(e) 2yy0=x+12. Show that the equation ( ) has no real Go to your computer or terminal and familiarize yourself with the equipment, theoperating system, and the speci c software you will be using. Then write a programthat will calculate and print the sum of the squares of the integers 1;2;:::;100.

10 Runthis For each part of problem 1, nd the solution for whichy(1) = Linear equations with constant coe cientsOne particularly pleasant, and important, type of linear di erential equation is the varietywith constant coe cients, such asy00+3y0+2y=0:( )It turns out that what we have to do to solve these equations is to try a solution of a certainform, and we will then nd that all of the solutions indeed are of that 's see if the functiony(x)=e xis a solution of ( ). If we substitute in ( ),and then cancel the common factore x, we are left with the quadratic equation 2+3 +2=0whose solutions are = 2and = 1.