Direct methods for solving Ax_k = b_k, where A is an n times n matrix and there

Question

Direct methods for solving Ax_k = b_k, where A is an n times n matrix and there are 1000 vectors b_k and some number of unknown vectors x_k Be able to compare the efficiency (order of operations) of using each method to solve for Gaussian Elimination for each k LU decomposition and back-substitution for each k LU decomposition once, and back-substitution for each k calculating the inverse A^-1 and multiplying x_k = A^-1 b_k for each k. QR decomposition once and back substitution with R for each k. How is the choice of method impacted by the condition number of A?

Explanation / Answer

1)Gaussian elimination requires 2(n^3)/3 operations for a system of n equations and n unknowns. so it has an arithametic complexity of O(n^3).

2)LU decomposition and back substitution is more efficient in solving n set of simultaneous linear equations with same coefficient matrix.A.The computational time is propotional to (4(n^3)/3).

But for gaussian elimination the computational time is propotional to((n^4)/3).

so when n=1000, guassian elmination will take (1000/4)=250 times the computational time taken by LU decomposition.

3)Calculating (A inverse) and multiplying

calculation of (A inverse) can be done by guass elimination or by LU decomposition.. Its computational time is described above

Multiplication time will also get added up so this method takes more computational time.

QR decoposition and back sustitution

This method will have a computational time equal to (2(n^3)+3(n^2)) .because this method involves QR factorization with omputational time  2(n^3). and matrix vector multiplication with computational time (2(n^2)). and back substitution with computational time (n^2).

condition number: If the condition number is high, then it is called ill conditioned and we get inaccurate solutions while solving .if the condition number is high then algorithms that solve the functions doesnot have backward stability.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.