Asna Notes | Computational Complexity Theory

Please download to get full document.

View again

of 95
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Documents

Published:

Views: 0 | Pages: 95

Extension: PDF | Download: 0

Share
Related documents
Description
noted
Transcript
  Approximations:From symbolic tonumerical computation,and applications Master d’informatique fondamentaleÉcole normale supérieure de LyonFall-winter 2013 Nicolas Brisebarre Bruno Salvy http://www.ens-lyon.fr/LIP/AriC/M2R/ASNA  Chapter 1Introduction The classical presentation of mathematical methods usually leaves out the problems of actuallygetting numerical values. In practice, a compromise between accuracy and efficiency is desirableand this turns out to require the development of specific (and often very nice) algorithms. Ouraim in this course is to exhibit the interplay between symbolic and numerical computation in orderto achieve as precise (or guaranteed or proved) computations as possible, and fast ! (At least in anumber of problems). 1.1 From symbolic to numerical computations 1.1.1 Examples of numerical instability Example 1.1. The Fibonacci recurrence. It is classical that the recurrence u n +2 = u n +1 + u n admits a solution of the form u n = aϕ n + bϕ ¯ n ,  with  ϕ = 1+ 5 √  2  and  ϕ ¯ = 1 ϕ  = 1 −  5 √  2 the solutions of the characteristic polynomial  x 2 − x − 1 .The values of   a  and  b  are dictated by the initial conditions. The classical Fibonacci sequenceis obtained with  u 0 =0  and  u 1 =1 , leading to  a = − b =1/ 5 √   , so that in particular  u n →∞  when n →∞ , since  a> 0  and  | ϕ | > 1 . On the opposite side, the sequence obtained with  a =0 ,  b =1 , orequivalently  u 0 =1 ,  u 1 =  ϕ ¯  is  ( ϕ ¯ n )  whose terms tend to 0 when  n →∞  since  | ϕ ¯ | < 1 . In practicehowever, this phenomenon is very difficult to observe, as the following experiments show. Maple 1] phi:=[solve(x^2=x+1,x)]; [1/2 5 √   +1/2 , 1/2 − 1/2 5 √   ] First, a purely numerical experiment: we compute  ϕ ¯  numerically and use it to get the first 50 values Maple 2] map(evalf,phi); [ 1.618033988 , − 0.6180339880 ] Maple 3] phi2:=%[2]; − 0.6180339880 Maple 4] N:=50:Maple 5] u[0]:=1:u[1]:=phi2:for i from 0 to N-2 do u[i+2]:=u[i]+u[i+1] od:Maple 6] L:=[seq(u[i],i=0..N)]; 3  [1 , − 0.6180339880 ,  0.3819660120 , − 0.2360679760 , 0.1458980360 , − 0.0901699400 , 0.0557280960 , − 0.0344418440 ,  0.0212862520 , − 0.0131555920 ,  0.0081306600 , − 0.0050249320 ,  0.0031057280 ,  − 0.0019192040 ,  0.0011865240 ,  − 0.0007326800 ,  0.0004538440 ,  − 0.0002788360 ,  0.0001750080 ,  − 0.0001038280 , 0.0000711800 , − 0.0000326480 , 0.0000385320 , 0.0000058840 , 0.0000444160 , 0.000\0503000 ,  0.0000947160 ,  0.0001450160 ,  0.0002397320 ,  0.0003847480 ,  0.0006244800 ,  0.001009\2280 ,  0.0016337080 ,  0.0026429360 ,  0.0042766440 ,  0.0069195800 ,  0.0111962240 ,  0.0181158040 , 0.0293120280 ,  0.0474278320 ,  0.0767398600 ,  0.1241676920 ,  0.2009075520 ,  0.3250752440 ,  0.5259\827960 , 0.8510580400 , 1.377040836 , 2.228098876 , 3.605139712 , 5.833238588 , 9.438378300 ] Here is a plot of these values: Maple 7] plots[listplot]([seq(u[i],i=0..N)]): The problem is that the numerical error introduced when replacing  ϕ ¯  by a 10-digit approximationamounts to having a very small, but nonzero, value for  a . At first, this goes unnoticed, buteventually, since  ϕ n tends to infinity, it overtakes the part in  ϕ ¯ n .A natural solution is to work  exactly  , starting with a symbolic value for  ϕ ¯  and reproducing thesame steps using symbolic computation: Maple 8] phi2:=phi[2]; 1/2 − 1/2 5 √  Maple 9] u[0]:=1:u[1]:=phi2: for i from 0 to N do u[i+2]:=u[i]+u[i+1]od:L:=[seq(u[i],i=0..N)]; [1 , 1/2 − 1/2 5 √   , 3/2 − 1/2 5 √   , 2 −  5 √   , 7/2 − 3/2 5 √   , 11 /2 − 5/2 5 √   , 9 − 4 5 √   ,  29 2  − 13 /2 5 √   , 47 2  − 21 /2 5 √   ,  38  − 17  5 √   ,  123 2  −  55 2 5 √   ,  199 2  −  89 2 5 √   ,  161 −  72  5 √   ,  521 2  −  233 2 5 √   ,  843 2  − 377 2 5 √   ,  682 − 305  5 √   ,  2207 2  −  987 2 5 √   ,  3571 2  −  1597 2 5 √   ,  2889 − 1292  5 √   ,  9349 2  −  4181 2 5 √   , 15127 2  −  6765 2 5 √   , 12238 − 5473  5 √   ,  39603 2  −  17711 2 5 √   ,  64079 2  −  28657 2 5 √   , 51841 − 23184  5 √   , 167761 2  −  75025 2 5 √   ,  271443 2  −  121393 2 5 √   ,  219602  −  98209  5 √   ,  710647 2  −  317811 2 5 √   , 1149851 2  −  514229 2 5 √   , 930249 − 416020  5 √   ,  3010349 2  −  1346269 2 5 √   ,  4870847 2  −  2178309 2 5 √   , 3940598  −  1762289  5 √   ,  12752043 2  −  5702887 2 5 √   ,  20633239 2  −  9227465 2 5 √   ,  16692641  − 7465176  5 √   ,  54018521 2  −  24157817 2 5 √   ,  87403803 2  −  39088169 2 5 √   ,  70711162 −  31622993  5 √   , 228826127 2  −  102334155 2 5 √   ,  370248451 2  −  165580141 2 5 √   ,  299537289  −  133957148  5 √   , 969323029 2  −  433494437 2 5 √   ,  1568397607 2  −  701408733 2 5 √   ,  1268860318  −  567451585  5 √   , 4106118243 2  −  1836311903 2 5 √   ,  6643838879 2  −  2971215073 2 5 √   ,  5374978561 − 2403763488  5 √   , 17393796001 2  −  7778742049 2 5 √   ,  28143753123 2  −  12586269025 2 5 √   ] 4  Introduction
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x