[수치해석] [c++,python] LU 분해(LU decomposition) 구현하기

LU decomposition(LU 분해법)

1. A=LU로 분해한다
2. Ly=B에서 y를 구한다.
3. 얻어진 y를 UX=y에 대입하여 최종적으로 방정식의 해 x를 구한다.

C++으로는 단순 구현, PYTHON으로는 GUI까지 구현하였다.

 

Github로 보기

 

GitHub - dkswnkk/DongA-Univ: 🍊 DongA-Univ. 동아대학교 코딩 과제

c++

#include <iostream>
#include <vector>
#include <iomanip>
#pragma warning (disable:4996)

using namespace std;
int n;
vector<vector<float>>A, L, U, I;
vector<float>B, temp, x, y;

/*
input:
4
3 -7 -2 2 -9
-3 5 1 0 5
6 -4 0 -5 7
-9 5 -5 12 11
output:
L=
1 0 0 0
-1 1 0 0
2 -5 1 0
-3 8 3 1
U=
3 -7 -2 2
0 -2 -1 2
0 0 -1 1
0 0 0 -1
x[1]=3, x[2]=4, x[3]=-6, x[4]=-1
*/

void resize() {    //테이블 크기 할당
    A.resize(n, vector<float>(n));
    L.resize(n, vector<float>(n, 0));
    U.resize(n, vector<float>(n, 0));
    temp.resize(n, 0);
    x.resize(n, 0);
    y.resize(n, 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freopen("LU_Input.txt", "r", stdin);
    //freopen("LU_Out.txt", "w", stdout);

    cin >> n;

    resize();


    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            if (i == k) temp[k] = 1;
            else temp[k] = 0;
        }
        I.push_back(temp);
    }

    for (int i = 0; i < n; i++) {    // 행렬삽입
        for (int k = 0; k < n + 1; k++) {
            if (k == n) {
                int input; cin >> input;
                B.push_back(input);
            }
            else cin >> A[i][k];
        }
    }


    L = I;
    U = A;

    for (int i = 0; i < n - 1; i++) {    //LU 분해
        for (int k = i + 1; k < n; k++) {
            L[k][i] = U[k][i] / U[i][i];
        }
        for (int k = i + 1; k < n; k++) {
            for (int z = i; z < n; z++) {
                U[k][z] = U[k][z] - L[k][i] * U[i][z];
            }
        }
    }

    cout << "\n" << "L행렬" << "\n";
    for (int i = 0; i < n; i++) {    //L 행렬 출력
        for (int k = 0; k < n; k++) {
            cout << right << setw(2) << L[i][k] << right << setw(2) << ' ';
        }
        cout << "\n";
    }

    cout << "\n" << "U행렬" << "\n";
    for (int i = 0; i < n; i++) {    //U 행렬 출력
        for (int k = 0; k < n; k++) {
            cout << right << setw(2) << U[i][k] << right << setw(2) << ' ';
        }
        cout << "\n";
    }


    for (int i = 0; i < n; i++) {    //해 구하기 1
        y[i] = B[i];
        for (int k = 0; k < i; k++) {
            y[i] = y[i] - (L[i][k] * y[k]);
        }
        y[i] = y[i] / L[i][i];
    }

    for (int i = n - 1; i >= 0; i--) {
        x[i] = y[i];
        for (int k = i + 1; k < n; k++) {
            x[i] = x[i] - U[i][k] * x[k];
        }
        x[i] = x[i] / U[i][i];
    }


    cout << "\n" << "해 출력" << "\n";
    for (int i = 0; i < n; i++) {    //해 출력하기
        cout << "x[" << i + 1 << "] =" << x[i] << "\n";
    }


}

python

import tkinter.messagebox as msgbox
import tkinter as tk
from numpy import array
from tkinter import *
from tkinter import filedialog
from tkinter import ttk
from copy import deepcopy


N=0
A = []
L = []
U = []
I = []
B = []
temp = []
x = []
y = []

def resize(N):  # 테이블 재할당
    global A, L, U, temp, x, y
    A = [deepcopy([0 for _ in range(N)]) for _ in range(N)]
    L = [deepcopy([0 for _ in range(N)]) for _ in range(N)]
    U = [deepcopy([0 for _ in range(N)]) for _ in range(N)]
    temp = [deepcopy(0) for _ in range(N)]
    x = [deepcopy(0) for _ in range(N)]
    y = [deepcopy(0) for _ in range(N)]


root=Tk()
root.title("LU 분해법_1724572_안주형")
root.geometry("640x480+300+100") #가로*세로+x좌표+y좌표
root.resizable(False,False) #x,y너비 변경불가 (창크기 변경불가)


def result(): #결과 버튼 눌렸을때 동작하는 함수

    msgbox.showinfo("알림","정상적으로 출력했습니다")
    N=len(A)
    for i in range(N):  # 대각행렬 만들기
        for k in range(N):
            if i == k:
                temp[k] = 1
            else:
                temp[k] = 0

        I.append(deepcopy(temp))

    L = deepcopy(I)
    U = deepcopy(A)

    for i in range(0, N - 1):  # LU분해
        for k in range(i + 1, N):
            L[k][i] = U[k][i] / U[i][i]
        for k in range(i + 1, N):
            for z in range(i, N):
                U[k][z] = U[k][z] - L[k][i] * U[i][z]

    root.text = Text(root)
    root.text.insert(END,str('--------L행렬-------- \n'))
    root.text.insert(END,'\n')
    L=array(L)

    for i in range(N):  #L행렬 출력
        for k in range(N):
            root.text.insert(END,'%6s' % str(L[i][k]) + ' ')
        root.text.insert(END,'\n')
    root.text.insert(END, '\n')
    root.text.insert(END,str('--------U행렬-------- \n'))


    for i in range(N):  #U행렬 출력
        for k in range(N):
            root.text.insert(END,'%6s' % str(U[i][k]) + ' ')
        root.text.insert(END,'\n')
    root.text.insert(END, '\n')

    for i in range(N):  # 해 구하기
        y[i] = B[i]
        for k in range(i):
            y[i] = y[i] - (L[i][k] * y[k])
        y[i] = y[i] / L[i][i]

    for i in range(N - 1, -1, -1):
        x[i] = y[i]
        for k in range(i + 1, N):
            x[i] = x[i] - U[i][k] * x[k]
        x[i] = x[i] / U[i][i]

    root.text.insert(END,'\n --------해 출력--------\n')
    root.text.insert(END, '\n')


    for i in range(N):
        root.text.insert(END,"x[" + str(i + 1) + "] = " + str(x[i])+'\n')

    root.text.configure(state='disabled')
    root.text.pack()


def open_file(): #파일 불러오기 함수

        file=filedialog.askopenfile(parent=root,mode='rb',title="파일을 불러오세요")
        lines = file.readlines()
        N = int(lines[0].strip().split()[0])

        resize(N)

        for i, line in enumerate(lines):
            if i == 0:
                continue
            items = list(map(int, line.strip().split()))
            for k in range(len(items)):
                if k == N:
                    B.append(items[k])
                else:
                    A[i - 1][k] = items[k]

        file.close()

def save_file(): #파일 저장하기 함수
    file= filedialog.asksaveasfile(mode='w', defaultextension=".txt",initialfile="LU_Output")
    text2save = str(root.text.get(0.0, END))
    file.write(text2save)
    file.close

#메뉴 영역
menu=Menu(root)
menu_file=Menu(menu,tearoff=0)
menu_file.add_command(label="파일 불러오기",command=open_file)
menu_file.add_command(label="파일 저장하기",command=save_file)
menu_file.add_separator()
menu_file.add_command(label="끝내기",command=root.quit)
menu.add_cascade(label="파일",menu=menu_file)

#본문 영역
btn1=Button(root,command=result,padx=5,pady=15,text="LU 분해법 진행하기").pack()
label=ttk.Label(root, text="1.파일을 불러온다.",font=("Times",14)).pack()
label=ttk.Label(root, text="2.위 LU 분해법 진행하기 버튼을 누른다.",font=("Times",14)).pack()
label=ttk.Label(root, text="3.저장은 자동으로 .txt 형식으로 저장되므로 파일이름만 정해준다.",font=("Times",14)).pack()
root.config(menu=menu)
root.mainloop()