Resolver un sistema de ecuaciones lineales

12

Escribe un programa para resolver una serie de ecuaciones lineales lo más cortas posible. Debe resolver un número arbitrario de problemas de ecuaciones. Pueden ingresar lo que desee, los coeficientes de matriz aumentada son probablemente los más fáciles. El programa no tiene que manejar coeficientes o soluciones no enteros. No se probarán casos degenerados o inválidos. El programa debe generar el valor de cada variable o forma de escalón de fila reducida.

No se permiten bibliotecas de resolución de ecuaciones, funciones matriciales ni ninguna forma de resolver automáticamente. Puede simular matrices con matrices o listas.

Entrada de ejemplo (o equivalente):

m={{2,1,-1,8},{-3,-1,2,-11},{-2,1,2,-3}}

Esto representa 2x+y-z=8, -3x-y+2z=-11, -2x+y+2z=-3

Ejemplo de salida (o equivalente):

{2,3,-1}

Esto representa x=2, y=3, z=-1

qwr
fuente
2
¿Se pueden separar los coeficientes de las variables y los términos constantes en dos matrices en la entrada?
user12205
@ace sí, está bien
qwr
1
¿Qué estás diciendo exactamente por casos degenerados? Supongo que te estás refiriendo a todos esos casos: 1) Entrada mal formada; 2) Cosas como 0x=0o 0x=5; 4) Casos donde el número de ecuaciones es diferente al número de variables; 5) Casos contradictorios como x+5y=7, x+5y=8; 6) Casos sin independencia lineal, como x+3y=6, 2x+6y=12. Estoy en lo cierto?
Victor Stafusa
@Victor Sí, cualquier entrada que tenga alguna ambigüedad o que no pueda resolverse.
qwr
¿Qué pasa con los casos que no son degenerados pero están mal condicionados? (O, en otras palabras, ¿qué tipo de pivote se requiere?)
Peter Taylor

Respuestas:

3

Python 169 166

Implementación

def s(a):
 if a:b=a[0];r=s([[x-1.*y*b[0]/r[0]for x,y in zip(b[1:],r[1:])]for r in a[1:]]);return[round((b[-1]-sum(x*y for x,y in zip(b[1:-1],r)))/b[0])]+r
 return[]

Manifestación

>>> arr=[[2, 1, -1, 8], [-3, -1, 2, -11], [-2, 1, 2, -3]]
>>> s(arr)
[2.0, 3.0, -1.0]

Nota

Si está de acuerdo con la aproximación de flotación, puede eliminar la llamada a la función de redondeo y seguir jugando golf a 159 caracteres

Abhijit
fuente
9

APL, 1 char

Sé que no cumple con los requisitos (revisados), pero es demasiado bueno para no publicar:

El símbolo "dominó" (división ÷dentro de un rectángulo) realiza la división matricial, por lo tanto, puede resolver cualquier sistema de ecuaciones lineales. Solo tiene que ponerlo entre el término constante vector y la matriz con los otros términos:

      8 ¯11 ¯3 ⌹ ⊃(2 1 ¯1)(¯3 ¯1 2)(¯2 1 2)
2 3 ¯1

(si quieres probarlo en TryApl, es )

Tobia
fuente
4

Javascript ( 284 181) - Método de eliminación de Gauss

function f(A){l=A.length;d=1;for(i=0;i+1;i+=d){v=A[i][i];for(k=0;k<l+1;k++)A[i][k]/=v;for(j=i+d;A[j];j+=d)for(k=0,w=A[j][i];k<l+1;k++)A[j][k]-=w*A[i][k];if(i==l-d)d=-1,i=l}return A}

Prueba

f([[2,1,-1,8],[-3,-1,2,-11],[-2,1,2,-3]]);

=> [[1,0,0,2],[0,1,0,3],[-0,-0,1,-1]]

La matriz devuelta combina la matriz de identidad y la solución.

Michael M.
fuente
Puedes guardar un par de personajes más.
MarcinJuraszek
En lugar de l=A.length;for(i=0;i<l;i++)usar for(i=0;i<l=A.length;i++).
Victor Stafusa
En lugar de for(i=l-1;i>=0;i--)usar for(i=l;--i;).
Victor Stafusa
También puede mover w=A[j][i]dentro for()y saltar {}alrededor.
MarcinJuraszek
Gracias a todos, logré fusionar los pasos hacia adelante y hacia atrás en un solo paso, ahorrando cien caracteres y algunos de sus consejos ya no son válidos. (excepto el consejo de @MarcinJuraszek)
Michael M.
3

Esta respuesta ya no se ajusta a la pregunta después del cambio de regla, ya que utiliza una función matricial. * *

Sabio , 32

~matrix(input())*vector(input())

Entrada de muestra:

[[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
[8, -11, -3]

Salida de muestra:

(2, 3, -1)

* Podría decirse que matrix()es una conversión tipográfica, no una función (la ejecución import types; isinstance(matrix, types.FunctionType)da False). Además, los ~y *son operadores , no funciones.

usuario12205
fuente
He actualizado las reglas. El código debe manejar un número diferente de ecuaciones y ahora no puede usar funciones de matriz.
qwr
3

Java - 522 434 228 213 caracteres

Resuelve comprobando sistemáticamente todas las n-tuplas enteras posibles mediante multiplicación directa hasta que se encuentre una que funcione.

La función toma matriz aumentada, A, vector de solución de prueba, x, y dimensión, n, como vector de solución de entrada - salida, x. Tenga en cuenta que el vector x es en realidad uno más grande que la dimensión para ayudar a analizar posibles soluciones. (Si declarara las variables A, x, n, j, k, s como variables de instancia, la función sería 31 caracteres más corta, para un total de 182, pero eso parece doblar las reglas demasiado lejos).

int[]Z(int[][]A,int[]x,int n){int j,k,s;for(;;){for(j=0;j<n;j++){for(k=s=0;k<n;s+=A[j][k]*x[k++]);if(s!=A[j][n])j+=n;}if(j==n)return x;for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){x[j]++;for(k=0;k<j;x[k++]=-x[n]);j=n;}}}

Programa de prueba (algo no golfista):

import java.util.*;
class MatrixSolver{
    public MatrixSolver() {
        Scanner p=new Scanner(System.in); //initialize everything from stdin
        int j,k,n=p.nextInt(),A[][]=new int[n][n+1],x[]=new int[n+1];
        for(j=0;j<n;j++)for(k=0;k<=n;A[j][k++]=p.nextInt());
        x=Z(A,x,n); //call the magic function
        for(j=0;j<n;j++) System.out.print(x[j]+" "); //print the output
    }
    public static void main(String[]args){
        new MatrixSolver();
    } 

    int[]Z(int[][]A,int[]x,int n){
        int j,k,s;
        for(;;){
            for(j=0;j<n;j++){ //multiply each row of matrix by trial solution and check to see if it is correct
                for(k=s=0;k<n;s+=A[j][k]*x[k++]);
                if(s!=A[j][n])j+=n;
            }
            if(j==n)return x; //if it is correct return the trial solution
            for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){//calculate the next trial solution
                x[j]++;
                for(k=0;k<j;x[k++]=-x[n]);
                j=n;
            }
        }
    }
}

El programa toma la entrada de stdin como enteros separados por espacios de la siguiente manera: primero, la dimensión del problema, segundo, las entradas de la matriz aumentada por fila.

Ejecución de muestra:

$java -jar MatrixSolver.jar
3 2 1 -1 8 -3 -1 2 -11 -2 1 2 -3
2 3 -1 

Afeité varios caracteres siguiendo los consejos de Victor sobre bucles y "público", almacenando el RHS en la matriz aumentada en lugar de por separado, y agregando una entrada adicional a mi solución de prueba para simplificar la generación de cada nueva solución de prueba. El OP también dijo que una función es suficiente, no es necesario contar todo el programa.

Criajo
fuente
while(true){f=0;for(j=0;j<n;j++)puede ser sustituido por while(true){for(f=j=0;j<n;j++). Además, tu clase no necesita ser pública. Los bucles for con una sola instrucción en el cuerpo no necesitan llaves.
Victor Stafusa
Creo que eso for(j=0;j<n;j++){for(k=0;k<n;k++){A[j][k]=p.nextInt();}b[j]=p.nextInt();}puede ser reemplazado porfor(j=0;j<n;b[j++]=p.nextInt())for(k=0;k<n;)A[j][k++]=p.nextInt();
Victor Stafusa
@Victor Gracias, hice esos y otros cambios.
Wally
while(true)se puede cambiar afor(;;)
user12205
@ace gracias - cambió eso y un par de cosas más y afeitó 15 caracteres.
Wally
1

JavaScript (ES6),  152  151 bytes

Implementación de la regla de Cramer .

(m)(v)mv

m=>v=>m.map((_,i)=>(D=m=>m+m?m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0):1)(m.map((r,y)=>r.map((k,x)=>x-i?k:v[y])))/D(m))

Pruébalo en línea!

Arnauld
fuente