関数forward_substitution マニュアル

(The documentation of function forward_substitution)
Last Update: 2021/12/6


◆機能・用途(Purpose)

下三角行列\(\myvector{L}\)と列ベクトル\(\myvector{b}\)で表される連立方程式 \(\myvector{L}\myvector{x}=\myvector{b}\)を前進代入で解く。
Solve a simultaneous equation \(\myvector{L}\myvector{x}=\myvector{b}\) by a forward substitution, where \(\myvector{L}\) is a lower triangular matrix and \(\myvector{b}\) is a column vector.

◆形式(Format)

#include <matrix/inverse.h>
inline struct columnvector forward_substitution
(const struct matrix L,const struct columnvector b)


◆引数(Arguments)

L 連立方程式の係数を表す下三角行列\(\myvector{L}\)。 正方行列であることのチェックは行われるが、 下三角行列であることのチェックは行われないので注意すること。
A lower triangular matrix \(\myvector{L}\) which represents the coefficients of the simultaneous equation. Note that only a check whether the matrix is square is implemented, without checking that the matrix is really a lower triangular matrix.
b 連立方程式の右辺を表す列ベクトル\(\myvector{b}\)。
A column vector \(\myvector{b}\) which represents the right hand side of the simultaneous equation.


◆戻り値(Return value)

連立方程式\(\myvector{L}\myvector{x}=\myvector{b}\)の解\(\myvector{x}\)。 下記の(\ref{eq.solution})式を用いて計算した\(x_i\)を並べた列ベクトルを返す。 いずれかの\(i\)について\(l_{ii}=0\)となる場合はエラー終了する。
The solution \(\myvector{x}\) of the simultaneous equation \(\myvector{L}\myvector{x}=\myvector{b}\), which is a columnvector composed of \(x_i\) calculated with eq. (\ref{eq.solution}) below. If \(l_{ii}=0\) for either \(i\), the program finishes as an error.

◆使用例(Example)

struct matrix A;
struct columnvector b;
struct LU decomposed=LU_decomposition(A);
struct columnvector bb=columnvector_swap_by_pivot(b,decomposed.pivot);
struct columnvector tmp=forward_substitution(decomposed.L,bb);
 struct columnvector solution=backward_substitution(decomposed.U,tmp);


◆計算式(Formula)

\(N \times N\)の下三角行列 \[\begin{equation} \myvector{L}= \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ \vdots & \ddots & \ddots & \vdots \\ \vdots & & \ddots & 0 \\ l_{N1} & \cdots & \cdots & l_{NN} \end{pmatrix} \label{eq.L} \end{equation}\] 、\(N\)次元の既知の列ベクトル \[\begin{equation} \myvector{b}= \begin{pmatrix} b_1 \\ \vdots \\ b_N \end{pmatrix} \label{eq.b} \end{equation}\] 、\(N\)次元の未知の列ベクトル \[\begin{equation} \myvector{x}= \begin{pmatrix} x_1 \\ \vdots \\ x_N \end{pmatrix} \label{eq.x} \end{equation}\] の間に連立方程式 \[\begin{equation} \myvector{L}\myvector{x}=\myvector{b} \label{eq.simultaneous_equation} \end{equation}\] が成り立つとする。(\ref{eq.simultaneous_equation})式を成分で表すと \[\begin{equation} \sum_{j=1}^{i} l_{ij} x_j = b_i \label{eq.simultaneous_equation.components} \end{equation}\] と書ける。これを \[\begin{equation} \sum_{j=1}^{i-1} l_{ij} x_j + l_{ii} x_i = b_i \label{eq.solve} \end{equation}\] と変形して\(x_i\)について解けば \[\begin{equation} x_i = \frac{1}{l_{ii}} \left( b_i - \sum_{j=1}^{i-1} l_{ij} x_j \right) \label{eq.solution} \end{equation}\] が得られる。(\ref{eq.solution})式を\(i=1,\cdots,N\)に順々に適用していけば \(\myvector{x}\)が求まる。
Let a simultaneous equation (\ref{eq.simultaneous_equation}) holds between an \(N\times N\) lower triangular matrix \(\myvector{L}\) (eq. \ref{eq.L}), an \(N\)-dimension known vector \(\myvector{b}\) (eq. \ref{eq.b}), and an \(N\)-dimension unknown vector \(\myvector{x}\) (eq. \ref{eq.x}). Eq. (\ref{eq.simultaneous_equation}) can be rewritten by components as (\ref{eq.simultaneous_equation.components}), which can further be arranged as (\ref{eq.solve}). The solution for \(x_i\) is thus (\ref{eq.solution}). Applying eq. (\ref{eq.solution}) from \(i=1\) to \(i=N\) in an ascending order gives the solution \(\myvector{x}\).