### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Numerical Analysis MATH 6370

UH

GPA 3.69

### View Full Document

## 73

## 0

## Popular in Course

## Popular in Mathmatics

This 7 page Class Notes was uploaded by Alvena McDermott on Saturday September 19, 2015. The Class Notes belongs to MATH 6370 at University of Houston taught by Alexandre Caboussat in Fall. Since its upload, it has received 73 views. For similar materials see /class/208369/math-6370-university-of-houston in Mathmatics at University of Houston.

## Popular in Mathmatics

## Reviews for Numerical Analysis

### 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

Department of Mathematics Fall 2007 MATH 63707 Section 10583 A Caboussat Theorem 1 Let A E Rn be symmetiic positive de nite then the GaussSeidel method converges Let D dizzga117 227 l l l 7ann be the diagonal part of A IfA and 2D7A are symmetric positive de nite then the Jacobi method converges Proof We remind A D 7 E 7 F GaussSeidel D 7 E is a lower triangular matrix lf aii 07 for all i7 then D 7 E is regular lndeed aii eZTAei gt 0 since A is positive definite7 and the GaussSeidel method is wellde ned We know that if pI 7 B lA pD 7 e 1F lt 17 then the method converges Let A E C and go 6 C go 0 such that D 7 E 1Fgo Ago F80 MD EM Thus Ago D 7 E 7 Fgo l 7 A D 7 Egol We distinguish two cases i A 1 In this case Ago 07 which is a contradiction ii A f l is therefore required Then we have some 7 17 MIND 7 EM Even if D 7 E is real since A is real7 both sides are complex numbers The complex conjugate of this relation reads 05490 17 VWWD ET80 1 NWWD FM We multiply the rst relation by l 7 Aquot and the second by l 7 A and sum 90As0 17 AsoD 7 EM 17 A WM 7 17 soD 7 FM 17 A 2 7A 7AgtsoAso 7 17 MQWOD 7 E7Fgtso 7 1 7l2s0DAs0 Therefore 2 7 A 7 Now 7 17 Wm Agtso 2 7 7 WWW 17 7 ll2WD AW 17 Mom 7 17 Wow Since A is positive definite7 goquotAgo gt 07 ll 7 AV gt 0 since A f l and goquotDgo gt 0 since D is positive de nite diagonal matrix with all elements aii gt 0 Therefore 17w2gt0 ewa All the eigenvalue of D 7 E 1F are small than one in modulusl Therefore the method convergesl Jacobi The Jacobi method is wellde ned for the same reasons than for the GaussSeidel method We show that pD 1E F lt 1 to ensure convergence Let A E C and go 6 C g0 0 such that D 1EFso A90 EFso ADso Therefore Asa DiEiFso1Dso 90Aso 1 7 A90Dso Since g0quotAg0 gt 0 and g0Dg0 gt 0 are both real numbers7 1 7 A gt 0 is real and A lt 1 Moreover 902D 7 AW 1 AWDso Since g0quot2D 7 Ag0 gt 0 is real7 1 A gt 0 is real and A gt 71 Conclusion is that A lt 1 and the method converges D problem exactly in one pass instead solve it approximately then iterate Multigrid methods perhaps the most important 39 y in numerical r 39 in the past twenty years are based on a recursive application of this idea Even direct algorithms have been affected by the new manner of computing Thanks to the work of Skeel and others it has been noticed that the expense of making a direct method stableisay of pivoting in Gaussian eliminationimay in certain contexts be cost ineffective Instead skip that stepisolve the problem directly but unstably then do one or two steps of iterative re nement Exact Gaussian elimination becomes just another preconditioner Other problems besides Ax b have undergone analogous changes and the famous example is linear programming Linear programming problems are mathematically nite and for decades people solved them by a nite algorithm the simplex method Then Karmarkar announced in 1984 that iterative in nite algorithms are sometimes better The result has been contw 1 y 39 quot 39 39 and a r r 39L shift of the entire eld of linear programming away from the rather anomalous position it has traditionally occupied towards the mainstream of numerical computation I believe that the existence of nite algorithms for certain problems together with other historical forces has distracted us for decades from a balanced view of numerical analysis Rounding errors and instability are important and numerical analysts will always be the experts in these subjects and at pains to ensure that the unwary are not tripped up by them But our central mission is to compute quantities that are typically uncomputable from an analytical point of view and to do it with lightning speed For guidance to the future we should study not Gaussian elimination and its beguiling stability properties but the diabolically fast conjugate gradient iterationior Greengard and Rokhlin s 0N multipole algorithm for particle simulationsior the exponential convergence of spectral methods for solving certain PDEsior the convergence in 01 iteration achieved by multigrid methods for many kinds of problemsior even Borwein and Borwein s magical AGM iteration for determining 1000000 digits of 7 in the blink of an eye That is the heart of numerical analysis Notes Many people too numerous to name provided comments on drafts of this essay Their suggestions led me to many publications that I would otherwise not have found I do not claim that any of the ideas expressed here are entirely new In fact 30 years ago in his Elements of Numerical Analysis Peter Henrici de ned numerical analysis as the theory of constructive methods in mathematical analysis Others have expressed similar views Joseph Traub Communications of the A CM 1972 for example de ned numerical analysis as the analysis of continuous algorithms For that matter both the Random House and the Oxford English dictionaries offer better de nitions than the three quoted here And should the eld be called numerical analysis scienti c computing or something else entirely mathematical engineering That is another essay ON Ten years ago I would have stopped at this point But the evolution of computing in the past decade has given the difference between D1 and D2 a new topicality Let us return to An b Much of numerical computation depends on linear algebra and this highly developed subject has been the core of numerical analysis since the beginning Nu merical linear algebra served as the subject with respect to which the now standard concepts of stability conditioning and backward error analysis were de ned and sharpened and the central gure in these developments from the 1950s to his death in 1986 was Jim Wilkinson I have mentioned that An b has the unusual feature that it can be solved in a nite sequence of operations In fact Ax b is more unusual than that for the standard algorithm for solving it Gaussian elimination turns out to have extraordinarily complicated stability properties Von N eumann wrote 180 pages of mathematics on this topic Turing wrote one of his major papers Wilkinson developed a theory that grew into two books and a career Yet the fact remains that for certain n x n matrices Gaussian elimination with partial pivoting ampli es rounding errors by a factor of order 2quot making it a useless algorithm in the worst case It seems that Gaussian elimination works in practice because the set of matrices with such behavior is vanishingly small but to this day nobody has a convincing explanation of why this should be so In manifold ways then Gaussian elimination is atypical Few numerical algorithms have such subtle stability properties and certainly no other was scrutinized in such depth by von N eumann Turing and Wilkinson The effect Gaussian elimination which should have been a sideshow lingered in the spotlight while our eld was young and grew into the canonical algorithm of numerical analysis Gaussian elimination set the agenda Wilkinson set the tone and the distressing result has been D1 Of course there is more than this to the history of how D1 acquired currency In the early years of r it was 39 39 39 39 that arithmetic issues would receive concerted atten tion Fixed point computation required careful thought and novel hardware oating point computation arrived as a second revolution a few years later Until these matters were well understood it was natural that arithmetic issues should be a central topic of numerical anal ysis and besides this another force was at work There is a general principle of computing that seems to have no name the faster the computer the more important the speed of algo rithms In the early years with the early computers the dangers of instability were nearly as great as they are today and far less familiar The gaps between fast and slow algorithms however were narrower A development has occurred in recent years that re ects how far we have come from that time Instances have been accumulating in which even though a nite algorithm exists for a problem an in nite algorithm may be better The distinction that seems absolute from a logical point of view turns out to have little importance in practiceiand in fact Abel and Galois notwithstanding large scale matrix eigenvalue problems are about as easy to solve in practice as linear systems of equations For An b iterative methods are becoming more and more often the methods of choice as computers grow faster matrices grow larger and less sparse because of the advance from 2D to 3D simulations and the 0N3 operation counts of the usual direct nite algorithms become ever more painful The name of the new game is iteration with preconditioning Increasingly often it is not optimal to try to solve a 4 for solving a linear system of equations Ax b To understand Gaussian elimination you have to understand computer science issues such as operation counts and machine architectures and you have to understand the propagation of rounding errorsistability That s all you have to understand and if somebody claims that D2 is just a more polite restatement of D1 you can t prove him or her wrong with the example of Gaussian elimination But most problems of continuous mathematics cannot be solved by nite algorithms Unlike Ax b and unlike the discrete problems of computer science most of the problems of numer ical analysis could not be solved exactly even if we could work in exact arithmetic Numerical analysts know this and mention it along with a few words about Abel and Galois when they teach algorithm for r 39 matrix 39 39 Too often they forget to mention that the same conclusion extends to virtually any problem with a nonlinear term or a derivative in itizero nding quadrature differential equations integral equations optimization you name it Even if rounding errors vanished numerical analysis would remain Approximating mere numbers the task of oating point arithmetic is indeed a rather small topic and maybe even a tedious one The deeper business of numerical analysis is approximating unknowns not knowns Rapid convergence of approximations is the aim and the pride of our eld is that for many problems we have invented algorithms that converge exceedingly fast These points are sometimes overlooked by enthusiasts of symbolic computing especially recent converts who are apt to think that the existence of Maple or Mathematica renders Matlab and Fortran obsolete It is true that rounding errors can be made to vanish in the sense that in principle any nite sequence of algebraic operations can be represented exactly on a computer by means of appropriate symbolic operations Unless the problem being solved is a nite one however this only defers the inevitable approximations to the end of the calculation by which point the quantities one is working with may have become extraordinarily cumbersome Floating point arithmetic is a name for numerical analysts habit of doing their pruning at every step along the way of a calculation rather than in a single act at the end Whichever way one proceeds in oating point or symbolically the main problem of nding a rapidly convergent algorithm is the same In summary it is a corollary of D2 that numerical analysis is concerned with rounding errors and also with the deeper kinds of errors associated with convergence of approximations which go by various names truncation discretization iteration Of course one could choose to make D2 more explicit by adding words to describe these approximations and errors But once words begin to be added it is hard to know where to stop for D2 also fails to mention some other important matters that these algorithms are implemented on computers whose architecture may be an important part of the problem that reliability and ef ciency are paramount goals that some numerical analysts write programs and others prove theorems and most important that all of this work is applied applied daily and successfully to thousands of applications on millions of computers around the world The problems of continuous mathematics are the problems that science and engineering are built upon without numerical methods science and engineering as practiced today would come quickly to a halt They are also the problems that preoccupied most mathematicians from the time of Newton to the twentieth century As much as any pure mathematicians numerical analysts are the heirs to the great tradition of Euler Lagrange Gauss and the rest If Euler were alive today he wouldn t be proving existence theorems Webster s New Collegiate Dictionary 1973 The study of quantitative approxi mations to the solutions of mathematical problems including consideration of the errors and bounds to the errors involved Chambers 20th Century Dictionary 1983 The study of methods of approximation and their accuracy etc The American Heritage Dictionary 1992 The study of approximate solutions to mathematical problems taking into account the extent of possible errors Approximations accuracy errors again It seems to me that these de nitions would serve most effectively to deter the curious from investigating further The singular value decomposition SVD affords another example of the perception of nu merical analysis as the science of rounding errors Although the roots of the SVD go back more than 100 years it is mainly since the 1960s through the work of Gene Golub and other numerical analysts that it has achieved its present degree of prominence The SVD is as fundamental an idea as the eigenvalue decomposition it is the natural language for discussing all kinds of questions of norms and extrema involving nonsymmetric matrices or operators Yet today thirty years later most mathematical scientists and even many applied mathe maticians do not have a working knowledge of the SVD Most of them have heard of it but the impression seems to be widespread that the SVD is just a tool for combating rounding errors A glance at a few numerical analysis textbooks suggests why In one case after an other the SVD is buried deep in the book typically in an advanced section on rank de cient least squares problems and recommended mainly for its stability properties 1 I am 39 1 that 39 39v or 39 many people think that D1 is at least half true In actuality it is a very small part of the truth And although there are historical explanations for the in uence of D1 in the past it is a less appropriate de nition today and is destined to become still less appropriate in the future I propose the following alternative de nition with which to enter the new century Numerical analysis is the study of algorithms D2 for the problems of continuous mathematics Boundaries between elds are always fuzzy no de nition can be perfect But it seems to me that D2 is as sharp a characterization as you could come up with for most disciplines The pivotal word is algorithms Where was this word in those chapter headings and dictionary de nitions Hidden between the lines at best and yet surely this is the center of numerical analysis devising and analyzing algorithms to solve a certain class of problems These are the problems of quot 1 quot C 39 means that real or complex variables are involved its opposite is discrete A dozen quali cations aside numerical ana lysts are broadly concerned with 39 problem while algorithm for discrete problems are the concern of other computer scientists Let us consider the implications of D2 First of all it is clear that since real and complex numbers cannot be represented exactly on computers D2 implies that part of the business of numerical analysis must be to approximate them This is where the rounding errors come in Now for a certain set of problems namely the ones that are solved by algorithms that take a nite number of steps that is all there is to it The premier example is Gaussian elimination 2 The following essay appeared in the November 1992 issue of SIAM News and the March 1993 issue of the Bulletin of the Institute for Mathematics and Applications THE DEFINITION OF NUMERICAL ANALYSIS Lloyd N Iiefethen Dept of Computer Science Cornell Unviersity LNT cscornelledu What is numerical analysis I believe that this is more than a philosophical question A certain wrong answer has taken hold among both outsiders to the eld and insiders distorting the image of a subject at the heart of the mathematical sciences Here is the wrong answer Numeiical analysis is the study of rounding errors D1 The reader will agree that it would be hard to devise a more uninviting description of a eld Rounding errors are inevitable yes but they are complicated and tedious and inot fundamental If D1 is a common perception it is hardly surprising that numerical analysis is widely regarded as an unglamorous subject In fact mathematicians physicists and computer scientists have all tended to hold numerical analysis in low esteem for many yearsia most unusual consensus Of course nobody believes or asserts D1 quite as baldly as written But consider the following opening chapter headings from some standard numerical analysis texts Isaacson A s Keller 1966 Hamming 1971 Danlquist A s Bj 39rck 1974 Norms arithmetic and well posed computations Roundoif and function evaluation Some general principles of numerical calculation How to obtain and estimate accuracy 1 1 1 2 Steer A s Bulirscn 1980 1 Error analysis Conte A s de Boer 1980 1 Atkinson 1987 1 Kananer MoIer A s Nash 1989 1 2 Number systems and errors Error its sources propagation and analysis Introduction Computer arithmetic and computational errors Error roundoff computer arithmetic 7 these are the words that keep reappearing What impression does an inquisitive college student get upon opening such books 0r consider the de nitions of numerical analysis in some dictionaries 1

### 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.