Solve Linear System

We start from a simple question of solving a linear system, which every (BSc/BEng etc.) students should encounter in their very first linear algebra course:

If the equation above is fulfilled for some , then for any , the statement below must also hold true, and vice verse, namely:

However, we still cannot compute the solution directly, as we still have equations in the above formulation and if is very large, the computation can be extremely expensive!!

Solution with Reduced Dimension

Our idea now is very simple: reduce the dimension of the space where and lives in. We want to replace with a much smaller , which makes the calculation more affordable, without loss of too much precision.

Recall what I have written in the Quantum Dissipative System post before, where we introduced orthogonal projectors , used them to separate the system and bath, studied the equation of motion, and used bath-correlation and Caldeira-Legget approximation to do some Perturbation Theory in order to fix the model and make it more precise.

The idea here is very similar, except that we know exactly about the dimensions we throw away. We change the basis by defining:

W=[w1,w2,...,wm]∈Rn×m,y~=Wy^,x~=Wx^.\begin{aligned} W=&\left[w_1, w_2, ..., w_m\right]\in \mathbb{R}^{n \times m},\\ \tilde{y}=&W \hat{y},\\ \tilde{x}=&W \hat{x}. \end{aligned}

And our linear system now becomes:

y^TWTAWx^=y^TWTb,\hat{y}^\mathrm{T} W^\mathrm{T} A W \hat{x} =\hat{y}^\mathrm{T} W^\mathrm{T}b,

or in more compact form:

y^TA~x^=y^Tb~,\hat{y}^\mathrm{T} \tilde{A} \hat{x} =\hat{y}^\mathrm{T} \tilde{b},

where .

The number of remaining equations become now . In practice, we solve first this smaller linear system and do several iterations, until the remainder, namely is close enough to .

How to Pick ?

If you open any textbook about numerical methods, a bunch of algorithms will show up to teach you how to solve linear systems, e.g. gradient descent, Lanzcos, Krylov etc. As a matter of fact, they are doing the same thing: approaching the exact solution, with their different choice of .

Connection with PDE Weak Solution Theory

In PDE weak solution theory, we do essential the same thing as turning the original strong form of equation into the weak form, i.e. . (Note that the converse does not generally hold true because we don’t require to be twice differentiable in the weak formulation) It is quite natural to think of them in an identical way and expect analogous behaviours from them, because we can view PDEs as linear systems of infinite dimension with the firmly established Functional Analysis theories.

In the next step, we use Ritz-Galerkin projection method to solve the equation in a discretized space by choosing an interpolator . This serves as essentially the same role as in solving the above linear system .

License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Join discussion here~