Write and let . The stated Euclidean norm givesTaking nonnegative square roots proves . At this is equality. This is a contraction bound in the transformed coordinates; an arbitrary nonorthogonal does not give the same unit-constant bound for the original error norm.
For the spectral error bound for a diagonalizable fixed-point iteration, the exact solution is a fixed point: . Subtracting it from the iteration gives the error recurrence , with . Multiplying by and using givesIterating proves , including because . This argument does not assume is orthogonal; it simply expresses the error in an eigenbasis.
Update the unknowns in row order, immediately using newly computed components. The component equations areThus and . Using only old values in all three row equations would instead describe the Jacobi method, not the Gauss-Seidel method.
The image of a linear map of is exactly the one-dimensional span of : its formula always returns a multiple of , and . Hence .
The rank-nullity theorem gives . Since by (e)(i), . This includes the case , where the complementary projector is zero.
For a sum of mutually orthogonal projectors, orthonormality gives for and one for . Therefore equals zero for different indices and for equal indices. Expanding the finite sum yieldsThus every stated partial sum is a projector. Its image of a linear map is the span of the first orthonormal set of vectors; arbitrary sums of idempotent matrices would not have this conclusion.
Set . Since , the previous result applies to this projector and gives . Substituting proves . These are the kernel-image identities for complementary projectors.
Conversely, if , then , which explicitly writes as an image of a linear map under . Hence . The two inclusions prove . No orthogonality assumption was used.
A triangular matrix has determinant equal to the product of its diagonal entries, so and . A permutation matrix exchanging two rows has determinant . Using multiplicativity of the determinant in yields . Hence .
Apply the same permutation to the right-hand side and solve two triangular systems. Forward substitution in givesso . Back substitution in gives , , and . Therefore . Substitution in the original system returns , as required.
Eliminate the first column using multipliers and . The two residual rows have second entries zero and four, so interchange their order for the next pivot. One resulting Pivoted LU decomposition isThe factors below the first pivot must follow the permuted row order, which is why contains before . Direct multiplication gives rows , and in both and . This checks the permutation convention rather than confusing with a different placement of .
For the specified row and column, expand the two matrix products and reorder only finite sums:The middle equality uses scalar associativity and distributivity, and the interchange of two finite sums. Together with their equal dimensions, equality of every entry proves .
The product is , so multiplying it by the matrix gives an matrix. The product is , so multiplying it on the left by the matrix also gives an matrix. Both multiplications have matching inner dimensions.
For the equal-cardinality basis criterion, because spans , repeatedly remove a vector whenever it is a linear combination of the others. Such a removal does not change the span. The finite process ends with a linearly independent spanning subset , hence a basis of .
If the original were linearly dependent, at least one removal would occur and . But a basis of an -dimensional vector space has vectors. Equivalently, apply the allowed claim to the basis and any fixed -vector basis of : the latter would wrongly be linearly dependent. Thus no removal was possible. The original spanning set is linearly independent and therefore a basis.
The supplied factors give . Back substitution in yields and , soMultiplying by the original matrix gives , so this least-squares minimizer has residual zero: this particular overdetermined system is exactly consistent. Full column rank still guarantees uniqueness of the minimizer.
Substitution gives . Since is invertible, cancel it on the left to obtain the nonsingular triangular systemThis is the reduced QR least-squares solution. Its geometric justification is the orthogonal decompositionThe second term is independent of , while invertibility of lets the first term be zero at exactly one point. Although , one must not replace by : is tall and its product is the orthogonal projection onto its column space.
The normal equations for linear least squares areThe supplied QR decomposition gives full column rank because is invertible and . Hence, for every nonzero , . Thus is a symmetric positive-definite matrix and the displayed square system is nonsingular.
From the zero initial vector, the linear-system residual is . Then , , and . The step is , givingAs a check, the new residual is , orthogonal to the preceding residual as expected after this exact line search. It is nonzero, so one iteration has not already solved the system.
Real symmetry and positive definiteness are sufficient, and the preceding parts establish both properties for this matrix. If a residual becomes zero, stop: the solution has been reached and the displayed step quotient should not be evaluated as .
For a convergence justification, let solve , let , and let . The quadratic energy error is . Moving by , with , is exact line search for a positive-definite quadratic and givesWriting for the extreme eigenvalues, one has and . ThereforeThe factor lies below one, so the energy tends to zero and positive definiteness forces . Here the bound is , since the eigenvalues are 1 and 11. This proves convergence for every initial vector, rather than merely checking one numerical iteration.
There are unlisted articles, also show them or only show them.