# SMS – Implicit Euler

Differential equation

$\displaystyle \ddot{\mathbf{x}} = \mathbf{f}(\mathbf{x}, \dot{\mathbf{x}})$

Reformulated differential equation (now 1st order)

$\displaystyle \left(\begin{array}{c}\dot{\mathbf{x}}\\ \dot{\mathbf{v}} \end{array}\right) = \left(\begin{array}{c}\mathbf{v}\\ \mathbf{f}(\mathbf{x}, \mathbf{v}) \end{array}\right)$

Explicit Euler

$\displaystyle \left(\begin{array}{c}\Delta\mathbf{x}\\ \Delta\mathbf{v} \end{array}\right) = h\left(\begin{array}{c}\mathbf{v}_0\\ \mathbf{f}(\mathbf{x}_0, \mathbf{v}_0) \end{array}\right) = h\left(\begin{array}{c}\mathbf{v}_0\\ \mathbf{f}_0 \end{array}\right)$

Implicit Euler

$\displaystyle \left(\begin{array}{c}\Delta\mathbf{x}\\ \Delta\mathbf{v} \end{array}\right) = h\left(\begin{array}{c}\mathbf{v}_0 + \Delta\mathbf{v}\\ \mathbf{f}(\mathbf{x}_0 + \Delta\mathbf{x}, \mathbf{v}_0 + \Delta\mathbf{v}) \end{array}\right)$

The only problematic equation

$\displaystyle \Delta\mathbf{v} = h\,\mathbf{f}(\mathbf{x}_0 + h(\mathbf{v}_0 + \Delta\mathbf{v}), \mathbf{v}_0 + \Delta\mathbf{v})$

First order expansion of $\mathbf{f}$ around $(\mathbf{x}_0, \mathbf{v}_0)$

$\displaystyle \mathbf{f}(\mathbf{x}_0 + \delta\mathbf{x}, \mathbf{v}_0 + \delta\mathbf{v}) = \mathbf{f}(\mathbf{x}_0, \mathbf{v}_0) + \frac{\partial \mathbf{f}}{\partial \mathbf{x}}\delta\mathbf{x} + \frac{\partial \mathbf{f}}{\partial \mathbf{v}}\delta\mathbf{v}$

(derivatives evaluated at $(\mathbf{x}_0, \mathbf{v}_0)$)

Getting specific with $\mathbf{f}$

$\displaystyle \mathbf{f}_i = \frac{1}{m_i}\sum_{j\neq i}k_{ij}\left(\|\mathbf{x}_j - \mathbf{x}_i\| - l_{ij}\right)\frac{\mathbf{x}_j - \mathbf{x}_i}{\|\mathbf{x}_j - \mathbf{x}_i\|}$

$\displaystyle \mathbf{f}_i = \frac{1}{m_i}\sum_{j\neq i}k_{ij}\left((\mathbf{x}_j - \mathbf{x}_i) - l_{ij} \frac{\mathbf{x}_j - \mathbf{x}_i}{\|\mathbf{x}_j - \mathbf{x}_i\|}\right)$

$\displaystyle \mathbf{f}_i = \frac{1}{m_i}\sum_{j\neq i}k_{ij} (\mathbf{x}_j - \mathbf{x}_i) - \frac{1}{m_i}\sum_{j\neq i}k_{ij} l_{ij} \frac{\mathbf{x}_j - \mathbf{x}_i}{\|\mathbf{x}_j - \mathbf{x}_i\|}$

Deriving against $\mathbf{x}_i$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_i}\left(\frac{1}{m_i}\sum_{j\neq i}k_{ij} (\mathbf{x}_j - \mathbf{x}_i)\right) = \frac{1}{m_i}\sum_{j\neq i}k_{ij} (\mathbf{0} - \mathbf{1}) = -\frac{1}{m_i}\left(\sum_{j\neq i}k_{ij}\right)\mathbf{1}$

$\displaystyle \left(\frac{\partial}{\partial \mathbf{x}}\frac{\mathbf{y}-\mathbf{x}}{\|\mathbf{y}-\mathbf{x}\|}\right)_{ij} = \frac{\partial}{\partial x_i}\frac{y_j-x_j}{\sqrt{\sum_k (y_k-x_k)^2}}$

$\displaystyle \left(\frac{\partial}{\partial \mathbf{x}}\frac{\mathbf{y}-\mathbf{x}}{\|\mathbf{y}-\mathbf{x}\|}\right)_{ij} = \frac{\partial}{\partial x_i}\left[(y_j-x_j)\left(\sum_k (y_k-x_k)^2\right)^{-\frac{1}{2}}\right]$

$\displaystyle \left(\frac{\partial}{\partial \mathbf{x}}\frac{\mathbf{y}-\mathbf{x}}{\|\mathbf{y}-\mathbf{x}\|}\right)_{ij} = -\delta_{ij}\left(\sum_k (y_k-x_k)^2\right)^{-\frac{1}{2}} + (y_j-x_j)\frac{\partial}{\partial x_i}\left(\sum_k (y_k-x_k)^2\right)^{-\frac{1}{2}}$

$\displaystyle \frac{\partial}{\partial x_i}\left(\sum_k (y_k-x_k)^2\right)^{-\frac{1}{2}} = -\frac{1}{2}\left(\sum_k (y_k-x_k)^2\right)^{-\frac{3}{2}}2\,(y_i-x_i)\,(-1)$

$\displaystyle \frac{\partial}{\partial x_i}\left(\sum_k (y_k-x_k)^2\right)^{-\frac{1}{2}} = \left(\sum_k (y_k-x_k)^2\right)^{-\frac{3}{2}}(y_i-x_i)$

$\displaystyle \frac{\partial}{\partial \mathbf{x}}\frac{\mathbf{y}-\mathbf{x}}{\|\mathbf{y}-\mathbf{x}\|} = -\frac{1}{\|\mathbf{y}-\mathbf{x}\|}\mathbf{1} + \frac{1}{\|\mathbf{y}-\mathbf{x}\|^3}(\mathbf{y}-\mathbf{x})(\mathbf{y}-\mathbf{x})^{\rm T}$

$\displaystyle \frac{\partial}{\partial \mathbf{x}}\frac{\mathbf{y}-\mathbf{x}}{\|\mathbf{y}-\mathbf{x}\|} = \frac{1}{\|\mathbf{y}-\mathbf{x}\|}\left(\mathbf{P_{y-x}} - \mathbf{1}\right)$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_i}\left(\frac{1}{m_i}\sum_{j\neq i}k_{ij} l_{ij} \frac{\mathbf{x}_j - \mathbf{x}_i}{\|\mathbf{x}_j - \mathbf{x}_i\|}\right) = \frac{1}{m_i}\sum_{j\neq i}\frac{k_{ij} l_{ij}}{\|\mathbf{x}_j-\mathbf{x}_i\|}\left(\mathbf{P}_{\mathbf{x}_j-\mathbf{x}_i} - \mathbf{1}\right)$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_i}\mathbf{f}_i = -\frac{1}{m_i}\left(\sum_{j\neq i}k_{ij}\right)\mathbf{1} - \frac{1}{m_i}\sum_{j\neq i}\frac{k_{ij} l_{ij}}{\|\mathbf{x}_j-\mathbf{x}_i\|}\left(\mathbf{P}_{\mathbf{x}_j-\mathbf{x}_i} - \mathbf{1}\right)$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_i}\mathbf{f}_i = \frac{1}{m_i}\left[\sum_{j\neq i}\frac{k_{ij} l_{ij}}{\|\mathbf{x}_j-\mathbf{x}_i\|}\left(\mathbf{1} - \mathbf{P}_{\mathbf{x}_j-\mathbf{x}_i}\right) - \left(\sum_{j\neq i}k_{ij}\right)\mathbf{1}\right]$

Deriving against $\mathbf{x}_k$ ($k \neq i$)

$\displaystyle \frac{\partial}{\partial \mathbf{x}_k}\left(\frac{1}{m_i}\sum_{j\neq i}k_{ij} (\mathbf{x}_j - \mathbf{x}_i)\right) = \frac{1}{m_i}\sum_{j\neq i}k_{ij} (\delta_{kj}\mathbf{1} - \delta_{ki}\mathbf{1}) = \frac{k_{ik}}{m_i} \mathbf{1}$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_k}\left(\frac{1}{m_i}\sum_{j\neq i}k_{ij} l_{ij} \frac{\mathbf{x}_j - \mathbf{x}_i}{\|\mathbf{x}_j - \mathbf{x}_i\|}\right) = \frac{1}{m_i}\sum_{j\neq i}\delta_{kj}\frac{k_{ij} l_{ij}}{\|\mathbf{x}_j-\mathbf{x}_i\|}\left(\mathbf{1}-\mathbf{P}_{\mathbf{x}_j-\mathbf{x}_i}\right)$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_k}\left(\frac{1}{m_i}\sum_{j\neq i}k_{ij} l_{ij} \frac{\mathbf{x}_j - \mathbf{x}_i}{\|\mathbf{x}_j - \mathbf{x}_i\|}\right) = \frac{1}{m_i}\frac{k_{ik} l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\left(\mathbf{1}-\mathbf{P}_{\mathbf{x}_k-\mathbf{x}_i}\right)$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_k}\mathbf{f}_i = \frac{k_{ik}}{m_i} \mathbf{1} - \frac{1}{m_i}\frac{k_{ik} l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\left(\mathbf{1}-\mathbf{P}_{\mathbf{x}_k-\mathbf{x}_i}\right)$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_k}\mathbf{f}_i = \frac{1}{m_i} \left(k_{ik} - \frac{k_{ik} l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\right) \mathbf{1}- \frac{1}{m_i}\frac{k_{ik} l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\mathbf{P}_{\mathbf{x}_k-\mathbf{x}_i}$

$\displaystyle \frac{\partial}{\partial \mathbf{x}_k}\mathbf{f}_i = \frac{k_{ik}}{m_i} \left[\left(1 - \frac{l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\right) \mathbf{1} - \frac{l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\mathbf{P}_{\mathbf{x}_k-\mathbf{x}_i}\right]$

First order expansion of the SMS $\mathbf{f}$

$\displaystyle \mathbf{f}(\mathbf{x}_0 + \delta\mathbf{x}, \mathbf{v}_0 + \delta\mathbf{v}) = \mathbf{f}(\mathbf{x}_0, \mathbf{v}_0) + \mathbf{M}\delta\mathbf{x}$

$\displaystyle \mathbf{M}_{ii} = \frac{1}{m_i}\left[\sum_{j\neq i}\frac{k_{ij} l_{ij}}{\|\mathbf{x}_j-\mathbf{x}_i\|}\left(\mathbf{1} - \mathbf{P}_{\mathbf{x}_j-\mathbf{x}_i}\right) - \left(\sum_{j\neq i}k_{ij}\right)\mathbf{1}\right]$

$\displaystyle \mathbf{M}_{ik} = \frac{k_{ik}}{m_i} \left[\left(1 - \frac{l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\right) \mathbf{1} - \frac{l_{ik}}{\|\mathbf{x}_k-\mathbf{x}_i\|}\mathbf{P}_{\mathbf{x}_k-\mathbf{x}_i}\right]$