Differences between revisions 5 and 8 (spanning 3 versions)
⇤ ← Revision 5 as of 2024-02-06 02:17:17 →
Size: 2337
Editor: DominicRicottone
Comment: Renaming for clarity
← Revision 8 as of 2024-02-06 03:49:03 → ⇥
Size: 3094
Editor: DominicRicottone
Comment: Clarification
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
## page was renamed from LinearAlgebra/Solution
= Solution =		 = General Solution =
Line 4: Line 3:
[[LinearAlgebra/Elimination|Elimination]] is a fundamental step in solving systems of equations, but the method demonstrated on that page relies upon the right hand side being known values. This page instead supposes that the right hand side is unknown. [[LinearAlgebra/Elimination|Elimination]] and other factorizations offer a method for obtaining the '''particular solutions''' (''x,,p,,'') of a linear system. The '''complete solution''' (''x,,c,,'') is the generalized answer.
Line 14: Line 13:


=== First Example ===

The example used here [[LinearAlgebra/Elimination|here]]:
Line 15: Line 20:
w + 2x + 2y + 2z = a
2w + 4x + 6y + 8z = b
3w + 6x + 8y + 10z = c		 x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2
Line 20: Line 25:
This corresponds to the following [[LinearAlgebra/Elimination|eliminated]] augmented matrix: Is rewritten as a linear system and eliminated into:
Line 23: Line 28:
┌   ┐
│ [1] 2 2 2 a│
│ 0 0 [2] 4 b-2a│
│ 0  0 0 0 c-b-a│
└   ┘		 ┌ ┐ ┌ ┐ ┌ ┐
│[1] 2 1 │ │ x│  │ 2│
│ 0 [2] -2 │ │ y│ = │ 6│
│ 0 0 [5]│ │ z│  │-10│
└ ┘ └ ┘ └ ┘
Line 30: Line 35:
The immediate question then is: for what values of ''a'', ''b'', and ''c'' is this system solvable?

----		 This system solved to ''x=2, y=1, z=-2''. For a matrix with '''full column rank''', the system can usually be solved like this.
Line 36: Line 39:
== Trivial Solvability == === Second Example ===
Line 38: Line 41:
The above system can be easily shown to be solvable for some values. Consider a system with '''free variables''':
Line 41: Line 44:
0w + 0x + 0y + 0z = c - b - a
0 = c - b - a		 w + 2x + 2y + 2z = 1
2w + 4x + 6y + 8z = 5
3w + 6x + 8y + 10z = 6
Line 45: Line 49:
In other words, for any values of ''a'' and ''b'' which sum to ''c'', this system is solvable.

----



== General Solvability ==

----



== Solutions ==

The first step to computing the '''complete solution''' (''x,,c,,'') is computing a '''particular solution''' (''x,,p,,'').

Find a valid set of values for the right hand side. In this system, for example, [1 5 6].

Set all '''free variables''' to zero. Substitute to find all '''pivot variables'''.		 This system is rewritten as a linear system and eliminated into:
Line 66: Line 52:
┌ ┐ ┌ ┐ ┌ ┐
│[1] 2 2 2│ │ w│ │ 1│
│ 0 0 [2] 4│ │ x│ = │ 3│
│ 0 0 0 0│ │ y│ │ 0│
└ ┘ │ z│ └ ┘
              └ ┘
}}}

The columns without a pivot correspond to free variables. For any set of values in the free variable positions, there is some '''particular solution''' that satisfies the system. So aim for the simplest particular solution, where every free variable is set to 0. Then solve algebraically for the pivot variables:

{{{
2y + 4z = 3
2y + 4(0) = 3
Line 69: Line 68:
w + 2x + 2y + 2z = 1
w + 2(0) + 2y + 2(0) = 1
Line 75: Line 76:
The particular solution is: ''w=-2, x=0, y=3/2, z=0'' is a solution. There is also the unstated [[LinearAlgebra/NullSpaces#Zero_Vector_as_a_Solution|zero vector solution]] of ''w=0, x=0, y=0, z=0''. But there are also infinitely many ''other'' solutions making use of the free variables.

----



== Complete Solution ==

The '''complete solution''' is defined as ''x,,c,, = x,,p,, + x,,0,,''. That is, the [[LinearAlgebra/NullSpaces#Solution|null space]] must be solved and added to the particular solution.

The null space solutions are ''[-2 1 0 0]'' and ''[2 0 -1 1]'' for the second example above.

'''''The''''' null space solution is any linear combination of the null space solution'''''s'''''. Again, for the second example above:
Line 78: Line 91:
[-2 0 3/2 0]        ┌ ┐ ┌ ┐
       │ -2 │ │ 2 │
x = C │ 1 │ + C │ 0 │
 0 1│ 0 │ 2│ -1 │
       │ 0 │ │ 1 │
       └ ┘ └ ┘
Line 81: Line 99:
Next, compute the [[LinearAlgebra/NullSpaces|null space]]. If the matrix has '''full column rank''', i.e. every column is a pivot column and there is no free column, then the particular solution is the complete solution.

Finally, the complete solution is the particular solution plus any combination of the null space.		 Altogether, the complete solution for the second example above is:
Line 94: Line 110:
The values ''C,,1,,'' and ''C,,2,,'' are any number, because any combination of the two vectors is valid for the complete solution.

General Solution

Elimination and other factorizations offer a method for obtaining the particular solutions (xp) of a linear system. The complete solution (xc) is the generalized answer.

Contents

  1. General Solution
    1. Introduction
      1. First Example
      2. Second Example
    2. Complete Solution

Introduction

First Example

The example used here here: 

x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2

Is rewritten as a linear system and eliminated into: 

┌           ┐ ┌  ┐   ┌   ┐
│[1]  2   1 │ │ x│   │  2│
│ 0  [2] -2 │ │ y│ = │  6│
│ 0   0  [5]│ │ z│   │-10│
└           ┘ └  ┘   └   ┘

This system solved to x=2, y=1, z=-2. For a matrix with full column rank, the system can usually be solved like this.

Second Example

Consider a system with free variables: 

w + 2x + 2y + 2z = 1
2w + 4x + 6y + 8z = 5
3w + 6x + 8y + 10z = 6

This system is rewritten as a linear system and eliminated into: 

┌           ┐ ┌  ┐   ┌  ┐
│[1] 2  2  2│ │ w│   │ 1│
│ 0  0 [2] 4│ │ x│ = │ 3│
│ 0  0  0  0│ │ y│   │ 0│
└           ┘ │ z│   └  ┘
              └  ┘

The columns without a pivot correspond to free variables. For any set of values in the free variable positions, there is some particular solution that satisfies the system. So aim for the simplest particular solution, where every free variable is set to 0. Then solve algebraically for the pivot variables: 

2y + 4z = 3
2y + 4(0) = 3
2y = 3
y = 3/2

w + 2x + 2y + 2z = 1
w + 2(0) + 2y + 2(0) = 1
w + 2y = 1
w + 2(3/2) = 1
w + 3 = 1
w = -2

w=-2, x=0, y=3/2, z=0 is a solution. There is also the unstated zero vector solution of w=0, x=0, y=0, z=0. But there are also infinitely many other solutions making use of the free variables.

Complete Solution

The complete solution is defined as xc = xp + x0. That is, the null space must be solved and added to the particular solution.

The null space solutions are [-2 1 0 0] and [2 0 -1 1] for the second example above.

The null space solution is any linear combination of the null space solutions. Again, for the second example above: 

       ┌    ┐     ┌    ┐
       │ -2 │     │  2 │
x  = C │  1 │ + C │  0 │
 0    1│  0 │    2│ -1 │
       │  0 │     │  1 │
       └    ┘     └    ┘

Altogether, the complete solution for the second example above is: 

┌    ┐     ┌    ┐     ┌    ┐
│ -2 │     │ -2 │     │  2 │
│  0 │ + C │  1 │ + C │  0 │
│ 3/2│    1│  0 │    2│ -1 │
│  0 │     │  0 │     │  1 │
└    ┘     └    ┘     └    ┘

CategoryRicottone

LinearAlgebra/GeneralSolution (last edited 2026-02-04 04:32:14 by DominicRicottone)