Entonces, cuando escribe código para realizar la eliminación gaussiana, generalmente se hace esto en forma de descomposición de PLU. (P es una matriz de permutación que realiza un seguimiento de los pivotes; L y U son matrices triangulares inferiores y superiores). La descomposición de PLU realmente es solo una eliminación gaussiana en la que realiza un seguimiento de las operaciones de fila elementales que está realizando. Así que veamos un ejemplo fácil solo para tener una idea:
Deje que [math] A = \ left (\ begin {array} {cc} 1 & 3 \\ 2 & 8 \ end {array} \ right) [/ math]
Ahora podemos hacer una operación de fila elemental en [math] A [/ math] y tener una matriz triangular superior:
[matemática] \ left (\ begin {array} {cc} 1 & 3 \\ 2 & 8 \ end {array} \ right) \ Rightarrow \ left (\ begin {array} {cc} 1 & 3 \\ 0 & 2 \ end {array} \ right) [/ math]
- ¿Qué significa cuando las matrices “conmutan”?
- ¿Importa la dirección de los vectores al calcular el ángulo entre ellos?
- Si [matemáticas] (\ overrightarrow {A} + \ overrightarrow {B}) \ times (\ overrightarrow {A} – \ overrightarrow {B}) = 2 (\ overrightarrow {B} \ times \ overrightarrow {A}), [ / matemáticas] ¿Cómo pruebo este problema matemático?
- ¿Cuál es la diferencia entre Algebra 2 y Algebra 2 Honors?
- ¿Cuáles son algunos usos del vector en la vida real?
Podemos hacer un seguimiento de esta operación de fila elemental colocando un 2 en la entrada inferior izquierda (ya que restamos 2 veces la primera fila de la segunda) en una matriz triangular inferior y verificamos
[matemática] A = \ left (\ begin {array} {cc} 1 & 0 \\ 2 & 1 \ end {array} \ right) \ left (\ begin {array} {cc} 1 & 3 \\ 0 & 2 \ end {array} \ right )[/matemáticas]
Entonces, si tenemos un sistema [matemático] Ax = b [/ matemático] podemos resolver para [matemático] x [/ matemático] resolviendo primero [matemático] Ly = b [/ matemático] y luego [matemático] Ux = y . [/ math] Estos dos últimos sistemas son triangulares, por lo que podemos resolverlos por sustitución. Así es como las computadoras resuelven los sistemas lineales.
Bien, entonces, ¿por qué necesitamos pivotar? Supongamos que tengo:
[matemática] A = \ left (\ begin {array} {cc} 0.0001 & 1 \\ 3 & 4 \ end {array} \ right) [/ math]
Sigo el mismo procedimiento:
[matemática] \ left (\ begin {array} {cc} 0.0001 & 1 \\ 3 & 4 \ end {array} \ right) \ Rightarrow \ left (\ begin {array} {cc} 0.0001 & 1 \\ 0 & -29,996 \ end { matriz} \ right) [/ math]
Así que ahora la descomposición LU de [math] A [/ math] se ve así:
[matemática] A = \ left (\ begin {array} {cc} 1 & 0 \\ 30,000 & 1 \ end {array} \ right) \ left (\ begin {array} {cc} 0.0001 & 1 \\ 0 & -29,996 \ end { matriz} \ right) [/ math]
Puede pensar “¿Y qué?”, Pero imagine que su computadora tiene una precisión muy limitada. Perderá información si no puede representar -29,996 y 0,0001 usando la misma cantidad de bits. Entonces, en cambio, giraremos antes de reducir la fila:
[matemáticas] \ left (\ begin {array} {cc} 0.0001 y 1 \\ 3 & 4 \ end {array} \ right) \ Rightarrow \ left (\ begin {array} {cc} 3 & 4 \\ 0.0001 & 1 \ end {array} \ right) \ Rightarrow \ left (\ begin {array} {cc} 3 & 4 \\ 0 & 0.9998666 \ ldots \ end {array} \ right) [/ math]
Así que ahora la descomposición de PLU de [math] A [/ math] se ve como
[matemática] A = \ left (\ begin {array} {cc} 0 & 1 \\ 1 & 0 \ end {array} \ right) \ left (\ begin {array} {cc} 1 y 0 \\ 0.000033 \ ldots & 1 \ end {array} \ right) \ left (\ begin {array} {cc} 3 y 4 \\ 0 y 0.999866 \ ldots \ end {array} \ right) [/ math]
Aquí la primera matriz en la descomposición representa el pivote. Tenga en cuenta que necesitamos mucha menos precisión para representar esta descomposición.
Tan genial ¿verdad? Mientras [math] A [/ math] sea invertible, todo estará bien. Si nos encontramos con este problema de precisión en el que estamos dividiendo por un número realmente pequeño, entonces simplemente pivotamos. Bueno no.
Deje [math] A = \ left (\ begin {array} {cc} 9999.9999 & -9999.9999 \\ 10000.0001 & -9999.9999 \ end {array} \ right) [/ math]
Ahora intentamos encontrar la descomposición LU de [math] A [/ math] y obtenemos
[matemáticas] \ left (\ begin {array} {cc} 9999.9999 y -9999.9999 \\ 10000.0001 y -9999.9999 \ end {array} \ right) \ Rightarrow \ left (\ begin {array} {cc} 9999.9999 & -9999.9999 \ \ 0 y 0.0002 \ end {array} \ right) [/ math]
Entonces
[matemáticas] A = \ left (\ begin {array} {cc} 1 & 0 \\ 1.00000011 \ ldots & 1 \ end {array} \ right) \ left (\ begin {array} {cc} 9999.9999 & -9999.9999 \\ 0 & 0.0002 \ end {array} \ right) [/ math]
Así que nuevamente terminamos con un problema de precisión, solo que esta vez el pivote no nos ayudará. Siga adelante y averigüe qué sucede cuando pivota. El resultado será aproximadamente el mismo con algunos signos cambiados. Esto se debe a que el número de condición de [matemáticas] A [/ matemáticas] es 10 ^ 8. Esto puede parecer un ejemplo realmente artificial, y es porque solo he usado matrices de 2 por 2 en mis ejemplos, pero con matrices cada vez más grandes, estos problemas comienzan a aparecer cada vez más.