If $A, B, C$ are $n \times n$ matrices, where both $B$ and $C$ are nonsingular, and $b$ is a vector of length $n$, how would you compute the following without computing any inverses?
$$x = B^{-1}(2A+I)(C^{-1}+A)b$$
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ This seems like a typical homework question in an introductory NA course. If you are having trouble with it, could you please expand on what you don't understand, instead of just posting the question statement? $\endgroup$– KirillCommented Feb 12, 2017 at 19:37
-
$\begingroup$ @Kirill I mainly don't understand where to start. Does the solution to this involve LU decomposition? The without computing any inverses part is just throwing me off completely. $\endgroup$– Bob MarleyCommented Feb 12, 2017 at 19:41
-
3$\begingroup$ A hint: Calculating $x = M^{-1}y$ is equivalent to solving (for $x$) the linear system $Mx = y$ (using, for example, the LU decomposition of $M$). $\endgroup$– GoHokiesCommented Feb 12, 2017 at 19:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
As was mentioned in the comment, calculating $x=M^{-1}y$ is equivalent to solving $Mx=y$. Here is the full solution:
First, you can reformulate the equation to:
$Bx=(2A+I)(C^{-1}+A)b$, and by defining $\tilde{b}=C^{-1}b$, the equation can be rewritten as:
$Bx=(2A+I)(I+AC)\tilde{b}$.
First, compute $\tilde{b}$ by solving (using, for example, LU decomposition for $C$):
$C\tilde{b}=b$. Now, once $\tilde{b}$ is computed, you can define $h=(2A+I)(I+AC)\tilde{b}$ and solve, using LU decomposition,
$Bx=h$
$\begingroup$
$\endgroup$
0
$$\rm x = B^{-1} (2A + I) (C^{-1} + A) b$$
Left-multiplying both sides by $\rm B$,
$$\rm B x = (2A + I) (C^{-1} + A) b$$
Let $\rm y:= C^{-1} b$. Hence,
$$\rm B x = (2A + I) (C^{-1} b + A b) = (2A + I) (y + A b) = (2A + I) y + (2A + I) A b$$
and, thus, we obtain a linear system of $2n$ equations in $2n$ unknowns
$$\begin{bmatrix} \mathrm B & -(2 \mathrm A + \mathrm I)\\ \mathrm O& \mathrm C\end{bmatrix} \begin{bmatrix} \mathrm x\\ \mathrm y \end{bmatrix} = \begin{bmatrix} (2 \mathrm A + \mathrm I) \mathrm A \mathrm b\\ \mathrm b\end{bmatrix}$$
which can be solved using Gaussian elimination.