前言

略

课程链接

线性系统以及解的形式

For a Linear System, we can form like this:
$$A\text{x}=b\text{\hspace{1em}(1)}$$
where $A$ refers to a matrix, x is parameters needs to be determined, and b is the bias.

As for the Existence and Solutions

If $A\in {\text{R}}^{M\times N}$, we have:

1. If $M=N$, and matrix $A$ is nonsingular and square, we have a unique solution.
2. If $M<N$, there are infinitely many solutions. We can find the null space of $A$ ($Ax=0)$ using SVD.
3. If $M>N$, we can ask for a least-square solution(If we couldn’t get the reasonable solution), e.g., from the normal equation $(A^{T}A)x=(A^{T}b)$

Additionally, If we have $M=N$, but the matrix $A$ is singular ($\det A=0$), this situation is equal the situation 2, for we can delete useless equations to make $M$ smaller.

Concepts in Linear Algebra

• Vector Space: Which means that for any $x$, $y$ in the space, we have $x+y$ and $cx$ in the space, too, where $c$ is a number.
• Linear independent: Easy to understand.
• Dimension: The max number of linearly independent vectors; Rank of $A$ is the dimension of the range of $A$.
• Null Space of $A$: the set of all x, such that $Ax=0$
• Range of $A$: the set of all $Ax$
• Rank of $A$: max number of linearly independent rows or columns
• $rankA+rank(NullSpace(A))=N$, where N is the number of columns of $A$.

Cramer Rules

where $A_j$ means that we replace the j-th column by the $b$ vector.

More advanced Computation Methods

Gauss Elimination

This method is used to find the inverse matrix or the solutions.
For a set of equations { L i } n \{L_i\}_n {Li​}n​, first we need to construct the Augmented matrix, then we need to reduce all the elements in columns one to 0 except for the first row. Then We repeat it. and reduce the left n columns of the augmented matrix to an identity matrix.

The result is the last column of the augmented matrix.

Link

Notice: LU equivalent to Gauss Elimination

LU Decomposition

NOTICE: Not all real square matrixes have LU decomposition. More normally, we have:
$$PA=LU\text{\hspace{1em}(2)}$$
where $P$ is a permutation matrix which records the row change information.

With the computational complexity is $O(N^3)$ and memory complexity is $O(N^2)$

Crout’s Algorithm for LU Decomposition

In summary, we can finish the Crout’s alg. in a column order.

Pivoting

Combination of Cramer’s Rule and LU Decomp to Get Solution

For an linear equation $Ax=b$,

• Do LU Dcomp for $A$, $LU=A$
• Forward steps: Using Cramer’s Rule to solute $Ly=b$, where $y=Ux$
• Backward stsp: Using Cramer’s Rule to solute $Ux=y$

One more thing

$$\det (A)=\det (U)$$

One more thing

Tutorial Result

(a)
$$L=\left[\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ 6& -3& 1\end{array}\right],U=\left[\begin{array}{ccc}1& 2& 5\\ 0& 4& 8\\ 0& 0& -5\end{array}\right]$$
$$x=[0.5,2.25,-1{]}^T$$
(b)
$$A^{-1}=\left[\begin{array}{ccc}-0.1& 0.1& 0.2\\ -0.95& 1.45& 0.4\\ 0.6& -0.6& -0.2\end{array}\right]$$

©
$$\det (A)=\det (U)=-20$$