Editing Cholesky decomposition (section)

=== Stability of the computation ===
Suppose that there is a desire to solve a [[condition number|well-conditioned]] system of linear equations. If the LU decomposition is used, then the algorithm is unstable unless some sort of pivoting strategy is used. In the latter case, the error depends on the so-called growth factor of the matrix, which is usually (but not always) small.

Now, suppose that the Cholesky decomposition is applicable. As mentioned above, the algorithm will be twice as fast. Furthermore, no [[Pivot element|pivoting]] is necessary, and the error will always be small. Specifically, if {{math|1='''Ax''' = '''b'''}}, and {{math|'''y'''}} denotes the computed solution, then {{math|'''y'''}} solves the perturbed system ({{math|1='''A''' + '''E''')'''y''' = '''b'''}}, where
<math display=block> \|\mathbf{E}\|_2 \le c_n \varepsilon \|\mathbf{A}\|_2. </math>
Here ||·||<sub>2</sub> is the [[matrix norm|matrix 2-norm]], ''c<sub>n</sub>'' is a small constant depending on {{mvar|n}}, and {{mvar|ε}} denotes the [[unit round-off]].

One concern with the Cholesky decomposition to be aware of is the use of square roots. If the matrix being factorized is positive definite as required, the numbers under the square roots are always positive ''in exact arithmetic''. Unfortunately, the numbers can become negative because of [[round-off error]]s, in which case the algorithm cannot continue. However, this can only happen if the matrix is very ill-conditioned. One way to address this is to add a diagonal correction matrix to the matrix being decomposed in an attempt to promote the positive-definiteness.<ref>{{cite journal
 | last1 = Fang | first1 = Haw-ren
 | last2 = O'Leary | first2 = Dianne P. | author2-link = Dianne P. O'Leary
 | doi = 10.1007/s10107-007-0177-6
 | issue = 2
 | journal = Mathematical Programming
 | mr = 2411401
 | pages = 319–349
 | title = Modified Cholesky algorithms: a catalog with new approaches
 | url = https://www.cs.umd.edu/~oleary/tr/tr4807.pdf
 | volume = 115
 | year = 2008| hdl = 1903/3674
 }}</ref> While this might lessen the accuracy of the decomposition, it can be very favorable for other reasons; for example, when performing [[Newton's method in optimization]], adding a diagonal matrix can improve stability when far from the optimum.