中国科学院李保滨矩阵分析课件八

Li Bao bin | UCAS
பைடு நூலகம்
9 / 65
Norms and Inner Products | Orthogonal Reduction
The Householder or Givens reduction is a stable algorithm for producing the QR factorization of An×n .
−1 −1
.
2 u2 ˆ 2 = I − 2 uT If R and R2 = u u 2
ˆ 2 A2 = R and
25 10 0 10
5 25 −4 and R2 R1 A = 0 25 10 0 0 10
0 15 20 1 −20 12 −9 . P = R2 R1 = 25 −15 −16 12
Norms and Inner Products | Orthogonal Reduction
Orthogonal Reduction
A matrix A can be reduced to row echelon form by elementary row operation by Gaussian elimination. Gaussian elimination is not the only way to reduce a matrix. Elementary reflector Rk can accomplish the same purpose, which called Householder reduction. It proceeds as follows. For Am×n = [A∗1 |A∗2 | · · · |A∗n ], use x = A∗1 to construct the elementary reflector R1 = I − 2 uu∗ u∗ u where u = A∗1 ± µ A∗1 e1 ,
Li Bao bin | UCAS
5 / 65
Norms and Inner Products | Orthogonal Reduction
To annihilate the entry below the (2,2)-position, set A2 = 0 −10 −25 −10
T 2
and
u2 = [A2 ]∗1 − [A2 ]∗1 e1 = 25 1 0 ˆ2 0 R then
Li Bao bin | UCAS
8 / 65
Norms and Inner Products | Orthogonal Reduction
If A has linearly independent columns, then the least squares solution for Ax = b is obtained by solving the nonsingular triangular system Rx = c. We now have four different ways to reduce a matrix to an upper-triangular form
Li Bao bin | UCAS
7 / 65
Norms and Inner Products | Orthogonal Reduction
Orthogonal Reduction and Least Squares
Orthogonal reduction can be used to solve the least squares problem with an inconsistent system Ax = b in which A ∈ Rm×n and m ≥ n. If ε denotes the difference ε = Ax − b, then, the general least square problem is to find a vector x that minimizes the quantity
(1) (2) (3) (4) Gaussian elimination Gram-Schmidt procedure Householder reduction Givens reduction
It’s natural to try to compare them and to sort out the advantages and disadvantages of each. First consider numerical stability. Strictly speaking, an algorithm is considered to be numerically stable if, under floating-point arithmetic, it always returns an answer that is the exact solution of a nearby problem.
Suppose that floating-point arithmetic produces an orthogonal matrix Q + E and upper triangular matrix R + F ˜ = (Q + E)(R + F) = QR + QF + ER + EF = A + QF + ER + EF. A If E and F account for the roundoff errors, and if their entries are small relative to those in A, then the entries in EF are negligible, and ˜ ≈ A + QF + ER. A Since Q is orthogonal, QF F = F F , and A F = QR F = R F . This means that neither QF nor ER can contain entries that are large relative to those in A. ˜ ≈ A, which says that the algorithm is stable. Hence A
Li Bao bin | UCAS
4 / 65
Norms and Inner Products | Orthogonal Reduction
Problem: Use Householder reduction to find an orthogonal matrix P such that PA = T is upper triangular with positive diagonal entries, where 0 −20 −14 27 −4 . A= 3 4 11 −2 Solution: To annihilate the entries below the (1,1)-position and to guarantee that t11 is positive, we set u1 = A∗1 − A∗1 e1 = A∗1 − 5e1 = (−5 3 4)T We obtain and R1 = I − 2 u1 uT . uT 1 u1
Li Bao bin | UCAS 6 / 65
Norms and Inner Products | Orthogonal Reduction
A sequence of plane rotations can be used to annihilate all elements below a particular pivot. This means that a matrix A can be reduced to an upper-trapezoidal form by using plane rotations. Such a process is usually called a Givens reduction Householder and Givens reductions are closely related to the results produced by applying the GramõSchmidt process to the columns of A. When A is nonsingular, Householder, Givens, and GramõSchmidt each produce an orthogonal matrix Q and an upper-triangular matrix R such that A = QR .
Tk−1 Tk−1 . 0 Ak Eventually, all of the rows or all of the columns will be exhausted, so the final result is one of the two following upper-trapezoidal forms: The result after k − 1 steps is Rk−1 · · · R2 R1 A =
Elementary reflectors are not the only type of orthogonal matrices that can be used to reduce a matrix to an upper-trapezoidal form. Plane rotation matrices are also orthogonal and can be used to selectively annihilate any component in a given column.
t11 tT 1 0 A2
,
Norms and Inner Products | Orthogonal Reduction