write a function to solve the system Ax=b where A is a positive definite matrix
ID: 3880994 • Letter: W
Question
write a function to solve the system Ax=b where A is a positive definite matrix using the functions forward_subs, back_subs, and cholesky_factor
def solve_system (A, b, nargout-l): x = np. zeros (b. Shape) Replace this comment with code - write a function to solve the system Ax-b, where A is a positive definite matrix - use the functions forward_subs, back_subs, and cholesky_ factor - the function should return the solution vector x - The function should work for square matrices of any size return (x)Explanation / Answer
Solving equations with positive definite A
Ax = b (A positive definite of order n)
Algorithm
• factor A as A = LLT
• solve LLT x = b – forward substitution Lz = b – back substitution LT x = z
Cost: (1/3)n3 flops
• factorization: (1/3)n3
• forward substitution: n2
• backward substitution: n2
Inverse of a positive definite matrix
suppose A is positive definite with Cholesky factorization A = LLT
• L is invertible (its diagonal is nonzero; see lecture 4)
• X = LTL1 is a right inverse of A:
AX = LLTLTL1 = LL1 = I
• X = LTL1 is a left inverse of A:
XA = LTL1LLT = LTLT = I
• hence, A is invertible and
A1 = LTL1
Summary
if A is positive definite of order n
• A can be factored as LLT
• the cost of the factorization is (1/3)n3 flops
• Ax = b can be solved in (1/3)n3 flops
• A is invertible: A1 = LTL1
• A has a full range: Ax = b is solvable for all b
• A has a zero nullspace: xTAx > 0 for all nonzero x
Cholesky factorization
every positive definite matrix A can be factored as
A = LLT
where L is lower triangular with positive diagonal elements
Cost: (1/3)n3 flops if A is of order n
• L is called the Cholesky factor of A
• can be interpreted as ‘square root’ of a positive define matrix
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.