A direct method for solving a linear system of equations is an algorithm that, neglecting rounding errors, determines the exact solution in finitely many steps. The algorithms are often based on a multiplicative decomposition of the matrix \(\varvec{A}\) of the linear system into two matrices of the form \(\varvec{A} = \varvec{BC}\) , where the matrices \(\varvec{B}\) and \(\varvec{C}\) are either easily invertible or at least matrix-vector products with the inverse of these matrices can be easily computed. First, we will consider the LU factorization of a matrix with and without pivoting and examine its existence and uniqueness. Subsequently, we present three different approaches for computing a QR decomposition: the Gram-Schmidt process, the Givens method, and the Householder transformation. Nowadays, however, direct methods are rarely used for the immediate solution of large linear systems of equations. However, they are often used in an incomplete form as preconditioners within iterative methods and for solving subproblems.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Direct Methods

  • Andreas Meister

摘要

A direct method for solving a linear system of equations is an algorithm that, neglecting rounding errors, determines the exact solution in finitely many steps. The algorithms are often based on a multiplicative decomposition of the matrix \(\varvec{A}\) of the linear system into two matrices of the form \(\varvec{A} = \varvec{BC}\) , where the matrices \(\varvec{B}\) and \(\varvec{C}\) are either easily invertible or at least matrix-vector products with the inverse of these matrices can be easily computed. First, we will consider the LU factorization of a matrix with and without pivoting and examine its existence and uniqueness. Subsequently, we present three different approaches for computing a QR decomposition: the Gram-Schmidt process, the Givens method, and the Householder transformation. Nowadays, however, direct methods are rarely used for the immediate solution of large linear systems of equations. However, they are often used in an incomplete form as preconditioners within iterative methods and for solving subproblems.