Question

LU be an LU factorization of matrix A e Fn×n computed by the Gaussian elimination Let PA with partial pivoting (GEPP). Let us denote Prove that (a) leyl 1, for all i >j S 2-1 maxij laijl You may assume P-1, i.e., in each step of the Gaussian elimination process the absolute value of the diagonal entry is already the largest among those of the entries below the diagonal entry on the same column You may prove the results with n4, but you are encouraged to work with a general n Hint: Let A(kLk-1 LiA. Try to bound the absolute values of the entries of ALAk) by induction

Answer 1

"A = [a_ij]_i, j = 1, 2, Ellipsis n, L = [l_ij]_i, j = 1, 2, Ellipsis n U = [u_ij]_i, j = 1, 2, Ellipsis n we apply partial pivoting on A and get PA = LU Here given that P = I (Identify matrix) (a) for partial pivoting we rearrange the matrix A such that the largest entry of that column is chosen as the pivot So, obviously the pivot element forced the entries of L to have magnitude not exceeding 1 Hence