Numerical Analysis EE, NCKU Tien-Hao Chang (Darby Chang) 1 Summary 1 exam, 1project and some exercises http://zoro.ee.ncku.edu.tw/na/ 2 Target Solve problems with numerical methods 3 In this slide Why numerical methods? – differences between human and computer – a very simple numerical method What is algorithm? – definition and components – three problems and three algorithms Convergence – compare rate of convergence 4 Why such methods? Computer is stupid 5 x-2=0 Human says, “x=2, easy!” 6 { x-2=0; } Computer says, “compilation error!” 7 What is the difference? 8 http://www.wallcoo.com/paint/Donald_Zolan_Early_Childhood_02/wallpapers/1280x1024/painting_children_kjb_DonaldZolan_68TheThinker_sm.jpg Human is logical (thinking) 9 http://files.myopera.com/conansakura/albums/31567/thumbs/2.jpg_thumb.jpg Can do inference 10 http://www.aclibrary.org/eventkeeper/Graphics/SLZ/computer.jpg Computer is procedural (executing) 11 An example (((x+3)-2)+6)=0 – Human requires only the rules (in this case, arithmetic), – and can inference the steps for the solution 12 Computer (((x+3)-2)+6)=0 – Requires the exact procedure (steps) • { x0=0–6; } • { x1=x0+2; } • { x=x1–3; } – These steps is numerical method 13 Does computer have any advantage? 14 http://www.masternewmedia.org/images/fast_snail_id86636_size350.jpg It is fast 15 So, why numerical methods? Computer is stupid Computer is fast (and works hard) Sometimes, stupid methods can solve difficult problems 16 17 18 1 72 + − + 18 + 1 − = 98.6 is the time of death, which cannot be solved explicitly 19 We know that is no earlier than PM 7:15, and is no later than PM 8:00. So… 20 could be PM 7:38 rubbish =.= 21 1 1 − 72 + − + 18 + = 98.6 A systematic procedure 1. Let as PM 7:38 2. Evaluate the above formula 3. 4. If the result exceeds 98.6, we use PM 7:27, otherwise, we use PM 7:49 instead Repeat step 2 & 3 until the result is close to 98.6 enough 22 http://www.leda-tutorial.org/en/unofficial/Pictures/BisectionMethod.png Bisection method 23 Bisection method The concept is – 1) find the mid-point, 2) evaluate it, and 3) shrink the solution range It is stupid: just trial and error But it works, because is ascending And… 24 And very accurate Actually, it is getting accurate after every trial 25 When #trails → ∞ Computer works hard, so it could happen 26 Any Questions? 27 Algorithm The heart of numerical analysis 28 Algorithm Definition – A precisely defined sequence of steps In this course – design; – implement; and – examine the performance 29 How to implement? 30 By hand too painful (but you might need to) 31 With computer in other words, do programming 32 Programming Even scared! 33 Algorithm could be simple 34 An example from statistics Mean and standard deviation on n values = =1 , = 2 =1 2 =1 − ( − 1) 35 36 In action input is 1,2,3,4,5 37 38 It is also an algorithm (a precisely defined sequence of steps) 39 Not A difficult sequence of steps 40 Any Questions? 41 Another example Definite integral using trapezoidal rule 42 A partition = 0 < 1 < ⋯ < −1 = 43 ℎ ≈ + 2 2 −1 + () =1 where = + ℎ, and ℎ = ( − )/ 44 45 In action 2 1 = 1 , = 4 46 47 Error The analytic solution is 2 The absolute error is 2 − 0.697023809 ≈ 3.877 × 10−3 48 49 Observations of the errors , the absolute error, is a decreasing function of When is doubled, is reduced by a factor (roughly 1/4) From the numerical evidence ≈ 2 where is independent of 50 Any Questions? 51 The third example Square root – is a nonnegative real number – +1 = 1 2 + – +1 converges to 52 53 Stopping condition +1 − ) < – +1 − ) < provides an estimate Prevent infinite loop – give a limit of the number of iterations 54 In action 2, i.e., = 2 0 = 2, = 0.005, = 10 55 56 So far a statistics problem, the integral problem, and the square root problem 57 Any Questions? 58 What is the differences among them? (hint: the concepts of the output) 59 Type of methods The statistics algorithm – generates an exact (analytic) solution The integral algorithm – generates an approximate (numerical) solution – many numerical methods work in much the same way The square root algorithm – generates a sequence of approximations which converge to the solution – another typical class of numerical methods 60 Poll Programming ability 61 Learnt C/C++ (??/24) Java (??/24) Other (??/24) 62 Learnt Data structure (??/24) Algorithm (??/24) 63 Language vs. algorithm Two languages – The same concept, different patterns – e.g., Chinese and English – 想睡覺, feel sleepy English vs. C – Increase i by 1 – { ++i; } Language is/defines the pattern Algorithm is/describes the concept 64 Pseudo-code Not any real programming language 65 A pseudo-code example 66 Can You Read/write pseudo-code? 67 Convergence When several numerical methods are available, choose the fastest one 68 lim = →∞ The sequence { } converges to the value , and is called the limit of the sequence 69 Rate of convergence Let { } converges to , { } converges to 0, is a constant, and − ≤ Rate of convergence of { } is ( ) is typically of the form – 1/ – 1/ 70 71 72 73 74 Any Questions? 75 Which Is Better? 1 1 1 , ( ) 2 10 2 76 Using L'Hôpital's rule (羅必達法則) This is provided by a student 陳攀任 In its simplest form, L'Hôpital's rule states that for functions and : ′ If lim () = lim () = 0 or ± ∞ and lim ′ exists, → → → () ′ then lim = lim ′ → () → () To compare 10 and 2 Let = 10 and = 2 , 10 10 ∙ 9 10 ∙ 9 ∙ 8 then lim = lim = lim = lim 2 →∞ () →∞ 2 →∞ ln 2 ∙ 2 →∞ ln 2 ∙ 2 10! = ⋯ = lim 10 =0 →∞ ln 2 ∙ 2 77 78 Rate of Convergence There is another definition for function 79 Another definition of rate of convergence for function 80 81 Rate of convergence Let { } converges to , { } converges to 0, is a constant, and − ≤ Rate of convergence of { } is ( ) is typically of the form – 1/ – 1/ 82 Order of Convergence A different measure of convergence speed than rate of convergence Examines the relationship between successive error values 83 Order of Convergence Iterative Method An iterative method is said to be of order if the sequence it generates converges of order The most common values of in practice are – = 1 (linear convergence) – = 2 (quadratic convergence) – = 3 (cubic convergence) Non-integer values for are possible 84 Note the dramatic difference between 1 and 2, and the slight difference between 2 and 3 85 86

Descargar
# Dismiss Time - Molecular Biomedical Informatics