TP I20, semaine 4

Dichotomie

Exemple de programme à réaliser :

#include <math.h>

int iteration;

double f (double x) {
  return sin (x) - 0.5;
}

double g (double x) {
  return x * x - 2;
}

double h (double x) {
  return exp (x) - 2;
}

double dichotomie (
  double f (double),
  double a, double b,
  double epsilon
) {
  double c;
  
  if (f (a) > 0) {
    c = a;
    a = b;
    b = c;
  }
  for (iteration = 0; fabs (b - a) > epsilon; iteration++) {
    c = (a + b) / 2;
    if (f(c) < 0)
      a = c;
    else
      b = c;
  }
  return a;
}

void main (void) {
  double x, epsilon = 1;
  int i;
  
  for (i = 1; i < 8; i++) {
    epsilon = epsilon / 100;
    x = dichotomie (g, 1, 2, epsilon);
    printf ("%2d %.15f (%2d iterations)\n", 2 * i, x, iteration);
  }
}

Exécution sur Sparc :

sin(x) - 0.5 , intervalle [0 1.5] :

 2 0.521484375000000 ( 8 iterations)
 4 0.523590087890625 (14 iterations)
 6 0.523598670959473 (21 iterations)
 8 0.523598771542311 (28 iterations)
10 0.523598775558639 (34 iterations)
12 0.523598775598202 (41 iterations)
14 0.523598775598298 (48 iterations)

x*x - 2 , intervalle [1 2] :

 2 1.414062500000000 ( 7 iterations)
 4 1.414184570312500 (14 iterations)
 6 1.414213180541992 (20 iterations)
 8 1.414213560521603 (27 iterations)
10 1.414213562326040 (34 iterations)
12 1.414213562372424 (40 iterations)
14 1.414213562373092 (47 iterations)

exp(x) - 2 , intervalle [0 1] :

 2 0.687500000000000 ( 7 iterations)
 4 0.693115234375000 (14 iterations)
 6 0.693146705627441 (20 iterations)
 8 0.693147175014019 (27 iterations)
10 0.693147180543747 (34 iterations)
12 0.693147180559208 (40 iterations)
14 0.693147180559940 (47 iterations)

Méthode de Lagrange

Exemple de programme à réaliser :

#include <math.h>

double exact;

double f1 (double x) {
  return sin (x) - 0.5;
}

double f2 (double x) {
  return x * x - 2;
}

double f3 (double x) {
  return exp (x) - 2;
}

double lagrange (
  double f (double),
  double a, double b,
  double epsilon
) {
  double c, ya, yb, ea, eb, ec;
  
  ya = f(a);
  ea = a - exact;
  eb = b - exact;
  while ( fabs (b - a) > epsilon ) {
    yb = f(b);
    c = (a * yb - b * ya) / (yb - ya);
    ec = c - exact;
    printf ("%.15f %10.2g %12g\n", c, ec, ec / ea / eb);
    a = b;
    b = c;
    ya = yb;
    ea = eb;
    eb = ec;
  }
  return b;
}

void main (void) {
  printf ("sin(x)=0.5 :\n");
  exact = asin (0.5);
  lagrange (f1, 0, 1.5, 1e-15);
  
  printf ("\nsqrt(2) :\n");
  exact = sqrt(2);
  lagrange (f2, 1, 2, 1e-15);
  
  printf ("\nln(2) :\n");
  exact = log (2);
  lagrange (f3, 0, 1, 1e-15);
}

Exécution sur Sparc :

sin(x) - 0.5 , intervalle [0 1.5] :

0.751883478185044       0.23    -0.446529
0.316506525043772      -0.21    -0.929092
0.537553609826517      0.014    -0.295178
0.524302997791102     0.0007    -0.243681
0.523595902482711   -2.9e-06    -0.292361
0.523598776182734    5.8e-10     -0.28885
0.523598775598299    4.4e-16    -0.264473
0.523598775598299   -1.1e-16 -4.27764e+08

x*x - 2 , intervalle [1 2] :

1.333333333333333     -0.081     0.333333
1.400000000000000     -0.014          0.3
1.414634146341463    0.00042     0.365854
1.414211438474870   -2.1e-06     0.355286
1.414213562057320   -3.2e-10     0.353501
1.414213562373095          0            0
1.414213562373095   -2.2e-16          Inf

exp(x) - 2 , intervalle [0 1] :

0.581976706869326 0.522678
0.676692703760405 0.482352
0.694081399681418 0.510711
0.693139474644914 0.501293
0.693147176960995 0.499923
0.693147180559959 0.504406
0.693147180559945 -0
0.693147180559945 NaN

Méthode de Newton

Exemple de programme à réaliser :

#include <math.h>

double exact;

double f1 (double x) {
  return sin (x) - 0.5;
}

double f2 (double x) {
  return x * x - 2;
}

double g2 (double x) {
  return 2 * x;
}

double f3 (double x) {
  return exp (x) - 2;
}

double newton (
  double f (double),
  double fprime (double),
  double a,
  double epsilon
) {
  double b, ea, eb;
  
  ea = a - exact;
  while (1) {
    b = a - f (a) / fprime (a);
    if ( fabs (b - a) < epsilon )
      break;
    eb = b - exact;
    printf ("%.15f %10.2g %12g\n", b, eb, eb / ea / ea);
    a = b;
    ea = eb;
  }
  return b;
}

void main (void) {
  printf ("sin(x)=0.5 :\n");
  exact = asin (0.5);
  newton (f1, cos, 0, 1e-15);
  
  printf ("\nsqrt(2) :\n");
  exact = sqrt(2);
  newton (f2, g2, 1, 1e-15);
  
  printf ("\nln(2) :\n");
  exact = log (2);
  newton (f3, exp, 0, 1e-15);
}

Exécution sur Sparc :

sin(x) - 0.5 , intervalle [0 1.5] :

0.500000000000000     -0.024    -0.086078
0.523444473818484   -0.00015    -0.277072
0.523598768727058   -6.9e-09    -0.288598
0.523598775598299   -1.1e-16     -2.35147

x*x - 2 , intervalle [1 2] :

1.500000000000000      0.086          0.5
1.416666666666667     0.0025     0.333333
1.414215686274510    2.1e-06     0.352941
1.414213562374690    1.6e-12     0.353522
1.414213562373095          0            0

exp(x) - 2 , intervalle [0 1] :

1.000000000000000       0.31     0.638674
0.735758882342885      0.043     0.452552
0.694042299918915     0.0009     0.492973
0.693147581059771      4e-07     0.499851
0.693147180560025      8e-14     0.499738
0.693147180559945          0            0