Solving a system of linear equations by the Kramer method

This example demonstrates the implementation of an algorithm for solving a system of linear equations using the Kramer method in the Julia programming language.

Introduction

What is the Kramer method?

Kramer's method is a method of solving systems of linear algebraic equations in which the number of equations coincides with the number of unknowns, and the determinant of the matrix of the system is nonzero. This method is based on the calculation of determinants and allows you to find a unique solution to the system.

Why is it needed?

Kramer's method is convenient because it provides an explicit formula for solving the system and is well suited for theoretical analysis. However, from a practical point of view, it is inefficient for large systems due to the need to calculate a set of determinants.

The method is used in cases where it is necessary to obtain an accurate analytical representation of the solution or the dimension of the system is small.

The main part

Installing and connecting the required package

import Pkg; Pkg.add("LinearAlgebra")

using LinearAlgebra

A function that implements Kramer's rule

function cramersolve(A::Matrix, b::Vector)
    # Calculating the main determinant of the system
    det_A = det(A)

    # We check that the system has a single solution (the determinant is not equal to 0)
    if det_A ≈ 0
        error("The system does not have a single solution (the determinant is zero)")
    end

    # Creating an array for storing solutions of variables x1, x2, ..., xn
    solutions = Float64[]

    # We go through each column of the matrix A
    for i in eachindex(b)
        # Copying the original coefficient matrix
        B = copy(A)
        
        # Replace the ith column with a vector of free terms of b
        B[:, i] = b
        
        # We calculate the determinant of the modified matrix and divide it by the main determinant
        push!(solutions, det(B) / det_A)
    end
    
    # Returning the received variable values
    return solutions
end

cramersolve (generic function with 1 method)

# Matrix of coefficients for variables
A = [2 -1  5  1;
     3  2  2 -6;
     1  3  3 -1;
     5 -2 -3  3]

# Vector of free terms
b = [-3, -32, -47, 49]

4-element Vector{Int64}:
  -3
 -32
 -47
  49

We call the function and output the result

println("Solving a system of linear equations by the Kramer method:")
@show cramersolve(A, b);

Решение системы линейных уравнений методом Крамера:
cramersolve(A, b) = [2.0, -11.999999999999998, -4.0, 1.0000000000000009]

Step-by-step explanation of the algorithm:

Step 1. First, the determinant of the main matrix is considered det(A). This is important because Kramer's method is applicable only when this determinant is not zero.

Step 2. Next, a time matrix is created B, which copies the original matrix A. For each unknown (, etc.) we replace the corresponding column of the matrix A on the vector of the right parts b.

Step 3. After that, we consider the determinant of the resulting modified matrix det(B) and we divide it by the main determinant det(A). We get the value of one of the roots of the system.

Step 4. These steps are repeated as many times as there are variables, resulting in a complete solution vector.

Compact version using a generator

The original version of your function uses a generator design, which makes it more compact.

# A more compact way to write a function is through a generator
function cramersolve_compact(A::Matrix, b::Vector)
    return [let B = copy(A); B[:, i] = b; det(B) end for i in eachindex(b)] ./ det(A)
end

cramersolve_compact (generic function with 1 method)

Please note: here is the expression let ... end creates a local scope that allows you to safely modify a copy of the matrix inside the loop. Construction [expr for i in collection] — this is an array generator in the Julia language.

@show cramersolve_compact(A, b);

cramersolve_compact(A, b) = [2.0, -11.999999999999998, -4.0, 1.0000000000000009]

Conclusion

We have considered the implementation of the classical method of solving systems of linear equations — the Kramer method — using the Julia programming language. We have written our own function. cramersolve, which makes it possible to find a unique solution to a system of equations under the condition of non-degeneracy (the determinant of the matrix of the system is nonzero).

This approach is good for understanding the essence of the algorithm, but in real-world problems, especially with large matrices (>1000×1000), more efficient methods such as LU decomposition or SVD are used. Nevertheless, the use of Kramer's rule is relevant in educational and research tasks to obtain an analytical representation of the solution.

The result shows that the implementation is working correctly and provides a solution for a given system of equations.

The example was developed using materials from Rosetta Code