9. Eliminasi Gauss dengan Scaled Partial Pivoting#

kita lihat SPL berikut

\[\begin{split} \begin{array}{cc} E_1: a_{11} x_1 + a_{12} x_2 &=& b_1 \\ E_2: a_{21} x_1 + a_{22} x_2 &=& b_2 \end{array} \end{split}\]

Asumsikan bahwa kita telah mendapatkan nilai dari \(x_2\) dan mengandung error pembulatan (round-off error), \(\hat{x}_2 = x_2 + \varepsilon_2\). Kemudian kita hitung \(x_1\) dengan \(\hat{x}_2\):

\[\begin{split} \begin{array}{cc} \hat{x}_1 &=& \frac{1}{a_{11}}(b_1 - a_{12}\hat{x}_2)\\ &=& \frac{1}{a_{11}}(b_1 - a_{12}x_2 - a_{12}\varepsilon_2)\\ &=& \frac{1}{a_{11}}(b_1 - a_{12}x_2) - \frac{a_{12}}{a_{11}} \varepsilon_2\\ &=& x_1 - \varepsilon_1 \end{array} \end{split}\]

dengan demikian kita dapatkan \(\varepsilon_1 = \frac{a_{12}}{a_{11}} \varepsilon_2\). Error di \(x_2\) terpropagasi dengan suatu faktor \(\frac{a_{12}}{a_{11}}\). Kasus ini disebut juga dengan error terpropagasi (propagated error). Untuk menghasilkan hasil yang terbaik, kita menginginkan nilai dari \(|a_{11}|\) sebesar mungkin.

Untuk menghindari hal tersebut, kita memerlukan penukaran baris di A.

function eliminasi_gauss(A, b)
    A_c = hcat(A, b)
    
    # jumlah baris dari A
    n = size(A_c, 1)
    
    # eliminasi maju
    for i in 1:n-1
        pivot = A_c[i, i]
        for j in i+1:n
            faktor = A_c[j, i] / pivot
            A_c[j, :] -= faktor .* A_c[i, :]
        end
    end
    
    # subtitusi mundur
    b = A_c[:, end]
    b[end] /= A_c[end, end-1]
    for i in n-1:-1:1
        pivot = A_c[i, i]
        b[i] -= sum(A_c[i, i+1:end-1] .* b[i+1:end])
        b[i] /= pivot
    end
    
    return b
end

eliminasi_gauss (generic function with 1 method)

A = [1e-17 -1; 1 2]
b = [-1; 3]

2-element Vector{Int64}:
 -1
  3

# Tukar baris
A[[1,2],:] = A[[2,1],:]
b[[1,2]] = b[[2,1]]

print("A = ", A)
print("b = ", b)

A = [1.0 2.0; 1.0e-17 -1.0]b =

[3, -1]

sol = eliminasi_gauss(A, b)

2-element Vector{Float64}:
 1.0
 1.0

Dari kasus tersebut, kita memerlukan teknik scaled partial pivoting. Idenya adalah mencari skala terbesar dari masing-masing koefisien di setiap persamaan, \(max_{k \leq i \leq n} |a_{ik}|\) untuk \(a_{ii}\), kemudian cari mana baris yang memiliki skala terbesar dan lakukan penukaran baris. Untuk lebih jelasnya, kita lihat algoritma berikut:

Algoritma: Eliminasi_Gauss_Scaled_Pivoting(A, b)

INPUT: A` adalah matriks augmented [A,b], n adalah ukuran dari A.
OUTPUT: variabel x 

1. Mencari skala terbesar dari setiap baris 

for i=1 to n
      s[i] = max(|a[i,j]|), j = 1,2,..,n
      if s[i] == 0
          print('tidak ada solusi tunggal')

for i=1 to n
  2. Mencari indeks dari baris yang memiliki skala terbesar dan lakukan penukaran baris:

  for i=1 to n-1
      p = argmax(|a[k, i]|/s[i]), k = 1,2,...,n (mencari indeks)
      if p ~= i
          A`[[i,p]] <=> A`[[p,i]] (lakukan penukaran baris)
          s[i] <=> s[p] (lakukan penukaran nilai skala)
  3. Selanjutnya, lakukan eliminasi maju seperti pada algoritma sebelumnya.

4. Lakukan subtitusi mundur.

9.1. Contoh 1#

Diberikan SPL

\[\begin{split} \begin{array}{cc} E_1: & x_1 &+& 2x_2 &+& x_3 &=& 3, \\ E_2: & 3x_1 &+& 4x_2 &+& &=& 3, \\ E_3: & 2x_1 &+& 10x_2 &+& 4x_3 &=& 10, \\ \end{array} \end{split}\]

Dari SPL tersebut, pertama kita cari skala terbesar di setiap baris/persamaan. Untuk baris pertama \(E_1\):

\[\begin{split} \begin{array}{cc} s_1 &=& \max_{1 \leq j \leq n} |a_{1j}|\\ &=& \max \{1, 2, 1\} \\ &=& 2 \end{array} \end{split}\]

baris kedua \(E_2\):

\[\begin{split} \begin{array}{cc} s_2 &=& \max_{1 \leq j \leq n} |a_{2j}|\\ &=& \max \{3, 4, 0\} \\ &=& 4 \end{array} \end{split}\]

dan, baris ketiga \(E_3\):

\[\begin{split} \begin{array}{cc} s_3 &=& \max_{1 \leq j \leq n} |a_{3j}|\\ &=& \max \{2, 10, 4\} \\ &=& 10. \end{array} \end{split}\]

Kemudian kita cari baris yang akan ditukar:

\[ \frac{a_{11}}{s_1} = \frac{1}{2}, \frac{a_{21}}{s_2} = \frac{3}{4}, \frac{a_{31}}{s_3} = \frac{2}{10} \rightarrow i=2 \]

dari sini kita dapatkan bahwa baris kedua \(E_2\) yang memiliki nilai terbesar. Dengan demikian, lakukan penukaran \(E_1 \leftrightarrow E_2\). Sehingga SPLnya menjadi

\[\begin{split} \begin{array}{cc} E_1: & 3x_1 &+& 4x_2 &+& &=& 3, \\ E_2: & x_1 &+& 2x_2 &+& x_3 &=& 3, \\ E_3: & 2x_1 &+& 10x_2 &+& 4x_3 &=& 10, \\ \end{array} \end{split}\]

Kemudian kita lakukan eliminasi maju untuk mengeliminasi \(x_1\) dari \(E_2\) dan \(E_3\)

\((E_2 - \frac{1}{3} E_1) \rightarrow (E_2)\)
\((E_3 - \frac{2}{3} E_1) \rightarrow (E_3)\).

Sehingga didapat SPL baru, yaitu

\[\begin{split} \begin{array}{cc} E_2: & 3x_1 &+& 4x_2 &+& &=& 3, \\ E_1: & && \frac{2}{3}x_2 &+& x_3 &=& 2, \\ E_3: & && \frac{22}{3}x_2 &+& 4x_3 &=& 8, \\ \end{array} \end{split}\]

dan kita cari lagi baris yang akan ditukar dari SPL baru tersebut:

\[ \frac{a_{12}}{s_1} = \frac{2/3}{2} = \frac{1}{3}, \frac{a_{32}}{s_3} = \frac{22/3}{10} = \frac{22}{30} \rightarrow i=3 \]

sehingga kita tukar \(E_1 \leftrightarrow E_3\), maka didapat SPL baru selanjutnya

\[\begin{split} \begin{array}{cc} E_2: & 3x_1 &+& 4x_2 &+& &=& 3, \\ E_3: & && \frac{22}{3}x_2 &+& 4x_3 &=& 8, \\ E_1: & && \frac{2}{3}x_2 &+& x_3 &=& 2, \\ \end{array} \end{split}\]

dan lakukan eliminasi maju untuk mengeliminasi \(x_2\) dari \(E_1\):

\((E_1 - \frac{1}{11} E_3) \rightarrow (E_1)\)

sehingga didapatkan SPL:

\[\begin{split} \begin{array}{cc} E_2: & 3x_1 &+& 4x_2 &+& &=& 3, \\ E_3: & && \frac{22}{3}x_2 &+& 4x_3 &=& 8, \\ E_1: & && && \frac{7}{11}x_3 &=& \frac{14}{11}, \\ \end{array} \end{split}\]

Kemudian lakukan subtitusi mundur, sehingga didapatkan \(x_1 = 1, x_2 = 0, x_3 = 2\).

9.2. Implementasi di Julia#

function eliminasi_gauss_scaled_pivoting(A, b)
    n = size(A, 1)
    x = zeros(n)
    scaling = [maximum(abs.(A[i, :])) for i in 1:n]  # Lakukan penskalaan pada masing-masing baris
    perm = collect(1:n)  # inisialisasi vektor permutasi

    # Eliminasi maju
    for k in 1:n-1
        # Cari pivot 
        pivot = k
        for i in k+1:n
            if abs(A[perm[i], k] / scaling[perm[i]]) > abs(A[perm[pivot], k] / scaling[perm[pivot]])
                pivot = i
            end
        end
        perm[k], perm[pivot] = perm[pivot], perm[k]  # Tukar baris di dalam vektor permutasi

        # Eliminasi
        for i in k+1:n
            faktor = A[perm[i], k] / A[perm[k], k]
            A[perm[i], k:n] -= faktor * A[perm[k], k:n]
            b[perm[i]] -= faktor * b[perm[k]]
        end
    end

    # Subtitusi mundur
    for i in n:-1:1
        x[i] = (b[perm[i]] - A[perm[i], i+1:n]' * x[i+1:n]) / A[perm[i], i]
    end

    return x
end

eliminasi_gauss_scaled_pivoting (generic function with 1 method)

A = [1. 2. 1.; 3. 4. 0.; 2. 10. 4.]
b = [3.; 3.; 10.]
sol = eliminasi_gauss_scaled_pivoting(A, b)

3-element Vector{Float64}:
0
0
0

9.3. Contoh 2#

\[\begin{split} \begin{array}{cc} E_1: & x_1 &+& 10^{17}x_2 &=& 10^{17}, \\ E_2: & x_1 &+& 10^{-17}x_2 &=& 1, \\ \end{array} \end{split}\]

A = [1. 1e17; 1. 1e-17]
b = [1e17; 1.];
println("A: ", A)
println("b: ", b)

A: [1.0 1.0e17; 1.0 1.0e-17]
b: 

[1.0e17, 1.0]

using LinearAlgebra

println("Condition number dari A: ", cond(A))
println("Determinan dari A: ", det(A))

Condition number dari A: 9.999999999999997e16
Determinan dari A: -1.0e17

x = eliminasi_gauss(A, b)

2-element Vector{Float64}:
 0.0
 1.0

x = eliminasi_gauss_scaled_pivoting(A, b)

2-element Vector{Float64}:
 1.0
 1.0

Metode Numerik dengan Julia

Eliminasi Gauss dengan Scaled Partial Pivoting

Contents

9. Eliminasi Gauss dengan Scaled Partial Pivoting#

9.1. Contoh 1#

9.2. Implementasi di Julia#

9.3. Contoh 2#