Notes on numerical analysis (II): numerical solution of linear equations

direct method

Catch up method

The coefficient matrix is tridiagonal matrix

$$A=\left[\begin{array}{cccccc}{b}_1& c_1& & & & \\ a_2& b_2& c_2& & & \\ & a_3& b_3& c_3& & \\ & & \ddots & \ddots & \ddots & \\ & & & a_{n-1}& b_{n-1}& c_{n-1}\\ & & & & a_n& b_n\end{array}\right]$$

The equations of

$$\{\begin{array}{lr}{b}_1{x}_1+c_1{x}_2=f_1& \\ a_i{x}_{i-1}+b_i{x}_i+c_i{x}_{i+1}=f_i,& i=2,3,4,\cdots ,n-1\\ a_n{x}_{n-1}+b_n{x}_n=f_n& \end{array}$$

, The solution of the catch-up method is divided into two steps ：

• Elimination process

  Process the given tridiagonal equations into unit upper didiagonal equations

  $$\{\begin{array}{lr}{x}_i+u_i{x}_{i+1}=y_i,& i=1,2,3,4,\cdots ,n-1\\ x_n=y_n& \end{array}$$

  , The processing procedure is

  $$\{\begin{array}{lr}{u}_1=\frac{c_1}{b_1},y_1=\frac{f_1}{b_1}& \\ u_i=\frac{c_i}{(b_i-a_i{u}_{i-1})},& i=2,3,4,\cdots ,n-1\\ y_i=\frac{f_i-a_i{y}_{i-1}}{b_i-a_i{u}_{i-1}},& i=2,3,4,\cdots ,n\end{array}$$

• The process of retrogression

  $$\{\begin{array}{lr}{x}_n=y_n& \\ x_i=y_i-u_i{x}_{i+1},& i=1,2,3,4,\cdots ,n-1\end{array}$$

Be careful , Only when tridiagonal matrix satisfies Diagonally dominant when , The meet

$$\{\begin{array}{lr}|b_1|>|c_1|& \\ |b_i|>|a_i|+|c_1|,& i=1,2,3,4,\cdots ,n-1\\ |b_n|>|a_n|& \end{array}$$

The catch-up process will not be interrupted .

Tridiagonal matrix $LU$ decompose

Is there any method that can directly start from the coefficient matrix of tridiagonal equations Direct processing How to find out the system of didiagonal equations on the unit ？ We consider the matrix $LU$ decompose .

$$\left[\begin{array}{cccccc}{b}_1& c_1& & & & \\ a_2& b_2& c_2& & & \\ & a_3& b_3& c_3& & \\ & & \ddots & \ddots & \ddots & \\ & & & a_{n-1}& b_{n-1}& c_{n-1}\\ & & & & a_n& b_n\end{array}\right]=\left[\begin{array}{ccccc}{d}_1& & & & \\ l_2& d_2& & & \\ & l_3& d_3& & \\ & & \ddots & \ddots & \\ & & & l_n& d_n\end{array}\right]\left[\begin{array}{ccccc}1& u_1& & & \\ & 1& u_2& & \\ & & \ddots & \ddots & \\ & & & 1& u_{n-1}\\ & & & & 1\end{array}\right]$$

among
$$L=\left[\begin{array}{ccccc}{d}_1& & & & \\ l_2& d_2& & & \\ & l_3& d_3& & \\ & & \ddots & \ddots & \\ & & & l_n& d_n\end{array}\right],U=\left[\begin{array}{ccccc}1& u_1& & & \\ & 1& u_2& & \\ & & \ddots & \ddots & \\ & & & 1& u_{n-1}\\ & & & & 1\end{array}\right]$$
,
And $l_i=a_i$. It's not hard to find out ,$U$ Matrix is the coefficient matrix of the system of two diagonal equations on the unit we need .

How do we get $U$ Array ？ consider $L$ and $U$ Matrix multiplication of , The equations can be obtained $$\{\begin{array}{lr}{b}_1=d_1& \\ c_i=u_i{d}_i,& i=1,2,3,4,\cdots ,n-1\\ b_{i+1}=u_i{a}_{i+1}+d_{i+1},& \end{array}$$

So we can Line by line Determine the matrix $L$ and $U$ The elements of , Its calculation formula is $$\{\begin{array}{lr}{d}_1=b_1& \\ u_i=\frac{c_i}{d_i},& i=1,2,3,4,\cdots ,n-1\\ d_{i+1}=b_{i+1}-u_i{a}_{i+1},& \end{array}$$

solve $Ax=f$ It can be equivalent to solving $L(Ux)=f$, That is, it is equivalent to solving $Ly=f$ and $Ux=y$ Two equations .

about $Ly=f$, It is the lower two diagonal equations , The specific form is $$\{\begin{array}{lr}{d}_1{y}_1=f_1& \\ a_i{y}_{i-1}+d_i{y}_i=f_i,& i=2,3,4,\cdots ,n\end{array}$$

Huidai , have to $$\{\begin{array}{lr}{y}_1=\frac{f_1}{d_1}& \\ y_i=\frac{f_i-a_i{y}_{i-1}}{d_i},& i=2,3,4,\cdots ,n\end{array}$$

about $Ux=y$, It is the system of two diagonal equations on the unit , The solution can be obtained by using the back substitution process in the catch-up method .