### Create a StudySoup account

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

Already have a StudySoup account? Login here

# CJA543 CJA543

SDSU

GPA 3.76

### View Full Document

## 19

## 0

## Popular in Course

## Popular in Criminal Justice

This 6 page Class Notes was uploaded by Ms. Lee Flatley on Tuesday October 20, 2015. The Class Notes belongs to CJA543 at San Diego State University taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/225296/cja543-san-diego-state-university in Criminal Justice at San Diego State University.

## Reviews for CJA543

### 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: 10/20/15

Numerical Matrix Analysis Lecture Notes 10 Conditioning and Stability Floating Point Arithmetic Stability Peter Blomgren blomgrenpeter gmail com Department of Mathematics and Statistics Dy mlcal Systems roup Computational Science Rsearch Center San Diego State University San Diego CA 921827720 httpterminussdsuedu Spring 2010 Outline 0 Finite Precision 0 IEEE Binary Floating Point from Math 541 0 Nonrepresentable Values a Source of Errors 9 Floating Point Arithmetic 0 Theorem and Notation 0 Fundamental Axiom of Floating Point Arithmetic 0 Example 9 Stability 0 Introduction What is the correct answer 0 Accur 0 Stability and Backward Stability acy Absolute and Relative Error 539 m Floating Point Arithmetic Stability 7 123 Floating Point Arithmetic Stability 7 223 Finite Precision A 64 bit real number double lEEE 754 1985 Special Signals The Binary Floating Point Arithmetic Standard 754 1985 IEEE The Institute for Electrical and Electronics Engineers In order to be able to represent zero ioo and NaN standard speCIfled the followmg layout for a 64 bit real number not a number the followmg speCIal Signals are defined in the SC10 C9 C1 C0 mm mm m1 m0 lEEE754 1985 standard Where Type S 1 bit C 11 bits M 52 bits signaling NaN u 2047 max Ouuuuu u quiet NaN u 2047 max 1uuuuu u SymbOI Blts DESCI IPUOquot negative infinity 1 2047 max 000000 0 5 1 The Sign bit OPositive 1negative positive infinity 0 2047 max 000000 0 negative zero 1 0 000000 0 c 11 The characteristic exponent Positive zero 0 0 0000000 m 52 The mantlssa with at least one 1 bit 7 S C4023 f 7 10 n f 7 51 m From httpwwwireesoft orgCIERFC183232 htm raw 2 1 7 Zena 7252 k0 k0 m 539 Floating Point Arithmetic Stability 7 323 Floating Point Arithmetic Stability 7 423 Examples Finite Precision Examples Finite Precision 10 51 71023 mk r 152c C ch2 7 f 22527k 10 51 mk 71023 k 0 k 0 r7152c 10 cch2quot 2222527 Example 1 k0 k 0 010000000000 Example 3 The Largest P05ltlve Real Number r1 710 221071023 1 21 E 0711111111110111111111111111111111111111111111111111111111111111 2 2 1 1 1 1 7 7 0 1023 7 7 7 7 Example 2 The Smallest Positive Real Number r3 7 l 1 2 lt1 2 l 22 l l 251 l 29gt 0 00000000000 21 23 lt2 7 x 1798 X 10308 r2 71 2 1 23 1 2 52 x 1113 X 10308 539 m Floating Point Arithmetic Stability 7 523 Floating Point Arithmetic Stability 7 623 That s Quite a Range Fun with Matlab lntegers In summary we can represent 0 11113 gtlt 10308 i1798 gtlt 10308 100 NaN 253 2 253 2 253 2 253 1 2 and a whole bunch of numbers in 253 1 253 O 253 253 i 1 1 7 1798x10308 71113gtlt10 308U1113gtlt10 3087 1798x10308 realmax 1797710308 realmin 22251 10308 eps 22204 1016 Bottom line Over or under flowing is usually not a problem in IEEE fl t39 39 t 39th t39 03 mg Pom an me IC The smallest not exactly representable integer is 53 1 The problem in scientific computing is what we cannot 2 1 970077199725477407993 represent my 5353 Floating Point Arithmetic Stability 7 723 Floating Point Arithmetic Stability 7 323 Something is Missing Gaps in the Representation 1 of 3 Something is Missing Gaps in the Representation 2 of 3 I There are gaps In the floating pomt representation A gap of 271075 doesn t seem too bad Given the representation However the size of the gap depend on the value itself 07000000000007 Consider r 30 7 71023 752 for the value v1 7 2 1 2 07100000000007 the next larger floating point value is and the next value 0 00000000000 Le the value V2 210231 251 010000000000 Here the difference is 2 2 52 2 51 The difference between these two values Is 2 1023 2 52 2 1075 ln eneral in the interval 2 2quot1 the a is 2 52 Any number In the Interval v17 vz Is not representable g l 7 l g P 539 m Floating Point Arithmetic Stability 7 923 Floating Point Arithmetic Stability 7 1023 Something is Missing Gaps in the Representation 3 of 3 The Relative Gap At the Other eXtremex the difference between It makes more sense to factor the exponent out of the discussion and talk about the relative gap 011111111110IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIn Exponent Gap Relative Gap GapExponent 271023 271075 2752 R X 10716 and the next value 21 2751 2752 21023 2971 2752 011111111110IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII Any difference between numbers smaller than the local gap Is not representable eg any number in the interval is 21023 2 52 2971 m 1996 10292 1 That s a fairly Significant gap A number large enough to 307 30 comfortably count all the particles in the universe See eg httphomeearthlinknetNmrobpubmathnumbers 10html m is represented by the value 339039 5353 Floating Point Arithmetic Stability 7 1123 Floating Point Arithmetic Stability 7 1223 The Floating Point Theorem Emach Theorem Floating point numbers represent intervals We let flX denote the floating point representation of X E R Notation The relative gap defines 5mm VX E R there exists 5 with lei S emach such that flX X1 e In 64 bit floating point arithmetic emach m 222 gtlt 10 In matlab the command eps returns this value Let the symbols 63 9 and denote the floating point Floating Point Arithmetic Emach All floating point operations are performed up to some precision ie Xey flX x a y tuxy This paired with our definition of emach gives us X yflxy7 X yflxy7 Axiom The Fundamental Axiom of Floating Point Arithmetic For all Xy E P where F is the set of floating point numbers there exists 5 with lei S emach such that Xey Xiy167 X y Xy1 6 X yx1e X yxyle That is every operation of floating point arithmetic is exact operations addition subtraction multiplication and division m up to a relative error of size at most emach Floating Point Arithmetic Stability 7 1323 Floating Point Arithmetic Stability 7 1423 Example Floating Point Error Scaled by 1010 Consider the following polynomial on the interval 1927 208 W x a 2P x9 7 18xS 144x7 7 a72x5 201ax5 7 4032x 537m3 7 4608gtlt2 2304x 7 512 St b39 39t nu 5353 Floating Point Arithmetic Stability 7 1523 Floating Point Arithmetic Stability 7 1623 Stability Introduction 1 of 3 Stability Introduction 2 of 3 With the knowledge that floating point errors happen we have to re define the concept of the right answer Previously in the context of conditioning we defined a mathematical problem as a map fX7Y where X Q C is the set of data input and Y Q Cm is the set of solutions We now define an implementation of an algorithm on a floating point device where F satisfies the fundamental axiom of floating point arithmetic as another map f X 7 Y ie E Y is a numerical solution of the problem Wiki History Pentium FDIV bug The Pentium FDIV bug was a bug in Intel39s original Pentium FPU Certain FP division operations performed with these processors would produce incorrect results According to Intel there were a few missing entries in the lookup table used by the divide operation algorithm Although encountering the flaw was extremely rare in practice Byte Magazine estimated that 1 in 9 billion FP divides with random parameters would produce inaccurate results both the flaw and Intel39s initial handling of the matter were heavily criticized Intel ultimately m recalled the defective processors E Floating Point Arithmetic Stability 7 1723 Floating Point Arithmetic Stability 7 1323 Stability Introduction 3 of 3 Accuracy The task at hand is to make useful statements about Even though is affected by many factors roundoff errors convergence tolerances competing processes on the computerquot etc we will be able to make maybe surprisingly clear statements about 96 Note that depending on the memory model the previous state of a memory location may affect the result in eg the case of cancellation errors If we subtract two 16 digit numbers with 13 common leading digits we are left with 3 digits of valid infor mation We tend to view the remaining 13 digits as random But really there is nothing random about what happens inside the computer we hope the randomness will depend on what happened preVIously Floating Point Arithmetic Stability 7 1923 The absolute error of a computation is MW 7 fgtltll and the relative error is MW 7 fgtltll Ilfill this latter quantity will be our standard measure of error If 1Nr is a good algorithm we expect the relative error to be small of the order emach We say that f is accurate if V E X MW 7 fgtltll llfmll OW 5353 Floating Point Arithmetic Stability 7 2023 Interpretation Oemach Stability Since all floating point errors are functions of emach the relative error in each operation is bounded by emach the relative error of the algorithm must be a function of emach H70 7 fgtltll llfill 65mach The statement e mach 05mach means that 3C 6 R such that e mach S CEmaclw 35 Emach l O In practice emach is fixed and the notation means that if we were to decrease emach then our error would decrease at least proportionally to emach Floating Point Arithmetic Stability 7 539 2123 If the problem f X a Y is ill conditioned then the accuracy goal MW 7 fgtltll llfill may be unreasonably ambitious 05mach Instead we aim for stability We say that f is a stable algorithm ifVXEX N N f x 7 f x ll N ll OEm llfXll for some gtlt with N llgtltgtltll f06mac M h A stable algorithm gives approximately the right answer to approximately the right question Floating Point Arithmetic Stability 7 2223 Backward Stability For many algorithms we can tighten this somewhat vague concept of stability An algorithm 27 is backward stable if V e x 270 fgtlt for some gtlt with llgtzlt7gtltll f 05mac llel A backward stable algorithm gives exactly the right answer to approximately the right question Next time Examples of stable and unstable algorithms Stability of Householder triangularization Floating Point Arithmetic Stability 7 2323

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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