Tridiagonal matrix algorithm/Derivation - Revision history

Jitse Niesen: replace by #REDIRECT tridiagonal matrix algorithm since this page was merged there

2008-09-09T01:51:06Z

replace by #REDIRECT tridiagonal matrix algorithm since this page was merged there

← Previous revision		Revision as of 01:51, 9 September 2008
Line 1:		Line 1:
	~~The derivation of the~~ [[tridiagonal matrix algorithm]] ~~involves manually performing some specialized [[Gaussian elimination]] in a generic manner.~~		#REDIRECT [[tridiagonal matrix algorithm]]

	Suppose that the unknowns are <math>x_1,\ldots, x_n</math>, and that the equations to be solved are:

	:<math>\begin{array}{lcl}
	b_1 x_1 + c_1 x_2 = d_1 \qquad &;& \ i = 1 \\
	a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i \qquad &;& \ i = 2, \ldots, n - 1 \\
	a_n x_{n - 1} + b_n x_n = d_n \qquad &;& \ i = n \\
	\end{array}
	\,</math>

	Consider modifying the second (<math>i = 2</math>) equation with the first equation as follows:

	:<math>
	(\mbox{equation 2}) \cdot b_1 - (\mbox{equation 1}) \cdot a_2
	</math>

	which would give:

	:<math>
	(a_2 x_1 + b_2 x_2 + c_2 x_3) b_1 - (b_1 x_1 + c_1 x_2) a_2 = d_2 b_1 - d_1 a_2
	\,</math>

	:<math>
	(b_2 b_1 - c_1 a_2) x_2 + c_2 b_1 x_3 = d_2 b_1 - d_1 a_2
	\,</math>

	and the effect is that <math>x_1</math> has been eliminated from the second equation. Using a similar tactic with the '''modified''' second equation on the third equation yields:

	:<math>
	(a_3 x_2 + b_3 x_3 + c_3 x_4) (b_2 b_1 - c_1 a_2) -
	((b_2 b_1 - c_1 a_2) x_2 + c_2 b_1 x_3) a_3
	= d_3 (b_2 b_1 - c_1 a_2) - (d_2 b_1 - d_1 a_2) a_3
	\,</math>

	:<math>
	(b_3 (b_2 b_1 - c_1 a_2) - c_2 b_1 a_3 )x_3 + c_3 (b_2 b_1 - c_1 a_2) x_4
	= d_3 (b_2 b_1 - c_1 a_2) - (d_2 b_1 - d_1 a_2) a_3
	\,</math>

	This time <math>x_2</math> was eliminated. If this procedure is repeated until the <math>n^{th}</math> row; the (modified) <math>n^{th}</math> equation will involve only one unknown, <math>x_n</math>. This may be solved for and then used to solve the <math>(n - 1)^{th}</math> equation, and so on until all of the unknowns are solved for.

	Clearly, the coefficients on the modified equations get more and more complicated if stated explicitly. By examining the procedure, the modified coefficients (notated with tildes) may instead be defined recursively:

	:<math>\tilde a_i = 0\,</math>

	:<math>\tilde b_1 = b_1\,</math>
	:<math>\tilde b_i = b_i \tilde b_{i - 1} - \tilde c_{i - 1} a_i\,</math>

	:<math>\tilde c_1 = c_1\,</math>
	:<math>\tilde c_i = c_i \tilde b_{i - 1}\,</math>

	:<math>\tilde d_1 = d_1\,</math>
	:<math>\tilde d_i = d_i \tilde b_{i - 1} - \tilde d_{i - 1} a_i\,</math>

	To further hasten the solution process, <math>\tilde b_i</math> may be divided out (if there's no division by zero risk), the newer modified coefficients notated with an asterisk will be:

	:<math>a'_i = 0\,</math>

	:<math>b'_i = 1\,</math>

	:<math>c'_1 = \frac{c_1}{b_1}\,</math>
	:<math>c'_i = \frac{c_i}{b_i - c'_{i - 1} a_i}\,</math>

	:<math>d'_1 = \frac{d_1}{b_1}\,</math>
	:<math>d'_i = \frac{d_i - d'_{i - 1} a_i}{b_i - c'_{i - 1} a_i}\,</math>

	This gives the following system with the same unknowns and coefficients defined in terms of the original ones above:

	:<math>\begin{array}{lcl}
	x_i + c'_i x_{i + 1} = d'_i \qquad &;& \ i = 1, \ldots, n - 1 \\
	x_n = d'_n \qquad &;& \ i = n \\
	\end{array}
	\,</math>

	The last equation involves only one unknown. Solving it in turn reduces the next last equation to one unknown, so that this backward substitution can be used to find all of the unknowns:

	:<math>x_n = d'_n\,</math>

	:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1</math>


	[[Category:Numerical linear algebra]]

Jitse Niesen: remove {{db-pagemove}} - does not seem vandalism to me; see Wikipedia talk:WikiProject Mathematics/Proofs

2008-09-09T01:45:40Z

remove {{db-pagemove}} - does not seem vandalism to me; see Wikipedia talk:WikiProject Mathematics/Proofs

← Previous revision		Revision as of 01:45, 9 September 2008
Line 1:		Line 1:
	{{db-pagemove}}
	The derivation of the [[tridiagonal matrix algorithm]] involves manually performing some specialized [[Gaussian elimination]] in a generic manner.		The derivation of the [[tridiagonal matrix algorithm]] involves manually performing some specialized [[Gaussian elimination]] in a generic manner.

Michael Hardy at 21:13, 8 September 2008

2008-09-08T21:13:26Z

← Previous revision		Revision as of 21:13, 8 September 2008
Line 1:		Line 1:
	{{db-pagemove}}		{{db-pagemove}}
	The derivation of the [[~~Tridiagonal~~ matrix algorithm]] involves manually performing some specialized [[Gaussian elimination]] in a generic manner.		The derivation of the [[tridiagonal matrix algorithm]] involves manually performing some specialized [[Gaussian elimination]] in a generic manner.

	Suppose that the unknowns are <math>x_1,\ldots, x_n</math>, and that the equations to be solved are:		Suppose that the unknowns are <math>x_1,\ldots, x_n</math>, and that the equations to be solved are:

Potatoswatter: Requesting speedy deletion (CSD G3). (TW)

2008-09-08T20:43:45Z

Requesting speedy deletion (CSD G3). (TW)

← Previous revision		Revision as of 20:43, 8 September 2008
Line 1:		Line 1:
			{{db-pagemove}}
	The derivation of the [[Tridiagonal matrix algorithm]] involves manually performing some specialized [[Gaussian elimination]] in a generic manner.		The derivation of the [[Tridiagonal matrix algorithm]] involves manually performing some specialized [[Gaussian elimination]] in a generic manner.

Wariner: grammar

2008-05-17T16:50:45Z

grammar

← Previous revision		Revision as of 16:50, 17 May 2008
Line 41:		Line 41:
	This time <math>x_2</math> was eliminated. If this procedure is repeated until the <math>n^{th}</math> row; the (modified) <math>n^{th}</math> equation will involve only one unknown, <math>x_n</math>. This may be solved for and then used to solve the <math>(n - 1)^{th}</math> equation, and so on until all of the unknowns are solved for.		This time <math>x_2</math> was eliminated. If this procedure is repeated until the <math>n^{th}</math> row; the (modified) <math>n^{th}</math> equation will involve only one unknown, <math>x_n</math>. This may be solved for and then used to solve the <math>(n - 1)^{th}</math> equation, and so on until all of the unknowns are solved for.

	Clearly, the coefficients on the modified equations get more and more complicated if stated explicitly. By examining the procedure, the modified coefficients (notated with tildes) may be instead be defined recursively:		Clearly, the coefficients on the modified equations get more and more complicated if stated explicitly. By examining the procedure, the modified coefficients (notated with tildes) may instead be defined recursively:

	:<math>\tilde a_i = 0\,</math>		:<math>\tilde a_i = 0\,</math>

Ben pcc: Cattegorizing.

2007-09-23T22:38:34Z

Cattegorizing.

← Previous revision		Revision as of 22:38, 23 September 2007
Line 79:		Line 79:

	:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1</math>		:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1</math>

	{{Uncategorized\|date=September 2007}}

			[[Category:Numerical linear algebra]]

Alaibot: Robot: tagging uncategorised page

2007-09-22T04:57:24Z

Robot: tagging uncategorised page

← Previous revision		Revision as of 04:57, 22 September 2007
Line 79:		Line 79:

	:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1</math>		:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1</math>
			{{Uncategorized\|date=September 2007}}

Ben pcc: Fix (other article).

2007-09-14T05:26:53Z

Fix (other article).

← Previous revision		Revision as of 05:26, 14 September 2007
Line 64:		Line 64:

	:<math>d'_1 = \frac{d_1}{b_1}\,</math>		:<math>d'_1 = \frac{d_1}{b_1}\,</math>
	:<math>d'_i = \frac{d_i}{b_i - c'_{i - 1} a_i}\,</math>		:<math>d'_i = \frac{d_i - d'_{i - 1} a_i}{b_i - c'_{i - 1} a_i}\,</math>

	This gives the following system with the same unknowns and coefficients defined in terms of the original ones above:		This gives the following system with the same unknowns and coefficients defined in terms of the original ones above:

Ben pcc: Some details...

2007-09-13T23:36:03Z

Some details...

New page

The derivation of the [[Tridiagonal matrix algorithm]] involves manually performing some specialized [[Gaussian elimination]] in a generic manner.

Suppose that the unknowns are <math>x_1,\ldots, x_n</math>, and that the equations to be solved are:

:<math>\begin{array}{lcl}
b_1 x_1 + c_1 x_2 = d_1 \qquad &;& \ i = 1 \\
a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i \qquad &;& \ i = 2, \ldots, n - 1 \\
a_n x_{n - 1} + b_n x_n = d_n \qquad &;& \ i = n \\
\end{array}
\,</math>

Consider modifying the second (<math>i = 2</math>) equation with the first equation as follows:

:<math>
(\mbox{equation 2}) \cdot b_1 - (\mbox{equation 1}) \cdot a_2
</math>

which would give:

:<math>
(a_2 x_1 + b_2 x_2 + c_2 x_3) b_1 - (b_1 x_1 + c_1 x_2) a_2 = d_2 b_1 - d_1 a_2
\,</math>

:<math>
(b_2 b_1 - c_1 a_2) x_2 + c_2 b_1 x_3 = d_2 b_1 - d_1 a_2
\,</math>

and the effect is that <math>x_1</math> has been eliminated from the second equation. Using a similar tactic with the '''modified''' second equation on the third equation yields:

:<math>
(a_3 x_2 + b_3 x_3 + c_3 x_4) (b_2 b_1 - c_1 a_2) -
((b_2 b_1 - c_1 a_2) x_2 + c_2 b_1 x_3) a_3
= d_3 (b_2 b_1 - c_1 a_2) - (d_2 b_1 - d_1 a_2) a_3
\,</math>

:<math>
(b_3 (b_2 b_1 - c_1 a_2) - c_2 b_1 a_3 )x_3 + c_3 (b_2 b_1 - c_1 a_2) x_4
= d_3 (b_2 b_1 - c_1 a_2) - (d_2 b_1 - d_1 a_2) a_3
\,</math>

This time <math>x_2</math> was eliminated. If this procedure is repeated until the <math>n^{th}</math> row; the (modified) <math>n^{th}</math> equation will involve only one unknown, <math>x_n</math>. This may be solved for and then used to solve the <math>(n - 1)^{th}</math> equation, and so on until all of the unknowns are solved for.

Clearly, the coefficients on the modified equations get more and more complicated if stated explicitly. By examining the procedure, the modified coefficients (notated with tildes) may be instead be defined recursively:

:<math>\tilde a_i = 0\,</math>

:<math>\tilde b_1 = b_1\,</math>
:<math>\tilde b_i = b_i \tilde b_{i - 1} - \tilde c_{i - 1} a_i\,</math>

:<math>\tilde c_1 = c_1\,</math>
:<math>\tilde c_i = c_i \tilde b_{i - 1}\,</math>

:<math>\tilde d_1 = d_1\,</math>
:<math>\tilde d_i = d_i \tilde b_{i - 1} - \tilde d_{i - 1} a_i\,</math>

To further hasten the solution process, <math>\tilde b_i</math> may be divided out (if there's no division by zero risk), the newer modified coefficients notated with an asterisk will be:

:<math>a'_i = 0\,</math>

:<math>b'_i = 1\,</math>

:<math>c'_1 = \frac{c_1}{b_1}\,</math>
:<math>c'_i = \frac{c_i}{b_i - c'_{i - 1} a_i}\,</math>

:<math>d'_1 = \frac{d_1}{b_1}\,</math>
:<math>d'_i = \frac{d_i}{b_i - c'_{i - 1} a_i}\,</math>

This gives the following system with the same unknowns and coefficients defined in terms of the original ones above:

:<math>\begin{array}{lcl}
x_i + c'_i x_{i + 1} = d'_i \qquad &;& \ i = 1, \ldots, n - 1 \\
x_n = d'_n \qquad &;& \ i = n \\
\end{array}
\,</math>

The last equation involves only one unknown. Solving it in turn reduces the next last equation to one unknown, so that this backward substitution can be used to find all of the unknowns:

:<math>x_n = d'_n\,</math>

:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1</math>