3
$\begingroup$

Given that I have a set of equations about varible $x_0,x_1,\cdots,x_n$, which own the following style:

$ \left( \begin{array}{cccccccc} \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 \\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ \color{red}{x_0} \\ \color{red}{x_1} \\ \color{red}{x_2} \\ \end{array} \right)=\left( \begin{array}{c} (1,1) \\ (2,3) \\ (3,-1) \\ (4,1) \\ (5,0) \\ \end{array} \right) $

Obviously, I cannot solve this linear system by LinearSolve[]. To solve this equation group, I only used the Solve[].

mat=
 {{1/6, 2/3, 1/6, 0, 0, 0, 0, 0}, {0, 1/6, 2/3, 1/6, 0, 0, 0, 0}, 
  {0, 0, 1/6, 2/3, 1/6, 0, 0, 0}, {0, 0, 0, 1/6, 2/3, 1/6, 0, 0}, 
  {0, 0, 0, 0, 1/6, 2/3, 1/6, 0}};
eqns = mat.{x0, x1, x2, x3, x4, x0, x1, x2};

$ \begin{pmatrix} \frac{x_0}{6}+\frac{2 x_1}{3}+\frac{x_2}{6}\\ \frac{x_1}{6}+\frac{2 x_2}{3}+\frac{x_3}{6}\\ \frac{x_2}{6}+\frac{2 x_3}{3}+\frac{x_4}{6}\\ \frac{x_0}{6}+\frac{x_3}{6}+\frac{2 x_4}{3}\\ \frac{2 x_0}{3}+\frac{x_1}{6}+\frac{x_4}{6} \end{pmatrix} $

yValues = {{1, 1}, {2, 3}, {3, -1}, {4, 1}, {5, 0}};
part1 = {x0, x1, x2, x3, x4} /. 
  Solve[Thread[eqns == yValues[[All, 1]]], {x0, x1, x2, x3, x4}]
part2 = {x0, x1, x2, x3, x4} /. 
  Solve[Thread[eqns == yValues[[All, 2]]], {x0, x1, x2, x3, x4}]
res = Transpose[Join[part1, part2]]

 {{75/11, -8/11}, {-9/11, 4/11}, {27/11, 58/11}, {3, -38/11}, {39/11, 28/11}}

Question

However, the index $n$ for variables $\{x_0,x_1,\cdots,x_n\}$ is very large ($n=100$) in my work. My solution that by Solve[] is very cockamamie. So I would like to know how to deal with this case by the built-in LinearSolve[] efficiently?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ You can partition your x-vector as $(x,y,x)$, where $x=(x_0,x_1,x_2)$ and $y=(x_3,x_4)$, and your matrix mat in a similar way (3x3 block matrix). Multiplying out the blocks and collecting $x$ and $y$ together will give you the linear system of reduced size that you can feed to LinearSolve $\endgroup$
    – sebhofer
    Oct 23, 2015 at 8:16
  • 3
    $\begingroup$ Do a fold-over: $$\begin{pmatrix}\frac16&\frac23&\frac16&0&0\\ 0&\frac16&\frac23&\frac16&0\\ 0&0&\frac16&\frac23&\frac16\\ \frac16&0&0&\frac16&\frac23\\ \frac23&\frac16&0&0&\frac16\end{pmatrix} \begin{pmatrix}x_0\\x_1\\x_2\\x_3\\x_4\end{pmatrix} =\begin{pmatrix}(1,1)\\(2,3)\\(3,-1)\\(4,1)\\(5,0)\\\end{pmatrix}$$ Is this part of your closed spline interpolation problem? $\endgroup$
    – J. M.'s eventual burnout ♦
    Oct 23, 2015 at 8:33
  • $\begingroup$ @J.M. Yes, see here $\endgroup$
    – xyz
    Oct 23, 2015 at 8:41
  • 2
    $\begingroup$ Maybe I missed something in your question. But once you have the equations, you can find the corresponding matrix by CoefficientArrays[eqns, {x0, x1, x2, x3, x4}][[2]] and then use LinearSolve. $\endgroup$
    – Fred Simons
    Oct 23, 2015 at 8:59
  • $\begingroup$ @FredSimons Yes, your method is right. I have achieved the right result by your method:) $\endgroup$
    – xyz
    Oct 23, 2015 at 9:10

3 Answers 3

Reset to default
7
+500
$\begingroup$

How to fold a "wide" matrix over to enforce "periodic" conditions:

mat = {{1/6, 2/3, 1/6, 0, 0, 0, 0, 0}, {0, 1/6, 2/3, 1/6, 0, 0, 0, 0},
       {0, 0, 1/6, 2/3, 1/6, 0, 0, 0}, {0, 0, 0, 1/6, 2/3, 1/6, 0, 0},
       {0, 0, 0, 0, 1/6, 2/3, 1/6, 0}};

{m, n} = Dimensions[mat];

LinearSolve[Take[mat, m, m] + PadRight[Take[mat, m, m - n], {m, m}],
            {{1, 1}, {2, 3}, {3, -1}, {4, 1}, {5, 0}}]

{{75/11, -8/11}, {-9/11, 4/11}, {27/11, 58/11}, {3, -38/11}, {39/11, 28/11}}
Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Is fold-over the "official" name for this operation? $\endgroup$
    – sebhofer
    Oct 23, 2015 at 10:15
  • 1
    $\begingroup$ I'm not aware of an official name, but I like the picturesque terminology. :) $\endgroup$
    – J. M.'s eventual burnout ♦
    Oct 23, 2015 at 10:18
  • $\begingroup$ I agree. It was just that you so confidently calling it "fold-over" in your comment made me feel like I should have known that it was actually a thing :-) $\endgroup$
    – sebhofer
    Oct 23, 2015 at 10:29
  • $\begingroup$ J.M. I would like to ask you a question about well-condition. For a square matrix $A$, I can use the formula $cond(A)=||A|||A^{-1}|||$ to calculate the conditional number of matrix $A$. However, I didn't know which value is proper for well-condition. Thanks a lot. $\endgroup$
    – xyz
    Oct 29, 2015 at 2:15
  • $\begingroup$ @Shutao, the idea with conditioning is that the nearer the condition is to $1$, the better the conditioning of the problem (as in the case of orthogonal/unitary matrices). Ill-conditioned systems have large condition numbers, and truly singular systems have infinite condition numbers. $\endgroup$
    – J. M.'s eventual burnout ♦
    Oct 29, 2015 at 2:28
4
$\begingroup$ 
l = 5; s = 3;
(* Solution 1 *)
# + SparseArray[#2, {l, l}] & @@ Internal`PartitionRagged[mat\[Transpose], {l, s}];
LinearSolve[%\[Transpose], yValues]

(* Solution 2 *)
Module[{m = #[[;; l]]}, m[[;; s]] += #[[-s ;;]]; m] &[mat\[Transpose]];
LinearSolve[%\[Transpose], yValues]
Improve this answer
$\endgroup$
1
  • $\begingroup$ Cool, Internal`PartitionRagged can be very useful! $\endgroup$
    – sebhofer
    Oct 23, 2015 at 10:10
2
$\begingroup$

This script accepts the equations (consistent equations) with the unknowns in any order.

vars = Variables[eqns]
A = Grad[eqns, vars]
B1 = Map[First, yValues]
B2 = Map[Last, yValues]
LinearSolve[A, B1]
LinearSolve[A, B2]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.