0
$\begingroup$

Here is an excerpt from the book 'Applied Numerical Linear Algebra' by James W. Demmel from SIAM

But I have done it slightly different taking $\hat{l}_{ij}$ and $\hat{u}_{ij}$ and ended up getting $|{E}_{ij}|\leq n\epsilon_m(|\hat L|\cdot |\hat U|)_{ij}.$

$A\in \mathbb{R}^{n\times n}$
Also $\hat{A}=\hat{L}\hat{U}$ and $E=\hat{A}-A$.
The $LU$ decomposition is performed using the following equations : \begin{alignat*}{3} & & l_{ij} & =\dfrac{a_{ij}-\sum_{k=1}^{j-1}l_{ik}u_{kj}}{u_{jj}}\qquad i>j\\ &\mathrm{and} & & \\ & & u_{ij} & =a_{ij}-\sum_{k=1}^{i-1}l_{ik}u_{kj}\qquad\quad i\leq j \end{alignat*} $ $
We know that fl$(\sum_{k=1}^{p}x_ky_k)$=$\sum_{k=1}^{p}x_ky_k(1+\delta_k)\qquad$ where $|\delta_k|\leq p\epsilon_m$

Using that we get \begin{equation} \hat{u}_{ij}=\big(a_{ij}-\sum_{k=1}^{i-1}\hat{l}_{ik}\hat{u}_{kj}(1+\delta_k)\big)(1+\delta^\prime) \end{equation} with $|\delta_k|\leq (i-1)\epsilon_m$ and $|\delta^\prime|\leq \epsilon_m$
Then we get \begin{alignat*}{4} & a_{ij}\>\> & = & \>\>\frac{1}{1+\delta^\prime}\hat{u}_{ij} \hat{l}_{ii} & + &\sum_{k=1}^{i-1}\hat{l}_{ik}\hat{u}_{kj}(1+\delta_k)\qquad\text{Since } \hat{l}_{ii}=1\qquad\\ & & = & \>\>\sum_{k=1}^{i}\hat{l}_{ik}\hat{u}_{kj} & + &\sum_{k=1}^{i}\hat{l}_{ik}\hat{u}_{kj}\delta_k \qquad \qquad\qquad\qquad\qquad \end{alignat*} $\mathrm{where\>\>} |\delta_k|\leq (i-1)\epsilon_m \mathrm{\>and\>} 1+\delta_i=\tfrac{1}{1+\delta^\prime}$
Hence we get $E_{ij}=-\sum_{k=1}^{i}\hat{l}_{ik}\hat{u}_{kj}\delta_k\qquad\qquad$ when $i\leq j$
And for $i\leq j$ \begin{alignat*}{3} & |E_{ij}|\> & = |\sum_{k=1}^{i}\hat{l}_{ik}\hat{u}_{kj}\delta_k| & \leq\sum_{k=1}^{i}|\hat{l}_{ik}||\hat{u}_{kj}||\delta_k|\\ & & & \leq\sum_{k=1}^{i}|\hat{l}_{ik}||\hat{u}_{kj}|n\epsilon_m\\ & & & =n\epsilon_m(|\hat{L}|\cdot |\hat{U}|)_{ij} \end{alignat*}$ $
Similarly for $l_{ij}$ we get \begin{equation} \hat{l}_{ij}=\dfrac{(1+\delta^\prime)(a_{ij}-\sum_{k=1}^{j-1}\hat{l}_{ik}\hat{u}_{kj}(1+\delta_k))}{\hat{u}_{jj}}(1+\delta^{\prime\prime}) \end{equation} with $|\delta_k|\leq (j-1)\epsilon_m, |\delta^\prime|\leq\epsilon_m$ and $|\delta^{\prime\prime}|\leq\epsilon_m$
Solving for $a_{ij}$ we get \begin{alignat*}{3} & a_{ij} & = & \dfrac{1}{(1+\delta^\prime)(1+\delta^{\prime\prime})}\hat{l}_{ij}\hat{u}_{jj}+\sum_{k=1}^{j-1}\hat{l}_{ik}\hat{u}_{kj}(1+\delta_k)\\ & \qquad & = & \sum_{k=1}^{j}\hat{l}_{ik}\hat{u}_{kj}+\sum_{k=1}^{j}\hat{l}_{ik}\hat{u}_{kj}\delta_k\qquad\mathrm{where\>\>} 1+\delta_j=\dfrac{1}{(1+\delta^\prime)(1+\delta^{\prime\prime})} \end{alignat*}$ $
Therefore we get $E_{ij}=-\sum_{k=1}^{j}\hat{l}_{ik}\hat{u}_{kj}\delta_k\qquad$ when $i>j$ with $|\delta_k|\leq n\epsilon_m$
Hence for $i> j$ \begin{alignat*}{3} & |E_{ij}|\> & |\sum_{k=1}^{j}\hat{l}_{ik}\hat{u}_{kj}\delta_k| & \leq\sum_{k=1}^{j}|\hat{l}_{ik}||\hat{u}_{kj}||\delta_k|\\ & & & \leq\sum_{k=1}^{j}|\hat{l}_{ik}||\hat{u}_{kj}|n\epsilon_m\\ & & & =n\epsilon_m(|\hat{L}|\cdot |\hat{U}|)_{ij} \end{alignat*} $ $
$\therefore$ we get \begin{equation} |E_{ij}|\leq n\epsilon_m(|\hat{L}|\cdot |\hat{U}|)_{ij}\qquad\qquad\hspace{17em} \end{equation}$ $

Have I done it correctly?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.