https://www.cfd-online.com/W/index.php?title=Fixed_point_theorem&feed=atom&action=historyFixed point theorem - Revision history2024-03-29T05:37:51ZRevision history for this page on the wikiMediaWiki 1.16.5https://www.cfd-online.com/W/index.php?title=Fixed_point_theorem&diff=6511&oldid=prevNsoualem at 15:25, 4 December 20062006-12-04T15:25:41Z<p></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 15:25, 4 December 2006</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 246:</td>
<td colspan="2" class="diff-lineno">Line 246:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Thus condition (*) guarantees that <math>F</math> is contractive and the</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Thus condition (*) guarantees that <math>F</math> is contractive and the</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Newton iterations will converge.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Newton iterations will converge.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">==Links==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">[http://www.math-linux.com/spip.php?article60 Fixed Point Method]</ins></div></td></tr>
</table>Nsoualemhttps://www.cfd-online.com/W/index.php?title=Fixed_point_theorem&diff=3342&oldid=prevPraveen at 10:53, 19 October 20052005-10-19T10:53:28Z<p></p>
<p><b>New page</b></p><div>The fixed point theorem is a useful tool for proving existence of solutions<br />
and also for convergence of iterative schemes. In fact the latter is used to <br />
prove the former. If the problem is to find the solution of<br />
<br />
:<math><br />
L(u) = 0<br />
</math><br />
<br />
then we convert it to a problem of finding a fixed point<br />
<br />
:<math><br />
u = F(u)<br />
</math><br />
<br />
''Statement''<br />
<br />
Let <math>X</math> be a complete metric space with distance<br />
<math>d(\cdot,\cdot)</math> and let <math>F: X \to X</math> be contractive,<br />
i.e., for some <math>0 < \alpha < 1</math>,<br />
<br />
:<math><br />
d( F(x), F(y) ) \le \alpha d(x,y), \ \ \ \forall x, y \in X<br />
</math><br />
<br />
Then there exists a unique fixed point <math>u \in X</math> such that<br />
<br />
:<math><br />
u = F(u)<br />
</math><br />
<br />
''Proof''<br />
<br />
Choose any <math>x_o \in X</math> and define the sequence <math>(x_n)</math> by<br />
the following iterative scheme<br />
<br />
:<math><br />
x_{n+1} = F(x_n)<br />
</math><br />
<br />
If we can show that the sequence <math>(x_n)</math> has a unique limit<br />
independent of the starting value then we would have proved the existence of<br />
the fixed point. The first step is to show that <math>(x_n)</math> is a Cauchy<br />
sequence.<br />
<br />
{|<br />
|-<br />
|<math>d(x_{m+1}, x_m) </math><br />
|<math>= d(F(x_m), F(x_{m-1}))</math><br />
|-<br />
|<br />
|<math>\le \alpha d( x_m, x_{m-1} ) </math><br />
|-<br />
|<br />
|<math>= \alpha d( F(x_{m-1}), F(x_{m-2}) ) </math><br />
|-<br />
|<br />
|<math>\le \alpha^2 d ( x_{m-1}, x_{m-2} ) </math><br />
|-<br />
|<br />
|<math>. </math><br />
|-<br />
|<br />
|<math>. </math><br />
|-<br />
|<br />
|<math>\le \alpha^m d(x_1, x_o)</math><br />
|}<br />
<br />
Now using the triangle inequality we get, for <math>n > m</math><br />
<br />
{|<br />
|<math>d(x_m, x_n) </math><br />
|<math>\le d(x_m, x_{m+1}) + d(x_{m+1}, x_{m+2}) + .... + d(x_{n-1},x_n) </math><br />
|-<br />
|<br />
|<math>\le (\alpha^m + \alpha^{m+1} + .... + \alpha^{n-1} ) d(x_o, x_1) </math><br />
|-<br />
|<br />
|<math>= \alpha^m \frac{ 1 - \alpha^{n-m} }{1 - \alpha} d(x_o, x_1) </math><br />
|-<br />
|<br />
|<math>\le \frac{ \alpha^m }{1 - \alpha} d(x_o, x_1)</math><br />
|}<br />
<br />
where the last inequality follows because <math>1 - \alpha^{n-m} < 1</math>.<br />
Now since <math>\alpha^m \to 0</math> as <math>m \to \infty</math> we see that<br />
<br />
:<math><br />
d(x_m, x_n) \to 0, \ \ \ \textrm{ as } \ \ \ m,n \to \infty<br />
</math><br />
<br />
which proves that <math>(x_n)</math> is a Cauchy sequence. Since <math>X</math><br />
is complete, this sequence converges to a unique limit <math>u</math>. It is<br />
now left to show that the limit is a fixed point.<br />
<br />
:<math><br />
d(u, F(u)) \le d(u, x_m) + d(x_m, F(u))<br />
\le d(u, x_m) + \alpha d(x_{m-1}, u)<br />
</math><br />
<br />
and since <math>u</math> is the limit of the sequence we see that the right<br />
hand side goes to zero so that<br />
<br />
:<math><br />
d(u, F(u)) = 0 \ \ \ \Longrightarrow \ \ \ u = F(u)<br />
</math><br />
<br />
The uniqueness of the fixed point follows easily. Let <math>u</math> and<br />
<math>\bar{u}</math> be two fixed points. Then<br />
<br />
:<math><br />
d(u, \bar{u} ) = d(F(u), F(\bar{u})) \le \alpha d(u, \bar{u})<br />
</math><br />
<br />
and since <math>0 < \alpha < 1</math> we conclude that <br />
<br />
:<math><br />
d(u, \bar{u}) = 0 \ \ \ \Longrightarrow \ \ \ u = \bar{u}<br />
</math><br />
<br />
==Application to solution of linear system of equations==<br />
<br />
We will apply the fixed point theorem to show the convergence of Jacobi<br />
iterations for the numerical solution of the linear algebraic system<br />
<br />
:<math><br />
Ax = b<br />
</math><br />
<br />
under the condition that the matrix <math>A</math> is diagonally dominant. Assuming<br />
that the diagonal elements are non-zero, define the diagonal matrix<br />
<br />
:<math><br />
D = \textrm{diag}(A_{11}, A_{22}, ...., A_{NN})<br />
</math><br />
<br />
and rewriting we get<br />
<br />
:<math><br />
x = D^{-1} [ b - (A-D)x]<br />
</math><br />
<br />
which is now in the form of a fixed point problem with<br />
<br />
:<math><br />
F(x) = D^{-1} [ b - (A-D)x]<br />
</math><br />
<br />
For measuring the distance between two vectors let us choose the maximum norm<br />
<br />
:<math><br />
d(x,y) = \max_{j} | x_j - y_j |<br />
</math><br />
<br />
We must show that <math>F</math> is a contraction mapping in this norm. Now<br />
<br />
:<math><br />
F(x) - F(y) = - D^{-1}(A-D)(x-y)<br />
</math><br />
<br />
so that the j'th component is given by<br />
<br />
:<math><br />
[F(x) - F(y)]_j = \sum_{k \ne j} \frac{ A_{jk} }{ A_{jj}} (x_k - y_k)<br />
</math><br />
<br />
From this we get<br />
<br />
:<math><br />
| [F(x) - F(y)]_j | \le \max_k | x_k - y_k | \sum_{k \ne j} \left| <br />
\frac{ A_{jk} }{ A_{jj}} \right|<br />
</math><br />
<br />
and<br />
<br />
:<math><br />
d( F(x), F(y) ) \le d(x,y)\max_j \sum_{k \ne j} \left| \frac{ A_{jk} }{ A_{jj}} <br />
\right|<br />
</math><br />
<br />
Hence the mapping is contractive if<br />
<br />
:<math><br />
\sum_{k \ne j} | A_{jk} | < | A_{jj} |, \ \ \ 1 \le j \le N<br />
</math><br />
<br />
which is just the condition of diagonal dominance of matrix <math>A</math>. Hence if<br />
the matrix is diagonally dominant then the fixed point theorem assures us<br />
that the Jacobi iterations will converge.<br />
<br />
==Application to Newton-Raphson method==<br />
<br />
Consider the problem of finding the roots of an equation<br />
<br />
:<math><br />
f(x) = 0<br />
</math><br />
<br />
If an approximation to the root <math>x_n</math> is already available then the next<br />
approximation <br />
<br />
:<math><br />
x_{n+1}= x_n + \Delta x_n<br />
</math><br />
<br />
is calculated by requiring that<br />
<br />
:<math><br />
f(x_n + \Delta x_n) = 0<br />
</math><br />
<br />
Using Taylors formula and assuming that <math>f</math> is differentiable we can<br />
approximate the left hand side,<br />
<br />
:<math><br />
f(x_n) + \Delta x_n f^\prime(x_n) = 0 \ \ \ \Longrightarrow \ \ \ <br />
\Delta x_n = - \frac{f(x_n)}{ f^\prime(x_n) }<br />
</math><br />
<br />
so that the new approximation is given by<br />
<br />
:<math><br />
x_{n+1} = x_n - \frac{f(x_n)}{f^\prime(x_n) }<br />
</math><br />
<br />
This defines the iterative scheme for Newton-Raphson method and the solution<br />
if it exists, is the fixed point of<br />
<br />
:<math><br />
F(x) = x - \frac{ f(x) }{ f^\prime(x) }<br />
</math><br />
<br />
If we assume that<br />
<br />
<math><br />
(*) \quad | F^\prime(x) | \le \alpha < 1<br />
</math><br />
<br />
in some neighbourhood of the solution then<br />
<br />
:<math><br />
F(y) - F(x) = \int^y_x F^\prime(z) d z \ \ \ \Longrightarrow \ \ \ |F(y) -<br />
F(x)| \le \alpha |y-x|<br />
</math><br />
<br />
Thus condition (*) guarantees that <math>F</math> is contractive and the<br />
Newton iterations will converge.</div>Praveen