Definition 2 echelon form 阶梯形. A m n matrix A is in echelon form if LP row A < LP2 row A < < LPm row A Definition 3 reduce

Size: px

Start display at page:

Download "Definition 2 echelon form 阶梯形. A m n matrix A is in echelon form if LP row A < LP2 row A < < LPm row A Definition 3 reduce"

下便马佳
5 years ago
Views:

1 Lecture Note on Linear Algebra 2. Row Reduction and Echelon Forms Wei-Shi Zheng, 20 What Do You Learn from This Note In the last note, we solve a system S by transforming it into another equivalent easy to solve system, say S. But what is the meaning of the so call easy to solve system? We suggest that systems with the augmented matrices in echelon form or even reduced echelon form are easy to solve. In order to enable us to analyze any system of linear equations, we will refine the method in the last section into a row reduction algorithm. This would make our operation more principled. Basic concept: leading entry 先导元素, row echelon form 阶梯形, echelon matrix 阶梯形矩阵, reduced row echelon form 简化阶梯形, reduced row echelon matrix 简化阶梯形矩阵, pivot position 主元位置 2 Echelon Form 阶梯形 Definition leading entry 先导元素. Let A be an m n matrix m rows and n columns. The leftmost nonzero entry 元素 of the i th row of A is said to be the leading entry of the i th row of A and denote the column position/index of this entry in the i th row by LPi row A. If all the entries of the i th row are zero zero row then define LPi row A := n + i

2 Definition 2 echelon form 阶梯形. A m n matrix A is in echelon form if LP row A < LP2 row A < < LPm row A Definition 3 reduced row echelon form 简化阶梯形. A m n matrix A is in reduced echelon form if. A is in echelon form; 2. Any leading entry is ; 3. Any leading entry is the only nonzero entry in its column. Definition 4 echelon matrix 阶梯形矩阵, reduced echelon matrix 简化阶梯形矩阵. An echelon matrix reduced echelon matrix is one that is in echelon form reduced echelon form Theorem 5. echelon form. Each matrix is row equivalent to one and only one reduced Proof. See textbook Appendix A. We will discuss it shortly in latter notes after introducing more about linear algebra. Definition 6 pivot position 主元位置. Let A be a matrix and B a matrix in echelon form such that A B. Suppose that the i th row of B is nonzero. Then we call the pair i, LPi row B a pivot position of A. The LPi row B th column is called a pivot column 主元列 of A. 2

3 3 The Row Reduction Algorithm 行化简算法 Why? 为什么要做行化简 The reduced echelon form of a matrix A has the same solution as the original one. More, the reduced echelon form is easy for computing. How? 怎么做? 基于什么原理?. The reduced echelon form is unique 简化的阶梯形是唯一的 ; 2. The leading entries are on the same positions in any echelon form corresponding to a given matrix A. 当给定矩阵化为任何一个阶梯形时, 先导元素总是在相同的位置上这些先导元素对应于简化阶梯形中的先导元素值是 ; 3. Perform elementary operations: interchange, scaling, and replacement 采用三种初等变化 Overview of the following algorithm: Two main steps:. STEP STEP 3, compute the echelon form of any given matrix A; 2. STEP 4, compute the reduced echelon form based on the computed echelon matrix. The algorithm Let A be any m n+ augmented matrix corresponding to a linear system consists of m linear equations and n variables. We describe a procedure 程序 for transforming A into its equivalent echelon form and furthermore, a reduced echelon form using elementary row operations. Step : If A is a zero matrix all entries are zero, 零矩阵, go to Step 4; If A is already in echelon form, go to Step 4; Otherwise, there must be a nonzero column of A. Let the j th column of A be the first leftmost nonzero column of A and the i th entry of this column the first nonzero entry. If i, apply r r i on A 注意 : 实际情况下, 我们可以找到不止一个 i, 那么计算机编程时可以采用一列中元素绝对值最大的元素的行作为选取的 i 值. 3

4 A = r r Step 2 这里实际是采用初等变换中的 scaling 和 replacement: r 2 := r 2 a 2j r, r 3 := r 3 a 3j r,..., a j a j on A in order. r 3 :=r 3 3r r 4 :=r 4 2 r r m := r m a mj a j r Apply Step 3: Go to Step for the sub matrix of A which is an m n matrix without the first row of A. 换句话说, 暂时不管包含刚计算的主元位置的行以及它上面的各行, 而对剩下的子矩阵使用上述的 2 个步骤, 直到没有非零行需要处理为止 r 2 r 4 r 3 r 4 Steps 3 form a procedure for transforming A into echelon form. To obtain the reduced echelon form of A, we need another step to proceed. Step 4: If A is a zero matrix then A is already in reduced echelon form and we quit the procedure; else let, p, 2, p 2,..., t, p t 4

5 be all pivot positions of A. Beginning with the rightmost pivot and working upward and to the left, apply r t := r t, r t := r t a t,pt r t,..., r := r a pt r t, a tpt r t := r t, r t 2 := r t 2 a t 2,pt r t,..., r := r a pt r t, a t,pt on A in order. 注 : r := r a p. 以上 Step 4 的操作总共有两个目的 : 第一使得每个主元归一化, 即通过 scaling 变成值为 ; 第二, 对于主元列, 通过 replacement 操作消去除主元外的其他元素 2. Step 到 Step 3, 称为行化简算法的向前步骤, 这是因为我们从先求第一行的主元开始 ;Step 4 是向后步骤, 因为我们从含主元的最后一行开始进行简化操作 The pivot positions of A are, 2, 2, 3, 3, 4. r 3 := 2 r 3 r 2 := 2r 2 r 2:=r 2 +r r := 2 r r :=r r r :=r 2r

6 The above described procedure is called Gaussian Elimination 高斯消元法. It is a very old algorithm. However it is one of the most fundamental algorithms in mathematics. You need to know this algorithm very well. 4 Solutions of Linear Systems 线性方程的解 Suppose that the augmented matrix A R m n+ has been transformed into the reduced echelon form. How can we say about the solution set of the system with augmented matrix A. There are 3 cases corresponding to empty, singleton and infinite solution set respectively. Case : The last column of A is a pivot column. In this case, the system with augmented matrix A contains an equation 0 = which is always unsatisfiable. So the solution set is empty. Case 2: Every column is a pivot column except the last one. In this case, the number of pivots is equal to n, that is the number of variables of the system. The matrix A is of the form 0 0 b 0 0 b b n, which corresponds to the system x = b x 2 = b 2 x n = b n. So b, b 2,..., b n is the only solution of this system. Case 3: Otherwise. In this case, the solution set is infinite, we can not list all solutions. However, the solution set can be parameterized by variables corresponding to 6

7 non pivot columns, which are called free variables 自由变量. That is, we can obtain a general solution which is expressed in terms of free variables. 我们会在以后章节更详细讨论 Let A = which is in reduced echelon form with pivot positions,, 2, 3. corresponding system is { x 2x 2 +x 4 = x 3 +8x 4 =. By moving terms, we have { x = + 2x 2 x 4 x 3 = 8x 4., The Thus, we obtain a general solution 通解 of the system: + 2x 2 x 4, x 2, 8x 4, x 4, where x 2, x 4 are free variables. If we assign values to x 2 and x 4 we will obtain a concrete solution of the system. For instance, if we put x 2 :=, x 4 := then we obtain a concrete solution 4,, 7,. Reference David C. Lay. Linear Algebra and Its Applications 3rd edition. Pages Bathers at Asnieres, by Seurat 7

ENGG1410-F Tutorial 6

ENGG1410-F Tutorial 6 Jianwen Zhao Department of Computer Science and Engineering The Chinese University of Hong Kong 1/16 Problem 1. Matrix Diagonalization Diagonalize the following matrix: A = [ ] 1 2 4 3 2/16 Solution The