(Solved): lu decomposition, flop count, matlab Suppose A has a LU decomposition. We can use this decomposition ...

Suppose $$A$$ has a LU decomposition. We can use this decomposition to solve linear systems in a slightly more efficient way. In particular, given $$A\mathrm{x}=\mathbf{b}$$ we can use the LU decomposition of $$A$$ to arrive at $$LU\mathbf{x}=\mathbf{b}.$$ Now we introduce an intermediate vector $$\mathbf{y}=U\mathbf{x}$$. This intermediate vector divides our method of solving the linear system into two steps: 1. Solve $$L\mathbf{y}=\mathbf{b}$$ for $$\mathbf{y}$$ by forward substitution. 2. Solve $$U\mathbf{x}=\mathbf{y}$$ for $$\mathbf{x}$$ by backward substitution. "What is forward substitution?" you may ask. It is precisely the same method as backward substitution, except now your coefficient matrix is lower-triangular and so you start by solving the first equation in your linear system and work down the hierarchy of equations. Here's a MATLAB code that performs forward substitution on a lower-triangular, augmented matrix: \% Forward substitution on a $$\mathrm{m}$$ by $$\mathrm{m}+1$$ lower triangular matrix L. $$[\mathrm{m},\mathrm{n}]=\mathrm{size}(\mathrm{L})$$ $$\mathrm{x}=\mathrm{L}(:,\mathrm{n});$$ \% Initialize column vector of unknowns (to be updated). $${}^1$$ Here, $$a$$ and $$b$$ are real numbers that are much smaller in size than $$1/?$$ but much larger in size than $$?$$. $$x(1)=L(1,n)/L(1,1);\%$$ Solve first equation of augmented matrix. for $$i=2:m\%i$$ counts up from 2 to $$m$$ in intervals of 1 . SUM $$=0;$$ for $$j=1:i?1$$ SUM $$=$$ SUM $$+L(i,j)?x(j)$$; end $$x(i)=(L(i,n)?SUM)/L(i,i);\%$$ Updates the ith entry of $$x$$. end $$x\%x$$ is the solution of the linear system. a. Compute the flop count of forward substitution. Please show the major steps of your calculation. b. Compute the flop count of solving the linear system using the LU decomposition of $$A$$. (This will be the sum of flops for both the forward and backward substitution steps.) Please use results from your previous homework. c. Based on your answers to (b) and previous homework questions, which of the following is more expensive: solving a linear system by Gaussian elimination or solving a linear system by LU decomposition, assuming the decomposition is known ahead of time? Remark: Of course, the LU decomposition is not usually known ahead of time, and it requires just as many flops to compute as it does to perform Gaussian elimination. However, once you've computed the LU decomposition once, you know it for all time. Thus, if you happen to be solving $$A\mathrm{x}=\mathrm{b}$$ for several different $$\mathbf{b}$$, you can use Gaussian elimination to determine the LU decomposition and then use this decomposition to solve your systems. Doing so requires fewer flops than using Gaussian elimination to solve each system.