%% This document created by Scientific Word (R) Version 2.5
%% Starting shell: tcimemo


\documentclass[12pt]{article}
\usepackage{amsfonts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{tcimemo}
%\usepackage{sw20mem1}
\usepackage{sw20exmA}
%TCIDATA{TCIstyle=memo/memo.lat,mem1,tcimemo}

%TCIDATA{Created=Wed Apr 30 11:53:59 1997}
%TCIDATA{LastRevised=Thu May 15 17:12:09 1997}
%TCIDATA{Language=American English}

\input{tcilatex}
\begin{document}


\begin{center}
\textbf{Concours Commun Polytechnique - Math\'{e}matiques 2 - 1997}
\end{center}

\medskip

\underline{\emph{Partie I}}

\medskip

I.1. $BX=Z\Leftrightarrow \;^{t}AAX=\;^{t}AY$

\ \ \ \ \ \ \ \ \ \ \ \ \ $\Leftrightarrow AX=Y\;$(car $A$ donc $^{t}A$ est
inversible)

\ \ \ \ \ \ \ \ \ \ \ \ \ $\Leftrightarrow X=A^{-1}Y$

\underline{Donc l'\'{e}quation lin\'{e}aire $BX=Z$ poss\`{e}de la solution
unique $X_{0}.$}

\medskip

2. $^{t}B=\;^{t}(^{t}AA)=\;^{t}AA=B$

\underline{Donc $B$ est sym\'{e}trique.}

\medskip

\frame{$
\begin{array}{l}
B\;\text{\'{e}tant sym\'{e}trique r\'{e}elle :} \\ 
\text{- son polyn\^{o}me caract\'{e}ristique est scind\'{e} dans }\Bbb{R} \\ 
\text{- les sous-espaces propres de }B\;\text{sont }2\text{ \`{a} }2\text{
orthogonaux} \\ 
\text{- il existe }P\in O(k)\;\text{telle que }P^{-1}BP\in D_{k}(\Bbb{R)}
\end{array}
$}

\medskip

3. \underline{$<U,BU>=\;^{t}U^{t}AAU=\left\| AU\right\| ^{2}>0$}$\;$($U\neq
0 $ et $A$ inversible $\Rightarrow AU\neq 0)$

Soit $\lambda \in Spec(B)$ et $U$ vecteur propre associ\'{e} \`{a} $B;$
alors $U\neq 0$ et $BU=\lambda U.$

D'o\`{u} $\left\langle U,BU\right\rangle =\left\{ 
\begin{array}{l}
^{t}U^{t}AAU=\left\| AU\right\| ^{2}>0 \\ 
\left\langle U,\lambda U\right\rangle =\lambda \left\| U\right\| ^{2}
\end{array}
\right. \;^{t}U^{t}AAU=\left\| AU\right\| ^{2}>0$

D'o\`{u} $\lambda >0.$ On a montr\'{e} que : 
\[
\frame{$Spec(B)\subset \Bbb{R}^{+*}$} 
\]

\medskip

4. Notons $(U_{1},...,U_{k})$ une base orthonorm\'{e}e de $\Bbb{R}^{k}$
form\'{e}e de vecteurs propres de $B.\;$Posons $V=\sum\limits_{i=1}^{k}%
\alpha _{i}U_{i}.$ Alors :

$\left\langle AV,AV\right\rangle =\;^{t}V^{t}AAV=\;^{t}VBV=\left\langle
V,BV\right\rangle =\left\| AV\right\| ^{2}.$

En outre :

$\left\langle AV,AV\right\rangle =\left\langle \sum\limits_{i=1}^{k}\alpha
_{i}U_{i},\sum\limits_{i=1}^{k}\alpha _{i}BU_{i}\right\rangle $

\ \ \ \ \ \ \ \ $\;=\left\langle \sum\limits_{i=1}^{k}\alpha
_{i}U_{i},\sum\limits_{i=1}^{k}\alpha _{i}\lambda _{i}U_{i}\right\rangle $

\ \ \ \ \ \ \ \ $\;=\sum\limits_{i=1}^{k}\alpha _{i}^{2}\lambda _{i}$ car $%
(U_{1},...,U_{k})$ est une base orthonorm\'{e}e de $\Bbb{R}^{k}.$

D'o\`{u} $\lambda _{\text{mini}}\sum\limits_{i=1}^{k}\alpha _{i}^{2}\leq
\left\| AV\right\| ^{2}\leq \lambda _{\text{maxi}}\sum\limits_{i=1}^{k}%
\alpha _{i}^{2}$ et comme $\sum\limits_{i=1}^{k}\alpha _{i}^{2}=1\;$($V$ est
unitaire)

a. \frame{$\left\langle AV,AV\right\rangle =\left\langle V,BV\right\rangle
=\left\| AV\right\| ^{2}\in \left[ \lambda _{\text{mini}},\lambda _{\text{%
maxi}}\right] $}

b. $\left\| BV\right\| =\left\| \sum\limits_{i=1}^{k}\alpha
_{i}BU_{i}\right\| =\left\| \sum\limits_{i=1}^{k}\alpha _{i}\lambda
_{i}U_{i}\right\| =\left( \sum\limits_{i=1}^{k}\alpha _{i}^{2}\lambda
_{i}^{2}\right) ^{1/2}$ car $(U_{1},...,U_{k})$ est une base orthonorm\'{e}e
de $\Bbb{R}^{k}.$ Or :

$\left( \sum\limits_{i=1}^{k}\alpha _{i}^{2}\lambda _{i}^{2}\right)
^{1/2}\in \left[ \lambda _{\text{mini}}\left( \sum\limits_{i=1}^{k}\alpha
_{i}^{2}\right) ^{1/2},\lambda _{\text{maxi}}\left(
\sum\limits_{i=1}^{k}\alpha _{i}^{2}\right) ^{1/2}\right] $ car les $\lambda
_{i}$ sont positifs. Comme $\left\| V\right\| =\left(
\sum\limits_{i=1}^{k}\alpha _{i}^{2}\right) ^{1/2}=1,$

\[
\frame{$\left\| BV\right\| \in \left[ \lambda _{\text{mini}},\lambda _{\text{%
maxi}}\right] $}
\]

Si $U$ est quelconque dans $\Bbb{R}^{k}\backslash \{0\},$ $V=\dfrac{U}{%
\left\| U\right\| }$ est unitaire. En appliquant a; et b; \`{a} $V,$ on
obtient :

$\left\langle AU,AU\right\rangle =\left\langle U,BU\right\rangle =\left\|
AU\right\| ^{2}\in \left[ \lambda _{\text{mini}}\left\| U\right\|
^{2},\lambda _{\text{maxi}}\left\| U\right\| ^{2}\right] $

et\ 

$\left\| BU\right\| \in \left[ \lambda _{\text{mini}}\left\| U\right\|
,\lambda _{\text{maxi}}\left\| U\right\| \right] $

relations qui sont encore vraies pour $U=0.$

Donc : $\forall U\in \Bbb{R}^{k},$

\[
\frame{$\left\langle AU,AU\right\rangle =\left\langle U,BU\right\rangle
=\left\| AU\right\| ^{2}\in \left[ \lambda _{\text{mini}}\left\| U\right\|
^{2},\lambda _{\text{maxi}}\left\| U\right\| ^{2}\right] $} 
\]

\[
\frame{$\left\| BU\right\| \in \left[ \lambda _{\text{mini}}\left\|
U\right\| ,\lambda _{\text{maxi}}\left\| U\right\| \right] $} 
\]

\medskip

5. D'apr\`{e}s la question 1., $R(X_{0})=0$ et $E(X_{0})=0.$

Si $U\neq X_{0},$ $BU-Z\neq 0$ et $E(U)\neq 0.$

\underline{Donc il existe un unique vecteur $X\in \Bbb{R}^{k}$ rendant $E$
minimale, c'est $X_{0}$}$.$

On a alors \underline{$E(X_{0})=\min\limits_{U\in \Bbb{R}^{k}}E(U)=0$}.

\medskip

\underline{\emph{Partie II}}

\medskip

1. $\forall \mu \in \Bbb{R},$ $f_{i}(\mu )=\left\| R(X_{i}+\mu
D_{i})\right\| ^{2}$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\;=\left\| B(X_{i}+\mu D_{i})-Z\right\|
^{2}$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\;=\left\| BX_{i}-Z+\mu BD_{i}\right\|
^{2}$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\;=\left\| BX_{i}-Z\right\| ^{2}+2\mu
\left\langle BX_{i}-Z,BD_{i}\right\rangle +\mu ^{2}\left\| BD_{i}\right\|
^{2}$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\;=E(X_{i})+2\alpha \mu +\beta \mu ^{2}$
avec :

\[
\frame{$\alpha =\left\langle BX_{i}-Z,BD_{i}\right\rangle $ et $\beta
=\left\| BD_{i}\right\| ^{2}$} 
\]

$f_{i}$ est une fonction polyn\^{o}me $C^{\infty }$ sur $\Bbb{R}.$ Comme $%
D_{i}\neq 0$ et $B$ est inversible, $BD_{i}\neq 0$ et $\beta >0.$ $f_{i}$
est donc du second degr\'{e} et admet un minimum pour $f_{i}^{\prime }(\mu
)=0\Leftrightarrow \mu =-\dfrac{\alpha }{\beta }.$

Donc $\mu _{i}=-\dfrac{\left\langle BX_{i}-Z,BD_{i}\right\rangle }{\left\|
BD_{i}\right\| ^{2}}\Rightarrow $

\[
\frame{$\mu _{i}=-\dfrac{\left\langle R(X_{i}),BD_{i}\right\rangle }{\left\|
BD_{i}\right\| ^{2}}$} 
\]

On a alors : $\min\limits_{\mu \in \Bbb{R}}f_{i}(\mu )=f_{i}(\mu
_{i})=E(X_{i})-2\dfrac{\left\langle R(X_{i}),BD_{i}\right\rangle }{\left\|
BD_{i}\right\| ^{2}}\left\langle BX_{i}-Z,BD_{i}\right\rangle +\dfrac{%
\left\langle R(X_{i}),BD_{i}\right\rangle ^{2}}{\left\| BD_{i}\right\| ^{4}}%
\left\| BD_{i}\right\| ^{2}$

$=E(X_{i})-2\dfrac{\left\langle R(X_{i}),BD_{i}\right\rangle }{\left\|
BD_{i}\right\| ^{2}}\left\langle R(X_{i}),BD_{i}\right\rangle +\dfrac{%
\left\langle R(X_{i}),BD_{i}\right\rangle ^{2}}{\left\| BD_{i}\right\| ^{2}}%
.\;$D'o\`{u} :

\[
\frame{$\min\limits_{\mu \in \Bbb{R}}f_{i}(\mu )=E(X_{i})-\dfrac{%
\left\langle R(X_{i}),BD_{i}\right\rangle ^{2}}{\left\| BD_{i}\right\| ^{2}}$%
} 
\]

\medskip

2. $f_{i}(\mu _{i})=E(X_{i})-\dfrac{\left\langle
R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\| BR(X_{i})\right\| ^{2}}$

$\;\;\;\;\;\;\;\;=E(X_{i})-\dfrac{\left\langle
R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\| BR(X_{i})\right\| ^{2}}$

$\;\;\;\;\;\;\;\;=E(X_{i})-\dfrac{\left\langle
R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\| BR(X_{i})\right\| ^{2}\left\|
R(X_{i})\right\| ^{2}}E(X_{i})$ (car $E(X_{i})=\left\| R(X_{i})\right\| ^{2}$%
)

$\;\;\;\;\;\;\;\;=E(X_{i})\left( 1-\dfrac{\left\langle
R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\| BR(X_{i})\right\| ^{2}\left\|
R(X_{i})\right\| ^{2}}\right) $

D'o\`{u} :

\[
\frame{$f_{i}(\mu _{i})=C_{i}E(X_{i})\;$avec $C_{i}=1-\dfrac{\left\langle
R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\| BR(X_{i})\right\| ^{2}\left\|
R(X_{i})\right\| ^{2}}$} 
\]

D'apr\`{e}s l'in\'{e}galit\'{e} de Cauchy-Schwarz, $\left\langle
R(X_{i}),BR(X_{i})\right\rangle ^{2}\leq \left\| BR(X_{i})\right\|
^{2}\left\| R(X_{i})\right\| ^{2}$ et $C_{i}\geq 0.$

D'apr\`{e}s la question I.3.,

$0\leq \left\langle R(X_{i}),BR(X_{i})\right\rangle \in \left[ \lambda _{%
\text{mini}}\left\| R(X_{i})\right\| ^{2},\lambda _{\text{maxi}}\left\|
R(X_{i})\right\| ^{2}\right] \Rightarrow $

$\dfrac{\left\langle R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\|
BR(X_{i})\right\| ^{2}\left\| R(X_{i})\right\| ^{2}}\in $

$\left[ \lambda _{\text{mini}}^{2}\dfrac{\left\| R(X_{i})\right\| ^{4}}{%
\left\| BR(X_{i})\right\| ^{2}\left\| R(X_{i})\right\| ^{2}},\lambda _{\text{%
maxi}}^{2}\dfrac{\left\| R(X_{i})\right\| ^{4}}{\left\| BR(X_{i})\right\|
^{2}\left\| R(X_{i})\right\| ^{2}}\right] \Rightarrow $

$\dfrac{\left\langle R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\|
BR(X_{i})\right\| ^{2}\left\| R(X_{i})\right\| ^{2}}\in \left[ \lambda _{%
\text{mini}}^{2}\dfrac{\left\| R(X_{i})\right\| ^{2}}{\left\|
BR(X_{i})\right\| ^{2}},\lambda _{\text{maxi}}^{2}\dfrac{\left\|
R(X_{i})\right\| ^{2}}{\left\| BR(X_{i})\right\| ^{2}}\right] $

En outre, toujours d'apr\`{e}s la question I.3.,

$\left\| BR(X_{i})\right\| ^{2}\in \left[ \lambda _{\text{mini}}^{2}\left\|
R(X_{i})\right\| ^{2},\lambda _{\text{maxi}}^{2}\left\| R(X_{i})\right\|
^{2}\right] $ et

$\dfrac{\left\| R(X_{i})\right\| ^{2}}{\left\| BR(X_{i})\right\| ^{2}}\in
\left[ \dfrac{1}{\lambda _{\text{maxi}}^{2}},\dfrac{1}{\lambda _{\text{mini}%
}^{2}}\right] .$

On en d\'{e}duit $\dfrac{\left\langle R(X_{i}),BR(X_{i})\right\rangle ^{2}}{%
\left\| BR(X_{i})\right\| ^{2}\left\| R(X_{i})\right\| ^{2}}\in \left[ 
\dfrac{\lambda _{\text{mini}}^{2}}{\lambda _{\text{maxi}}^{2}},\dfrac{%
\lambda _{\text{maxi}}^{2}}{\lambda _{\text{mini}}^{2}}\right] $ $%
\Rightarrow $

$\dfrac{\left\langle R(X_{i}),BR(X_{i})\right\rangle ^{2}}{\left\|
BR(X_{i})\right\| ^{2}\left\| R(X_{i})\right\| ^{2}}\geq \dfrac{\lambda _{%
\text{mini}}^{2}}{\lambda _{\text{maxi}}^{2}}.\;$On a montr\'{e} :

\[
\frame{$0\leq C_{i}\leq 1-\dfrac{\lambda _{\text{mini}}^{2}}{\lambda _{\text{%
maxi}}^{2}}$} 
\]

\medskip

3. Supposons la suite $(X_{i})$ parfaitement d\'{e}finie, ce qui signifie $%
\forall i\in \Bbb{N},$ $X_{i}\neq 0.$

(Dans le cas contraire, $\exists i_{0}\in \Bbb{N},$ $%
D_{i_{0}}=R(X_{i_{0}})=0\Leftrightarrow X_{i_{0}}=A^{-1}Y=X_{0},$ $%
E(X_{i_{0}})=0$ et l'algorithme s'arr\^{e}te : le test est non pr\'{e}vu)

On a alors $\forall i\in \Bbb{N}^{*},$ $E(X_{i+1})=C_{i}E(X_{i})$ (question
2.)

Comme $\forall i\in \Bbb{N}^{*},$ $E(X_{i})\geq 0$ et $C_{i}\leq 1,$ la
suite $(E(X_{i}))$ est d\'{e}croissante et minor\'{e}e par $0,$ donc 
\underline{$(E(X_{i}))$ converge}.

Posons $\theta =1-\dfrac{\lambda _{\text{mini}}^{2}}{\lambda _{\text{maxi}%
}^{2}}.\;$Alors $\theta \in [0,1[$ et d'apr\`{e}s la question 2.,

$\forall i\in \Bbb{N}^{*},$ $0\leq E(X_{i+1})\leq \theta E(X_{i})\Rightarrow 
$

$\forall i\in \Bbb{N}^{*},$ 0$\leq E(X_{i})\leq \theta ^{i-1}E(X_{1})\;$%
(r\'{e}currence simple)

On en d\'{e}duit que $:$

\[
\frame{$\lim\limits_{i\rightarrow +\infty }E(X_{i})=0$} 
\]

On a alors $\left\| B(X_{i}-X_{0})\right\| ^{2}=\left\|
BX_{i}-Z-(BX_{0}-Z)\right\| ^{2}$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\;=\left\|
BX_{i}-Z\right\| ^{2}$ (car $BX_{0}=Z$)

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $%
\;=\left\| R(X_{i})\right\| ^{2}$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ $\;=E(X_{i})$

De plus, $\left\| B(X_{i}-X_{0})\right\| ^{2}\geq \lambda _{\text{mini}%
}^{2}\left\| X_{i}-X_{0}\right\| ^{2}.$

Donc :$\left\| X_{i}-X_{0}\right\| ^{2}\leq \dfrac{E(X_{i})}{\lambda _{\text{%
mini}}^{2}}$ ($\lambda _{\text{mini}}^{2}>0$). Comme $\lim\limits_{i%
\rightarrow +\infty }E(X_{i})=0,$ $\lim\limits_{i\rightarrow +\infty
}\left\| X_{i}-X_{0}\right\| ^{2}=0$ et 
\[
\frame{$\lim\limits_{i\rightarrow +\infty }X_{i}=X_{0}$} 
\]

\medskip

4. $\forall i\in \Bbb{N}^{*},\;\left\| X_{i}-X_{0}\right\| ^{2}\leq \dfrac{%
E(X_{i})}{\lambda _{\text{mini}}^{2}}\leq \dfrac{\theta ^{i-1}E(X_{1})}{%
\lambda _{\text{mini}}^{2}}.$

Pour un nombre d'it\'{e}rations donn\'{e}, la pr\'{e}cision sera
influenc\'{e}e par le facteur $\theta =1-\dfrac{\lambda _{\text{mini}}^{2}}{%
\lambda _{\text{maxi}}^{2}}.\;$Plus il est proche de $0,$ plus la
convergence est rapide.\ Cela correspond \`{a} $\dfrac{\lambda _{\text{mini}%
}^{2}}{\lambda _{\text{maxi}}^{2}}$ proche de $1$ ou encore un spectre de $B$
concentr\'{e} dans une plage \'{e}loign\'{e}e de $0.$

\medskip

\underline{\emph{Partie III}}

Logiciel de calcul employ\'{e} : \underline{MAPLE}

\TEXTsymbol{>} restart;

\TEXTsymbol{>} with(linalg):

Warning, new definition for norm

Warning, new definition for trace

\TEXTsymbol{>} val\_mini:=proc(X) ;

\TEXTsymbol{>} val\_maxi:=proc(X) ;

1.a.

\TEXTsymbol{>} A:=matrix([[4,0,1],[0,4,-1],[-2,1,8]]);

\TEXTsymbol{>} Y:=vector([6,-6,13]);

\medskip

1.b.

\TEXTsymbol{>} B:=multiply(transpose(A),A);

\TEXTsymbol{>} Z:=multiply(transpose(A),Y);

\medskip

2.

\TEXTsymbol{>} X:=vector([0,0,0]):

\TEXTsymbol{>} for n from 1 to 10 do

d:=evalf(matadd(multiply(B,X),Z,1,-1));

\# calcul de la direction de descente

T:=multiply(B,d);

mu:=-dotprod(d,T)/dotprod(T,T);

\# calcul de mu

X:=matadd(X,d,1,mu); \# calcul de X

od:

print(`X(10)=`,X);

\[
\frame{X(10)=[.9999995725, -1.000000508, 1.999999548]} 
\]

\medskip

3.a.

\TEXTsymbol{>} theta:=evalf(1-(val\_mini(B)/val\_maxi(B))\symbol{94}2);

\TEXTsymbol{>} \# calcul du coefficient theta

\[
\frame{theta := .9477756523} 
\]

\medskip

3.b.

On a vu que $\forall n\in \Bbb{N},$ $E(X_{n+1})\leq \theta ^{n}E(X_{1}).$
Donc $\theta ^{n}\leq \dfrac{1}{1000}\Rightarrow $

$E(X_{n+1})\leq E(X_{1})/1000.$

Or $\theta ^{n}\leq \dfrac{1}{1000}\Leftrightarrow n\ln \theta \leq -\ln
(1000)$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\;\Leftrightarrow n\geq -\dfrac{\ln (1000)}{%
\ln (\theta )}$

\frame{Donc si $n_{0}$ est la partie enti\`{e}re de $-\dfrac{\ln (1000)}{\ln
(\theta )}+1,$ $E(X_{n_{0}+1})\leq \theta ^{n_{0}}E(X_{1})$}

\TEXTsymbol{>} n:=floor(-ln(1000)/ln(theta))+1;

\TEXTsymbol{>} \# n est le nombre d'it\'{e}rations demand\'{e}

\[
\frame{n=129} 
\]

\begin{center}
$\infty \infty \infty \infty \infty \infty \infty \infty \infty \infty
\infty $

\medskip
\end{center}

R\'{e}dig\'{e} par 

\[
\begin{array}{l}
Pierre\;Bron,\;professeur\;de\;Sp\acute{e}ciales\;TSI \\ 
Lyc\acute{e}e\;Chaptal,\;6,\;all\acute{e}e\;Chaptal,\;22000\;StBrieuc \\ 
Tel.\;0296639414 \\ 
Email:106233.3407@COMPUSERVE.COM
\end{array}
\]

\`{a} l'aide de Scientific Workplace

\end{document}
