4. Principle of « double Lagrange »#

The method proposed here is the one implemented in code CASTEM 2000 (personal communication from Th. CHARRAS and P. VERPEAUX). An intuitive layout could be as follows:

We can see that the dualized problem [éq 2-4] has zero terms on the diagonal: those corresponding to Lagrange’s degrees of freedom. This property is also noticeable on the Lagrangian [éq 2-5]: there are no quadratic terms in \(\lambda\).

This nullity of diagonal terms prevents certain permutations of rows and columns: you cannot place a Lagrange before the physical degrees of freedom that it constrains.

The idea is then to break down each Lagrange coefficient \(\lambda\) into 2 equal parts \({\lambda }^{1}\) and \({\lambda }^{2}\). Equation \(\mathrm{Cu}=d\) is then replaced by:

\(\begin{array}{}\mathrm{Cu}-\alpha ({\lambda }^{1}-{\lambda }^{2})=d\\ \mathrm{Cu}+\alpha ({\lambda }^{1}-{\lambda }^{2})=d\end{array}\)

where \(\alpha\) is a nonzero constant.

Let’s show the equivalence of the old problem and the new one:

Problem 1: « simple Lagrange »

find \(\mathrm{\{}\begin{array}{c}\mathrm{u}\mathrm{\in }{\mathrm{ℝ}}^{n}\\ \lambda \mathrm{\in }{\mathrm{ℝ}}^{p}\end{array}\) such as \((S)\text{:}\mathrm{\{}\begin{array}{c}\text{Au}+{\mathrm{C}}^{\mathrm{T}}\lambda \mathrm{=}\mathrm{b}\\ \text{Cu}\mathrm{=}\mathrm{d}\end{array}\)

\((S)\iff \{\begin{array}{}{\lambda }^{1}={\lambda }^{2}\\ \lambda ={\lambda }^{1}+{\lambda }^{2}\\ \text{Au}+{C}^{T}\lambda =b\\ \text{Cu}=d\end{array}\iff \{\begin{array}{}\text{Au}+{C}^{T}{\lambda }^{1}+{C}^{T}{\lambda }^{2}=b\\ \text{Cu}-{\text{αλ}}^{1}+{\text{αλ}}^{2}=d\\ \text{Cu}+{\text{αλ}}^{1}-{\text{αλ}}^{2}=d\end{array}\)

\(\alpha\) is a \(\mathrm{\ne }0\) constant

Hence the problem equivalent to the previous one:

Problem 2: « double Lagrange »

find \(\mathrm{\{}\begin{array}{c}\mathrm{u}\mathrm{\in }{\mathrm{ℝ}}^{n}\\ {\lambda }^{1},{\lambda }^{2}\mathrm{\in }{\mathrm{ℝ}}^{p}\mathrm{\times }{\mathrm{ℝ}}^{p}\end{array}\) such as \((\text{S'})\text{:}\mathrm{\{}\begin{array}{c}\text{Au}+{\mathrm{C}}^{\mathrm{T}}{\lambda }^{1}+{\mathrm{C}}^{\mathrm{T}}{\lambda }^{2}\mathrm{=}\mathrm{b}\\ \text{Cu}\mathrm{-}{\text{αλ}}^{1}+{\text{αλ}}^{2}\mathrm{=}\mathrm{d}\\ \text{Cu}+{\text{αλ}}^{1}\mathrm{-}{\text{αλ}}^{2}\mathrm{=}\mathrm{d}\end{array}\)

The new problem can be written as:

\(\text{K'}\text{X'}=\text{F'}\)

with:

\(\{\begin{array}{}X\text{'}=(u,{\lambda }_{1},{\lambda }_{2})\\ \text{F'}=(\text{b,}\text{d,}d)\end{array}\)

\(\text{K'}=\left[\begin{array}{ccc}A& {C}^{T}& {C}^{T}\\ C& -\mathrm{\alpha l}& \mathrm{\alpha l}\\ C& \mathrm{\alpha l}& -\mathrm{\alpha l}\end{array}\right]\)

The problem corresponds to making the functional extreme:

\(\begin{array}{}L\text{'}(u,{\lambda }^{1},{\lambda }^{2})=\frac{1}{2}(\text{Au,}u)-(\text{b,}u)+({\lambda }^{1},\text{Cu}-d)\\ +({\lambda }^{2},\text{Cu}-d)-\frac{\alpha }{2}({\lambda }^{1}-{\lambda }^{2},{\lambda }^{1}-{\lambda }^{2})\end{array}\)

It can be shown (see Appendix 2) that if a certain rule for numbering unknowns is observed, and by choosing the constant \(\alpha >0\), the matrix \(\text{K'}\) verifies the condition cond1.

This rule is as follows:

For a blocking relationship \(\text{Cu}-d=0\), it corresponds to 2 Lagrange multipliers \({\lambda }^{1}\) and \({\lambda }^{2}\). This relationship involves a number of physical degrees of freedom.

Rule \({R}_{0}\):

For each blocking relationship, \({\lambda }^{1}\) should be placed before the first degree of constrained physical freedom and \({\lambda }^{2}\) after the last degree of constrained physical freedom.

To reduce the memory occupancy of the matrix \(K\), it is necessary to try to minimize the width of the band. This is what we do in Code_Aster by « framing » relationships « as closely as possible »: \({\lambda }^{1}\) is placed just before the first constrained degree of freedom, \({\lambda }^{2}\) is placed just after the last constrained ddl.

Illustration:

That’s a problem with 4 physical degrees of freedom: \({u}_{1}{\text{,u}}_{2}{\text{,u}}_{3}{\text{,u}}_{4}\).

This system is subject to 2 conditions:

\(\{\begin{array}{}{a}_{\text{11}}{u}_{1}+{a}_{\text{13}}{u}_{3}={b}_{1}\\ {a}_{\text{22}}{u}_{2}+{a}_{\text{24}}{u}_{4}={b}_{2}\end{array}\)

Let’s call \({\lambda }_{1}^{1},{\lambda }_{1}^{2}\) the 2 Lagrange degrees of freedom associated with the 1st condition and \({\lambda }_{2}^{1},{\lambda }_{2}^{2}\) those associated with the 2nd condition.

Assuming that the physical degrees of freedom have been numbered in the order: \({u}_{1}{\text{,u}}_{2}{\text{,u}}_{3}{\text{,u}}_{4}\), the total numbering of the degrees of freedom retained by*Aster* is then:

\({\lambda }_{1}^{1}\text{,}{u}_{1}\text{,}{\lambda }_{2}^{1}\text{,}{u}_{\mathrm{2,}}{u}_{\mathrm{3,}}{\lambda }_{1}^{2}\text{,}{u}_{4},{\lambda }_{2}^{2}\)

\({\lambda }_{1}^{1}\) and \({\lambda }_{1}^{2}\) frame the constrained degrees of freedom « as closely as possible » (\({u}_{1}\) and \({u}_{3}\))

\({\lambda }_{2}^{1}\) and \({\lambda }_{1}^{2}\) frame the constrained degrees of freedom « as closely as possible » (\({u}_{2}\) and \({u}_{4}\))

The « double Lagrange » technique associated with rule \({R}_{0}\) therefore makes it possible to solve any physically well-posed linear system with the \({\mathit{LDL}}^{T}\) algorithm without permutation. However, the demonstration assumes that the matrix \(A\) is symmetric and positive (not necessarily defined).

Note:

The assumptions: \(A\) symmetric and \(A\) positive are required to use \({\mathit{LDL}}^{T}\) (or \(\mathit{LU}\) ) without permutation as shown by the following two counterexamples:

\({A}_{1}=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\) is symmetric but not positive,
\({A}_{2}=\left[\begin{array}{cc}0& 1\\ -1& 1\end{array}\right]\) is positive but not symmetric.