Gaussian Elimination

อ่านก่อน

อินพุท

  • m : เมทริกซ์ (base-1) ที่รวมสัมประสิทธิ์ของตัวแปรและคำตอบ (ดูตัวอย่างการใช้งาน)
  • pivoting : การเลือกตัวหลัก ค่าที่เป็นไปได้คือ NO_PIVOT, SIMPLE_PIVOT, และ SCALE_PIVOT
def gaussian_elimination(m, pivoting = NO_PIVOT)   

เอาท์พุท

  • อาร์เรย์ (base-1) ที่เก็บคำตอบของสมการ

กรณีที่ไม่มีคำตอบหรือมีคำตอบมากมายจะ raise Exception

โค้ดทั้งหมด

require_relative 'base1'

NO_PIVOT     = 0
SIMPLE_PIVOT = 1
SCALE_PIVOT  = 2

def gaussian_elimination(m, pivoting = NO_PIVOT)   
  # forward elimination
  n = m.row_count
  scale = initialize_scale(m) if pivoting != NO_PIVOT
  for i in 1..(n-1)
    pivot(m, i, pivoting, scale) if pivoting != NO_PIVOT
   
    for j in (i+1)..(n)
      v = m.row(j) - m.row(i) * (1.0 * m[j,i] / m[i,i])  
      m.set_row(j, v)
    end
  end
  
  if m[n,n] == 0 then raise 'No unique solution' end 
  
  # backward substitution
  x = Array1.new(n)
  x[n] = m[n,n+1] / m[n,n]
  (n).downto(1) do |i|
    sum = 0.0
    (i+1).upto(n) { |j| sum += m[i,j] * x[j] }    
    x[i] = (m[i,n+1] - sum) / m[i,i]
  end
  return x
end

def initialize_scale(m)
  scale = Array1.new(m.row_count)
  scale.fill { |i| m.column(i).map{|i| i.abs}.max.to_f }
  return scale
end

def pivot(m, j, pivoting, scale) 
  case pivoting 
   when SIMPLE_PIVOT 
     max_row = (j..m.row_count).max_by {|i| m[i,j].abs }
   when SCALE_PIVOT  
     max_row = (j..m.row_count).max_by {|i| m[i,j].abs / scale[i]}
     scale[j], scale[max_row] = scale[max_row], scale[j]
  end
 
  # swap row j and max_row 
  row_j = m.row(j)
  m.set_row(j,   m.row(max_row))
  m.set_row(max_row, row_j)
end

การใช้งาน


ผลการรัน

หากจะนำโค้ดหรือข้อความไปใช้ ต้องแสดงที่มา และห้ามใช้ในเชิงพาณิชย์

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s