CPGE Informatique MPSI / 1TSI /PCSI
Lydex – Ben guerir Programmation Mr L. BOUHOU
Chap XI
Ingénierie Numérique
11 .1. Généralités
[Link] du graphe d’une fonction
Exemple
from scipy import *
from pylab import *
import [Link] as plt
def f(x) :
return (x**(1/2))*cos(x)
def Tracer():
x = linspace(0,5,30)
y = f(x)
axis([0,5,-4,4])
axhline(color='r')
[Link](x,y)
[Link] ()
Tracer()
11.1.2.Méthode Dichotomique
Voir TD numéro :8
11.2. Zéro d'une fonction
11.2.1. Méthode dichotomique:
Pour la recherche du zéro d’une fonction sur un intervalle [a,b], par la méthode dichotomique, on procède
successivement en calculant f(a), f(b) et f((a+b)/2) et en regardant le signe de ces trois expressions afin de déduire :
- Si f(a) * f((a+b)/2) <0 , alors il y a un zéro dans l'intervalle [a , (a+b)/2]
- sinon si f((a+b)/2) * f(b) < 0 alors il y a un zéro dans l'intervalle [(a+b)/2, b]
-Si f(a+b) /2 = 0 alors (a+b) / 2 est zéro de f
Le plus souvent on ne pourra pas trouver une valeur exacte seulement une valeur approchée.
Dans l'algorithme par dichotomie on s'arrête au bout de n étapes afin d'obtenir une précision ε telle que (b-a)/2n <= ε
Soit n>= (log(b-a) – log(ε))/ log(2)
Application
def dichotomie(a, b, f, eps=1e-10):
if(fabs(a - b) <= eps): return (a+b)/2.0
else:
m = (a+b)/2
if f(a) * f(m) <= 0: return dichotomie(a, m, f, eps)
elif f(m) * f(b) <= 0:return dichotomie(m,b, f, eps)
1
CPGE Informatique MPSI / 1TSI /PCSI
Lydex – Ben guerir Programmation Mr L. BOUHOU
vérification : pour determiner le zero de g(x) = x**(1/2) * cos(x)
from math import *
def g(x):
return x**(1/2) * cos(x)
x=1
y=2
R=dichotomie(x, y, g)
print("Valeur du zéro de la fonction f sur [%s,%s] :%s" %(x, y, R))
11.2.2. Méthode de Newton
La méthode de Newton appelée également méthode de Newton-Raphson a pour but de réaliser l'approximation d'une
fonction affine g d'une fonction f différentiable en un point a.
Principe : approximation d'une fonction en se basant sur le développement de Taylor au premier ordre.
- On choisit un point de départ x0 proche de la solution recherchée.
- On fait alors une approximation grossière en la considérant égale à sa tangente f(x) ~ f(x0) + f ’ (x0) * (x-x0).
- On détermine alors le point d'intersection avec l'axe des abscisses en résolvant l'équation :f(x0) + f ’ (x0) * (x-x0)=0
- On obtient alors le point x1. Et on réitère le processus à partir de ce point.
- On construit par récurrence la suite : xn+1= xn - (f(xn)/f’(xn))
Méthode de Newton
def newton(f, df, xi, h , n):
if(n == 0): return xi
else:
return newton(f, df, xi - f(xi)/df(f,xi,h), h, n-1)
Application : calcule d’une approximation du zero de g(x) = x- log(x) – 3 au voisinage de 2
From math import * def verifier() :
def g(x): x0 = 2
return x- log(x)-3 y0=g(x0)
h=0.0001
def dg (f,x, h): n=10
return (f(x+h)-f(x-h)) / (2.0*h) print("Abcisse du zéro (méthode Newton) :", newton(g, dg, x0, h, n))
verifier() Abcisse du zéro (méthode Newton) : 4.505241495792883
2
CPGE Informatique MPSI / 1TSI /PCSI
Lydex – Ben guerir Programmation Mr L. BOUHOU
11.3. Méthode d’Intégration
Soit une fonction f à valeurs réelles, continue par morceaux sur un intervalle [ a , b ]. On souhaite calculer une valeur
a
approchée de l’intégrale ∫ f ( t ) dt .
b
11.3.1. Méthode des rectangles
La méthode des rectangles consiste à approximer la fonction f par une fonction en escalier. On considère un entier n
b−a b−a
et un pas de subdivision . Pour tout entier k de [0,n], on pose ak=a+k* . Sur l’intervalle [ak , ak+1], on
n n
a +a
approxime f par la fonction constante égale à f( k k+1 ) (voir figure 9.1)
2
On prend, comme valeur approchée de l’intégrale de f sur [a,b], l’intégrale de la fonction en escalier ainsi construite,
b−a
c'est-à-dire la somme des aires des rectangles(les rectangles ont tous une base de longueur ).
n
Une implémentation de la méthode des rectangles pour calculer ∫ f ( t ) dt en subdivisant l’intervalle [a,b] en n
a
intervalles est proposée ci-après. En voici le code Python.
def rectangles (f,a,b,n) : #Méthode des rectangles
S=0
for i in range (0,n):
xi=a+(b-a)*i/n
xj=a+(b-a)*(i+1)/n
S+=f((xi+xj)/2.0)*(xj-xi)
3
CPGE Informatique MPSI / 1TSI /PCSI
Lydex – Ben guerir Programmation Mr L. BOUHOU
return S
b
(b−a) n−1 ( b−a ) ( b−a )
on peut montrer que : ∫ f ( t ) dt ≈ ∑
n k=0
f (a+
2n
+k
n
)
a
par conséquence, notre fonction rectangles() peut s’écrire de la façon suivante :
def rectangles (f,a,b,n) : #Methode des rectangles
S=0
for i in range (0,n):
xi=a+(b-a)/2*n + i * (b-a)/n
S+=f(xi)
return((b-a)/n) * S
11.3.2. Méthode des trapèzes
La méthode des trapèzes consiste à approximer la fonction f par une fonction continue affine par morceaux. Ceux-ci
b−a
coïncident avec la fonction f au point de la subdivision (voir figure 9.2). En notant ak = a+k* les points de la
n
(b−a)
∗(f ( a k )+ f ( a k+1 ) )
subdivision du segment [a,b], l’aire de chaque trapèze est égale à n , c'est-à-dire, en sommant,
2
( )
b n−1
f ( a )+ f ( b )
∫ f ( t ) dt ≈ b−a
n
∗
2
+k =∑ f ( ak ) .
❑
a
Voici une implémentation de la méthode des trapèzes en Python:
def trapezes(f,a,b,n):#Methode des trapezes
S=0
for i in range (0,n):
xi=a+(b-a)*i/float(n)
xj=a+(b-a)*(i+1)/float(n)
S+=(f(xi)+f(xj))/2.0*(xj-xi)
return S