tsai
/
mathnet-numerics
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
Math.NET Numerics
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
50 Commits
25 Branches
121 Tags
187 MiB
 
 
 
Branch: gh-pages
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'gh-pages'
${ noResults }
mathnet-numerics/LinearEquations.html

225 lines
18 KiB
Raw Permalink Blame History

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Linear Equation Systems
</title>
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<meta name="author" content="Christoph Ruegg, Marcus Cuda, Jurgen Van Gael">
<link rel="stylesheet" id="theme_link" href="https://cdnjs.cloudflare.com/ajax/libs/bootswatch/4.6.0/materia/bootstrap.min.css">
<script src="https://code.jquery.com/jquery-3.4.1.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/bootstrap@4.6.0/dist/js/bootstrap.bundle.min.js" integrity="sha384-Piv4xVNRyMGpqkS2by6br4gNJ7DXjqk09RmUpJ8jgGtD7zP9yug3goQfGII0yAns" crossorigin="anonymous"></script>
<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<link rel="shortcut icon" type="image/x-icon" href="/favicon.ico">
<link type="text/css" rel="stylesheet" href="https://numerics.mathdotnet.com/content/navbar-fixed-left.css" />
<link type="text/css" rel="stylesheet" href="https://numerics.mathdotnet.com/content/fsdocs-default.css" />
<link type="text/css" rel="stylesheet" href="https://numerics.mathdotnet.com/content/fsdocs-custom.css" />
<script type="text/javascript" src="https://numerics.mathdotnet.com/content/fsdocs-tips.js"></script>
<!-- HTML5 shim, for IE6-8 support of HTML5 elements -->
<!--[if lt IE 9]>
<script src="http://html5shim.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
<!-- BEGIN SEARCH BOX: this adds support for the search box -->
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/JavaScript-autoComplete/1.0.4/auto-complete.css" />
<!-- END SEARCH BOX: this adds support for the search box -->
</head>
<body>
<nav class="navbar navbar-expand-md navbar-light bg-secondary fixed-left" id="fsdocs-nav">
<button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarsExampleDefault" aria-controls="navbarsExampleDefault" aria-expanded="false" aria-label="Toggle navigation">
<span class="navbar-toggler-icon"></span>
</button>
<div class="collapse navbar-collapse navbar-nav-scroll" id="navbarsExampleDefault">
<a href="https://numerics.mathdotnet.com/"><img id="fsdocs-logo" src="/logo.png" /></a>
<!-- BEGIN SEARCH BOX: this adds support for the search box -->
<div id="header">
<div class="searchbox" id="fsdocs-searchbox">
<label for="search-by">
<i class="fas fa-search"></i>
</label>
<input data-search-input="" id="search-by" type="search" placeholder="Search..." />
<span data-search-clear="">
<i class="fas fa-times"></i>
</span>
</div>
</div>
<!-- END SEARCH BOX: this adds support for the search box -->
<ul class="navbar-nav">
<li class="nav-header">Math.NET Numerics</li>
<li class="nav-item"><a class="nav-link" href="Packages.html">NuGet & Binaries</a></li>
<li class="nav-item"><a class="nav-link" href="ReleaseNotes.html">Release Notes</a></li>
<li class="nav-item"><a class="nav-link" href="https://github.com/mathnet/mathnet-numerics/blob/master/LICENSE.md">MIT License</a></li>
<li class="nav-item"><a class="nav-link" href="Compatibility.html">Platform Support</a></li>
<li class="nav-item"><a class="nav-link" href="https://numerics.mathdotnet.com/api/">Class Reference</a></li>
<li class="nav-item"><a class="nav-link" href="https://github.com/mathnet/mathnet-numerics/issues">Issues & Bugs</a></li>
<li class="nav-item"><a class="nav-link" href="Users.html">Who is using Math.NET?</a></li>
<li class="nav-header">Contributing</li>
<li class="nav-item"><a class="nav-link" href="Contributors.html">Contributors</a></li>
<li class="nav-item"><a class="nav-link" href="Contributing.html">Contributing</a></li>
<li class="nav-item"><a class="nav-link" href="Build.html">Build & Tools</a></li>
<li class="nav-item"><a class="nav-link" href="https://github.com/mathnet/mathnet-numerics/discussions/categories/ideas">Your Ideas</a></li>
<li class="nav-header">Getting Help</li>
<li class="nav-item"><a class="nav-link" href="https://discuss.mathdotnet.com/c/numerics">Discuss</a></li>
<li class="nav-item"><a class="nav-link" href="https://stackoverflow.com/questions/tagged/mathdotnet">Stack Overflow</a></li>
<li class="nav-header">Getting Started</li>
<l class="nav-item"i><a class="nav-link" href="/">Getting started</a></li>
<li class="nav-item"><a class="nav-link" href="Constants.html">Constants</a></li>
<li class="nav-item"><a class="nav-link" href="Matrix.html">Matrices and Vectors</a></li>
<li class="nav-item"><a class="nav-link" href="Euclid.html">Euclid & Number Theory</a></li>
<li class="nav-item">Combinatorics</li>
<li class="nav-header">Evaluation</li>
<li class="nav-item"><a class="nav-link" href="Functions.html">Special Functions</a></li>
<li class="nav-item"><a class="nav-link" href="Integration.html">Integration</a></li>
<li class="nav-header">Statistics/Probability</li>
<li class="nav-item"><a class="nav-link" href="DescriptiveStatistics.html">Descriptive Statistics</a></li>
<li class="nav-item"><a class="nav-link" href="Probability.html">Probability Distributions</a></li>
<li class="nav-header">Generation</li>
<li class="nav-item"><a class="nav-link" href="Generate.html">Generating Data</a></li>
<li class="nav-item"><a class="nav-link" href="Random.html">Random Numbers</a></li>
<li class="nav-header">Solving Equations</li>
<li class="nav-item"><a class="nav-link" href="LinearEquations.html">Linear Equation Systems</a></li>
<li class="nav-header">Optimization</li>
<li class="nav-item"><a class="nav-link" href="Distance.html">Distance Metrics</a></li>
<li class="nav-header">Curve Fitting</li>
<li class="nav-item"><a class="nav-link" href="Regression.html">Regression</a></li>
<li class="nav-header">Native Providers</li>
<li class="nav-item"><a class="nav-link" href="MKL.html">Intel MKL</a></li>
<li class="nav-header">Working Together</li>
<li class="nav-item"><a class="nav-link" href="CSV.html">Delimited Text Files (CSV)</a></li>
<li class="nav-item"><a class="nav-link" href="MatrixMarket.html">NIST MatrixMarket</a></li>
<li class="nav-item"><a class="nav-link" href="MatlabFiles.html">MATLAB</a></li>
<li class="nav-item"><a class="nav-link" href="IFSharpNotebook.html">IF# Notebook</a></li>
</ul>
</div>
</nav>
<div class="container">
<div class="masthead">
<h3 class="muted">
<a href="https://numerics.mathdotnet.com">Math.NET Numerics</a> |
<a href="https://www.mathdotnet.com">Math.NET Project</a> |
<a href="https://github.com/mathnet/mathnet-numerics">GitHub</a>
</h3>
</div>
<hr />
<div class="container" id="fsdocs-content">
<h1><a name="Linear-Equation-Systems" class="anchor" href="#Linear-Equation-Systems">Linear Equation Systems</a></h1>
<p>A system of linear equations is a collection of linear equations involving the same set of variables:</p>
<p><span class="math">\[\begin{alignat}{7}
3x &amp;\; + \;&amp; 2y &amp;\; - \;&amp; z &amp;\; = \;&amp; 1 &amp; \\
2x &amp;\; - \;&amp; 2y &amp;\; + \;&amp; 4z &amp;\; = \;&amp; -2 &amp; \\
-x &amp;\; + \;&amp; \tfrac{1}{2} y &amp;\; - \;&amp; z &amp;\; = \;&amp; 0 &amp;
\end{alignat}\]</span></p>
<p>More generally, we can write</p>
<p><span class="math">\[\begin{alignat}{7}
a_{11} x_1 &amp;&amp;\; + \;&amp;&amp; a_{12} x_2 &amp;&amp;\; + \cdots + \;&amp;&amp; a_{1n} x_n &amp;&amp;\; = \;&amp;&amp;&amp; b_1 \\
a_{21} x_1 &amp;&amp;\; + \;&amp;&amp; a_{22} x_2 &amp;&amp;\; + \cdots + \;&amp;&amp; a_{2n} x_n &amp;&amp;\; = \;&amp;&amp;&amp; b_2 \\
\vdots\;\;\; &amp;&amp; &amp;&amp; \vdots\;\;\; &amp;&amp; &amp;&amp; \vdots\;\;\; &amp;&amp; &amp;&amp;&amp; \;\vdots \\
a_{m1} x_1 &amp;&amp;\; + \;&amp;&amp; a_{m2} x_2 &amp;&amp;\; + \cdots + \;&amp;&amp; a_{mn} x_n &amp;&amp;\; = \;&amp;&amp;&amp; b_m \\
\end{alignat}\]</span></p>
<p>where we all parameters <span class="math">\(a_{ij}\)</span> and <span class="math">\(b_i\)</span> are known and we would like to find <span class="math">\(x_j\)</span> that satisfy
all these equations. If we have the same number <span class="math">\(n\)</span> of unknown variables <span class="math">\(x_j\)</span> as number of
equations <span class="math">\(m\)</span>, and all these equations are independent, then there is a unique solution.</p>
<p>This is a fundamental problem in the domain of linear algebra, and we can use its power to find the solution.
Accordingly we can write the equivalent problem with matrices and vectors:</p>
<p><span class="math">\[\mathbf{A}=
\begin{bmatrix}
a_{11} &amp; a_{12} &amp; \cdots &amp; a_{1n} \\
a_{21} &amp; a_{22} &amp; \cdots &amp; a_{2n} \\
\vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
a_{m1} &amp; a_{m2} &amp; \cdots &amp; a_{mn}
\end{bmatrix},\quad
\mathbf{x}=\begin{bmatrix}x_1\\x_2\\ \vdots \\x_n\end{bmatrix},\quad
\mathbf{b}=\begin{bmatrix}b_1\\b_2\\ \vdots \\b_m\end{bmatrix}\]</span></p>
<p>such that</p>
<p><span class="math">\[\mathbf{A}\mathbf{x}=\mathbf{b}\]</span></p>
<p>The initial example system would then look like this:</p>
<p><span class="math">\[\begin{bmatrix}3 &amp; 2 &amp; -1 \\2 &amp; -2 &amp; 4 \\-1 &amp; \tfrac{1}{2} &amp; -1\end{bmatrix}
\begin{bmatrix}x\\y\\z\end{bmatrix}
\;=\;
\begin{bmatrix}1\\-2\\0\end{bmatrix}\]</span></p>
<p>Which we can solve explicitly with the LU-decomposition, or simply by using the Solve method:</p>
<table class="pre"><tr><td class="snippet"><pre class="fssnip highlighted"><code lang="csharp"><span class="k">var</span> A <span class="o">=</span> Matrix&lt;<span class="k">double</span>&gt;.Build.DenseOfArray(<span class="k">new</span> <span class="k">double</span>[,] {
{ <span class="n">3</span>, <span class="n">2</span>, <span class="n">-1</span> },
{ <span class="n">2</span>, <span class="n">-2</span>, <span class="n">4</span> },
{ <span class="n">-1</span>, <span class="n">0.5</span>, <span class="n">-1</span> }
});
<span class="k">var</span> b <span class="o">=</span> Vector&lt;<span class="k">double</span>&gt;.Build.Dense(<span class="k">new</span> <span class="k">double</span>[] { <span class="n">1</span>, <span class="n">-2</span>, <span class="n">0</span> });
<span class="k">var</span> x <span class="o">=</span> A.Solve(b);
</code></pre></td></tr></table>
<p>The resulting <span class="math">\(\mathbf{x}\)</span> is <span class="math">\([1,\;-2,\;-2]\)</span>, hence the solution <span class="math">\(x=1,\;y=-2,\;z=-2\)</span>.</p>
<p>In F# the syntax is a bit lighter:</p>
<pre class="fssnip highlighted"><code lang="fsharp"><span class="k">let</span> <span onmouseout="hideTip(event, 'fs1', 1)" onmouseover="showTip(event, 'fs1', 1)" class="id">A</span> <span class="o">=</span> <span class="id">matrix</span> <span class="pn">[</span><span class="pn">[</span> <span class="n">3.0</span><span class="pn">;</span> <span class="n">2.0</span><span class="pn">;</span> <span class="o">-</span><span class="n">1.0</span> <span class="pn">]</span>
<span class="pn">[</span> <span class="n">2.0</span><span class="pn">;</span> <span class="o">-</span><span class="n">2.0</span><span class="pn">;</span> <span class="n">4.0</span> <span class="pn">]</span>
<span class="pn">[</span> <span class="o">-</span><span class="n">1.0</span><span class="pn">;</span> <span class="n">0.5</span><span class="pn">;</span> <span class="o">-</span><span class="n">1.0</span> <span class="pn">]</span><span class="pn">]</span>
<span class="k">let</span> <span onmouseout="hideTip(event, 'fs2', 2)" onmouseover="showTip(event, 'fs2', 2)" class="id">b</span> <span class="o">=</span> <span class="id">vector</span> <span class="pn">[</span> <span class="n">1.0</span><span class="pn">;</span> <span class="o">-</span><span class="n">2.0</span><span class="pn">;</span> <span class="n">0.0</span> <span class="pn">]</span>
<span class="k">let</span> <span onmouseout="hideTip(event, 'fs3', 3)" onmouseover="showTip(event, 'fs3', 3)" class="id">x</span> <span class="o">=</span> <span onmouseout="hideTip(event, 'fs1', 4)" onmouseover="showTip(event, 'fs1', 4)" class="id">A</span><span class="pn">.</span><span class="id">Solve</span><span class="pn">(</span><span onmouseout="hideTip(event, 'fs2', 5)" onmouseover="showTip(event, 'fs2', 5)" class="id">b</span><span class="pn">)</span> <span class="c">// 1;-2;-2</span>
</code></pre>
<h2><a name="Normalizing-Equation-Systems" class="anchor" href="#Normalizing-Equation-Systems">Normalizing Equation Systems</a></h2>
<p>In practice, a linear equation system to be solved is often not in the standard form required
to use the linear algebra approach. For example, let's have a look at the following system:</p>
<p><span class="math">\[\begin{bmatrix}1 &amp; 2 &amp; 3 &amp; 4\\2 &amp; 3 &amp; 4 &amp; 5\\3 &amp; 4 &amp; 5 &amp; 6\\4 &amp; 5 &amp; 6 &amp; 7\end{bmatrix}
\begin{bmatrix}0\\0\\V\\T\end{bmatrix}
\;=\;
\begin{bmatrix}F\\M\\20\\0\end{bmatrix}\]</span></p>
<p>The first two values of the solution vector <span class="math">\([0,\;0,\;V,\;T]\)</span> are constant zero, so we can simplify
the system to:</p>
<p><span class="math">\[\begin{bmatrix}3 &amp; 4\\4 &amp; 5\\5 &amp; 6\\6 &amp; 7\end{bmatrix}
\begin{bmatrix}V\\T\end{bmatrix}
\;=\;
\begin{bmatrix}F\\M\\20\\0\end{bmatrix}\]</span></p>
<p>Then we need to subtract the two unknowns from the right side back from the left (so that they
become zero on the right side), by introducing a new column each. First we subtract
<span class="math">\([F,\;0,\;0,\;0]^T\)</span> from both sides:</p>
<p><span class="math">\[\begin{bmatrix}3 &amp; 4 &amp; -1\\4 &amp; 5 &amp; 0\\5 &amp; 6 &amp; 0\\6 &amp; 7 &amp; 0\end{bmatrix}
\begin{bmatrix}V\\T\\F\end{bmatrix}
\;=\;
\begin{bmatrix}0\\M\\20\\0\end{bmatrix}\]</span></p>
<p>Then we subtract <span class="math">\([0,\;M,\;0,\;0]^T\)</span> from both sides the same way:</p>
<p><span class="math">\[\begin{bmatrix}3 &amp; 4 &amp; -1 &amp; 0\\4 &amp; 5 &amp; 0 &amp; -1\\5 &amp; 6 &amp; 0 &amp; 0\\6 &amp; 7 &amp; 0 &amp; 0\end{bmatrix}
\begin{bmatrix}V\\T\\F\\M\end{bmatrix}
\;=\;
\begin{bmatrix}0\\0\\20\\0\end{bmatrix}\]</span></p>
<p>Which is in standard from, so we can solve normally:</p>
<pre class="fssnip highlighted"><code lang="fsharp"><span class="k">let</span> <span onmouseout="hideTip(event, 'fs4', 6)" onmouseover="showTip(event, 'fs4', 6)" class="id">A&#39;</span> <span class="o">=</span> <span class="id">matrix</span> <span class="pn">[</span><span class="pn">[</span> <span class="n">3.0</span><span class="pn">;</span> <span class="n">4.0</span><span class="pn">;</span> <span class="o">-</span><span class="n">1.0</span><span class="pn">;</span> <span class="n">0.0</span> <span class="pn">]</span>
<span class="pn">[</span> <span class="n">4.0</span><span class="pn">;</span> <span class="n">5.0</span><span class="pn">;</span> <span class="n">0.0</span><span class="pn">;</span> <span class="o">-</span><span class="n">1.0</span> <span class="pn">]</span>
<span class="pn">[</span> <span class="n">5.0</span><span class="pn">;</span> <span class="n">6.0</span><span class="pn">;</span> <span class="n">0.0</span><span class="pn">;</span> <span class="n">0.0</span><span class="pn">;</span> <span class="pn">]</span>
<span class="pn">[</span> <span class="n">6.0</span><span class="pn">;</span> <span class="n">7.0</span><span class="pn">;</span> <span class="n">0.0</span><span class="pn">;</span> <span class="n">0.0</span> <span class="pn">]</span><span class="pn">]</span>
<span class="k">let</span> <span onmouseout="hideTip(event, 'fs5', 7)" onmouseover="showTip(event, 'fs5', 7)" class="id">b&#39;</span> <span class="o">=</span> <span class="id">vector</span> <span class="pn">[</span> <span class="n">0.0</span><span class="pn">;</span> <span class="n">0.0</span><span class="pn">;</span> <span class="n">20.0</span><span class="pn">;</span> <span class="n">0.0</span> <span class="pn">]</span>
<span class="k">let</span> <span onmouseout="hideTip(event, 'fs6', 8)" onmouseover="showTip(event, 'fs6', 8)" class="id">x&#39;</span> <span class="o">=</span> <span onmouseout="hideTip(event, 'fs4', 9)" onmouseover="showTip(event, 'fs4', 9)" class="id">A&#39;</span><span class="pn">.</span><span class="id">Solve</span><span class="pn">(</span><span onmouseout="hideTip(event, 'fs5', 10)" onmouseover="showTip(event, 'fs5', 10)" class="id">b&#39;</span><span class="pn">)</span> <span class="c">// -140; 120; 60; 40</span>
</code></pre>
<div class="fsdocs-tip" id="fs1">val A : obj</div>
<div class="fsdocs-tip" id="fs2">val b : obj</div>
<div class="fsdocs-tip" id="fs3">val x : obj</div>
<div class="fsdocs-tip" id="fs4">val A&#39; : obj</div>
<div class="fsdocs-tip" id="fs5">val b&#39; : obj</div>
<div class="fsdocs-tip" id="fs6">val x&#39; : obj</div>
</div>
<!-- BEGIN SEARCH BOX: this adds support for the search box -->
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/JavaScript-autoComplete/1.0.4/auto-complete.css" />
<script type="text/javascript">var fsdocs_search_baseurl = 'https://numerics.mathdotnet.com/';</script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/lunr.js/2.3.8/lunr.min.js"></script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/JavaScript-autoComplete/1.0.4/auto-complete.min.js"></script>
<script type="text/javascript" src="https://numerics.mathdotnet.com/content/fsdocs-search.js"></script>
<!-- END SEARCH BOX: this adds support for the search box -->
</div>
</body>
</html>