How can I effectively solve linear system $Ax = b$ with some known variables

Question

Consider system $Ax = b, x = (x_1,\ldots, x_n)^T$. Suppose that some of variable $x_i$ is known. How can I find the rest of unknown variable effectively? Assume that system has unique solutions after we substitute all known variables $x_i$.

One way to do it is manually substituting the known variable and rewrite the system in different form then we can solve system by some method like $QR$ decomposition, ....But it seems to be not effectively and difficult if I have to write a program. For example, how can I write a program in Matlab with input $A,b$ and some known variable $x_i$, output: find the rest unknown variables ? Thank you for your time.

Answer 1

Apply a permutation matrix so that the known values of $x$ are all at the bottom of the vector.

Then, your system is

$$A\begin{bmatrix}x_{unknown}\\x_{known}\end{bmatrix} = \begin{bmatrix}b_{unknown}\\b_{known}\end{bmatrix}$$

Now, you can also write $A$ as a block matrix $$A=\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}$$and get a new, smaller system to solve, since

$$A_{11} x_{unknown} + A_{12} x_{known} = b_{unknown}$$

meaning that $$A_{11}x_{unknown} = b^*$$

where $b^*=b_{unknown} - A_{12}x_{known}$

Answer 2

We have \begin{align} A x &= b \iff \\ \sum_i a_i \, x_i &= b \end{align} and know some of the components $x_i$. This leads to a reduction of active columns: \begin{align} \sum_i a_i x_i &= b \iff \\ \sum_{i \in U} \, a_i x_i &= b - \sum_{i\in K} a_i \, x_i \iff \\ A' x' &= b' \end{align} where $K$ is the set of indices belonging to known variables and $U$ is the set of indices belonging to unknowns.

Note however that the number of rows has not changed. So you now have to solve an overestimated system unless you try to identify the $\lvert K \rvert$ equations, which are redundant. \begin{align} A' x' &= b' \Rightarrow \\ (A')^T A' x' &= (A')^T b' \iff \\ x' &= ((A')^T A')^{-1} (A')^T b' \end{align}

One way to do it is manually substituting the known variable and rewrite the system in different form then we can solve system by some method like $QR$ decomposition, ....

It is just that. And noting that we end up with a $n \times \lvert U \rvert$ system matrix, not a $\lvert U \rvert \times \lvert U \rvert$ one.