These are the first set of questions. See homepage for more practice problems. I learned a lot from Kelly in our practice session. Theory in these notes is from the Stewart book. There are still a few questions I have but here is what I have so far.

Here is how to solve for the n-th root, however, am not sure of the reasoning of the derivation. The approximation works differently than the Newton method.

The advantage is that the root can be solved with multiplication, division, addition, and subtraction. 

How well does this work for n=1,2,3,4. Running an experiment shows how well this method works. The table below shows that the approximation converges quickly for n=1,2,3 but is terrible for n =4. N=2 isa special case that converges quickly as it has quadratic convergence as oppossed to n=1, 2 that have linear convergence. 
 
 

Number of iterations to convergence (tolerance 1e-12)             A         n= 1         2           3     4            1          47          11          38    (over 10000 itereations)            2          47          11          46            5          47          10          46            7          47          10          45           10          47           9          46           13          47           9          47           20          47           9          48           31          46           9          49           50          46           8          48           53          46           8          47          100           0           8          49          101          40           8          49         1001          50           6          53

 

Convergence is a measurement between the optimal value and the iterated value. Stewart’s book gives the convergence of the Newton method as follows. Calculating the n-th root iteration should be similar.

The terminology for this is quadratically convergent. 

Here is my experimental Matlab code:
 

% Practice Newton method for estimating roots.  n = 2; a = 3; x = 5; total =[]; %conv; % a, n numbers = [1 2 5 10 20 50 100 1000]; %numbers = [10 20 30 100 1000 10000]; for count = 1:size(numbers,2),    for n = 1:3,         total = [];         %n=3;         x = 100;         % Tolerance value         a = numbers(count);         while (abs(a-x^n)> 1e-12),             x = x + (a/x^(n-1));             x = x/2;             total = [total x];          end          n      a      conv(count,n) = size(total,2);  end end % plot each estimation plot(total,total.^n,'m.')

Operations to perform sqrt(a) is when n=2. I ran the following experiment on Capefear. The iterative method was faster than the sqrt function call; the tradoff might be in the accuracy of the sqrt. I used the UNIX time

Iteration time 100000: 0.03u 0.01s 0:00.04 100.0%

SQRT time 100000:   0.05u 0.01s 0:00.06 100.0%

 

// Run with gcc root.c -o root -lm  #include <math.h>  main() {     float x=5;     float a =15;     int i;     for(i=0;i <100000; i=i+1)        if(1) { // change to zero to test other case          // faster method           x = 100.0; // first guess          while ((a-x*x) > 0.1)              x = (x+(a/x))/2.0;        }        else           x= sqrt(15.0);  }

The accuracy of floating point numbers is limited to the number of bits that represent the number. The mantissa represents a limited amount range of rational numbers. A rounding error is caused when a number is computed outside the possibility of the mantissa. The less bits in the mantissa, the less rational numbers can be represented. Therefore the largest i possible for a calculator is less than for a Sun machine; the calculator has less bits per floating point number than the Sun machine.

 
 
 

Matlab on PC (Pentium II) = 49 iterations

 

% Floating point numbers      i=1;      while (((1.0/i)*i-1) == 0.0),          i=i+1;      end      display('Number of iterations');      i

C on capefear = Double: 49 Single: 41 iterations.
 

main() { int i=1; double t; // Cast to double or float to get double or single precision while((t=(1/(double)i)*(double)i-1) ==0.0)         i = i+1; printf("Number of iterations %d\n", i); }