File: Large-Dense-Linear-Systems-Normal-Equations.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (107 lines) | stat: -rw-r--r-- 5,408 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".

(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: Large Dense Linear Systems Normal Equations</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Large Dense Linear Systems Normal Equations">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Large Dense Linear Systems Normal Equations">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Large-Dense-Linear-Systems.html#Large-Dense-Linear-Systems" rel="up" title="Large Dense Linear Systems">
<link href="Large-Dense-Linear-Systems-TSQR.html#Large-Dense-Linear-Systems-TSQR" rel="next" title="Large Dense Linear Systems TSQR">
<link href="Large-Dense-Linear-Systems.html#Large-Dense-Linear-Systems" rel="previous" title="Large Dense Linear Systems">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Large-Dense-Linear-Systems-Normal-Equations"></a>
<div class="header">
<p>
Next: <a href="Large-Dense-Linear-Systems-TSQR.html#Large-Dense-Linear-Systems-TSQR" accesskey="n" rel="next">Large Dense Linear Systems TSQR</a>, Up: <a href="Large-Dense-Linear-Systems.html#Large-Dense-Linear-Systems" accesskey="u" rel="up">Large Dense Linear Systems</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Normal-Equations-Approach"></a>
<h4 class="subsection">38.6.1 Normal Equations Approach</h4>
<a name="index-large-linear-least-squares_002c-normal-equations"></a>

<p>The normal equations approach to the large linear least squares
problem described above is popular due to its speed and simplicity.
Since the normal equations solution to the problem is given by
</p><div class="example">
<pre class="example">c = ( X^T X + \lambda^2 I )^-1 X^T y
</pre></div>
<p>only the <em>p</em>-by-<em>p</em> matrix <em>X^T X</em> and
<em>p</em>-by-1 vector <em>X^T y</em> need to be stored. Using
the partition scheme described above, these are given by
</p><div class="example">
<pre class="example">X^T X = \sum_i X_i^T X_i
X^T y = \sum_i X_i^T y_i
</pre></div>
<p>Since the matrix <em>X^T X</em> is symmetric, only half of it
needs to be calculated. Once all of the blocks (<em>X_i,y_i</em>)
have been accumulated into the final <em>X^T X</em> and <em>X^T y</em>,
the system can be solved with a Cholesky factorization of the
<em>X^T X</em> matrix. If the Cholesky factorization fails (occasionally
due to numerical rounding errors), a QR decomposition is then used.
In both cases, the <em>X^T X</em> matrix is first transformed via
a diagonal scaling transformation to attempt to reduce its condition
number as much as possible to recover a more accurate solution vector.
The normal equations approach is the fastest method for solving the
large least squares problem, and is accurate for well-conditioned
matrices <em>X</em>. However, for ill-conditioned matrices, as is often
the case for large systems, this method can suffer from numerical
instabilities (see Trefethen and Bau, 1997).  The number of operations
for this method is <em>O(np^2 + {1 \over 3}p^3)</em>.
</p>



</body>
</html>