1
2In this section, we deal with only with the FirstOrderType2R case.
3
4
5  \begin{equation}
6    \begin{array}{l}
7      \label{eq:full-toto1-ter}
8      M x_{k+1} = M x_{k} +h \theta f(x_{k+1},t_{k+1}) +h(1-\theta)f(x_{k},t_{k}) + h r_{k+\gamma} \\[2mm]
9      y_{k+\gamma} =  h(t_{k+\gamma},x_{k+\gamma},\lambda _{k+\gamma}) \\[2mm]
10      r_{k+\gamma} = g(t_{k+\gamma},\lambda_{k+\gamma})\\[2mm]
11    \end{array}
12\end{equation}
13
14 \paragraph{Newton's linearization of the first line of~(\ref{eq:full-toto1-ter})} The first line of the  problem~(\ref{eq:full-toto1-ter}) can be written under the form of a residue $\mathcal R$ depending only on $x_{k+1}$ and $r_{k+\gamma}$ such that
15\begin{equation}
16  \label{eq:full-NL3}
17  \mathcal R (x_{k+1},r _{k+\gamma}) =0
18\end{equation}
19with $$\mathcal R(x,r) = M(x - x_{k}) -h\theta f( x , t_{k+1}) - h(1-\theta)f(x_k,t_k) - h r. $$
20The solution of this system of nonlinear equations is sought as a limit of the sequence $\{ x^{\alpha}_{k+1},r^{\alpha}_{k+\gamma} \}_{\alpha \in \NN}$ such that
21 \begin{equation}
22   \label{eq:full-NL7}
23   \begin{cases}
24     x^{0}_{k+1} = x_k \\ \\
25     r^{0}_{k+\gamma} = (1-\gamma ) r_{k} + \gamma r^0_{k+1}  = r_k \\ \\
26     \mathcal R_L( x^{\alpha+1}_{k+1},r^{\alpha+1}_{k+\gamma}) = \mathcal
27     R(x^{\alpha}_{k+1},r^{\alpha}_{k+\gamma})  + \left[ \nabla_{x} \mathcal
28     R(x^{\alpha}_{k+1},r^{\alpha}_{k+\gamma})\right] (x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1} ) + \\[2mm]
29     \qquad\qquad\qquad\qquad\qquad\qquad\left[ \nabla_{r} \mathcal R(x^{\alpha}_{k+1},r^{\alpha}_{k+\gamma})\right] (r^{\alpha+1}_{k+\gamma} - r^{\alpha}_{k+\gamma} ) =0
30 \end{cases}
31\end{equation}
32\begin{ndrva}
33  What about $r^0_{k+\gamma}$ ?
34\end{ndrva}
35
36The residu free is also defined (useful for implementation only):
37\[\mathcal R _{\free}(x) \stackrel{\Delta}{=}  M(x - x_{k}) -h\theta f( x , t_{k+1}) - h(1-\theta)f(x_k,t_k).\]
38We get
39\begin{equation}
40  \mathcal R (x^{\alpha}_{k+1},r^{\alpha}_{k+\gamma}) = \fbox{$\mathcal R^{\alpha}_{k+1} \stackrel{\Delta}{=}  \mathcal R_{\free}(x^{\alpha}_{k+1} )  - h r^{\alpha}_{k+\gamma}$}\label{eq:full-rfree-1}
41\end{equation}
42
43\[  \mathcal R
44_{\free}(x^{\alpha}_{k+1} )=\fbox{$ \mathcal R _{\free, k+1} ^{\alpha} \stackrel{\Delta}{=}  M(x^{\alpha}_{k+1} - x_{k}) -h\theta f( x^{\alpha}_{k+1} , t_{k+1}) - h(1-\theta)f(x_k,t_k)$}\]
45
46The computation of the Jacobian of $\mathcal R$ with respect to $x$, denoted by $   W^{\alpha}_{k+1}$ leads to
47\begin{equation}
48   \label{eq:full-NL9}
49   \begin{array}{l}
50    W^{\alpha}_{k+1} \stackrel{\Delta}{=} \nabla_{x} \mathcal R (x^{\alpha}_{k+1})= M - h  \theta \nabla_{x} f(  x^{\alpha}_{k+1}, t_{k+1} ).\\
51 \end{array}
52\end{equation}
53At each time--step, we have to solve the following linearized problem,
54\begin{equation}
55   \label{eq:full-NL10}
56    \mathcal R^{\alpha}_{k+1} + W^{\alpha}_{k+1} (x^{\alpha+1}_{k+1} -
57    x^{\alpha}_{k+1}) - h  (r^{\alpha+1}_{k+\gamma} - r^{\alpha}_{k+\gamma} )  =0 ,
58\end{equation}
59By using (\ref{eq:full-rfree-1}), we get
60\begin{equation}
61  \label{eq:full-rfree-2}
62  \mathcal R _{\free}(x^{\alpha}_{k+1})  - h  r^{\alpha+1}_{k+\gamma}   + W^{\alpha}_{k+1} (x^{\alpha+1}_{k+1} -
63    x^{\alpha}_{k+1})  =0
64\end{equation}
65
66%\fbox
67{
68  \begin{equation}
69    \boxed{ x^{\alpha+1}_{k+1} = h(W^{\alpha}_{k+1})^{-1}r^{\alpha+1}_{\gamma+1} +x^\alpha_{\free}}
70  \end{equation}
71}
72with :
73\begin{equation}
74  \boxed{x^\alpha_{\free}\stackrel{\Delta}{=}x^{\alpha}_{k+1}-(W^{\alpha}_{k+1})^{-1}\mathcal R_{\free,k+1}^{\alpha} \label{eq:full-rfree-12}}
75\end{equation}
76
77The matrix $W$ is clearly non singular for small $h$.
78
79Note that the linearization is equivalent to the case (\ref{eq:rfree-2}) and (\ref{eq:rfree-12}) with $\gamma=1$ and replacing $r_{k+1}$ by $r_{k+\gamma}$.
80
81 \paragraph{Newton's linearization of the second  line of~(\ref{eq:full-toto1-ter})}
82The same operation is performed with the second equation of (\ref{eq:full-toto1-ter})
83\begin{equation}
84  \begin{array}{l}
85    \mathcal R_y(x,y,\lambda)=y-h(t_{k+\gamma},\gamma x + (1-\gamma) x_k ,\lambda) =0\\ \\
86  \end{array}
87\end{equation}
88which is linearized as
89\begin{equation}
90  \label{eq:full-NL9}
91  \begin{array}{l}
92    \mathcal R_{Ly}(x^{\alpha+1}_{k+1},y^{\alpha+1}_{k+\gamma},\lambda^{\alpha+1}_{k+\gamma}) = \mathcal
93    R_{y}(x^{\alpha}_{k+1},y^{\alpha}_{k+\gamma},\lambda^{\alpha}_{k+\gamma}) +
94    (y^{\alpha+1}_{k+\gamma}-y^{\alpha}_{k+\gamma})- \\[2mm] \qquad  \qquad \qquad \qquad  \qquad \qquad
95    \gamma C^{\alpha}_{k+1}(x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1}) - D^{\alpha}_{k+\gamma}(\lambda^{\alpha+1}_{k+\gamma}-\lambda^{\alpha}_{k+\gamma})=0
96  \end{array}
97\end{equation}
98
99This leads to the following linear equation
100\begin{equation}
101  \boxed{y^{\alpha+1}_{k+\gamma} =  y^{\alpha}_{k+\gamma}
102  -\mathcal R^{\alpha}_{y,k+1}+ \\
103  \gamma C^{\alpha}_{k+1}(x^{\alpha+1}_{k+1}-x^{\alpha}_{k+1}) +
104  D^{\alpha}_{k+\gamma}(\lambda^{\alpha+1}_{k+\gamma}-\lambda^{\alpha}_{k+\gamma})}. \label{eq:full-NL11y}
105\end{equation}
106with,
107\begin{equation}
108     \begin{array}{l}
109  C^{\alpha}_{k+\gamma} = \nabla_xh(t_{k+1}, x^{\alpha}_{k+\gamma},\lambda^{\alpha}_{k+\gamma} ) \\ \\
110  D^{\alpha}_{k+\gamma} = \nabla_{\lambda}h(t_{k+1}, x^{\alpha}_{k+\gamma},\lambda^{\alpha}_{k+\gamma})
111 \end{array}
112\end{equation}
113and
114\begin{equation}\fbox{$
115\mathcal R^{\alpha}_{yk+1} \stackrel{\Delta}{=} y^{\alpha}_{k+\gamma} - h(x^{\alpha}_{k+\gamma},\lambda^{\alpha}_{k+\gamma})$}
116 \end{equation}
117
118Note that the linearization is equivalent to the case (\ref{eq:NL11y}) by replacing $\lambda_{k+1}$ by $\lambda_{k+\gamma}$ and $x_{k+1}$ by $x_{k+\gamma}$.
119
120 \paragraph{Newton's linearization of the third  line of~(\ref{eq:full-toto1-ter})}
121The same operation is performed with the third equation of (\ref{eq:full-toto1-ter})
122\begin{equation}
123  \begin{array}{l}
124    \mathcal R_r(r,\lambda)=r-g(\lambda,t_{k+1}) =0\\ \\  \end{array}
125\end{equation}
126which is linearized as
127\begin{equation}
128  \label{eq:full-NL9}
129  \begin{array}{l}
130      \mathcal R_{L\lambda}(r^{\alpha+1}_{k+\gamma},\lambda^{\alpha+1}_{k+\gamma}) = \mathcal
131      R_{r,k+\gamma}^{\alpha} + (r^{\alpha+1}_{k+\gamma} - r^{\alpha}_{k+\gamma}) - B^{\alpha}_{k+\gamma}(\lambda^{\alpha+1}_{k+\gamma} -
132      \lambda^{\alpha}_{k+\gamma})=0
133    \end{array}
134  \end{equation}
135\begin{equation}
136  \label{eq:full-rrL}
137  \begin{array}{l}
138    \boxed{r^{\alpha+1}_{k+\gamma} = g(\lambda ^{\alpha}_{k+\gamma},t_{k+\gamma}) -B^{\alpha}_{k+\gamma}
139      \lambda^{\alpha}_{k+\gamma} + B^{\alpha}_{k+\gamma} \lambda^{\alpha+1}_{k+\gamma}}
140  \end{array}
141\end{equation}
142with,
143\begin{equation}
144     \begin{array}{l}
145  B^{\alpha}_{k+\gamma} = \nabla_{\lambda}g(\lambda ^{\alpha}_{k+\gamma},t_{k+\gamma})
146 \end{array}
147\end{equation}
148and the  residue for $r$:
149\begin{equation}
150\boxed{\mathcal
151      R_{rk+\gamma}^{\alpha} = r^{\alpha}_{k+\gamma} - g(\lambda ^{\alpha}_{k+\gamma},t_{k+\gamma})}
152  \end{equation}
153Note that the linearization is equivalent to the case (\ref{eq:rrL}) by replacing $\lambda_{k+1}$ by $\lambda_{k+\gamma}$ and $x_{k+1}$ by $x_{k+\gamma}$.
154
155\paragraph{Reduction to a linear relation between  $x^{\alpha+1}_{k+1}$ and
156$\lambda^{\alpha+1}_{k+\gamma}$}
157
158Inserting (\ref{eq:full-rrL}) into~(\ref{eq:full-rfree-12}), we get the following linear relation between $x^{\alpha+1}_{k+1}$ and
159$\lambda^{\alpha+1}_{k+1}$,
160
161\begin{equation}
162   \begin{array}{l}
163     x^{\alpha+1}_{k+1} = h(W^{\alpha}_{k+1} )^{-1}\left[g(\lambda^{\alpha}_{k+\gamma},t_{k+\gamma}) +
164    B^{\alpha}_{k+\gamma} (\lambda^{\alpha+1}_{k+\gamma} - \lambda^{\alpha}_{k+\gamma}) \right ] +x^\alpha_{free}
165\end{array}
166\end{equation}
167that is
168\begin{equation}
169  \begin{array}{l}
170\boxed{x^{\alpha+1}_{k+1}=x_p + h (W^{\alpha}_{k+1})^{-1}    B^{\alpha}_{k+\gamma} \lambda^{\alpha+1}_{k+\gamma}}
171   \end{array}
172  \label{eq:full-rfree-13}
173\end{equation}
174with
175\begin{equation}
176  \boxed{x_p \stackrel{\Delta}{=}  h(W^{\alpha}_{k+1} )^{-1}\left[g(\lambda^{\alpha}_{k+\gamma},t_{k+\gamma}) -B^{\alpha}_{k+\gamma} (\lambda^{\alpha}_{k+\gamma}) \right ] +x^\alpha_{free}}
177\end{equation}
178
179
180\paragraph{Reduction to a linear relation between  $y^{\alpha+1}_{k+\gamma}$ and
181$\lambda^{\alpha+1}_{k+\gamma}$}
182
183Inserting (\ref{eq:full-rfree-13}) into (\ref{eq:full-NL11y}), we get the following linear relation between $y^{\alpha+1}_{k+1}$ and $\lambda^{\alpha+1}_{k+1}$,
184\begin{equation}
185   \begin{array}{l}
186 y^{\alpha+1}_{k+1} = y_p + \left[ h \gamma C^{\alpha}_{k+\gamma} ( W^{\alpha}_{k+1})^{-1}  B^{\alpha}_{k+1} + D^{\alpha}_{k+1} \right]\lambda^{\alpha+1}_{k+1}
187   \end{array}
188\end{equation}
189with
190\begin{equation}
191y_p = y^{\alpha}_{k+1} -\mathcal R^{\alpha}_{yk+1} + \gamma C^{\alpha}_{k+1}(x_q) - D^{\alpha}_{k+1} \lambda^{\alpha}_{k+1}
192\end{equation}
193that is
194\begin{equation}\boxed{
195y_p =  h(x^{\alpha}_{k+\gamma},\lambda^{\alpha}_{k+\gamma}) + \gamma C^{\alpha}_{k+1}(x_q) - D^{\alpha}_{k+1} \lambda^{\alpha}_{k+1} }
196\end{equation}
197\textcolor{red}{
198  \begin{equation}
199   \boxed{ x_q=(x_p -x^{\alpha}_{k+1})\label{eq:full-xqq}}
200  \end{equation}
201}
202
203
204\paragraph{The linear case}
205\begin{equation}
206  \begin{array}{lcl}
207    y_p &=&  h(x^{\alpha}_{k+\gamma},\lambda^{\alpha}_{k+\gamma}) + \gamma C^{\alpha}_{k+1}(x_q) - D^{\alpha}_{k+1} \lambda^{\alpha}_{k+1}\\
208        &=&  C^{\alpha}_{k+1} x^{\alpha}_{k+\gamma} + D^{\alpha}_{k+1}\lambda^{\alpha}_{k+\gamma}  + \gamma C^{\alpha}_{k+1}(x_q) - D^{\alpha}_{k+1} \lambda^{\alpha}_{k+1} \\
209        &=& C^{\alpha}_{k+1}  (x^{\alpha}_{k+\gamma} + \gamma x_p - \gamma x^{\alpha}_{k+1} ) \\
210        &=& C^{\alpha}_{k+1}  ((1-\gamma) x_{k} + \gamma x_{free} ) \text {since } x_p =x_{free}
211\end{array}
212\end{equation}
213
214
215
216
217\paragraph{Implementation details}
218
219For the moment (Feb. 2011), we set $x_q=(1-\gamma) x_{k} + \gamma x_{free} $ in the linear case.
220The nonlinear case is not yet implemented since we need to
221change the management of \texttt{ H_alpha} Relation to be able to compute the mid--point values.
222% things that remain to  do
223%
224% \begin{itemize}
225% \item implement the function \texttt{BlockVector  computeg(t,lambda)} and \texttt{SimpleVector computeh(t,x,lambda)} which takes into account the values of the argument and return and vector
226% \item remove temporary computation in Relation of {\verb Xq, \verb g_alpha and \verb H_alpha }. This should be stored somewhere else. (in the  node of the graph)
227% \end{itemize}
228
229
230
231
232
233
234
235
236\clearpage
237
238
239%%% Local Variables:
240%%% mode: latex
241%%% TeX-master: "DevNotes"
242%%% End:
243