multiphysicsL4.tex

%
% Copyright © 2014 Peeter Joot.  All Rights Reserved.
% Licenced as described in the file LICENSE under the root directory of this GIT repository.
%
%\input{../blogpost.tex}
%\renewcommand{\basename}{multiphysicsL4}
%\renewcommand{\dirname}{notes/ece1254/}
%\newcommand{\keywords}{ECE1254H}
%\input{../peeter_prologue_print2.tex}
%
%\usepackage{kbordermatrix}
%
%\beginArtNoToc
%\generatetitle{ECE1254H Modeling of Multiphysics Systems.  Lecture 4: Modified nodal analysis.  Taught by Prof.\ Piero Triverio}
%%\subsection{Modified nodal analysis}
\index{modified nodal analysis}
%\label{chap:multiphysicsL4}
%
%\subsection{Disclaimer}
%
%Peeter's lecture notes from class.  These may be incoherent and rough.
%\chapter{Solving large systems}
%
The goal is to solve \textAndIndex{linear systems} of the form
%
\begin{equation}\label{eqn:multiphysicsL4:60}
   M \Bx = \Bb,
\end{equation}
%
possibly with thousands of elements.
%
\sectionAndIndex{Gaussian elimination.}
%
\begin{equation}\label{eqn:multiphysicsL4:80}
   \kbordermatrix{
        & 1      & 2      & 3      \\
      1 & M_{11} & M_{12} & M_{13} \\
      2 & M_{21} & M_{22} & M_{23} \\
      3 & M_{31} & M_{32} & M_{33} \\
   }
\begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
\end{bmatrix}
=
\begin{bmatrix}
   b_1 \\
   b_2 \\
   b_3 \\
\end{bmatrix}
\end{equation}
%
It's claimed for now, to be seen later, that back substitution is the fastest way to arrive at the solution, less computationally complex than completion the diagonalization.
%
Steps
%
\begin{equation}\label{eqn:multiphysicsL4:100}
   (1) \cdot \frac{M_{21}}{M_{11}} \implies
\begin{bmatrix}
      M_{21} &  \frac{M_{21}}{M_{11}}  M_{12} &  \frac{M_{21}}{M_{11}}  M_{13} \\
\end{bmatrix}
\end{equation}
%
\begin{equation}\label{eqn:multiphysicsL4:120}
   (2) \cdot \frac{M_{31}}{M_{11}} \implies
\begin{bmatrix}
      M_{31} &  \frac{M_{31}}{M_{11}}  M_{32} &  \frac{M_{31}}{M_{11}}  M_{33} \\
\end{bmatrix}
\end{equation}
%
This gives
%
\begin{equation}\label{eqn:multiphysicsL4:140}
\begin{bmatrix}
%\mathLabelBox
%{
      M_{11}
%}
%{Pivot}
      & M_{12} & M_{13} \\
   0 &  M_{22} - \frac{M_{21}}{
%\mathLabelBox
%{
   M_{11}
%}{Multiplier}
}  M_{12} & M_{23} - \frac{M_{21}}{M_{11}}  M_{13} \\
   0 &  M_{32} - \frac{M_{31}}{M_{11}}  M_{32} & M_{33} - \frac{M_{31}}{M_{11}}  M_{33} \\
\end{bmatrix}
\begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
\end{bmatrix}
=
\begin{bmatrix}
   b_1 \\
   b_2 - \frac{M_{21}}{M_{11}} b_1 \\
   b_3 - \frac{M_{31}}{M_{11}} b_1
\end{bmatrix}.
\end{equation}
%
Here the \(M_{11}\) element is called the \textAndIndex{pivot}.  Each of the \(M_{j1}/M_{11}\) elements is called a \textAndIndex{multiplier}.  This operation can be written as
%
\begin{equation}\label{eqn:multiphysicsL4:160}
\begin{bmatrix}
      M_{11} & M_{12} & M_{13} \\
   0 &  M_{22}^{(2)} & M_{23}^{(3)} \\
   0 &  M_{32}^{(2)} & M_{33}^{(3)} \\
\end{bmatrix}
\begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
\end{bmatrix}
=
\begin{bmatrix}
   b_1 \\
   b_2^{(2)} \\
   b_3^{(2)} \\
\end{bmatrix}.
\end{equation}
%
Using \( M_{22}^{(2)} \) as the pivot this time, form
\begin{equation}\label{eqn:multiphysicsL4:180}
\begin{bmatrix}
      M_{11} & M_{12} & M_{13} \\
   0 &  M_{22}^{(2)} & M_{23}^{(3)} \\
   0 &             0 & M_{33}^{(3)} - \frac{M_{32}^{(2)}}{M_{22}^{(2)}} M_{23}^{(2)} \\
\end{bmatrix}
\begin{bmatrix}
   x_1 \\
   x_2 \\
   x_3 \\
\end{bmatrix}
=
\begin{bmatrix}
   b_1 \\
   b_2 - \frac{M_{21}}{M_{11}} b_1 \\
   b_3 - \frac{M_{31}}{M_{11}} b_1
   - \frac{M_{32}^{(2)}}{M_{22}^{(2)}} b_{2}^{(2)} \\
\end{bmatrix}.
\end{equation}
%
\section{LU decomposition.}
\index{LU decomposition}
%
Through Gaussian elimination, the system has been transformed from
%
\begin{equation}\label{eqn:multiphysicsL4:200}
   M x = b
\end{equation}
%
to
\begin{equation}\label{eqn:multiphysicsL4:220}
   U x = y.
\end{equation}
%
The Gaussian transformation written out in the form \( U \Bx = b \) is
%
\begin{equation}\label{eqn:multiphysicsL4:240}
U \Bx =
\begin{bmatrix}
   1 & 0 & 0 \\
   -\frac{M_{21}}{M_{11}} & 1 & 0 \\
   \frac{M_{32}^{(2)}}{M_{22}^{(2)}}
   \frac{M_{21}}{M_{11}}
-
\frac{M_{31}}{M_{11}}
&
-
\frac{M_{32}^{(2)}}{M_{22}^{(2)}}
& 1
\end{bmatrix}
\begin{bmatrix}
   b_1 \\
   b_2 \\
   b_3
\end{bmatrix}.
\end{equation}
%
As a verification observe that the
operation matrix \( K^{-1} \), where \( K^{-1} U = M \) produces the original system
%
\begin{equation}\label{eqn:multiphysicsL4:260}
\begin{bmatrix}
   1 & 0 & 0 \\
   \frac{M_{21}}{M_{11}} & 1 & 0 \\
   \frac{M_{31}}{M_{11}} &
   \frac{M_{32}^{(2)}}{M_{22}^{(2)}} &
   1
\end{bmatrix}
\begin{bmatrix}
   U_{11} & U_{12} & U_{13} \\
   0      & U_{22} & U_{23} \\
   0      & 0      & U_{33} \\
\end{bmatrix}
\Bx = \Bb
\end{equation}
%
\index{LU decomposition}
Using this LU decomposition is generally superior to standard Gaussian elimination, since it can be used for many different \(\Bb\) vectors, and cost no additional work after the initial factorization.
%
The steps are
%
\begin{equation}\label{eqn:multiphysicsL4:280}
\begin{aligned}
b
&= M x
\\ &= L \lr{ U x}
\equiv L y.
\end{aligned}
\end{equation}
%
The matrix equation \( L y = b \) can now be solved by substituting first  \( y_1 \), then \( y_2 \), and finally \( y_3 \).  This is called \textAndIndex{forward substitution}.
%
The final solution is
%
\begin{equation}\label{eqn:multiphysicsL4:300}
U x = y,
\end{equation}
%
using \textAndIndex{back substitution}.
%
Note that this produced the vector \( y \) as a side effect of performing the Gaussian elimination process.
%
%\index{LU decomposition}
\makeexample{Numeric LU factorization.}{example:multiphysicsL4:1}{
\input{luExample.tex}
}
%
\index{LU decomposition!pivot}
\makeexample{Numeric LU factorization with pivots.}{example:multiphysicsL4:2}{
\input{luExample2.tex}
}
%
\makeexample{LU with pivots.}{example:multiphysicsL4:3}{
\input{luAlgorithm.tex}
}
%
%\EndArticle
%\EndNoBibArticle