# PRAKTIKUM 4 <a id="chapter1"></a>
__Solusi Sistem Persamaan Linear__

*Topik*
1. Metode Substitusi Mundur
2. Metode Eliminasi Gauss
3. Metode Faktorisasi LU

<hr style="border:2px solid black"> </hr>

# 1 Metode Substitusi Mundur
Metode dasar yang digunakan untuk mencari solusi dari sistem persamaan linear adalah metode substitusi. Metode substitusi ini membutuhkan persyaratan yaitu matriks $ A $ pada sistem $ AX=B $ merupakan matriks segitiga. Jika $ A $ merupakan matriks segitiga atas, maka metode substitusi yang digunakan adalah substitusi mundur. Contoh berikut ini menunjukkan penyelesaian dari sistem segitiga atas dengan metode substitusi mundur. Adapun untuk substitusi maju, dapat dipelajari sendiri dengan analogi yang sama dengan substitusi mundur.

__Pseudocode__:


```julia
function backsub(A,B)
    # Hitung ukuran matriks dan inisiasi solusi X
    n = length(B);
    X = zeros(n,1);
    # Hitung nilai solusi X ke-n
    X[n] = B[n]/A[n,n];
    # Hitung nilai solusi X ke- n-1 sampai X ke-1
    for i = n-1:-1:1
        X[i] = (B[i] - A[i,i+1:n]'X[i+1:n])/A[i,i];
    end
    return X
end 
```

### Contoh Soal 1
Diberikan sistem segitiga atas seperti berikut.

\begin{align}
4x_1 -  x_2 + 2x_3 + 3x_4 &= 20\\
	 - 2x_2 + 7x_3 - 4x_4 &= -7\\
	 	 	  6x_3 + 5x_4 &=  4\\
	 	 	  		 3x_4 &=  6
\end{align} 

Selesaikan sistem persamaan linear tersebut menggunakan metode substitusi mundur.

**Solusi:**


```julia
A = [ 4 -1  2  3
      0 -2  7 -4
      0  0  6  5
      0  0  0  3];
B = [20; -7; 4; 6];

X = backsub(A,B)
```

### Substitusi Maju
Dengan mengamati pseudocode metode substitusi mundur, buatlah suatu fungsi yang mencari solusi SPL $AX=B$ dengan $A$ matriks segitiga bawah, yaitu dengan substitusi maju.



```julia
function forwardsub(A,B)
    # Hitung ukuran matriks dan inisiasi solusi X
    n = length(B);
    X = zeros(n,1);
    # Hitung nilai solusi X ke-1
    X[1] = B[1]/A[1,1];
    # Hitung nilai solusi X ke-1 sampai X ke-n
    for i = 2:n
        X[i] = (B[i] - A[i,1:i-1]'X[1:i-1])/A[i,i];
    end
    return X
end
```


```julia
A = [1 0 0 0
     1 2 0 0
    -1 0 1 0
    -2 1 1 2]
B = [1, 12, 8, 7]
X = forwardsub(A,B)
```


```julia
A\B
```

# 2 Metode Eliminasi Gauss
Metode eliminasi Gauss berangkat dari metode substitusi mundur. Maksudnya adalah sistem persamaan linear dengan matriks $ A $ bukan matriks segitiga atas diubah terlebih dahulu menjadi matriks segitiga atas dengan eliminasi. Selanjutnya, matriks hasil eliminasi tersebut diselesaikan menggunakan substitusi mundur.

__Pseudocode__:


```julia
# Metode Eliminasi Gauss Tanpa Pivoting
function elimGaussNonPivoting(A,b)
    # Hitung ukuran matriks dan inisiasi solusi X
    n = length(b);
    X = zeros(n,1);
    # Buatlah matriks Gandeng [A|b]
    Aug = [A b];
    # Lakukan operasi baris dasar terhadap matriks gandeng
    for p = 1:n-1 # p menunjukkan kolom
        # Jika pivot bernilai nol, maka gagal.
        if Aug[p,p]==0
            error("Harus Pakai Pivoting")
        end
        # Lakukan eliminasi menggunakan operasi Eij(k)
        for i = p+1:n # i menunjukkan baris
            k = Aug[i,p]/Aug[p,p];
            Aug[i,:] = Aug[i,:] - k*Aug[p,:];
        end
    end
    # Pisahkan matriks gandeng menjadi A dan b, kemudian selesaikan menggunakan substitusi mundur.
    A = Aug[:,1:n];
    b = Aug[:,1+n];
    X = backsub(A,b);
end
```


```julia
# Metode Eliminasi Gauss Dengan Pivoting
function elimGaussWithPivoting(A,b)
    # Hitung ukuran matriks dan inisiasi solusi X
    n = length(b);
    X = zeros(n,1);
    # Buatlah matriks Gandeng [A|b]
    Aug = [A b];
    # Lakukan operasi baris dasar terhadap matriks gandeng
    for p = 1:n-1
        # Lakukan operasi pindah baris untuk menentukan nilai pivot
        val,j = findmax(abs.(Aug[p:n,p]));
        C = Aug[p,:];
        Aug[p,:] = Aug[j+p-1,:];
        Aug[j+p-1,:] = C;
        # Jika pivot bernilai nol, maka gagal.
        if Aug[p,p] == 0;
            error("Matriks tidak punya solusi tunggal")
        end 
        # Lakukan eliminasi menggunakan operasi Eij(k)
        for i = p+1:n
            k = Aug[i,p]/Aug[p,p];
            Aug[i,:] = Aug[i,:] - k*Aug[p,:];
        end
    end
    # Pisahkan matriks gandeng menjadi A dan b, kemudian selesaikan menggunakan substitusi mundur.
    A = Aug[:,1:n];
    b = Aug[:,1+n];
    X = backsub(A,b);
end
```

### Contoh Soal 2
Diberikan sistem persamaan linear dengan 5 persamaan seperti berikut.
\begin{align*}
\begin{pmatrix} 
  2 &  5 &  4 &  2 &  3 \\
  4 &  1 &0.4 &  6 &  5 \\
0.9 &  4 &  8 &  7 & 10 \\
  5 &  7 &0.5 &  2 &  7 \\
  2 &  6 &  8 &  9 &  4 \\
\end{pmatrix}
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4\\x_5\\
\end{pmatrix}=
\begin{pmatrix}
26\\24.4\\32.8\\30.5\\53\\
\end{pmatrix}
\end{align*}
1. Selesaikan sistem persamaan tersebut menggunakan metode eliminasi Gauss tanpa _pivoting_ dan eliminasi Gauss dengan _pivoting_ 
2. Tunjukkan bahwa eliminasi Gauss dengan _pivoting_ memiliki **galat yang lebih kecil** daripada eliminasi Gauss tanpa _pivoting_, jika diketahui solusi eksak persamaan, yaitu $ X^*=\begin{pmatrix}
2&3&1&3&-1
\end{pmatrix}^T $.

**Solusi:**

Hitung solusi SPL


```julia
A = [ 2    5    4    2    3
      4    1  0.4    6    5
    0.9    4    8    7   10
      5    7  0.5    2    7
      2    6    8    9    4];
B = [26; 24.4; 32.8; 30.5; 53];
```


```julia
Xn = elimGaussNonPivoting(A,B)
```


```julia
Xp = elimGaussWithPivoting(A,B)
```

Hitung panjang vektor galat


```julia
using LinearAlgebra
```


```julia
Xeksak = [2;3;1;3;-1];
En = norm(Xn-Xeksak) 
```


```julia
Xeksak = [2;3;1;3;-1]; 
Ep = norm(Xp-Xeksak)
```

# 3 Metode Faktorisasi LU
Metode faktorisasi $ LU $ tanpa _ivoting_ mendefinisikan matriks $ A $ pada sistem persamaan linear sebagai $ A=LU $

Sementara itu, metode faktorisasi $ LU $ dengan _pivoting_ mendefinisikan matriks $ A $ pada sistem persamaan linear sebagai $ PA=LU $. 

Solusi sistem persamaan linear dapat dicari dengan substitusi maju dan mundur dari matriks $ P $, $ L $, dan $ U $.

__Pseudocode__:


```julia
# Metode Faktorisasi LU Tanpa Pivoting
function LUtanpaP(A);
    # Hitung ukuran matriks dan matriks L sebagai pencatat pengali.
    n,n = size(A);
    L = zeros(n,n);
    # Lakukan operasi baris dasar terhadap matriks
    Aug = copy(A);
    for p = 1:n-1
        # Jika pivot bernilai nol, maka gagal.
        if Aug[p,p]==0
            error("Pivot bernilai nol");
        end
        # Lakukan eliminasi menggunakan operasi Eij(k) untuk matriks A lalu simpan pengali m = k pada matriks L.
        for i = p+1:n
            k = Aug[i,p]/Aug[p,p];
            Aug[i,1:n] = Aug[i,1:n] - k*Aug[p,1:n];
            L[i,p] = k;
        end
    end
    # Simpan hasil eliminasi Gauss sebagai matriks U.
    U = Aug;
    # Tambahkan matriks identitas pada catatan pengali L.
    L = L .+ I(n);
    return L, U
end
```


```julia
# Metode Faktorisasi LU Dengan Pivoting 
function LUdenganP(A)
    # Hitung ukuran matriks dan matriks L sebagai pencatat pengali serta matriks permutasi P.
    n,n = size(A);
    L = zeros(n,n);
    P = Array(I(n));
    # Lakukan operasi baris dasar terhadap matriks gandeng
    Aug = copy(A)
    for p = 1:n-1
        # Lakukan operasi pindah baris untuk menentukan nilai pivot
        val,j = findmax(abs.(Aug[p:n,p]));
        # Pivoting U
        C = Aug[p,:];
        Aug[p,:] = Aug[j+p-1,:];
        Aug[j+p-1,:] = C;
        # Pivoting L
        C = L[p,:];
        L[p,:] = L[j+p-1,:];
        L[j+p-1,:] = C;
        # Pivoting P
        C = P[p,:];
        P[p,:] = P[j+p-1,:];
        P[j+p-1,:] = C;
        # Jika pivot bernilai nol, maka gagal.
        if Aug[p,p]==0
            error("Matriks Singular")
        end
        # Lakukan eliminasi menggunakan operasi Eij(k) untuk matriks A dan simpan pengali m = k di matriks nol yang telah disediakan.
        for i = p+1:n
            k = Aug[i,p]/Aug[p,p]
            Aug[i,1:n] = Aug[i,1:n] - k*Aug[p,1:n];
            L[i,p] = k;
        end
    end
    # Simpan hasil eliminasi Gauss sebagai matriks U.
    U = Aug;
    # Tambahkan matriks identitas pada catatan pengali L.
    L = L + I(n);
    return L,U,P
end
```

### Contoh Soal 3
Diberikan sistem persamaan linear dengan 5 persamaan seperti berikut.
\begin{align*}
\begin{pmatrix} 
  2 &  5 &  4 &  2 &  3 \\
  4 &  1 &0.4 &  6 &  5 \\
0.9 &  4 &  8 &  7 & 10 \\
  5 &  7 &0.5 &  2 &  7 \\
  2 &  6 &  8 &  9 &  4 \\
\end{pmatrix}
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4\\x_5\\
\end{pmatrix}=
\begin{pmatrix}
26\\24.4\\32.8\\30.5\\53\\
\end{pmatrix}
\end{align*}
1. Selesaikan sistem persamaan tersebut menggunakan metode faktorisasi LU tanpa _pivoting_ dan faktorisasi LU dengan _pivoting_ 
2. Tunjukkan bahwa faktorisasi LU dengan _pivoting_ memiliki **galat yang lebih kecil** daripada faktorisasi LU tanpa _pivoting_, jika diketahui solusi eksak persamaan, yaitu $ X^*=\begin{pmatrix}
2&3&1&3&-1
\end{pmatrix}^T $.

**Solusi:**

Hitung solusi SPL


```julia
A = [ 2    5    4    2    3
      4    1  0.4    6    5
    0.9    4    8    7   10
      5    7  0.5    2    7
      2    6    8    9    4];
B = [26; 24.4; 32.8; 30.5; 53];
```


```julia
# Cari matriks L, dan U menggunakan faktorisasi LU tanpa pivoting
L,U = LUtanpaP(A)
L
```


```julia
U
```


```julia
# A = LU ---> Ax = B ---> LUx = B --- misalkan Ux = Y ---> LY=B
# Hitung solusi Y kemudian hitung solusi X
Y = forwardsub(L,B)
Xn = backsub(U,Y)
```


```julia
Xeksak = [2;3;1;3;-1];
En = norm(Xn-Xeksak)
```


```julia
# Cari matriks L, U, dan P menggunakan faktorisasi LU dengan pivoting
L,U,P = LUdenganP(A)
L
```


```julia
U
```


```julia
P
```


```julia
# PA = LU ---> Ax = B ----> PAx = PB ---> LUx = PB -- misalkan Ux = Y ---> LY=PB
# Hitung solusi Y kemudian hitung solusi X
Y = forwardsub(L,P*B);
Xp = backsub(U,Y)
```


```julia
Xeksak = [2;3;1;3;-1]
Ep = norm(Xp-Xeksak)
```

<hr style="border:2px solid black"> </hr>

# Soal Latihan
Kerjakan soal berikut pada saat kegiatan praktikum berlangsung.

`Nama: ________`

`NIM: ________`

### Soal 1
Diberikan SPL seperti berikut.

$$\begin{align*}
\begin{pmatrix} 
  4.0 &  2.0 &  1.0 &  3.0 &  9.0 &  1.0 \\
  5.0 &  3.0 &  9.0 &  3.0 &  1.0 &  2.0 \\
  10.0&  7.0 &  2.0 &  1.0 &  8.0 &  3.0 \\
  9.0 &  0.3 &  8.0 &  4.0 &  8.0 &  5.0 \\
  8.0 &  0.7 &  0.7 &  2.0 &  7.0 &  1.0 \\
  2.0 &  6.0 &  10.0&  2.0 &  6.0 &  5.0 \\
\end{pmatrix}
\begin{pmatrix} 
x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\
\end{pmatrix}
=
\begin{pmatrix} 
  17.0 \\
  42.0 \\
  30.0 \\
  58.4 \\
  33.7 \\
  23.0 \\
\end{pmatrix}
\end{align*}$$

Gunakan metode eliminasi Gauss tanpa _pivoting_ dan eliminasi Gauss dengan _pivoting_ untuk mencari penyelesaikan sistem persamaan tersebut, kemudian tunjukkan bahwa metode eliminasi Gauss dengan _pivoting_ memiliki galat lebih kecil dibandingkan metode eliminasi Gauss tanpa _pivoting_.


```julia

```

### Soal 2

Diberikan sistem persamaan linear seperti berikut.

$$\begin{align*}
\begin{pmatrix}
  4.0 &  2.0 &  1.0 &  3.0 &  9.0 &  1.0 \\
  5.0 &  3.0 &  9.0 &  3.0 &  1.0 &  2.0 \\
  10.0&  7.0 &  2.0 &  1.0 &  8.0 &  3.0 \\
  9.0 &  0.3 &  8.0 &  4.0 &  8.0 &  5.0 \\
  8.0 &  0.7 &  0.7 &  2.0 &  7.0 &  1.0 \\
  2.0 &  6.0 &  10.0&  2.0 &  6.0 &  5.0 \\
\end{pmatrix}
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\
\end{pmatrix}
=
\begin{pmatrix}
  17.0 \\
  42.0 \\
  30.0 \\
  58.4 \\
  33.7 \\
  23.0 \\
\end{pmatrix}
\end{align*}$$

Gunakan metode faktorisasi $ LU $ tanpa _pivoting_ dan faktorisasi $ LU $ dengan _pivoting_ untuk mencari penyelesaikan sistem persamaan tersebut, kemudian tunjukkan bahwa metode faktorisasi $ LU $ dengan _pivoting_ memiliki galat lebih kecil dibandingkan metode faktorisasi $ LU $ tanpa _pivoting_.


```julia

```

4e789c8b1e31f0b6125141d98ac1f3494f78dc8f
ipynb
Jupyter Notebook
notebookpraktikum/Praktikum 04.ipynb
mkhoirun-najiboi/metnum.jl
a6e35d04dc277318e32256f9b432264157e9b8f4
MIT
notebookpraktikum/Praktikum 04.ipynb
mkhoirun-najiboi/metnum.jl
a6e35d04dc277318e32256f9b432264157e9b8f4
MIT
notebookpraktikum/Praktikum 04.ipynb
mkhoirun-najiboi/metnum.jl
a6e35d04dc277318e32256f9b432264157e9b8f4
MIT
Qwen/Qwen-72B
1. YES
2. YES