JavaScript is disabled on your browser. Enable JavaScript to use this site. Learn more

6.006 24. Numerics II

Add to Favourites

Post to:

MIT OpenCourseWare http://ocw.mit.edu6.006Introduction to AlgorithmsSpring 2008For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. � �� • • �� ((a), 1/b) �� •← �� • � �� 112Figure 1: Ratio of a Square's Diagonal to its Sides �� √2=1. 414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 � � �� λ�P �λ �� • • �� α,β �P � �� (α)β�P �� α, β �� (()) ()() �� (())()()�� αβ �� Cn� �� n �� C0 =1 �� Cn+1? �� n +1 �� 2� �� k �� α� n − k �� β nCn+1 = Ck · Cn−k n ≥ 0 k=0 C0 =1 C1 = C02 =1 C2 = C0C1 + C1C0 =2 C3 = =5 ··· �� -� � � � �� ABCD1000,000,000,0001Figure 2: Geometry Problem BD =1 �� AD� AD = AC − CD = 500, 000, 000, 000 − 500, 000, 000, 0002 − 1 a �� AD �� f(x)=0 �� f(x)= x2 − a xixi+1y = f(x)Figure 3: Newton's Method �� (xi, f(xi)) �� y = f(xi) + f�(xi) (x − xi) �� f�(xi) �� · xi+1 = �� f(xi) xi+1 = xi − f�(xi) �� f(x)= x 2 − a a χi+1 = χi − (χi 2 − a)= χi + χi 2χi 2 �� χ0 =1.000000000 a =2 χ1 =1.500000000 χ1 =1.416666666 χ1 =1.414215686 χ1 =1.414213562 �� √2 �� d�� 1�.414213562373··· � �� 10d√2� � �√2 102d� � �� · �� √2� �� AD� �� n�� r =2, 10� 0 ≤ x,y < rn x = x1 · rn/2 + x0 x1 = �� y = y1 · rn/2 + y0 x0 = �� 0 ≤ x0,x1

Description
Upon completion of this lesson, you should be able to:
1. High precision arithmetic
2. Multiplication
3. Division
4. Algorithm
5. Error Analysis and
6. Termination

Instructors: Prof. Erik Demaine, Prof. Ronald Rivest, Prof. Srinivas Devadas, MIT Course Number: 6.006 Level: Undergraduate, 6.006 24. Numerics II, Introduction to Algorithms, Electrical Engineering and Computer Science, Engineering, Massachusetts Institute of Technology: MIT Open Course Ware, http://ocw.mit.edu (02-11-2011). License: Creative Commons BY-NC-SA: http://ocw.mit.edu/terms/#cc.