From a3fb090ff96fc67ee054b15da005126ef578894c Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Thu, 26 Aug 2021 13:43:23 -0400 Subject: notes from math classes --- li/02_solving | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 li/02_solving (limited to 'li/02_solving') diff --git a/li/02_solving b/li/02_solving new file mode 100644 index 0000000..ae67d6b --- /dev/null +++ b/li/02_solving @@ -0,0 +1,40 @@ +Ax = b where A = mxn, x = 1xm, b = 1xn. x_i and b_i are defined to be in +the ith row of their corresponding vectors. + +If C is an invertible mxm matrix, CAx = Cb is equivalent to Ax = b. +(1) + If x_0 satisfies Ax_0 = b, CAx_0 = Cb is satisfied. +(2) + If x_1 satisfies CAx_0 = Cb, C^{-1} CAx_0 = C^{-1} Cb \to Ax_0 = b + is satisfied. + +(I believe this proof requires associativity) + + LU Decomposition/Factorization + +Goal: Factorize A into a lower triangular and upper triangular matrices +L and U respectively. (These are very non-unique) + +A = LU. Conventionally, L is mxm, and U is mxn. +Ax = b ---> LUx = b ---> Y = Ux, LY = b. + +If we assert that L is an invertible matrix (e.g. ones down the +diagonal), this is trivial to solve + 1 0 0 y1 b1 +( c21 1 0 ... ) * ( y2 ) = ( b2 ) + c31 c32 1 y3 b3 + ... ... ... +Y has a unique solution by construction. ( ex: y1 = b1, c21*y1 + y2 = b2 ...) + +U is upper triangular, meaning that it is strictly zero below the +diagonal started at the top-left. (However, we have no control over the +values of the diagonal or the values above the diagonal) + +[Note] How do we ensure that L and U retain the properties of the +original matrix's solution? (i.e. not just matrices of zero) + +Using a series of row operations (written as invertible matrices C_1, +C_2, ..., C_k -- that is, adding a multiple to a lower row) will turn A +into echelon (upper triangular), and C_1^{-1}C_2^{-1}*...*C_k^{-1} = L +(lower triangular). U is not reduced-echelon, but it is echelon/upper +triangular. -- cgit