Everything About Linear Algebra
Linear, advanced, and numerical viewpoints
Qiulin Fan
2026
Chapter 1Introduction
This is the public reading view for three source-preserving collections:
- •
introductory linear algebra notes and personal homework submissions;
- •
a short advanced linear algebra notebook based on LADR and GTM 135;
- •
numerical linear algebra notes on norms, factorisations, conditioning, and stability.
The original course directories, source manifests, and migration receipts remain the authority for provenance. This file only groups those sources into one continuous reading path; source-authored omissions and explicit TODOs are not silently completed here.
Linear Algebra
Chapter 2Linear equations, vectors, and matrices
2.1WS 1, p. 1: vectors and vector spaces
(complement: “MathHygine”) Principle of Mathematical Induction:
For the system
place numbers in the columns of the augmented matrix
A matrix with only one column is called a column vector, or simply a vector. The entries of a vector are called its components. The set of all column vectors with
A matrix with only one row is a row vector. In this text, we refer to vectors as column vectors unless otherwise stated. 下一章会说 preference for column vectors 的 apparent reason.
For example,
- 1.
is called a matrix (row, col; three by four). - 2.
Matrix
if same size and . - 3.
If
is , is called a square matrix, and the entries form the main diagonal of . - 4.
A square matrix
is called diagonal provided all its entries above and below the diagonal are , i.e. whenever . - 5.
is called upper triangular provided all its entries below the main diagonal are ; lower triangular: entries above the main diagonal are .
Note that the
Standard representation of vectors:
Consider the system
The matrix which contains the coefficients is called its coefficient matrix,
2.2WS 1, p. 2: augmented matrices and RREF
For the sake of clarity, we will often indicate the position of the equal signs in the equations by a dotted line:
我们可以把之前的对 equation 的操作用在 matrix 上,并且将 answer represented as a vector. Thus the displayed system has answer
Example:
这个 equation 容易解是因为:
- 1.
The leading coefficient is always
. - 2.
The leading variable in each equation 在其他 equation 中不出现.
- 3.
The leading variables in natural order 出现.
当一个 linear system 有这些三条性质后就非常容易解,因而我们希望将 linear system reduce 至满足
For example, row operations reduce the displayed augmented matrix to
From top to down, move on to the
- 1.
Divide by
, so . - 2.
Eliminate
from all other equations above and below. - 3.
Proceed to next equation.
- 4.
Check: if
non- , inconsistent. - 5.
Rearrange equations so the leading variables are in natural order.
The reduced row-echelon form (行阶梯矩阵 or Rref) satisfies:
- 1.
若一 row 有 non-
entries, the first non- entry must be , called the leading or pivot. - 2.
若一 col 中有 pivot,则 col 中其他 entries 必须为
. - 3.
若一 row 中有 pivot,则它后每个 row 必须有 pivot 在它右边(and rows of
s must be at the bottom of matrix).
Definition 2.2 (Elementary row operation)
之前我们对 linear system 中 equations 的三种 operations 用在 matrix 上,这三种 operation 统称 elementary row operations:
- 1.
Divide a row by a non-zero scalar.
- 2.
Subtract a multiple of a row from another.
- 3.
Swap two rows.
这种使用 elementary row operations 将 matrix 化为 rref 的解 linear system 的 algorithm 叫做 Gauss–Jordan elimination.
Chapter 3Linear systems and matrices
The worksheet starts with a system of linear equations:
To solve for
- 1.
Eliminate terms that are off the diagonal.
- 2.
Make the coefficients of the variables along the diagonal equal to
.
The row-reduction calculation on the page is
where the first arrow subtracts the first equation and the next arrow uses
The intervening operations are
Finally, we check the sol by substituting
Chapter 4Linear combinations
4.1WS 3, p. 1: geometry and number of solutions
Geometric Interpretation: three planes can have a point of intersection
- •
planes having a line in common: a system with infinitely many sols. - •
planes with no common intersection: a system without sols.
For
reduction gives
For
reduction yields
Complement (Joy of sets): To say a set is close under some operation
4.2Number of solutions of a linear system
本章:① examine how many sols a system of linear equations can possibly can. ② Then we will present some definitions and rules of matrix algebra.
A system of equa. is said to be consistent if it has at least
If consistent, either infinitely many sols (at least one free variable) or exactly one sol (if all variables are leading).
For an
- 1.
and . - 2.
If the system is inconsistent,
. - 3.
If the system has one sol,
. - 4.
If the system has infin sols,
.
If system inconsistent, rref of augmented matrix contains a row
As contrapositive: (1) if
Theorem 4.1 (Number of equations vs. number of unknowns)
If a linear system has exactly one sol, then it has at least as many equations as variables (i.e.
To illustrate it: consider
4.3WS 3, pp. 2–3: matrix algebra and linear combinations
Definition 4.2 (Sum and scalar multiples of matrices)
For same-size matrices, addition is entrywise; for
Definition 4.3 (Dot products of vectors)
For
Definition 4.4 (The product of
Let
Example:
Theorem 4.2 (
Let the columns of
Definition 4.5 (Linear combination)
A vector
Example: is
Theorem 4.3 (Algebraic rule for
If
Theorem 4.4 (Matrix form of a linear system)
With augmented matrix
For
Chapter 5Linear transformations
5.1WS 4, p. 1: coordinate encoding and standard matrices
现在你的位置为
这个加密方位的码为
Definition 5.1 (Linear transformation)
A function
Example:
Definition 5.2 (Identity matrix)
Identity matrix, denoted by
For
For
5.2WS 4, p. 2: linearity, bases, and transition matrices
Theorem 5.1 (Standard matrix)
Consider a linear transformation
Theorem 5.2 (Linearity test)
A transformation
Definition 5.3 (Distribution vectors and transition matrices)
A vector
Chapter 6Geometry of linear transformations
6.1WS 5, p. 1: examples, scaling, and projection
在 2-1 我们知道
The source diagrams apply them to
- •
: 放大一倍, sending them to and . - •
: orthogonal projection onto -axis, sending both to . - •
: reflection about -axis. - •
: clockwise 转 degrees, sending them to and . - •
: 向右 shear, sending them to and . - •
: counterclockwise shift + 放大 倍, sending them to and .
Theorem 6.1 (Scalings)
Definition 6.1 (Orthogonal projection)
Consider a line
随意取
Definition 6.2 (Reflection)
Consider a line
The matrix of
6.2WS 5, p. 2: rotations and shearing
Theorem 6.2 (Rotations)
For a nonzero vector
Theorem 6.3 (Rotations combined with a scaling)
将
6.35. Shearing
Vertical shear:
Horizontal shear:
Theorem 6.4 (Horizontal and vertical shearing)
Horizontal shearing of slope
The source’s concluding table records:
- •
Scaling by
: . - •
Orthogonal projection onto line
: , for and . - •
Reflection about line
: . - •
Rotation through angle
(逆时针): . - •
Rotation through
with scaling by : . - •
Shear: horizontal
; vertical .
Chapter 7Gram–Schmidt and QR factorization
7.1WS 17, p. 1: proof of QR factorization QR factorization
Let
The
The worksheet computes
Because
7.2Proof of matrix product theorem
For ordered bases
where
Note that if
Chapter 8Orthogonal transformations
8.1WS 18, p. 1: definition and matrix criteria
Theorem 8.1 (Equivalent characterizations)
因而 linear trans 保留 dot product iff 保留 length. The proof expands
then cancels equal norm terms.
(a) An orthogonal trans
Definition 8.2 (Orthogonal matrix)
A square matrix
If
The worksheet proves
8.2WS 18, p. 2: products and change of basis
If
Theorem 8.2 (Products of orthogonal matrices)
If
Indeed,
so
Theorem 8.3 (Orthogonal maps and their matrices)
For the reverse direction,
Claim 1: If
and
Thus
8.3WS 18, p. 3: conclusion
Claim 2: orthogonal matrices 的 product 也是 orthogonal matrix. 这是因为 orthogonal transformations 的 composition 也是 orthogonal transformation,且它的自身的 matrix 代表为 orthogonal matrix。
Claim 3: 如果
All three factors are orthogonal, hence so is
Claim 4:
we obtain
a product of orthogonal matrices; hence
总结:
Chapter 9Least squares
9.1WS 19, p. 1: projection and image/kernel theorem
The source diagram labels
(a)
The worksheet also records
Theorem 9.2 (Image-kernel orthogonality)
For an
Write
A second proof uses the displayed transpose identity:
Consequently
9.2WS 19, p. 2: normal equations
The normal equation:
Theorem 9.3 (Kernel of
For an
If
For the rest proof of normal equation, the source diagram records
总结:对于
Chapter 10Inner-product spaces
10.1WS 20, p. 1: examples and generalized Gram–Schmidt
For the Inner product space
- 1.
. - 2.
Linearity:
. - 3.
Positive definite:
, and .
(b) 同 (a),inner product space
P4: find two different inner products in
P5: Every finite dimensional inner product space has an orthonormal basis. Take
and, in general,
proof: generalized Gram–Schmidt.
10.2WS 20, p. 2: coordinates and matrix inner products
P8: 任选 orthonormal basis
Indeed
P9:
For the standard basis, the
Because the inner product is symmetric, so is
P10: All inner products on
where (1)
(这个条件等价:充分条件为
实际上的理解为:把
Chapter 11Diagonalization and eigenspaces
11.1WS 23, p. 1: four theorems
Theorem 11.1 (Eigenbasis and diagonal matrix)
For a finite-dimensional vector space
Indeed,
Theorem 11.2 (Diagonalizable transformation)
The definition notes:
Theorem 11.3 (Diagonalizable matrix)
Proof:
(Thm 7.1.3) 如果
Proof note:
Hence the change of basis yields the diagonal matrix.
Chapter 12Eigenvalues and eigenspaces
12.1WS 24, p. 1: characteristic polynomial and multiplicities
Theorem 12.1 (Eigenvalues are roots)
The eigenvalues of
简明 proof:
Theorem 12.2 (Distinct-eigenvalue eigenspaces)
因而 eigenbases of distinct eigenspaces have linearly independent union, and if
Theorem 12.3 (Geometric and algebraic multiplicity)
For eigenvalue
Let
Therefore
so
and
Theorem 12.4 (Degree of the characteristic polynomial)
For
This is the corollary of the preceding two theorems: if
Chapter 13Complex eigenvalues
13.1WS 26, p. 1: complex roots and real matrices
P5(b). Let
z w=(a c-b d)+(b c+a d)i
(c) Fact:
For
(b) Factor
where
(c) Diagonalization over
For
so
and
P9: 任何有一对 complex eigenvalue
Chapter 14Spectral theorem
14.1WS 27, p. 1: theorem and first two claims
Theorem 14.1 (Spectral theorem)
Equivalently,
Claim 1: if
and
Claim 2: if
Claim 2 pt.(1): if
Since
Claim 2 pt.(2): consider
Thus
14.2WS 27, p. 2: induction proof
Claim 2 pt.(3): if
Base case: a
Let
so
Then
for some
By the inductive hypothesis,
The middle matrix is diagonal and
Personal Linear Algebra Homeworks
14.3Homework 1 — submitted work
Note
Visual transcription of the personal finished submission. Source: 217-Hw-1-finished.pdf; page references below are PDF pages.
14.3.1Source p. 1 — Exercise 20
Find the values of
The submitted row reduction is
14.3.2Source p. 2 — Exercise 20; Exercise 32 begins
For no solution,
Exercise 32 asks for a polynomial of degree at most two,
14.3.3Source p. 3 — Exercise 32
The augmented matrix is reduced as
14.3.4Source p. 4 — Exercise 34
Find a polynomial of degree at most two which passes through
14.3.5Source p. 5 — Exercise 34; Exercise 44
The reduction for Exercise 34 ends at
For Exercise 44, the line through
14.3.6Source p. 6 — Exercise 12
The homogeneous augmented matrix recorded is
14.3.7Source p. 7 — Exercise 12
The submitted reduction clears the first column, then the second column. Its displayed intermediate rows include
14.3.8Source p. 8 — Exercise 12
The final reduced matrix is
14.3.9Source p. 9 — Exercise 36
For a vector
14.3.10Source p. 10 — Exercise 44
For the traffic-flow diagram, the submitted equations are
14.3.11Source p. 11 — Exercise 44
The submitted row reduction reaches
14.3.12Source p. 12 — Exercise 44
The submitted solution is
14.3.13Source p. 13 — Problem 1(a)–(c)
(a) True: “2 is even” and “3 is odd” are true, hence their disjunction is true.
(b) True:
(c) False: the derivative claim is true, but the submitted work states that
14.3.14Source p. 14 — Problem 1(d)–(e); Problem 2(a)
(d) True: the premise “there are infinitely many even primes” is false, since the only even prime is
(e) True: each right triangle has two acute angles and every positive real number has a positive cube root; the implication is true.
For Problem 2(a), the table in the submission says that a proof proves nothing for a universal statement and that an existential statement is true; a counterexample proves a universal statement false and proves nothing for an existential statement.
14.3.15Source p. 15 — Problem 2(b)–(d)
(b) True: every prime integer is either even or odd.
(c) False:
(d) False: the submitted contradiction uses
14.3.16Source p. 16 — Problem 2(e)–(g)
(e) True: the submitted argument chooses the integer immediately above
(f) True: every square is a rectangle.
(g) False:
14.3.17Source p. 17 — Problem 3
The submitted negations are:
- •
(a) 2 is not even and 3 is not odd.
- •
(b) the Riemann hypothesis is true and 217 is prime.
- •
(c) the derivative is not
or . - •
(d) there are infinitely many even primes, and 10 is not even or
is not odd. - •
(e) every right triangle in
has two acute angles, and some real number has no positive cube root. - •
(f)
there exists with . - •
(g) all squares are not rectangles.
14.3.18Source p. 18 — Problem 4
The submitted converses and contrapositives are:
- •
(a) Converse: “If something exists, it can think.” Contrapositive: “If something does not exist, it cannot think.”
- •
(b) Converse: “If
is irrational, then is irrational.” Contrapositive: “If is not rational, then is not rational.” - •
(c) Converse: “If
is prime, then is a natural number greater than 2 such that its Collatz sequence does not reach 1.” The contraposition is also written in terms of not being prime and the alternatives concerning and its Collatz sequence.
14.3.19Source p. 19 — Problem 5
(a1) The set is all odd natural numbers. (a2) The graph is the right half of the unit circle centred at the origin, including the boundary.
(b1) The submitted set notation is {(x,y,z) in RR̂3 : x̂2+ŷ2+ẑ2=1}. (b2) The submitted set notation is {sqrt(2)n : n in ZZ}.
(c) The submitted truth values are: {sqrt(2)} in RR false; {sqrt(2)} subset RR true;
14.3.20Source p. 20 — Problem 6(a)
The submitted lists are 1/2 NN = {1/2,1,3/2,2,5/2,3,...}, 1/3 NN = {1/3,2/3,1,4/3,5/3,2,...}, and 3NN = {3,6,9,12,15,18,...}. It records 1/2 NN intersect 1/3 NN = NN, and writes the union beginning {1/3,1/2,2/3,1,4/3,3/2,...}. It also gives 1/2 NN without 1/3 NN = {1/2,3/2,5/2,7/2,9/2,11/2,...} and (3NN)̂c = NN without 3NN = {1,2,4,5,7,8,10,...}.
14.3.21Source p. 21 — Problem 6(b)
The claimed least
14.3.22Source p. 22 — Problem 7
Let
14.3.23Source p. 23 — Problem 7
Applying De Morgan’s law, the submitted negation is
The accompanying English reads: “for all time there are some people you cannot fool, or for some time you can fool no people in the world, or for all time you can fool all people. (You can at least achieve one of three things).”
14.4Homework 2 — submitted work
Note
Visual transcription of the personal finished submission. Source: 217-Hw-2-finished.pdf; page references below are PDF pages.
14.4.1Source p. 1 — Exercise 26
Let
14.4.2Source p. 2 — Exercise 26; Exercise 34 begins
If
Exercise 34 introduces the standard coordinate vectors
14.4.3Source p. 3 — Exercise 34
For
For a matrix
14.4.4Source p. 4 — Exercise 48(a)–(b)
(a) If
(b) If
14.4.5Source p. 5 — Exercise 48(c)
The drawing places the homogeneous solutions on a line through the origin and the particular solution
14.4.6Source p. 6 — Exercise 48(c)
The geometric explanation concludes: all solutions form the line parallel to the homogeneous-solution line through the head of
14.4.7Source p. 7 — Exercise 6
For
The submitted standard matrix is
14.4.8Source p. 8 — Exercise 38; Exercise 44 begins
For Exercise 38,
The submitted sketch shows this vector combination. Exercise 44 begins with
14.4.9Source p. 9 — Exercise 44
With
Thus the submitted matrix for
14.4.10Source p. 10 — Exercise 46
For
Hence the matrix is
14.4.11Source p. 11 — Part B, Problem 1(a)–(b)
(a)
(b)
14.4.12Source p. 12 — Part B, Problem 1(c)–(d)
(c)
(d)
14.4.13Source p. 13 — Part B, Problem 2(a)–(b)
The submitted truth values are (a) false, (b) true, (c) false, (d) false, (e) true.
For (a), take A intersect B = emptyset but
14.4.14Source p. 14 — Part B, Problem 2(b)–(c)
For (b), if
For (c), the same squaring map with
14.4.15Source p. 15 — Part B, Problem 2(d)–(e)
For (d), using the same
For (e), it begins the two inclusions for a bijection
14.4.16Source p. 16 — Part B, Problem 2(e)
If m in f[A intersect B], then x in A intersect B, so m in f[A] intersect f[B]. Conversely, m in f[A intersect B].
14.4.17Source p. 17 — Part B, Problem 3(a)
Assume
then division yields
14.4.18Source p. 18 — Part B, Problem 3(b)
The submitted example is
14.4.19Source p. 19 — Part B, Problem 4(a)–(b)
For an additive
14.4.20Source p. 20 — Part B, Problem 4(c)–(d) begins
The induction for
Part (d), for negative integers, begins on this page.
14.4.21Source p. 21 — Part B, Problem 4(d); recreational part (e)
The work completes the negative-integer case using
14.5Homework 3 — submitted work
Note
Visual transcription of the personal finished submission. Source: 217-Hw-3-finished.pdf; page references below are PDF pages.
14.5.1Source p. 1 — Exercise 20
Reflection about the
14.5.2Source p. 2 — Exercise 38(a)–(c)
(a) Projection onto an arbitrary unit vector
(b) A reflection matrix is
(c) A rotation matrix is
14.5.3Source p. 3 — Exercise 38(d); Exercise 18 begins
(d) The horizontal and vertical shear matrices are
For Exercise 18, let
14.5.4Source p. 4 — Exercise 34
For
Thus
14.5.5Source p. 5 — Exercise 12
For
14.5.6Source p. 6 — Exercise 12; Exercise 34 begins
The final augmented matrix is
By Theorem 2.4.5,
For a diagonal
14.5.7Source p. 7 — Part B, Problem 1(a)–(b)
The source defines trace, determinant, transpose, and symmetric matrix, then asks truth values for transpose claims. The submission marks (a) false and takes
For (b), it marks false using the same matrices and records
14.5.8Source p. 8 — Part B, Problem 1(c)
The statement
14.5.9Source p. 9 — Part B, Problem 1(c)–(d)
The
the
For (d), the submission begins induction: for a symmetric
14.5.10Source p. 10 — Part B, Problem 1(d)–(e)
The inductive multiplication is
which is symmetric. Hence
(e) is false:
14.5.11Source p. 11 — Part B, Problem 2(a)–(c)
(a) True. A
(b) False. The counterexample is
(c) True. If
14.5.12Source p. 12 — Part B, Problem 2(d)
(d) True. If
14.5.13Source p. 13 — Part B, Problem 3(a)
If there is an
14.5.14Source p. 14 — Part B, Problem 4(a)
Statement (a) is marked true. Write
If
Thus every column of
14.5.15Source p. 15 — Part B, Problem 4(b)
Statement (b) is false. The counterexample uses
14.5.16Source p. 16 — Part B, Problem 5(a)
For a linear
so it is linear. Thus
14.5.17Source p. 17 — Part B, Problem 5(a)
The submission restates the inductive conclusion: the base case and inductive step prove that if
14.5.18Source p. 18 — Part B, Problem 5(b)
Define
14.5.19Source p. 19 — Part B, Problem 5(c)
Let
14.6Homework 4 - submitted work
14.6.1Exercise 28 - inverse of a linear transformation
For
the standard matrix is
The submitted elimination of
Thus
and
14.6.2Exercise 30 - invertibility
Let
Therefore
14.6.3Exercise 42 - permutation matrices
By elementary transformations that change row order, any permutation matrix can be transformed into
and
14.6.4Exercise 6 - kernel
For
Hence
so
14.6.5Exercise 14 - image
For
Therefore
14.7Part B
14.7.1Problem 1 - nilpotent transformations
Let
14.7.1.1(a)
We prove by induction on
Thus the statement holds for all
14.7.1.2(b)
Assume that
14.7.1.3(c)
If
Then
and, similarly,
14.7.2Problem 2 - the vector space
For
and the function
All expressions are defined in
The element
Finally,
where
14.7.3Problem 3 - polynomial transformation
Let
14.7.3.1(a)
For
and for
Thus
14.7.3.2(b)
we have
14.7.3.3(c)
take
Then
14.7.4Problem 4 - left multiplication
For
14.7.4.1(a)
For
So
14.7.4.2(b)
If
14.7.4.3(c)
If
14.7.4.4(d)
The map
14.7.5Problem 5 - rotations and projection
For
14.7.5.1(a)
14.7.5.2(b)
The final rotation does not affect the kernel. Projection kills exactly the
14.7.5.3(c)
For
equivalently
14.8Homework 5 - submitted work
14.8.1Exercise 56 - linear independence
Rearrange the four given vectors as
Each
14.8.2Exercise 33 - hyperplanes
For
Thus a hyperplane in
14.8.3Exercise 63 - equal-dimensional nested subspaces
Let
14.8.4Exercise 12 - arithmetic sequences
Let
then
For
Hence
14.8.5Exercise 28 - commuting matrices
Let
so
The displayed matrices are linearly independent, so they are a basis and
14.9Part A - Problem 6
For each diagram, the submitted dependent triples are:
(a)
14.10Part B
14.10.1Problem 1 - images of independent lists
14.10.1.1(a)
False. Let
14.10.1.2(b)
True. Assume
Independence of
14.10.2Problem 2 - prescribed kernel and image
The rref required by
is
The target image has basis
and
The transformation is not unique. For example, elementary transformations preserve the rref, and
has the same required kernel and image but is different from
14.10.3Problem 3 - maps defined on a basis
14.10.3.1(a)
Let
For
and
14.10.3.2(b)
Let
By part (a), this is a valid linear transformation. Its image is
14.10.3.3(c)
The map is not unique: the construction depends on an arbitrarily chosen basis of
14.10.4Problem 4 - ranks and nullities of a composition
14.10.4.1(a)
True. Since
14.10.4.2(b)
True. View the composition in two stages. First
14.10.4.3(c)
True. Rank-nullity yields
Part (b) then implies
14.10.4.4(d)
False. If
14.10.5Problem 5 - symmetric and skew-symmetric matrices
For
14.10.5.1(a)
14.10.5.2(b)
If
14.10.5.3(c)
Both are subspaces. Each contains the zero matrix. If
14.10.5.4(d)
There are
For a skew-symmetric matrix, the lower entries are the negations of the upper entries and every diagonal entry is zero. Thus
14.11Homework 6 - submitted work
14.11.1Exercise 50 - hexagonal coordinates
For the basis
The point with
Moving by the first two summands means moving in parallel to
14.11.2Exercise 70 - upper triangular coordinate matrix
There is no basis
is upper triangular. Suppose, for a contradiction, that
Then the generalized key theorem gives
Writing
Thus
14.11.3Exercise 58 - the solutions of
14.11.3.1(a)
For
Then
so
14.11.3.2(b)
If
14.11.3.3(c)
is in
Part (b) gives
Thus
14.11.4Exercise 46 - multiplication by
For
Thus
14.11.5Exercise 68 - isomorphism condition
For
The source and target have equal dimension, so
14.12Part B
14.12.1Problem 1 - coefficient map
Let
14.12.1.1(a)
For coefficient columns
and
14.12.1.2(b)
If
so
Thus
14.12.1.3(c)
If
14.12.1.4(d)
An isomorphism is injective and surjective, so by (b) and (c) its list is linearly independent and spans
14.12.2Problem 2 - coordinate matrices for symmetrization
Let
14.12.2.1(a)
With
14.12.2.2(b)
For
14.12.2.3(c)
Solving
14.12.2.4(d)
The corresponding subspace of
with basis
14.12.2.5(e)
Solving
14.12.2.6(f) and (g)
The coordinate isomorphism sends
Hence the image of the
the same subspace as in part (d). Both are
14.12.2.7(h)
Using
14.12.3Problem 3 - a trigonometric vector space
Let
and
14.12.3.1(a)
For
So
14.12.3.2(b)
14.12.3.3(c)
For
Thus
14.12.3.4(d)
so
14.12.3.5(e)
Row reduction of
Therefore
14.12.3.6(f)
The coordinate vector of
14.12.4Problem 4 - products of vector spaces
14.12.4.1(a)
If
14.12.4.2(b)
Let
Then
so the listed vectors span. If their linear combination is
is a basis of
14.12.4.3(c)
The basis in (b) has
14.12.5Problem 5 - sum and intersection
Let
14.12.5.1(a)
14.12.5.2(b)
If
The map
14.12.5.3(c)
Since
14.12.5.4(d)
For three-dimensional subspaces of
Then
14.13Homework 7 — submitted work
Chapter 15Part A
15.14.3 Exercise 14
For
so
Hence
A basis for the kernel is
15.24.3 Exercise 28
For
This has full rank, so
15.34.3 Exercise 60
In
The submitted change-of-basis matrices are
and
15.45.1 Exercise 6
For
Thus
15.55.1 Exercise 17
For
Thus
15.65.1 Exercise 26
With
Chapter 16Part B
16.1Problem 1
For ordered bases
So
Taking
Consequently,
16.2Problem 2
For
so
The submitted interpretation is that it rotates every vector in
16.3Problem 3
Let
for each integer
Thus
For the false kernel claim, it takes
It records
but
For equal nullities, rank-nullity gives
The page proves
16.4Problem 4
For
The source diagram verifies
hence
For
and therefore
16.5Problem 5
For
The source chooses
so
16.6Problem 6
Let
With
The source uses
to obtain
16.7Homework 8 — submitted work
Chapter 17Part A
The assigned book exercises are 5.1: 45; 5.2: 14, 26; 5.3: 36; and 5.4: 26, 32.
17.15.1 Exercise 45
For
so
17.25.2 Exercise 14
For
It states that
17.35.2 Exercise 26
For
and
17.45.3 Exercise 36
For
giving
17.55.4 Exercise 26
For
Its reduced echelon form is
so
17.65.4 Exercise 32
For
The source gives
and
Chapter 18Part B
18.1Problem 1
For
18.1.1(a)
If
so
18.1.2(b)
If the basis is not perpendicular, some
by linear independence. Thus
18.2Problem 2
For the set
- •
(a) False.
, but is not orthogonal; the page gives , whereas its inverse is . - •
(b) True. The composition of the orthogonal maps represented by
has standard matrix , so . - •
(c) True by the same composition argument for
. - •
(d) True. If
were orthogonal but were not, with and , then , a contradiction. - •
(e) True.
gives ; gives , so is symmetric.
18.3Problem 3
For an orthonormal basis
and the calculation on the page is
For two orthonormal bases
so
18.4Problem 4
The submitted answers are:
- •
(a) True.
, from and double orthogonal complement. - •
(b) True.
, then rank-nullity gives . - •
(c) True.
and rank-nullity yield . - •
(d) True. With (b), (c), and
, . - •
(e) False.
but ; if they cannot be equal.
18.5Problem 5
18.5.1(a)
For
implies
18.5.2(b)
For a relation
if coefficients on both sides are nonzero then the equal nonzero vectors would belong to
18.5.3(c)
A pairwise orthogonal set with fewer than
18.6Problem 6
18.6.1(a)
The source applies Gram–Schmidt to full-rank
It takes the orthonormal basis matrix and the transpose of the upper factor, obtaining the stated QL factorization. The resulting lower factor is triangular with positive diagonal.
18.6.2(b)
The finished submission stops after the construction for (a); no visible proof for part (b) appears in the source PDF.
18.7Homework 9 — submitted work
Chapter 19Part A
The assigned exercises are 5.4: 27, 31; and 5.5: 15, 23, 32(a–d).
19.15.4 Exercise 27
The work observes that
19.25.4 Exercise 31
For the three points
The normal equations recorded in the submission are
and solving them gives
19.35.5 Exercise 15
For the bilinear expression in the exercise, symmetry requires
19.45.5 Exercise 23
With
the answer verifies the inner-product properties and gives the orthonormal basis
19.55.5 Exercise 32
For the weighted integral inner product
the computation in the submitted pages records
when
when
The associated polynomial sequence is recorded as
Chapter 20Part B
20.1Problem 1
The submitted solution finds the plane of best fit for the three displayed points by writing its normal-equation system. Its computed coefficient vector is
which is also plotted on the graph in the original submission.
20.2Problem 2
20.2.1(a)
For (i), the proposed expression is not an inner product: the work uses
which is nonzero while
20.2.2(b)
For (i), the weighted integral with weight
20.3Problem 3
Let
20.3.1(a)
The work finds
20.3.2(b)
The submitted orthonormalized functions are recorded approximately as
20.3.3(c)
For
and, after expansion,
20.4Homework 10 — submitted work
Chapter 21Part A
The assigned exercises are 6.1: 20, 54; 6.2: 42, 50; 6.3: 14; and 7.1: 12, 18, 42.
21.16.1 Exercise 20
By the row operations shown in the submission, the determinant of the given
for every
21.26.1 Exercise 54
The answer uses positivity to conclude that the determinant of the displayed
21.36.2 Exercise 42
For a QR factorization
so the determinant is positive.
21.46.2 Exercise 50
For the matrix whose
21.56.3 Exercise 14
The parallelepiped volume is found from the determinant. Since the displayed vectors are linearly dependent, the result is
21.67.1 Exercise 12
For
the characteristic equation gives eigenvalues
Thus it diagonalizes to
21.77.1 Exercise 18
For reflection in a plane, the plane is the
21.87.1 Exercise 42
The matrices in
The five matrix units in positions
Chapter 22Part B
22.1Problem 1
The proof shows that an alternating bilinear form
Conversely, antisymmetry gives
22.2Problem 2
Let
it computes
The determinant calculation is
which agrees with the determinant in any other basis. Finally, for
the only eigenvalue is
22.3Problem 3
The construction defines
It proves that
22.4Problem 4
The response uses the characteristic polynomial to find eigenvalues, and uses similarity to preserve the polynomial. It then applies the displayed eigenvector criterion to decide diagonalizability.
22.5Problem 5
For a
where the two summands lie in the
Advanced Linear Algebra
Chapter 23Review on Basic Concepts
23.1Subspace and direct sum
vector space 的 subset
- 1.
包含 0
- 2.
对 addition 和 scalar multiplication 闭合
两个 subset 的和就是各取一个元素相加的所有情况.
很显然我们知道:
Proposition 23.1
两个 subspace
且
显然可以随便和。同一个
我们显然发现:
Proposition 23.2
我们发现,其实可以 direct sum 的 subspaces 是 “垂直的”,意思是:
Theorem 23.1
并且:
Theorem 23.2
Remark
实际上两个 subspace 的交集里只要有一个非 0 点,那么这个点 span 的整个 dim 为 1 的线都在交集里.
Note
Chapter 24Linear functional and Duality
Definition 24.1 (Linear functional)
Chapter 25Eigenvalues and Operators
Chapter 26Operators on complex VS
Chapter 27Multilinear Algebra
Numerical Linear Algebra
Chapter 28tensor product and matrix multiplication
这里我们放弃陈述两个 over 同一 field 的 vector spaces 的 tensor product 的 algebraic definition,直接看应用的。(完整的 definition 是两个 over 同一个 ring 的 modules
Definition 28.1 ((not rigorous) Tensor product)
令
s.t. 对于
对于
Proposition 28.1 (representing tensor product as matrix)
如果我们有两个矩阵:
可以把它们的 tensor product
can verify:这个表示是符合 tensor product 的 bilinearity 的。
(我们可以把
Definition 28.2 (outer product of two vectors)
对于
28.1matrix product through outer product
Theorem 28.1 (representing matrix multiplication by outer products)
对于
Proof
In md.
Remark
两个 vectors 的 outer product,一定是一个 rank 为 1 的 matrix。因为它每一 column 都是
但是我们可以累加
Chapter 29orthogonal vectors and matrices
Definition 29.1 (adjoint(hermitian conjugate))
̂*:
(where each overline means complex conjuate.)
Remark
Can easily comfirm:
Definition 29.2 (standard inner product and norm on
The standard inner product:
The standard norm:
Remark
Note: It is actually
这是因为两个复数相乘等于长度相乘幅角相加,而 conjugate 的幅角是相反的,所以 conjugate 之间相乘等于幅角相互抵消,结果在 positive real axis 上,取开方得到长度。
而平方得到的则是一个转两次的幅角。
Remark
Can easily verifies:
且注意:By bilinearity,对于
Definition 29.3 (orthogonal, orthonomal vectors)
Say
Say
Say
Theorem 29.1 (orthogonal
orthogonal 的 vectors 一定 linearly independent。
Proof
trivial.
Corollary 29.1
orthogonal 的
29.1decomposing vector by an orthonormal set
Theorem 29.2 (decomposing vector by an orthonormal set)
给定
Claim:这个
Proof
注意:由于
我们在两边取和
并且由于
Remark
如果
对于 unit vector
现在我们引入另一个形式的 projection 表达:projection matrix
Theorem 29.3 (projection matrix)
对于任意的 unit vector
其中
Proof
In md.
Notice that this matrix is rank 1.
Remark
unitrary: 即
In real case, 它被称为 orthogonal matrix.
Theorem 29.4 (unitrary matrix 的充要条件)
Proof
显然,因为 unitrary
Theorem 29.5 (unitrary transfromation preserves inner product and length)
如果
并且自然得到
Proof
Follows from:
Remark
并不 preserve 自定义的 inner product,只 preserve standard inner product 和 standard norm.
Chapter 30norms
Definition 30.1 (norm)
一个 norm on a vector space
- 1.
nonnegativity (0 iff
) - 2.
trianglar ineq
- 3.
homogenity
的 function
30.1norms on
Example 30.1
以下为
Lp-norm:
weighted norm: 给定一个 norm
TODO (source 03-norms.tex, line 28): selected TeX refers to 01-fundamentals.assets/Screenshot 2025-01-29 at 22.41.10.png; the asset is not among the selected chapter sources.
TODO (source 03-norms.tex, line 29): selected TeX refers to 01-fundamentals.assets/Screenshot 2025-01-29 at 22.41.52.png; the asset is not among the selected chapter sources.
30.2operator norms on matrix spaces
We know: 所有的
所以我们当然也可以给 matrix 赋范。
matrix 代表一个 linear transformation,所以 norm 的意义实际上是它 stretch vector 的程度的一种评估。
Example 30.2
Definition 30.2 (Operator norm)
induced by vector norm. 表示它stretch vector 的最大程度。其中, source 和 image vector 分别用 norm n,m 来判定。
如果 source 和 image vector 的 norm 是一样的,比如都使用某个
(这更加常用,因为通常我们会对 source 和 image vector 的大小使用相同的评估)
Proposition 30.1 (diagonal matrix 的 norm: reduced to max diag element)
如果
其中
Proof
很直观。我们要把一个以
因而选择绝对值最大的
Proposition 30.2 (1-norm: reduced to max column sum)
matrix 的 1-norm 实则就是 1-norm 最大列的 1-norm.
Proof
因为
并且
并且我们发现,这个值是可以取到的: suppose
直观而言,由于 1-norm 的单位球和它的 image 都是一个多面体,它取到最大的点一定是某个顶点。以这里的
Proposition 30.3 (
matrix 的
Proof
直观上,image 的 sup norm 只取最大的那一个 entry,因而一定是取矩阵总(absolute)长度最大的一列, 因为每一列都只贡献 image vector 中的一个 entry。
并且,我们注意到,source vector (on单位球) 包括了所有的最大 entry 为
TODO (source 03-norms.tex, line 89): selected TeX refers to 01-fundamentals.assets/image-20250130003611232.png; the asset is not among the selected chapter sources.
Note: sup norm 的单位球和它的 image 也都是一个多面体。
30.3Caychy-Swartz and Frobeniu norm
Theorem 30.1 (Hölder inequility and Cachy-Swartz)
Let
Holder ineq:
Cauchy-Schwarz ineq(special case of Hölder ineq when
Remark
Holder’ ineq 可以 generalize 到
Proof
of Cauchy-Swartz:
By homogenity of inner product and norm, it suffices to prove for unit vector
因而
等号成立 iff
Example 30.3
Applying Cauchy-Swartz 可以发现: row vector 的 matrix 2-norm 等于它 (adjointed) 作为 vector 的 vector 2-norm.
这是因为 consider
Example 30.4
任取两个 vectors
这是因为:
即
Example 30.5
Theorem 30.2
(并且通常取不到等号.)
Proof
不证明了. Playing with definition 加上 Cauchy-Swartz.
Definition 30.3 (Frobenious norm)
等于把这个 matrix 展开为
Theorem 30.3 (equivalent form of Frobenius norm)
Proof
trivial.
Proposition 30.4
Proof
因为
因而:
(虽然这看起来很不对, 但容易验证, 这上下两个 sum 是相等的. )
Theorem 30.4 (unitrary matrix preserves 2-norm 和 Frobenius norm)
Let
Proof
因为
Frobenius norm:
Chapter 31SVD
SVD 的 motivation:一个 linear transformation 可以通过 unit sphere 的 image 来唯一确定。并且,这个 unit sphere 的 image 一定是一个 hyperellipse (高维椭圆)。
Definition 31.1 (principal semiaxes, Singular value)
对于一个 linear transformation
我们称
31.1reduced SVD
Chapter 32QR factorization
32.1projector
Definition 32.1
我们称一个 operator
Note: 不要求是 linear 的. For linear case, 这是一个idempotent linear map.
(而我们将主要关注于 linear orthogonal projector.)
Remark
一个 projector 总有:
对于任意
即:在第一次作用后,之后再对其结果进行这一映射不作出任何改变。
直观:这个映射的效果是把一个向量投影到一个低维度子空间上,从而,在作用过一次后,再次施加这一映射将没有任何改变。
Remark
对于 orthogonal 的 projector,我们称其为 orthogonal projector; 对于 non-orthogonal 的 projector,我们称其为 oblique projector.
Remark
projector 虽然不保证是 linear 的,但是要么是 linear 的,要么就是个 affine transformation. 和 linear 也差不多. 不用在意这些细节.
以下,我们都只考虑 projector linear 的情况. nonlinear 的情况是类似的.
Lemma 32.1
我们发现,一个 projector
Lemma 32.2
一个 projector 的 eigenvalue 只有可能是
其中
Lemma 32.3 (complement projector)
如果
我们称
并且我们有: complementary projector 的 ker 是原 projector 的 im, im 是原 projector 的 ker.
Remark
Theorem 32.1
一个 projector
Theorem 32.2
一个 projector
Corollary 32.1
orthogonal projector
32.2classical Gram-Schmidt orthogonalization
classical Gram-Schmidt 是计算 reduced QR 分解的算法.
TODO (source 05-qr-factorization.tex, lines 77–82): selected TeX includes the figure assets/Screenshot 2025-04-17 at 11.44.46.png, captioned reduced QR and labelled fig:reduced QR; the asset is not among the selected chapter sources.
32.2.1idea of triangular orthogonalization
classical Gram-Schmidt orthogonalization 的 idea 是: 我们逐列地将
具体: 我们每次都把
展开这个定义:
这个过程可以通过定义:
(Note that the sign of
从而这个过程写作:
我们发现:
这个过程使得:
从而:
32.2.2algorithm
Classical Gram-Schmidt (unstable)
FOR j = 1 TO n
v_j ← a_j
FOR i = 1 TO j-1
r_ij ← q_i* a_j
v_j ← v_j - r_ij q_i
ENDFOR
r_jj ← ||v_j||_2
q_j ← v_j / r_jj
ENDFOR32.3modified Gram-Shimitdt (triangular orthogonalization)
32.4Household Triangularization
Chapter 33Discrete Fourier transform and FFT algorithm
Chapter 34conditioning and stability
Source attribution in the selected TeX chapter title: doi:10.1137/1.9780898719574.ch3.
接下来 chapter 中我们将讨论 numerical analysis 中的两个 fundamental issues: Conditioning 和 Stability. Conditioning 指的是 perturbation behavior of a mathematical problem; 而 Stability 指的是解决这一问题的 algorithm 的 perturbation behavior.
Definition 34.1 (problem, problem instance)
我们把一个 problem 看作是一个 function, 把 normed VS
其中,这个 problem
Conditioning 研究的就是一个 problem instance
一个 well-conditioned problem instance 就是指,
34.1absolute/relative condition number of a problem
Definition 34.2 (absolute condition number)
来表示
定义 absolute condition number 为:
Remark
即,
我们发现,这和导数的定义很相近,就是加了一个 norm。当然,并不完全是。因为这里取的是
具体:我们发现,当
(这里使用 approx,但是可以严格证明.) 从而,如果
简写:
这里还有另外一个 condition number:
Definition 34.3 (relative condition number)
(recall:
即
Remark
它表示的是,对于
对于 differentiable
这里对于 absolute/relative condition number 有一种不严谨的记法: 我们把
Example 34.1
问题 1.
well-conditioned.
问题 2.
well-conditioned.
TODO (source 07-conditioning-and-stability.tex, lines 70–73): selected TeX includes assets/condition1.png; the asset is not among the selected chapter sources.
34.1.1examples: 两数相减
Example 34.2
问题 3:
For simplicity, 取
如果
For example:
它们的差:
如果浮点数只能保留 7 位有效数字 (单精度), 那么
34.1.2example: polynomial 求根
Example 34.3
问题 4: polynomial 求根.
我们考虑
如果 coefficient
从而对于这个问题:
证明 selected-TeX label perturbation of a root given perturbation of a coeff: (非 rigorous)
perturbed polynomial 即:
我们要求的 perturbation
即:
从而:
Using Taylor expansions:
其中
从而得到
Polynomial rootfinding 是 ill-conditioned, 即便不涉及 multiple roots 问题. 比如经典的 “Wilkinson polynomial”:
它的 most sensitive root 是
TODO (source 07-conditioning-and-stability.tex, lines 138–143): selected TeX includes assets/Screenshot 2025-04-15 at 00.21.49.png, captioned Wilkinson's example 中 roots 的 perturbation, by $tilde(a)_k = a_k(1 + 10̂(-10) r_k)$ and labelled fig:wilkinson-root-perturbation; the asset is not among the selected chapter sources.
34.1.3example: matrix 乘 vector
这个 example 分为三部分:
- 1.
Fixing
, - 2.
Fixing
, inverse problem: - 3.
fixing
,
Example 34.4
Matrix-vector multiplication:
即:
Note: 对于任意非零
所以
(2) Inverse problem: given
因而我们把
Definition 34.4 (Condition number of a matrix)
我们定义 condition number of a matrix:
Notice: 如果
where
对于
即 image of the unit sphere 作为 hyperrellipse 的 eccentricity.
Remark
我们已经知道了,对于
那么等号在什么时候取到呢? 我们以 forward problem 为例: 取
- 1.
unitary, - 2.
- 3.
我们令
所以
这个最大值就是:
这在
即,当
同理,对于 inverse problem,令
其中
最大值发生在
因此
即,当
至此,我们可以总结这个 theorem (a general version of Theorem 12.2 in textbook Ch12):
Theorem 34.1 (conditioning of matrix times vector)
For problem
并且,对于 forward problem,等号当且仅当
现在我们来考虑: Fixing
我们有:
我们知道
By matrix norm 小于等于拆分后 norms 的乘积的定理,我们于是有:
即
于是我们得到
神奇地发现,它也被
并且, equality in this bound will hold whenever
而,我们可以发现对于任意
是一个从
我们可以证明这个 supremum 可以达到. 选择
其中
从而我们可以得到这个结论:
Theorem 34.2 (conditioning of matrix times vector: given
对于
34.2float number and machine epsilon
34.2.1float number system
我们知道计算机处理的是离散的数值. 即,一个 computer 的 number system 并非
这个
- 1.
base integer
- 2.
precision integer
(通常
precision 决定了这个系统的对数字表示的相对精度 (即即将定义的 machine epsilon); biased exponent 决定了这个系统能够表示的数的范围的上下限.
从而,
这里的
现实中,
TODO (source 07-conditioning-and-stability.tex, lines 297–302): selected TeX includes assets/Screenshot 2025-04-15 at 10.56.30.png, captioned IEEE and labelled fig:ieee-double-precision; the asset is not among the selected chapter sources.
IEEE double precision:
因而更加现实的 system
- 1.
还要包括一个额外的参数: exponent offset
, 控制 bounded by some 和 . - 2.
现实的 ieee standard 和我们的 ideal 模型
不同的点, 不仅是 bounded 具有 和 , 还有: 它的每个数其实是 而不是 . 前面的 称为 leading bit. 这是因为在规格化二进制浮点数系统中, 所有非零数的尾数都可以唯一表示成以 开头的形式. 因为这个 总是存在, 可以省略它来节省空间. - 3.
考虑更多的 symbols, 例如:
Note:
Definition 34.5 (machine epsilon)
对于一个 discrete number system
为什么要这样定义: 因为这两点:
Proposition 34.1
对于任意的
这一点是显然的. 任意的大小不能过大的实数,都可以在 machine epsilon 的误差内被 float number 表示.
更加好的是:
Theorem 34.3 (Fundamental Axion of Floating Point Arithmetic)
对于一个 discrete number system
such that:
for 任意的
(Exclusion: relative error 并不包括
即:任意基本运算的相对于自身的误差,都被 bound 在
为什么是相对误差而不是绝对误差? 因为我们能表示的有效数字位数是固定的. 越大的数,其小数点后的有效数字就越小. 从而,绝对误差就越大. 但是相对误差仅和
(Note: On a computer in which intermediate quantities are truncated rather than rounded, Fundamental Axion of Floating Point Arithmetic hold with
Remark
之所以 Float number 的讨论是重要的,因为它是计算机用来近似表示一个实数的方法,而所有的数值计算都要经由此为媒介. 需要注意的是:ultimate access to numbers is via +,−,⋆,÷, 复杂度和误差最终由基本运算衡量.
对于 losing 1 bit 的 round off error 等问题,我们并不在意; 但是,当大量计算 iteratively 堆叠时,一些 first algorithms for many problems might lose half the bits. 这是一个很大的数量: 例如 Classical Gram Schmidt 会失去 half the digits, 相比 modified Gram-Schmidt 而言. 例如, accurate bits 从 52 变为 26.
因而,基于 float number (via machine epsilon) 对一个 algorithm 的 stability 进行分析是重要的. 接下来我们将讲解 stability of an algorithm 这个概念.
34.3stability
Review: 一个 Problem (in our def) 是一个 function
而我们现在定义什么是一个 algorithm:
34.3.1def: algorithm, stability, accuracy
Definition 34.6 (algorithm)
一个 algorithm for a problem
定义上就是这么简单.
注意: 我们这里的 algorithm 是一个比较 restricted 的定义. Specially, 它并不考虑 randomized algorithms.
Example 34.5
Randomized rounding:
把
我们把 round 得到的结果标记为
这个 rounding 是一个 algorithm, 但是不包含在我们这里的定义里. 因为原问题是
因而我们的定义其实是 restricted 的. 我们这里只考虑 determinstic 的 algorithm.
Definition 34.7 (accuracy of an algorithm)
给定一个 problem
即: algorithm 给出的答案和正确答案的相对 difference.
如果对于每个
即 relative error is on the order of machine epsilon, 那么我们称这个 algorithm 是 accurate 的.
Problem: 对于一个 well-conditioned 的问题,我们自然地想要一个足够 accurate 的 algorithm; 但是对于 ill-conditioned 的问题,要求给出一个足够 accurate 的 algorithm 是很困难的事情,因为 perturbations on ill-conditioned inputs 使得它给出准确结果的难度很大.
因而,generally, 我们应该放低要求.
Definition 34.8 (stability of an algorithm)
给定一个 problem
能够使得
那么则称,这个 algorithm
Remark
显然,stable 是比 accurate 稍微宽松的要求. 它的要求是: 这个 algorithm gives nearly the right answer to nearly the right question. 比起 accurate, 它放宽在于: 不需要 solve exactly the same question, 只需要 solve 一个很相近的 question 就可以了.
为什么要这样要求? 因为一个计算机很大的问题是: 我们的 input 和理论上的 input 还是不一样的. 比如,我们要输入一个
从而,我们需要对 input 放宽,尽可能去容忍类似于 round up 这样的问题.
这个时候我有一个问题: stable 这个概念,相比于 accurate,是为了迁就 ill-conditioned 的问题,只要保证我们的算法给出的结果一定是原问题周围某个相似的问题的数值解就可以了. 但是如果这个 problem 是 ill-conditioned,那么原问题的解可能和它周围的其他问题的解差别非常大. 一个 stable 但不 accuratae 的 algorithm,意思就是: 在某些 ill-conditioned 的 input 上,给出的解和我们想要的原问题的解差别非常大,那这个算法还能成为好吗?
这就是数值分析的核心哲学问题之一. stability 已经是一个足够的条件,因为你并不能要求算法给你“一个问题本身都无法承诺”的东西. Stable algorithm 是对现实的诚实反应,承认输入的不可避免误差,并保证: 你得到的结果是“某个微小扰动问题”的真实答案. 它告诉你: 在你所能拥有的误差范围内, 这就是最合理的答案了. 稳定性 = 不人为放大错误.
之所以我们只要求算法的稳定性,就是因为: 如果非要要求准确性,那么很多优秀的 algorithm 可能会因为仅仅几个 problem 本身就 ill-condtioned 的点上的大误差,被判为 inaccurate.
还有一个比 stable 更强的定义
Definition 34.9 (backward stability)
给定一个 problem
能够使得
backward stable 的要求是: 这个 algorithm gives exactly the right answer to nearly the right question. 它蕴含的信息是: 对于这个算法
backward stable 和 accurate 是 dual 的: accurate 要求的是这个 algorithm gives nearly the right answer to the right question.
Remark
这些定义里面的
Example 34.6
我们用一个例子来阐明 “
problem: 给定
Formally: 对于任意的
使得
这个
Remark
对于 finite dimensional NVS 而言,我们不需要关注使用的是哪个 norm,因为我们知道,finite dimensional NVS 上所有 norms 都是 topologically equiv 的. 这个等价在这里对 asympototic bound 的讨论中很有用,因为 topologically equiv 即: 对于任意两个 norms
因而,对于 finite dimensional NVS 而言,如果任意一个 norm 满足
那么任意的 norm 都满足这一点.
34.3.2example: floating point arithmetic
Example 34.7
当然,四种 floating point arithmetic 是有 backward statble 的算法的.
我们以两数相减 from
其中,
where by def,
并且我们知道, float 减法的 error 也是 within machine epsilon 的:
从而
where
我们把
从而,这个 canonical algorithm 计算出的是:
where for all
Remark
值得提的是: 两个数相加的问题
34.3.3example: inner/outer product
For inner product: problem is
显然, canonical algorithm: compute the pairwise products
这个算法是 backward stable 的.
但是, for outer product: problem is
我们想要计算
Canonical algorithm: compute the
它是 stable 的,但却不是 backward stable 的. 因为直观而言: 我们每个 entry 的计算有不同的乘法误差,导致:
Remark
对于 solution space
34.3.4theorem: what backward stabililty implies about the accuracy
Theorem 34.4
Suppose a backward stable algorithm is applied to solve a problem
(notice: 这说明如果
Proof
By backward stability, we have
我们把
而由于这里
这个不等式是因为:
这一 theorem 表明: backward stability + good conditioning
Chapter 35backward error analysis of NLA algorithms
Source attribution in the selected TeX chapter title: doi:10.1137/1.9780898719574.ch3.
我们在上一个 Ch 中介绍了 conditioning 和 stability. 现在我们用它们对经典的 NLA algorithms 进行 backward error analysis.
35.1Stability of Householder Triangularization
我们 set
R = triu (randn(50));
[Q,X] = qr(randn(50));
A = Q*R然后我们再对
[Q2,R2] = qr(A);
norm (Q2 - Q);
ans = 0.00889
norm (R2-R) / norm(R);
ans = 0.00071我们发现
但是,当我们用这个
norm (A - Q2*R2) / norm(A);
ans = 1.432e-15我们发现一个惊人的事实: 这个 QR 分解的 error