.pdf
.ipynb
Méthode de point fixe
1. Principe
On considère toujours l’équation \(f(x) = \sin(2x) -1 + x = 0\). On peut construire deux problèmes équivalents
Démonstration
-
Si l’hypothèse H1 est vérifiée: La fonction \(g(x) = \phi(x) - x\) est continue sur \([a,b]\) et, pour l’hypothèse sur l’image de \(\phi\), on a que \(g(a) = \phi(a) - a \geq 0\) et \(g(b) = \phi(b) - b \leq 0\). On sait alors qu’il existe au moins un zéro de \(g\) dans l’intervalle \([a,b]\), donc il existe au moins un point fixe de \(\phi\) dans \([a,b]\).
-
Si l’hypothèse H2 est vérifiée: on peut montrer que l’hypothèse H2 est équivalent à:
\(\exists K<1\) tel que \(|\phi(x_1) - \phi(x_2) |\leq K |x_1 - x_2|, \quad \forall x_1, x_2 \in [a,b]\).
Soient \(\alpha_1, \alpha_2 \in [a, b]\) deux points fixes différents, on a donc que
ce qui est absurde. Il existe donc un unique point fixe \(\alpha\) de \(\phi\) dans \([a,b]\).
Soient \(x^{(0)} \in [a, b]\) et \(x^{(k+1)}=\phi(x^{(k)})\). On a que
c-à-d
Puisque \(K < 1\), pour \(k \rightarrow \infty\), on a que
Donc, \(\forall x^{(0)}\in[a,b]\), la suite \(\{x^{(k)}\}\) définie par \(x^{(k+1)}=\phi(x^{(k)})\), \(k\geq 0\) converge vers \(\alpha\) lorsque \(k\rightarrow\infty\).
|
Pour la dernière partie, on peut montrer cela de manière alternative A partir de
\[x^{(k+1)}-\alpha=\phi\left(x^{(k)}\right)-\phi(\alpha)\]
on tire, grâce au théorème de Lagrange appliqué à la fonction \(\phi\), qu’il existe \(\eta\) compris entre \(x^{(k)}\) et \(\alpha\) tel que
\[x^{(k+1)}-\alpha=\phi^{\prime}(\eta)\left(x^{(k)}-\alpha\right) .\]
Or, \(x^{(k)}\) et \(\alpha\) appartiennent à \([a, b]\), donc on a \(\eta \in[a, b]\) aussi; ceci entraîne le résultat voulu, grâce à l’hypothèse \(\mathrm{H} 2\) :
\[\left|x^{(k+1)}-\alpha\right|=\left|\phi^{\prime}(\eta)\left(x^{(k)}-\alpha\right)\right|=\left|\phi^{\prime}(\eta)\right|\left|x^{(k)}-\alpha\right| \leq K\left|x^{(k)}-\alpha\right| .\]
|
|
On remarque que, si \(0<\mid \phi'(\alpha)\mid<1\), alors pour n’importe quelle constante \(C\) telle que \(|\phi'(\alpha)|<C<1\), si \(k\) est suffisamment grand on a :
\[\mid x^{(k+1)}-\alpha\mid\leq C\mid x^{(k)}-\alpha\mid.\]
|
Démonstration: Convergence d’ordre 2
Un développement de Taylor de \(\phi\) en \(x=\alpha\) donne
où \(\eta\) est entre \(x^{(k)}\) et \(\alpha\). Ainsi, on a
2. Implémentation de la méthode de point fixe
L’implémentation de la méthode de point fixe est très simple:
def fixpoint(phi, x0, tol, nmax, *args):
"""
FIXPOINT Fixed point iterations.
P=FIXPOINT(PHI,X0,TOL,NMAX) tries to find the fixed point P of the
continuous and differentiable function PHI using fixed point iterations
starting from X0. PHI is a function which accepts real scalar input x
and returns a real scalar value. If the search fails, an error message is displayed.
[P,RES,NITER]= FIXPOINT(PHI,...) returns the value of the residual in ZERO
and the iteration number at which ZERO was computed.
[P,RES,NITER,INC]= FIXPOINT(PHI,...) returns a list INC with the absolute values of the
differences between successive approximations (increments).
"""
x = x0
phix = phi(x, *args)
niter = 0
diff = tol + 1
inc = [x0]
while diff >= tol and niter < nmax:
niter += 1
diff = abs(phix - x)
x = phix
phix = phi(x, *args)
inc.append(diff)
if niter >= nmax:
print('fixpoint stopped without converging to the desired tolerance',
'because the maximum number of iterations was reached')
p = x
res = phix - x
return p, res, niter, incvoici un exemple d’utilisation de la méthode de point fixe
from tan.eqnonlin.fixpoint import fixpoint
# Define a function phi for fixed-point iteration
phi = lambda x: -x**2/4 + x +1 # Example function
x0 = 1.5 # Initial guess
tol = 1e-5 # Tolerance
nmax = 100 # Maximum number of iterations
# Call the fixpoint function
p, res, niter, inc = fixpoint(phi, x0, tol, nmax)
print(f"Fixed Point: {p}, Residual: {res}, Iterations: {niter}")Results
Fixed Point: 1.9999999999999858, Residual: 1.4210854715202004e-14, Iterations: 4
3. Influence de \(\mid \phi'(\alpha) \mid\)
Quelques exemples sur comment la valeur de \(\mid \phi'(\alpha)\mid\) influence la convergence.
- Cas convergent
-
\(0<\phi'(\alpha)<1\), \(\qquad \qquad \qquad\) \(-1<\phi'(\alpha)<0\).
- Cas divergent
-
\(\phi'(\alpha)>1\), \(\qquad \qquad \qquad\) \(\phi'(\alpha)<-1\).
5. Newton: une méthode de point fixe
La méthode de Newton constitue une méthode de point fixe : \(x^{(k+1)}=\phi(x^{(k)})\) pour la fonction
Soit \(\alpha\) un zéro pour la fonction \(f\), c-à-d tel que \(f(\alpha)=0\). On remarque que \(\phi'(\alpha)=0\), lorsque \(f'(\alpha)\neq 0\). En effet,
Details
La propriété de la convergence vient de la Proposition Proposition: Convergence locale, tandis que la convergence quadratique est une conséquence de la Proposition Proposition:. Convergence d’ordre 2 et du fait que \(\phi^\prime(\alpha) = 0\) et que \(\frac{\phi''(\alpha)}{2} = \frac{f''(\alpha)}{2 f'(\alpha)}\).
On dit que un zéro \(\alpha\) de \(f\) est de multiplicité \(p\), \(p\in\mathbb{N}\) si \(f(\alpha)=\ldots =f^{(p-1)}(\alpha)=0\,\,\,\,\text{ et } f^{(p)}(\alpha)\neq 0.\) Un zéro de multiplicité \(p=1\) est appelé zéro simple.
|
_Si \(f'(\alpha)=0\), la convergence de la méthode de Newton est seulement linéaire, pas quadratique. On considère alors la méthode de Newton modifiée:
\[{x^{(k+1)}=x^{(k)}-p\frac{f(x^{(k)})}{f'(x^{(k)})},\,\,\,k=0,1,2\ldots.}\]
avec \(p\) la multiplicité de \(\alpha\)._ Si la multiplicité \(p\) de \(\alpha\) n’est pas connue, il y a d’autres méthodes, des méthodes adaptatives, qui permettent de récupérer l’ordre quadratique de la convergence. |
5.1. Un critère d’arrêt pour Newton
Quand faut-il terminer les itérations de l’algorithme de Newton?
Un bon critère d’arrêt est le contrôle de l’incrément: les itérations s’achèvent dès que
où \(\epsilon\) est une tolérance fixée.
En fait, si on note \(e^{(k)} = \alpha - x^{(k)}\) l’erreur à l’itération \(k\), on a
avec \(\xi^{(k)}\) entre \(x^{(k)}\) et \(\alpha\), et
Or, si \(k\) est suffisamment grand, \(\phi^\prime(\xi^{(k)}) \approx \phi^\prime(\alpha)\), et on sait que pour la méthode de Newton \(\phi'(\alpha) = 0\).
Donc on a
L’erreur qu’on commet lorsque l’on adopte le critère [crit-arret] est donc plus petite que la tolérance fixée.
6. Critères d’arrêt
En général, pour toutes les méthodes étudiées, on peut utiliser deux critères d’arrêt différents : les itérations s’achèvent dès que
- Contrôle de l’incrément
-
on contrôle l’incrément \(|x^{(k+1)} - x^{(k)}|\) et on s’arrête dès que \(|x^{(k+1)} - x^{(k)}| < \epsilon\) où \(\epsilon\) est une tolérance fixée.
- Contrôle du résidu
-
on contrôle le résidu \(|f(x^{(k)})|\) et on s’arrête dès que \(|f(x^{(k)})| < \epsilon\) où \(\epsilon\) est une tolérance fixée.
On a vu que pour la méthode de Newton le premier critère (contrôle de l’incrément) est optimal au sens qu’il garantit que l’erreur finale soit plus petite que la tolérance fixée.
Par contre, le deuxième critére (contrôle du residu) est satisfaisant lorsque \(|f'|\simeq 1\) dans un voisinage de la racine \(\alpha\). Sinon il est soit trop restrictif (si \(|f'|\gg 1\)) soit trop faible (si \(|f|\ll 1\)):
Deux cas où le résidu est un mauvais estimateur de l’erreur: \(|f'(x)|\gg 1\) (à gauche), \(|f'(x)|\ll 1\) (à droite) avec \(x\) dans un voisinage de \(\alpha\).