関数backward_substitution マニュアル

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


◆機能・用途(Purpose)

上三角行列\(\myvector{U}\)と列ベクトル\(\myvector{b}\)で表される連立方程式 \(\myvector{U}\myvector{x}=\myvector{b}\)を後退代入で解く。
Solve a simultaneous equation \(\myvector{U}\myvector{x}=\myvector{b}\) by a backward substitution, where \(\myvector{U}\) is an upper triangular matrix and \(\myvector{b}\) is a column vector.

◆形式(Format)

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


◆引数(Arguments)

U 連立方程式の係数を表す上三角行列\(\myvector{U}\)。 正方行列であることのチェックは行われるが、 上三角行列であることのチェックは行われないので注意すること。
An upper triangular matrix \(\myvector{U}\) 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 an upper triangular matrix.
b 連立方程式の右辺を表す列ベクトル\(\myvector{b}\)。
A column vector \(\myvector{b}\) which represents the right hand side of the simultaneous equation.


◆戻り値(Return value)

連立方程式\(\myvector{U}\myvector{x}=\myvector{b}\)の解\(\myvector{x}\)。 下記の(\ref{eq.solution})式を用いて計算した\(x_i\)を並べた列ベクトルを返す。 いずれかの\(i\)について\(u_{ii}=0\)となる場合はエラー終了する。
The solution \(\myvector{x}\) of the simultaneous equation \(\myvector{U}\myvector{x}=\myvector{b}\), which is a columnvector composed of \(x_i\) calculated with eq. (\ref{eq.solution}) below. If \(u_{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{U}= \begin{pmatrix} u_{11} & \cdots & \cdots & u_{1N} \\ 0 & \ddots & & \vdots \\ \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & u_{NN} \end{pmatrix} \label{eq.U} \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{U}\myvector{x}=\myvector{b} \label{eq.simultaneous_equation} \end{equation}\] が成り立つとする。(\ref{eq.simultaneous_equation})式を成分で表すと \[\begin{equation} \sum_{j=i}^{N} u_{ij} x_j = b_i \label{eq.simultaneous_equation.components} \end{equation}\] と書ける。これを \[\begin{equation} u_{ii} x_i + \sum_{j=i+1}^N u_{ij} x_j = b_i \label{eq.solve} \end{equation}\] と変形して\(x_i\)について解けば \[\begin{equation} x_i = \frac{1}{u_{ii}} \left( b_i - \sum_{j=i+1}^{N} u_{ij} x_j \right) \label{eq.solution} \end{equation}\] が得られる。(\ref{eq.solution})式を\(i=N,\cdots,1\)に順々に適用していけば \(\myvector{x}\)が得られる。 (\ref{eq.solution})式の右辺が既知の量のみから構成されるためには 大きな\(i\)から順に(\(i=N,\cdots,1\)の順に) 計算していかなければならない点に注意。
Let a simultaneous equation (\ref{eq.simultaneous_equation}) holds between an \(N\times N\) upper triangular matrix \(\myvector{U}\) (eq. \ref{eq.U}), 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=N\) to \(i=1\) in a descending order gives the solution \(\myvector{x}\). Note that the calculation must be performed in a descending order to make sure that the right hand side of eq. (\ref{eq.solution}) is composed of known quantities.