Solving simultaneous linear equations in Python (sweeping method and fractional representation)

Introduction

& Emsp; Hello, this is mana binding. This is an article that I will introduce because I was able to make a program that I made a lot because of the necessity. I made a program to solve a system of linear equations that is reasonably practical. Please kindly let me know if there are any bugs. Please note that we will not explain how to sweep out.

environment

The & emsp; environment is Python3 series.

> python --version
Python 3.9.0

program

The & emsp; program is shown below.

solve_PE.py


import sys

def hakidashi(m, show_matrix):
    num_line = len(m)
    num_column = len(m[0])
    div = lambda a, b: 0 if b==0 else a / b
    for p in range(num_line):
        m[p] = [div(n, m[p][p]) for n in m[p]]
        for i in range(num_line):
            x = div(m[i][p], m[p][p])
            for j in range(num_column):
                if(i != p):
                    m[i][j] = m[i][j] - x * m[p][j]
    if(show_matrix):
        for e in m:
            print(e)
    return list(map(lambda m: m[-1], m))

def dec_to_frac(f, max_denominator, calc_accuracy):
    for i in range(1, max_denominator + 1):
        k1 = int(f * i)
        k2 = k1 + 1
        if(abs((k1 / i) - f) < calc_accuracy):
            return f"{k1}/{i}"
        elif(abs((k2 / i) - f) < calc_accuracy):
            return f"{k2}/{i}"
    else:
        return "not found"

def read_file(file_name, file_codec):
    c, m = [], []
    with open(file_name, encoding=file_codec) as f:
        lists = list(f.readlines())
        c = split_line(lists[0])
        for l in lists[1:]:
            m.append(split_line(l, num=True))
    return c, m

def split_line(line, num=False):
    line = line.strip()
    line += "#"
    data_line = []
    word = ""
    is_firstblank = True
    for e in line:
        if(" " == e and is_firstblank):
            data_line.append(word)
            is_firstblank = False
            word = ""
        elif("," == e):
            data_line.append(word)
            word = ""
        elif("#" == e):
            data_line.append(word)
            break
        else:
            is_firstblank = True
            word += e
    else:
        data_line.append(word)
    return [
        float(x.strip())
        if num else
        x.strip()
        for x in data_line 
        if x not in ["", " "]
    ]

if __name__ == "__main__":
    file_name = sys.argv[1]
    file_encode = "utf-8"
    max_denominator = 10000000
    calc_accuracy = 0.0000000001
    show_matrix = True
    
    c, m = read_file(file_name, file_encode)
    if(len(c) + 1 == len(m[0])):
        ans = hakidashi(m, show_matrix)
        for c, ans in zip(c, ans):
            f = dec_to_frac(ans, max_denominator, calc_accuracy)
            print(f"{c} = {ans} ({f})")
    else:
        print("data error", file=sys.stderr)

& emsp; Below is a description of each.

How to sweep out

& emsp; hakidashi () is the corresponding function. There is no particular ingenuity, but in order to avoid the error of dividing by zero, a function called div is defined internally, and 0 is returned when it seems to be divided by zero. You can judge that print is done just before the return because the constant term does not become 1 correctly when an equation that has no solution is passed.

Fractional representation

& emsp; dec_to_frac () is the corresponding function. It verifies while changing the denominator, and returns a character string expressed as a fraction when the precision is acceptable. If it is not found in the range, not found is displayed. This is a for loop and the number of calculations is large, so if it is too heavy, adjust the values ​​of max_denominator and calc_accuracy.

I referred to this site. FloatToFraction (JavaScript version)

Read file

& emsp; read_file () and split_line () are the corresponding functions. & emsp; read_file opens the file data from the file name given from the command line and passes it to split_line. c is an array that contains character labels (x, y, etc.), and m is numeric array data. & emsp; split_line is a polite division so that it can be read in comma separate or space separate, or comments can be written.

How to use

For example, use a file with the following text:

mat1.txt


x y z
4 2 1 26
1 6 3 48
4 1 5 34

The above represents the following simultaneous equations.

4x + 2y + z = 26 \\\ x + 6y + 3z = 48 \\\ 4x + y + 5z = 34
> python solve_PE.py mat1.txt
[1.0, 0.0, 0.0, 2.727272727272727]
[0.0, 1.0, 0.0, 5.818181818181818]
[0.0, 0.0, 1.0, 3.454545454545455]
x = 2.727272727272727 (30/11)
y = 5.818181818181818 (64/11)
z = 3.454545454545455 (38/11)

Also, consider the case where there is no solution as shown below.

mat2.txt


x1, x2    #The lower formula is the upper formula
3, 6, 9   #Because it's just doubled
6, 12, 18 #There is no solution

In addition, # represents a comment, and it is possible to actually describe it in a file.

> python solve_PE.py mat2.txt
[1.0, 2.0, 3.0]
[0, 0, 0]
x1 = 3.0 (3/1)
x2 = 0 (0/1)

The values ​​are entered appropriately, but you can see that it is strange because the matrix above is not triangular.

in conclusion

& emsp; Thank you for your hard work. Did it work? It's a program that can be used quite well even though it's less than a hundred lines, so I think Python is amazing, and the algorithm that my predecessor thought was amazing (impression of elementary school students). It's fun to be able to build it yourself, and I want to live with happiness in these things. & emsp; Thank you for reading to the end. I hope it helps. It doesn't matter, but I can't really count on writing something next. I am surprised to see past articles by myself. I've got my hands on it, so I'll put it around here. Thank you very much.

Recommended Posts

Solving simultaneous linear equations in Python (sweeping method and fractional representation)
I tried it with Wolfram Alpha by referring to "Solving simultaneous linear equations with Python (sweeping method and fractional expression)".
Matrix Calculations and Linear Equations: Linear Algebra in Python <3>
[Scientific / technical calculation by Python] Solving simultaneous linear equations, numerical calculation, numpy
Eigenvalues and eigenvectors: Linear algebra in Python <7>
Linear Independence and Basis: Linear Algebra in Python <6>
Let's solve simultaneous linear equations with Python sympy!
Identity matrix and inverse matrix: Linear algebra in Python <4>
Inner product and vector: Linear algebra in Python <2>
Solve simultaneous equations in an instant using Python
"Linear regression" and "Probabilistic version of linear regression" in Python "Bayesian linear regression"
Solve simultaneous ordinary differential equations with Python and SymPy.
Simplex method (simplex method) in Python
Linear search in Python
Private method in python
Overview of generalized linear models and implementation in Python
Non-linear simultaneous equations can be easily solved in Python.
List method argument information for classes and modules in Python
List concatenation method in python, difference between list.extend () and “+” operator
First Computational Physics: Quantum mechanics and linear algebra in python.
Stack and Queue in Python
Implement method chain in Python
Unittest and CI in Python
Online linear regression in Python
Suppressing method overrides in Python
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part1-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part2-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part4-
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
List of Linear Programming (LP) solvers and modelers available in Python
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part3-
MIDI packages in Python midi and pretty_midi
Difference between list () and [] in Python
View photos in Python and html
Sorting algorithm and implementation in Python
How to solve simultaneous linear equations
Try implementing extension method in python
Manipulate files and folders in Python
About dtypes in Python and Cython
Assignments and changes in Python objects
Check and move directories in Python
Implemented label propagation method in Python
Ciphertext in Python: IND-CCA2 and RSA-OAEP
Simulate Monte Carlo method in Python
Hashing data in R and Python
Hash method (open address method) in Python
Function synthesis and application in Python
Export and output files in Python
[Python] Difference between function and method
Reverse Hiragana and Katakana in Python2.7
Reading and writing text in Python
[GUI in Python] PyQt5-Menu and Toolbar-
Solve ordinary differential equations in Python
Create and read messagepacks in Python